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

Лекция Итерационные методы решения системы алгебраических линейных уравнений.

Условие сходимости итерационного процесса.Метод Якоби.Метод Зейделя

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

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

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

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

Для сходимости итерационного процесса достаточно, чтобы было выполнено условие
(норма матрицы). Критерий окончания итераций зависит от применяемого итерационного метода.

Метод Якоби .

Самый простой способ приведения системы к виду, удобному для итерации, состоит в следующем:

Из первого уравнения системы выразим неизвестное x 1 , из второго уравнения системы выразимx 2 , и т. д.

В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:

Компоненты вектора d вычисляются по формулам:

Расчетная формула метода простой итерации имеет вид:

или в покоординатной форме записи выглядит так:

Критерий окончания итераций в методе Якоби имеет вид:

Если
, то можно применять более простой критерий окончания итераций

Пример 1. Решение системы линейных уравнений методом Якоби.

Пусть дана система уравнений:

Требуется найти решение системы с точностью

Приведем систему к виду удобному для итерации:

Выберем начальное приближение, например,

- вектор правой части.

Тогда первая итерация получается так:

Аналогично получаются следующие приближения к решению.

Найдем норму матрицы B.

Будем использовать норму

Так как сумма модулей элементов в каждой строке равна 0.2, то
, поэтому критерий окончания итераций в этой задаче

Вычислим нормы разностей векторов:

Так как
заданная точность достигнута на четвертой итерации.

Ответ: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1

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

Метод можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (n+1) -го приближения к неизвестномуx i приi >1 используют уже найденные(n+1)- е приближения к неизвестнымx 1 ,x 2 , ...,x i - 1 , а неn -ое приближение, как в методе Якоби.

Расчетная формула метода в покоординатной форме записи выглядит так:

Условия сходимости и критерий окончания итераций можно взять такими же, как в методе Якоби.

Пример 2. Решение систем линейных уравнений методом Зейделя.

Рассмотрим параллельно решение 3-х систем уравнений:

Приведем системы к виду удобному для итераций:

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

1-ая система:

Точным решением будут значения: x 1 = 1.4, x 2 = 0.2 . Итерационный процесс сходится.

2-ая система:

Видно, что итерационный процесс расходится.

Точное решение x 1 = 1, x 2 = 0.2 .

3-я система:

Видно, что итерационный процесс зациклился.

Точное решение x 1 = 1, x 2 = 2 .

Пусть матрица системы уравнений A – симметричная и положительно определенная. Тогда при любом выборе начального приближения метод Зейделя сходится. Дополнительных условий на малость нормы некоторой матрицы здесь не накладывается.

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

Если A – симметричная и положительно определенная матрица, то систему уравнений часто приводят к эквивалентному виду:

x =x -τ (Ax - b), τ – итерационный параметр.

Расчетная формула метода простой итерации в этом случае имеет вид:

x (n+1 ) =x n - τ (Ax (n ) - b).

и параметр τ > 0 выбирают так, чтобы по возможности сделать минимальной величину

Пусть λ min и λ max – минимальное и максимальное собственные значения матрицы A. Оптимальным является выбор параметра

В этом случае
принимает минимальное значение равное:

Пример 3. Решение систем линейных уравнений методом простой итерации. (вMathCAD)

Пусть дана система уравнений Ax = b

Для построения итерационного процесса найдем собственные числа матрицы A:

- используется встроенная функция для нахождения собственных чисел.

Вычислим итерационный параметр и проверим условие сходимости

Условие сходимости выполнено.

Возьмем начальное приближение - вектор x0, зададим точность 0.001 и найдем начальные приближения по приведенной ниже программе:

Точное решение

Замечание. Если в программе возвращать матрицу rez, то можно просмотреть все найденные итерации.

1. Пусть известен отрезок , который содержит один корень уравнения f(x) = 0. Функция f является непрерывно дифференцируемой функцией на этом отрезке (f(x)ÎC 1 ). При выполнении этих условий можно применять метод простой итерации.

2. По функции f(x) строится функция j(x), удовлетворяющая трём условиям: она должна быть непрерывно дифференцируемой (j(x)ÎC 1 ), такая, что уравнение x = j(x) равносильно уравнению f(x)=0; должна также переводить отрезок в себя .

Будем говорить, что функция j(x) переводит отрезок [ a, b] в себя, если для любого x Î [ a, b], y = j(x) также принадлежит [ a, b] (y Î [ a, b]).

