Тема 2: Методы решения СЛАУ

1 2 3 4

Тема 1: Основные понятия курса

П.1 Характеристики алгоритмов:

¾ Погрешность

¾ Трудоемкость

¾ Требование памяти

П.2 Абсолютная и относительная погрешности:

-приближенное значение некоторой величины

- точное

- абсолютная погрешность
- относительная погрешность (должна быть <<1)

П.3 Изменение абсолютной и относительной погрешностей при арифметических операциях:

Теорема 1.1:

При сложении и вычитании приближенных величин абсолютные погрешности складываются (абсолютная погрешность суммы (разницы) не превосходит суммы абсолютных погрешностей).

Доказательство:

приближенное точное значение абсолютная погрешность суммы

значение суммысуммы

Теорема 1.2:

При перемножении (делении) приближенных величин относительные погрешности складываются (т.е. относительная погрешность произведения (частного) не превышает суммы относительных погрешностей).

Доказательство:

Деление – доказать самостоятельно

П.4 Изменение погрешности при вычислении функции:

Теорема 1.3:

При вычислении функции абсолютная погрешность умножается на

Следствие 1.4:

При вычислении степенной функции () относительная погрешность умножается в раз.

Доказательство:

Следствие 1.5:

При вычислении экспоненты

относительная погрешность результата равна абсолютной погрешности аргумента.

Замечание 1.6:

Если многократно суммировать приближенные величины одного порядка, то абсолютная погрешность будет увеличиваться не в nраз, а в раз (так как количество “+” и“-” примерно равно(nслагаемых)).

П.5 Источники погрешности:

v Исходные данные

v Округление чисел при машинном вычислении

v Погрешность вычислительных методов

Тема 2: Методы решения СЛАУ

П.1 Точные и приближенные методы решения СЛАУ:

В дальнейшем будем считать n=k

Ax=b

A= ,b=

Методы решения СЛАУ делятся на 2 группы: точные и приближенные

o Точные (т.е. методы, которые дают точное решение за конечное число шагов при условии, что все действия выполняются абсолютно точно).

o Приближенные (итерационные)

При применении этих методов точное решение никогда не будет получено, оно является пределом последовательности приближенных решений.

Точные методы: метод Гаусса, метод Крамера, метод обратной матрицы,...

Приближенные методы: метод простых итераций, метод Зейделя,...

1. Метод Гаусса:

Основная идея: привести исходную матрицу А к треугольному виду с помощью элементарных преобразований строк, после чего СЛАУ легко решается.

Метод состоит из двух частей:

1-ая часть – прямой ход: приведение матрицы к треугольному виду.

2-ая часть – обратный ход: решение СЛАУ с треугольной матрицей.

Прямой ход:

1) 2)

………………………………..

……..

Нюансы метода Гаусса:

Если ведущий элемент (на диагонали) на каком либо этапе обратного хода равен нулю – переставим строки (строки смотрим ниже диагонали) так, чтобы ведущий элемент не был равен нулю. Если это невозможно, т.е. в j -ом столбце все строки с j -ой и вниз нулевые, тогда матрица А вырожденная.

2. Модификация метода Гаусса:

Метод Гаусса с выбором ведущего элемента.

Единственное отличие модифицированного метода Гаусса от обычного состоит в том, что на каждом этапе прямого хода на место ведущего элемента ставим максимальный по модулю среди возможных, то есть среди элементов столбца, который находится не выше главной диагонали.

Пример решения СЛАУ модифицированным методом Гаусса:

Необходимо поменять строки местами таким образом, чтобы ведущим элементом был максимальный по модулю среди элементов данного столбца ниже главной диагонали.

В данном примере вторую строку нужно поставить на место первой.

После перестановки строк имеем:

Ответ:

Замечания: метод Гаусса с выбором ведущего элемента работает лучше (точнее) чем обычный метод Гаусса (т.е. его точность выше). Погрешности при реализации метода Гаусса возникают при машинном округлении чисел, модифицированный метод Гаусса позволяет решать с той же точностью.

3. Трудоемкость метода Гаусса:

Прямой ход: три вложенных цикла

j от 1 до n -1 - по столбцу

i от j +1 до n - по строке

k от j +1 до n +1

Итого трудоемкость прямого хода

Обратный ход: два цикла

П.2 Приближенные методы решения СЛАУ:

§ В приближенных методах точные решения получаются как предел бесконечной последовательности приближений, который мы в некоторый момент времени обрываем (когда достигается заданная точность).

1. Справочный материал. Нормы векторов и матриц:

Пусть х – n -мерный вектор.

