Лабораторная работа №2. Итерационные методы решения СЛАУ.

Краткие теоретические сведения.

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

Рассмотрим систему линейных алгебраических уравнений:

(2.1)

 

Будем рассматривать систему n уравнений с n неизвестными. Введем обозначения:

 

А = , , ,

 

где матрица А – основная матрица системы, - вектор-столбец неизвестных, - вектор-столбец свободных членов.

Тогда систему (2.1) можно записать в виде:

 

. (2.2)

 

Решением СЛАУ будем называть любой набор значений неизвестных, , обращающих все уравнения системы в тождества.

Будем обозначать через точное решение СЛАУ:

 

 

Известно, что если матрица A квадратная и невырожденная, , то СЛАУ имеет единственное решение.

Рассмотрим итерационные методы решения СЛАУ.

Метод простой итерации.

Рассмотрим СЛАУ в виде (2.2):

 

.

Преобразуем систему к виду:

 

(2.3)

 

Приведение системы вида (2.2) к виду (2.3) можно осуществить различными способами. Например, можно выполнить эквивалентные преобразования:

 

,

где α - некоторый параметр, подбирая который можно влиять на сходимость метода, E – единичная матрица.

Или, если матрица А имеет ненулевые диагональные элементы, то i -е уравнение делят на элемент , чтобы получить единичный коэффициент перед x_i. Затем в i -м уравнении в левой части оставляют x_{i ,} а все остальные слагаемые переносят в правую часть. Получаем систему вида , где:

 

(2.4).

 

В развернутой форме система имеет вид:

 

(2.5)

 

Пусть теперь система записана в виде (2.3). Зададим произвольным образом начальное приближение и подставим его в правую часть системы (2.3). Получим 1 -е приближение.

 

.

 

Вновь подставим полученное приближение в правую часть системы (2.3), получим 2 -е приближение и т.д. Повторяя процесс подстановок k раз, на k- итерации мы получаем k -е приближение:

. (2.6)

 

Здесь

 

Организуя, таким образом, итерационный процесс, получаем рекуррентную последовательность приближений : . Вычисление последовательности приближений по формуле (2.6) называется методом простых итераций. Итерационный процесс должен быть построен таким образом, чтобы последовательность приближений с ростом k стремилась к решению системы (2.3).

Достаточное условие сходимости метода простых итераций дает следующая теорема.

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

Выполнение условия берется по любой матричной норме: кубической евклидовой, октаэдрической.

Из теоремы следует, что метод простых итераций сходится, если выполняется хотя бы одно из условий:

1. , (по кубической норме матрицы)

2. , (по евклидовой норме) (2.7)

3. . (по октаэдрической норме)

Если условие (2.7) выполняется, начальное приближение может быть выбрано любым. Например, можно положить .

В частном случае представления системы вида (2.3) в виде (2.5), развернутая форма для итераций принимает вид:

 

Погрешность k -го приближения в методе простых итераций оценивается неравенством:

(2.8)

Заметим, что чем меньше норма матрицы || B ||, тем быстрее сходятся итерации.

При решении СЛАУ обычно используют кубическую норму вектора и матрицы.

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

(2.9)

Введем обозначение: q=||B||. Тогда, если норма матрицы || B ||>1/2, итерации заканчиваются, когда выполнится условие:

(2.10)

а

где - допустимая абсолютная погрешность нахождения решения СЛАУ. Эти условия должны быть выполнены по (k) и (k-1) приближениям для всех неизвестных. Например, первое условие (2.9) можно представить через логическое «и» в виде:

 

.

 

Метод Зейделя.

Метод Зейделя является модификацией метода простых итераций. Как и в методе простых итераций приведем систему вида (2.2) каким-либо способом к виду (2.3).

При применении метода простых итераций, в общем случае итерации осуществлялись бы по формуле:

 

, (2.11)

 

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

 

, (2.12)

 

Метод вычисления решения на основе итерационной последовательности (2.12) называется методом Зейделя.

Такое усовершенствование позволяет ускорить сходимость метода Зейделя по сравнению с методом простых итераций почти в два раза.

Запишем развернутую форму для итераций метода Зейделя для системы вида (2.5):