На функцию j(x) накладывается третье условие:

Формула метода: x n +1 = j(x n).

3. При выполнении этих трех условий для любого начального приближения x 0 Î последовательность итераций x n +1 = j(x n) сходится к корню уравнения: x = j(x) на отрезке ().

Как правило, в качестве x 0 выбирается один из концов .

,

где e – заданная точность

Число x n +1 при выполнении условия остановки итерационного процесса является приближенным значением корня уравнения f(x) = 0 на отрезке , найденным методом простой итерации с точностью e.

Построить алгоритм для уточнения корня уравнения: x 3 + 5x – 1 = 0 на отрезке методом простой итерации с точностью e.

1. Функция f(x) = x 3 +5x-1 является непрерывно дифференцируемой на отрезке , содержащем один корень уравнения.

2. Наибольшую трудность в методе простой итерации представляет построение функции j(x), удовлетворяющей всем условиям:

Рассмотрим: .

Уравнение x = j 1 (x) эквивалентно уравнению f(x) = 0, но функция j 1 (x) не является непрерывно дифференцируемой на отрезке .

Рис. 2.4. График функции j 2 (x)

С другой стороны, , следовательно, . Отсюда: – непрерывно дифференцируемая функция. Отметим, что уравнение:x = j 2 (x) эквивалентно уравнению f(x) = 0. Из графика (рис. 2.4) видно, что функция j 2 (x) переводит отрезок в себя.

Условие, что функция j(x) переводит отрезок в себя, можно переформулировать следующим образом: пусть – область определения функции j(x), а – область изменения j(x).

Если отрезок принадлежит отрезку , то функция j(x) переводит отрезок в себя.

, .

Все условия для функции j(x) выполнены.

Формула итерационного процесса: x n +1 = j 2 (x n).

3. Начальное приближение: x 0 = 0.

4. Условие остановки итерационного процесса:

Рис. 2.5. Геометрический смысл метода простой итерации

.

При выполнении этого условия x n +1 – приближенное значение корня на отрезке , найденное методом простой итерации с точностью e . На рис. 2.5. иллюстрируется применение метода простой итерации.

Теорема о сходимости и оценка погрешности

Пусть отрезок содержит один корень уравнения x = j(x), функция j(x) является непрерывно дифференцируемой на отрезке , переводит отрезок в себя, и выполнено условие :

.

Тогда для любого начального приближения x 0 Î последовательность сходится к корню уравнения y = j(x) на отрезке и справедлива оценка погрешности :

.

Устойчивость метода простой итерации. При выполнении условий теоремы о сходимости алгоритм метода простой итерации является устойчивым.

Сложность метода простой итерации . Объем памяти ЭВМ, необходимый для реализации метода простой итерации, незначителен. На каждом шаге нужно хранить x n , x n +1 , q и e.

Оценим число арифметических действий, необходимых для реализации метода простой итерации. Запишем оценку для числа n 0 = n 0 (e) такого что, для всех n ³ n 0 выполняется неравенство:

Из этой оценки вытекает, что чем ближе q к единице, тем медленнее сходится метод.

Замечание. Не существует общего правила построения j(x) по f(x) так, чтобы выполнялись все условия теоремы о сходимости. Часто используется следующий подход: в качестве функции j выбирается функция j(x) = x + k× f(x), где k – константа.

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

и .

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

Достоинством итерационных методов является их применимость к плохо обусловленным системам и системам высоких порядков, их самоисправляемость и простота реализации на ПК. Итерационные методы для начала вычисления требуют задания какого-либо начального приближения к искомому решению.

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

Для применения метода итераций исходную систему (2.1) или (2.2) необходимо привести к виду

после чего итерационный процесс выполняется по рекуррентным формулам

, k = 0, 1, 2, ... . (2.26а )

Матрица G и вектор получены в результате преобразования системы (2.1).

Для сходимости (2.26а ) необходимо и достаточно, чтобы |l i (G )| < 1, где l i (G ) – все собственные значения матрицы G . Сходимость будет также и в случае, если ||G || < 1, так как |l i (G )| < " ||G ||, где " – любой.

Символ || ... || означает норму матрицы. При определении ее величины чаще всего останавливаются на проверке двух условий:

||G || = или ||G || = , (2.27)

где . Сходимость гарантирована также, если исходная матрица А имеет диагональное преобладание, т. е.

. (2.28)

