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

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

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

,

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

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

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

£ 0,001.

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

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

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

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-м шаге.

Ответ: х₁» 3,571; х₂ » –0,957; х₃ » 1,489; х₄ » –0,836.

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

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

; . (30)

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

Þ (31)

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

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

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

Рис. 2.4. Блок-схема метода простых итераций для решения СЛАУ

Особенностью блок-схемы являются блоки:

(13) – назначение его рассмотрим ниже;

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

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

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

= ; .

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

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

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

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

Цикл II – счетчик номеров матрицы А и вектора :

i = 1: S = b₁ = 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 – (–1) × 0 = 2, и переходим к блоку 9, в котором j увеличиваем на единицу: j = 3.

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

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

Блок 12: S = S / a₁₁ = 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 увеличиваем на единицу:

i = 2: S = b₂ = 4 (блок 8).

–––––––––––––––––––––––––––––––––––––––––––––––––––––––

Переходим во вложенный Цикл III, блок 9: 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₂₂ = 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:

i = 3: S = b₃ = 6 (блок 8).

–––––––––––––––––––––––––––––––––––––––––––––––––––––––

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

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

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

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

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

Блок 12: S = S / a₃₃ = 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.

Посредством блока 22 по ссылке «D» переходим к блоку 6 и de = 0.

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

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

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

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

Блок 21. Выполняем печать значений второй итерации: = (1,075; 1,3; 1,175)^T, it = 2; de = 0,575; и т.д.

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

Данный метод является модификацией метода простой итерации и для системы (25) имеет следующую технологию

(32)

Суть его состоит в том, что при вычислении очередного приближения в системе (32) и в формуле (27*), если имеет место соотношение (27), вместо используются уже вычисленные ранее , т.е. (27*) преобразуется к виду

, i = 1, …, n. (33)

Это позволяет ускорить сходимость итераций почти в два раза. Оценка точности аналогична методу простой итерации. Схема алгоритма аналогична схеме метода простой итерации, если x0_j заменить на x_j и убрать строки x0_i = 1, x0_i = x_i.

Пример. Методом Зейделя решить систему линейных уравнений с точностью e = 0,0001, приводя ее к виду, удобному для итераций.

(34)

Условия (27) для системы не удовлетворяются, поэтому приведем ее к виду соответствующему данному требованию.

(35)

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

По технологии счета (32)

k	х1	х2	х3	k	х1	х2	х3
	0.19	0.97	–0.14		0.2467	1.1135	–0.2237
	0.2207	1.0703	–0.1915		0.2472	1.1143	–0.2241
	0.2354	1.0988	–0.2118		0.2474	1.1145	–0.2243
	0.2424	1.1088	–0.2196		0.2475	1.1145	–0.2243
	0.2454	1.1124	–0.2226

Ответ: x₁ = 0.248; x₂ = 1.115; x₃ = –0.224.

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

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

(36)

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

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

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

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