Нормой вектора называется число, удовлетворяющее следующим свойствам (аксиомам и нормам):

1) , =0 x=0 - Норма неотрицательна и равна нулю когда вектор равен нулю.

Примеры норм: x = ()

§ - первая норма

§ - вторая норма

§ -бесконечная норма

Замечания:

а) Фактически норма вектора есть ни что иное, как его длина.

б) Мы живем в пространстве с нормой 2, но на практике обычно удобнее использовать 1-ую или бесконечную нормы.

Определение: Нормой матрицы А называется число, которое определяется таким образом:

Теорема 2.1:

Норма произведения не превосходит произведения норм.

Доказательство: y

Имеем:

Следствие 2.2:

Норма k-ой степени

Следующая цель – эффективно научиться считать нормы матрицы.

Теорема 2.3:

Легко вычисляются

по опр.

(2.1)

максимальная сумма модулей элементов матрицы по столбцам.

(2.2)

максимальная сумма модулей элементов матрицы по строкам.

Доказательство формулы 2.2:

Итак, мы доказали неравенство

для полного доказательства теоремы необходимо доказать второе неравенство(для этого достаточно определить вектор , которого выполняется (*)).

если для некоторого вектора выполняется такое равенство, то:

для окончательного доказательства остается определить вектор , для которого выполняется искомое равенство (*).

Для того чтобы определить искомый вектор со свойством (*), рассмотрим ту строку матрицы, в которой достигается максимальная сумма модулей элементов. Пусть это строка с номером

тогда положим соответствующую координату

Тогда координата с номером 0 получается умножением на столбец.

, с учетом этого факта получили искомое соотношение (*), что и доказывает формулу 2.2. Формулу 2.1 предлагается доказать самостоятельно.

2.Метод простых итераций (МПИ):

Пусть дана СЛАУ с квадратной невырожденной матрицей А, проделаем с ней следующие преобразования: поделим каждую строку матрицы на диагональный элемент (предполагается что все элементы не нулевые). Данное преобразование называется приведением матрицы к виду удобному для итерации.

После данных преобразований по диагонали получаются единицы:

(.... – какие то произвольные элементы, получившиеся путем преобразования исходных, по выше описанному способу)

разобьем матрицу А на сумму матриц Е и С, где матрица Е – единичная матрица и матрица С – по диагонали нули.

А=Е+С

С=

Е=

(где элементы матрицы С: - и есть элементы матрицы А)

Исходное СЛАУ преобразовано таким образом:

Ax=b (E+C)=b

x+Cx=b x=b-Cx (2.3)

СЛАУ приведенное к виду удобному для итераций.

Рассмотрим итерационный процесс (2.4)

Из вектора - получаем следующий вектор .

Стартовый вектор - обычный нулевой вектор.

Теорема 2.4:

Если итерационный процесс (2.4) сходится, то есть существует

, то этот предельный вектор и будет точным решением исходного

СЛАУ (2.3)

Доказательство:

Рассмотрим формулу (2.4)

Необходимо исследовать важный вопрос: когда итерационный процесс (2.4) – сходится?

Ответ дает теорема 2.5

Теорема 2.5(достаточное условие сходимости):

Если ||C||<1, то итерационный процесс 2.4 сходится, и скорость его сходимости – геометрическая прогрессия со знаменателем||C||.

Доказательство:

Для того чтобы доказать, что данная последовательность сходится, докажем, что норма разности , считаем, что k >l

0 0

(2.5)

Следствие 2.6:

Если , то - точное решение исходного СЛАУ (сходится со скоростью геометрической прогрессии со знаменателем ), а именно, если взять стартовый вектор . (2.6)

Следствие 2.7 (оценка необходимого числа шагов для достижения заданной точности):

Если заданна погрешность , то, сделав N шагов, мы получим решение с заданной точностью, т. е.

точное

Доказательство:

Решаем неравенство из формулы (2.6):

; ;

Пример СЛАУ, решенной МПИ:

Матрица А имеет вид:

:5 (приводим к виду удобному для итераций - делим каждую

:(-3) строку матрицы так, чтобы получить единицы по главной

:4 диагонали)

Получаем матрицу:

Разбиваем матрицу А на сумму матриц Е и С:

А=Е+С:

Первый шаг по МПИ (начальный вектор X - нулевой):

Второй шаг МПИ:

………………….

количество шагов

Замечание 2.8:

Заметим, что условие для матрицы С, полученной из матрицы А с помощью стандартной процедуры приведения к виду удобному для итераций, равносильно тому, что для исходной матрицы А выполняется условие диагонального преобразования по строкам, т.е. в каждой строке диагональный элемент строго больше суммы модулей.