Если (2.27) или (2.28) выполняется, метод итерации сходится при любом начальном приближении . Чаще всего вектор берут или нулевым, или единичным, или берут сам вектор из (2.26).

Существует много подходов к преобразованию исходной системы (2.2) с матрицей А для обеспечения вида (2.26) или выполнения условий сходимости (2.27) и (2.28).

Например, (2.26) можно получить следующим образом.

Пусть А = В + С , det В ¹ 0; тогда (B + С )= Þ B = −C + Þ Þ B –1 B = − B –1 C + B –1 , откуда= − B –1 C + B –1 .

Положив –B –1 C = G , B –1 = , получим (2.26).

Из условий сходимости (2.27) и (2.28) видно, что представление А = В + С не может быть произвольным.

Если матрица А удовлетворяет условиям (2.28), то в качестве матрицы В можно выбрать нижнюю треугольную:

, a ii ¹ 0.

; Þ ; Þ ; Þ

Подбирая параметр a, можно добиться, чтобы ||G || = ||E + aA || < 1.

Если имеет место преобладание (2.28), тогда преобразование к (2.26) можно осуществить, решая каждое i -е уравнение системы (2.1) относительно x i по следующим рекуррентным формулам:

(2.28а )

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

В качестве примера рассмотрим систему

(2.29)

Как видно, в уравнениях (1) и (2) нет диагонального преобладания, а в (3) есть, поэтому его оставляем неизменным.

Добьемся диагонального преобладания в уравнении (1). Умножим (1) на a, (2) на b, сложим оба уравнения и в полученном уравнении выберем a и b так, чтобы имело место диагональное преобладание:

(2a + 3b) х 1 + (–1,8a + 2b) х 2 +(0,4a – 1,1b)х 3 = a .

Взяв a = b = 5, получим 25х 1 + х 2 – 3,5х 3 = 5.

Для преобразования уравнения (2) с преобладанием (1) умножим на g, (2) умножим на d и из (2) вычтем (1). Получим

(3d – 2g) х 1 + (2d + 1,8g) х 2 +(–1,1d – 0,4g) х 3 = −g .

Положив d = 2, g = 3, получим 0 х 1 + 9,4 х 2 – 3,4 х 3 = −3. В результате получим систему

(2.30)

Такой прием можно применять для нахождения решения широкого класса матриц.

или

Взяв в качестве начального приближения вектор = (0,2; –0,32; 0) Т , будем решать эту систему по технологии (2.26а ):

k = 0, 1, 2, ... .

Процесс вычисления прекращается, когда два соседних приближения вектора решения совпадают по точности, т. е.

.

Технология итерационного решения вида (2.26а ) названа методомпростой итерации .

Оценка абсолютной погрешности для метода простой итерации:

где символ || ... || означает норму.

Пример 2.1 . Методом простой итерации с точностью e = 0,001 решить систему линейных уравнений:

Число шагов, дающих ответ с точностью до e = 0,001, можно определить из соотношения

£ 0,001.

Оценим сходимость по формуле (2.27). Здесь ||G || = = max{0,56; 0,61; 0,35; 0,61} = 0,61 < 1; = 2,15. Значит, сходимость обеспечена.

В качестве начального приближения возьмем вектор свободных членов, т. е. = (2,15; –0,83; 1,16; 0,44) Т . Подставим значения вектора в (2.26а ):

Продолжив вычисления, результаты занесем в таблицу:

k	х 1	х 2	х 3	х 4
	2,15	–0,83	1,16	0,44
	2,9719	–1,0775	1,5093	–0,4326
	3,3555	–1,0721	1,5075	–0,7317
	3,5017	–1,0106	1,5015	–0,8111
	3,5511	–0,9277	1,4944	–0,8321
	3,5637	–0,9563	1,4834	–0,8298
	3,5678	–0,9566	1,4890	–0,8332
	3,5760	–0,9575	1,4889	–0,8356
	3,5709	–0,9573	1,4890	–0,8362
	3,5712	–0,9571	1,4889	–0,8364
	3,5713	–0,9570	1,4890	–0,8364

Сходимость в тысячных долях имеет место уже на 10-м шаге.

Ответ : х 1 » 3,571; х 2 » –0,957; х 3 » 1,489; х 4 » –0,836.

Это решение может быть получено и с помощью формул (2.28а ).

Пример 2.2 . Для иллюстрации алгоритма с помощью формул (2.28а ) рассмотрим решение системы (только две итерации):

; . (2.31)