(2.13)

 

Формулу для итераций системы вида (2.5) метода Зейделя можно записать в другом виде. Разложим матрицу B вида (2.4) в сумму двух строго треугольных (нулевые элементы главной диагонали) матриц, т.е. положим , где:

 

 

В этом случае система (2.3) приобретет вид:

 

.

 

А метод Зейделя соответственно запишется в виде:

 

(2.14)

 

Достаточным условием сходимости метода Зейделя является условие доминирования диагональных элементов в матрице A построкам или по столбцам:

, или , . (2.15)

 

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

В частном случае системы вида (2.5) достаточные условия сходимости (2.7) метода простых итераций приобретают вид (2.15). Таким образом, для нашего частного случая достаточными условиями сходимости для обоих методов являются условия доминирования диагональных элементов в матрице A построкам или по столбцам.

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

Для системы вида (2.5) в методе Зейделя в случае выполнения условия справедлива следующая апостериорная оценка абсолютной погрешности k -приближения:

(2.16)

 

Из оценки (2.16) следуют и условие остановки итерационного процесса. Введем обозначение: ..Итерации продолжаются до тех пор, пока не выполнится условие:

(2.17)

Для контроля полезно найти невязку полученного решения :

(2.18)

 

Рассмотрим итерационные методы на примере.

Пусть требуется решить СЛАУ с точностью .

 

(2.19)

 

Точное решение системы: . Система из 3-х уравнений, с 3 неизвестными, определитель матрицы, , система имеет единственное решение. Сразу заметим, что в системе выполняется достаточное условие сходимости (доминирование диагональных элементов матрицы A) и оба метода будут сходиться к решению системы. Диагональные элементы матрицы , поэтому в соответствии с рекомендациями, из первого уравнения выразим , из второго , из третьего .

Получим:

 

(2.20)

 

Соответственно, матрица B и вектор-столбец свободных членов имеют вид:

 

 

Вычислим нормы матрицы B.

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

.

Евклидова норма матрицы вычисляется через корень квадратный из суммы квадратов всех элементов матрицы B.

.

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

.

 

Решим СЛАУ м етодом простой итерации.

Зададим произвольное начальное приближение: .

Подставим начальное приближение в правую часть системы (2.20), и на 1-ой итерации получим 1-ое приближение: .

Подставив 1-е приближение в правую часть системы (2.20), получим 2- приближение. На 2-ой итерации имеем:

 

 

Проверим выполнение условия прекращения итераций. Т.к. норма матрицы , применять будем условие (2.10). Оно принимает вид:

,

поэтому итерации продолжаются.

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

Метод Зейделя.

1-я итерация:

Подставим то же начальное приближение в первое уравнение системы (2.16), получим . При вычислении значения используем только что полученное значение . Имеем: . При вычислении , подставим в 3-е уравнение полученные на 1-ой итерации значения . Получим: .

2-я итерация:

 

 

После двух итераций проверим выполнение условия (2.15). Матрица в нашем случае имеет вид:

Ее кубическая норма равна . Условие (2.8) приобретает вид:

.

Как видим, погрешность нахождения решения на второй итерации в методе Зейделя меньше, чем в методе простых итераций. На 6 итерации, получим решение системы: .

Вычислим по формуле (2.14) невязку полученного решения. Для этого для каждого уравнения системы (2.15) вычислим абсолютную величину разности между значениями правой части уравнения и значением левой части уравнения при подстановке в него полученных значений неизвестных. Максимальная из полученных величин и даст нам невязку приближенного решения. Например, для первого уравнения имеем:

.

Произведя вычисления по всем уравнениям, имеем:

.

 

 

Задание.

 

1. Решить СЛАУ методом простых итераций и Зейделя согласно варианту. Варианты заданий указаны в таблице 2.1. Предусмотреть проверку достаточных условий сходимости методов. Точность нахождения решения СЛАУ .

2. Вычислить невязку полученного решения.

 

Таблица 2.1 - Варианты заданий

№	Матрица системы A	Вектор- столбец свободных членов
1.
2.
3.
4.
5.
6.
8.
9.
Продолжение таблицы 2.1 - Варианты заданий
10.
11.
12.
13.
14.