Преобразуем систему к виду (2.26) согласно (2.28а ):

Þ (2.32)

Возьмем начальное приближение = (0; 0; 0) Т . Тогда для k = 0 очевидно, что значение = (0,5; 0,8; 1,5) Т . Подставим эти значения в (2.32), т. е. при k = 1 получим = (1,075; 1,3; 1,175) Т .

Ошибка e 2 = = max(0,575; 0,5; 0,325) = 0,575.

Блок-схема алгоритма нахождения решения СЛАУ по методу простых итераций согласно рабочим формулам (2.28а ) представлена на рис. 2.4.

Особенностью блок-схемы является наличие следующих блоков:

– блок 13 – его назначение рассмотрено ниже;

– блок 21 – вывод результатов на экран;

– блок 22 – проверка (индикатор) сходимости.

Проведем анализ предложенной схемы на примере системы (2.31) (n = 3, w = 1, e = 0,001):

= ; .

Блок 1. Вводим исходные данные A , , w, e, n : n = 3, w = 1, e = 0,001.

Цикл I . Задаем начальные значения векторов x 0 i и х i (i = 1, 2, 3).

Блок 5. Обнуляем счетчик числа итераций.

Блок 6. Обнуляем счетчик текущей погрешности.

В цикле II выполняется изменение номеров строк матрицы А и вектора .

Цикл II: i = 1: s = b 1 = 2 (блок 8).

Переходим во вложенный цикл III, блок9 – счетчик номеров столбцов матрицы А : j = 1.

Блок 10: j = i , следовательно, возвращаемся к блоку 9 и увеличиваем j на единицу: j = 2.

В блоке 10 j ¹ i (2 ¹ 1) – выполняем переход к блоку 11.

Блок 11: s = 2 – (–1) × х 0 2 = 2 – (–1) × 0 = 2, переходим к блоку 9, в котором j увеличиваем на единицу: j = 3.

В блоке 10 условие j ¹ i выполняется, поэтому переходим к блоку 11.

Блок 11: s = 2 – (–1) × х 0 3 = 2 – (–1) × 0 = 2, после чего переходим к блоку 9, в котором j увеличиваем на единицу (j = 4). Значение j больше n (n = 3) – заканчиваем цикл и переходим к блоку 12.

Блок 12: s = s / a 11 = 2 / 4 = 0,5.

Блок 13: w = 1; s = s + 0 = 0,5.

Блок 14: d = | x i – s | = | 1 – 0,5 | = 0,5.

Блок 15: x i = 0,5 (i = 1).

Блок 16. Проверяем условие d > de : 0,5 > 0, следовательно, переходим к блоку 17, в котором присваиваем de = 0,5 и выполняем возврат по ссылке «А » к следующему шагу цикла II – к блоку7, в котором i увеличиваем на единицу.

Цикл II: i = 2: s = b 2 = 4 (блок 8).

j = 1.

Посредством блока 10 j ¹ i (1 ¹ 2) – выполняем переход к блоку 11.

Блок 11: s = 4 – 1 × 0 = 4, переходим к блоку 9, в котором j увеличиваем на единицу: j = 2.

В блоке 10 условие не выполняется, поэтому переходим к блоку 9, в котором j увеличиваем на единицу: j = 3. По аналогии переходим к блоку 11.

Блок 11: s = 4 – (–2) × 0 = 4, после чего заканчиваем цикл III и переходим к блоку 12.

Блок 12: s = s / a 22 = 4 / 5 = 0,8.

Блок 13: w = 1; s = s + 0 = 0,8.

Блок 14: d = | 1 – 0,8 | = 0,2.

Блок 15: x i = 0,8 (i = 2).

Блок 16. Проверяем условие d > de : 0,2 < 0,5; следовательно, возвращаемся по ссылке «А » к следующему шагу цикла II – к блоку7.

Цикл II: i = 3: s = b 3 = 6 (блок 8).

Переходим во вложенный цикл III, блок9: j = 1.

Блок 11: s = 6 – 1 × 0 = 6, переходим к блоку 9: j = 2.

Посредством блока 10 выполняем переход к блоку 11.

Блок 11: s = 6 – 1 × 0 = 6. Заканчиваем цикл III и переходим к блоку 12.

Блок 12: s = s / a 33 = 6 / 4 = 1,5.

Блок 13: s = 1,5.

Блок 14: d = | 1 – 1,5 | = 0,5.

Блок 15: x i = 1,5 (i = 3).

Согласно блоку 16 (с учетом ссылок «А » и «С ») выходим из цикла II и переходим к блоку18.

Блок 18. Увеличиваем число итераций it = it + 1 = 0 + 1 = 1.

В блоках 19 и 20 цикла IV заменяем начальные значения х 0 i полученными значениями х i (i = 1, 2, 3).

Блок 21. Выполняем печать промежуточных значений текущей итерации, в данном случае: = (0,5; 0,8; 1,5) T , it = 1; de = 0,5.

Переходим к циклу II на блок 7 и выполняем рассмотренные вычисления с новыми начальными значениями х 0 i (i = 1, 2, 3).

После чего получим х 1 = 1,075; х 2 = 1,3; х 3 = 1,175.

Здесь , значит, метод Зейделя сходится.

По формулам (2.33)

k	х 1	х 2	х 3
	0,19	0,97	–0,14
	0,2207	1,0703	–0,1915
	0,2354	1,0988	–0,2118
	0,2424	1,1088	–0,2196
	0,2454	1,1124	–0,2226
	0,2467	1,1135	–0,2237
	0,2472	1,1143	–0,2241
	0,2474	1,1145	–0,2243
	0,2475	1,1145	–0,2243

Ответ: x 1 = 0,248; x 2 = 1,115; x 3 = –0,224.

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

Для ускорения сходимости используется искусственный прием – так называемый метод релаксации . Суть его заключается в том, что полученное по методу итерации очередное значение x i ( k ) пересчитывается по формуле

где w принято изменять в пределах от 0 до 2 (0 < w £ 2) с каким-либо шагом (h = 0,1 или 0,2). Параметр w подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.

Релаксация – постепенное ослабление какого-либо состояния тела после прекращения действия факторов, вызвавших это состояние (физ. техн.).

Пример 2.4 . Рассмотрим результат пятой итерации с применением формулы релаксации. Возьмем w = 1,5:

Как видно, получен результат почти седьмой итерации.

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

Теорема Самарского

Пусть - самосопряженная положительно определенная матрица:

,
,

- положительно определенная матрица, - положительное число:

,
.

Тогда при любом выборе нулевого приближения итерационный процесс, который определяется рекуррентной формулой , сходится к решению исходной системы.

Прежде, чем переходить к доказательству теоремы, обсудим более подробно главное ее требование – положительную определенность матрицы
. Это требование можно переписать в виде:

,
,
.

т. е. оно, в частности, предполагает, что матрица является положительно определенной. Кроме того, неравенство определяет интервал, в котором может изменяться параметр:

.

После этих замечаний перейдем к доказательству теоремы. Выразим из соотношения через:

и подставим в рекуррентную формулу для итерационной последовательности. В результате получим:

.

Отличие итерационной формулы от заключается в том, что она является однородной.

Матрица - положительно определенная. Следовательно она невырожденная и имеет обратную
. С ее помощью рекуррентное соотношение можно разрешить относительно
:

, так что
.

Умножая обе части равенства слева на матрицу , получим еще одно рекуррентное соотношение

.

Рассмотрим последовательность положительных функционалов:

.

Составим аналогичное выражение для
и преобразуем его с помощью рекуррентных формул и:

Из самосопряженности матрицы и формулы следует

В результате формула принимает вид:

Таким образом, последовательность функционалов с учетом условия
образует монотонно невозрастающую последовательность, ограниченную снизу нулем

.

,

где
- строго положительная константа. В результате, согласно и будем иметь

Из этого неравенства и сходимости последовательности функционалов следует, что
при
. В свою очередь
, так что

Теорема доказана.

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

Такое название получил метод, при котором в качестве матрицы выбирается единичная матрица:
, а итерационный параметрпредполагается независящим от номера итерации. Иными словами, метод простой итерации – это явный стационарный метод, когда очередная итерация
вычисляется по рекуррентной формуле

Будем считать, что матрица удовлетворяет условию теоремы Самарского,
, тогда формула, определяющая границу интервала сходимости по итерационному параметру, принимает вид

.

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

Разложим вектор
по базису собственных векторов

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

.

Дальнейшее исследование метода простой итерации построим на конкретном анализе рекуррентной формулы. Введем матрицу оператора перехода

,

и перепишем формулу в виде

.

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

.

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

Лемма 1

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

.

Доказательство элементарно. Оно проводится прямой проверкой

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

.

Лемма 2

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

,

Достаточность . Условие означает, что норма матрицы, согласно, будет меньше единицы:
. В результате получаем

При
.

Необходимость . Допустим, что среди собственных значенийнашлось хотя бы одно, которое не удовлетворяет условию леммы, т. е.

.

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

,
.

т. е.
. Необходимость выполнения неравенства для всех собственных значенийдля сходимости метода простой итерации доказана.

Лемма 2 определяет программу дальнейшего исследования сходимости метода простой итерации: нужно установить диапазон изменения параметра при котором все собственные значения удовлетворяют неравенству. Это легко сделать. На рис. 1 приведены графики убывающих линейных функций
. Все они выходят из одной точки
,
и идут вниз из-за отрицательных коэффициентов при, причем быстрее всех убывает функция
. Когда она принимает значение
, условие для нее перестает выполняться:

, при
.

Найденное значение является границей интервала сходимости метода простой итерации

.

Это неравенство нам уже известно. Оно было получено ранее из теоремы Самарского как достаточное условие сходимости. Дополнительный анализ на основе леммы 2 позволяет уточнить результат. Теперь мы установили, что принадлежность итерационного параметра интервалу является необходимым и достаточным условием сходимости метода простой итерации.

Перейдем к исследованию скорости сходимости метода. Оценка погрешности показывает, что она убывает по закону геометрической прогрессии со знаменателем

.

Рассмотрим рис. 2, который поможет нам провести анализ этой формулы. Он аналогичен рис.1, только на нем приведены графики не функций
, а их модулей. При малыхвсе собственные значения
положительны, причем наибольшим из них является
, которое убывает с ростомс наименьшей скоростью. Однако с переходом через точку
собственное значение
, меняя знак, становится отрицательным. В результате теперь его модуль с увеличениемне убывает, а растет и при
приближается к предельному значению – к единице.

Найдем на отрезке
точку, в которой убывающая функция
сравнивается с возрастающей функцией
. Она определяется уравнением

которое дает

.

В результате получаем:

Свое наименьшее значение норма матрицы достигает при
:

.

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

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

Задача 2.

Рассмотреть систему двух уравнений с двумя неизвестными

и построить для нее приближенное решение с помощью метода простой итерации.

Выпишем сразу решение системы

,
,

чтобы потом иметь возможность сравнивать его с членами итерационной последовательности.

Перейдем к решению системы методом простой итерации. Матрица системы имеет вид

.

Она самосопряженная и положительно определенная, поскольку

Составим характеристическое уравнение для матрицы и найдем его корни:

,

,

С их помощью можно определить границу интервала сходимости и оптимальное значение итерационного параметра:

,
.

Для построения итерационной последовательности выберем какое-нибудь значение итерационного параметра на интервале сходимости, например,
. В этом случае рекуррентная формула для членов итерационной последовательности принимает вид:

, где

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

,
,
,

,
,
,

,
,
,

,
,
.

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

.

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

Проведем несколько равносильных преобразований. Умножим обе части системы на один и тот же скалярный множитель затем прибавим к правой и левой частям системы вектор Систему уравнений можно теперь записать в виде, удобном для итераций:

(2.15)

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

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

(2.16)

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

Существуют другие формы записи метода итераций , например

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

Теорема (достаточное условие сходимости метода простой итерации ). Итерационный процесс (2.16) сходится к решению СЛАУ со скоростью геометрической прогрессии при выполнении условия:

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

Пусть - точное решение системы (2). Вычитая из (2.16)-(2.15), получим , или, обозначив погрешность , получим для эволюции погрешности уравнение Справедлива цепочка неравенств: , где

Отсюда следует, что при

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

Теорема (критерий сходимости метода простой итерации (без доказательства)) . Пусть СЛАУ (2.15) имеет единственное решение. Тогда для сходимости итерационного процесса (2.16) необходимо и достаточно, чтобы все собственные значения матрицы по абсолютной величине были меньше единицы.

Сравним по количеству арифметических действий прямые и итерационные методы . Метод Гаусса без выбора главного элемента при требует

Арифметических действий; метод простой итерации (2.16) , где i - число приближений, необходимое для достижения заданной точности. Значит, при I < n/3 метод итераций становится предпочтительнее. В реальных задачах, в основном, Кроме того, итерационные методы можно делать более эффективными, изменяя итерационные параметры. В ряде случаев итерационные методы оказываются более устойчивыми по отношению к накоплению ошибок округления, чем прямые .