Достоинством итерационных методов является их применимость к плохо обусловленным системам и системам высоких порядков, их самоисправляемость и простота реализации на ПК. Итерационные методы для начала вычисления требуют задания какого-либо начального приближения к искомому решению.
Следует заметить, что условия и скорость сходимости итерационного процесса существенно зависят от свойств матрицы А системы и от выбора начальных приближений.
Для применения метода итераций исходную систему (2.1) или (2.2) необходимо привести к виду
, (2.26)
после чего итерационный процесс выполняется по рекуррентным формулам
, k = 0, 1, 2, ... . (2.26а)
Матрица G и вектор получены в результате преобразования системы (2.1).
Для сходимости (2.26а) необходимо и достаточно, чтобы |li(G)| < 1, где li(G) – все собственные значения матрицы G. Сходимость будет также и в случае, если ||G|| < 1, так как |li(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–1B= − B–1C+ B–1, откуда= − B–1C+ B–1.
Положив –B–1C = G, B–1= , получим (2.26).
Из условий сходимости (2.27) и (2.28) видно, что представление А = В + С не может быть произвольным.
Если матрица А удовлетворяет условиям (2.28), то в качестве матрицы В можно выбрать нижнюю треугольную:
, aii ¹ 0.
Или
; Þ ; Þ ; Þ
Þ .
Подбирая параметр a, можно добиться, чтобы ||G|| = ||E + aA|| < 1.
Если имеет место преобладание (2.28), тогда преобразование к (2.26) можно осуществить, решая каждое i-е уравнение системы (2.1) относительно xi по следующим рекуррентным формулам:
(2.28а)
т. е. .
Если в матрице А нет диагонального преобладания, его нужно добиться с помощью каких-либо линейных преобразований, не нарушающих их равносильности.
В качестве примера рассмотрим систему
(2.29)
Как видно, в уравнениях (1) и (2) нет диагонального преобладания, а в (3) есть, поэтому его оставляем неизменным.
Добьемся диагонального преобладания в уравнении (1). Умножим (1) на a, (2) на b, сложим оба уравнения и в полученном уравнении выберем a и b так, чтобы имело место диагональное преобладание:
Это решение может быть получено и с помощью формул (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)Т.
Ошибка e2 = = max(0,575; 0,5; 0,325) = 0,575.
Блок-схема алгоритма нахождения решения СЛАУ по методу простых итераций согласно рабочим формулам (2.28а) представлена на рис. 2.4.
Особенностью блок-схемы является наличие следующих блоков:
– блок 13 – его назначение рассмотрено ниже;
– блок 21 – вывод результатов на экран;
– блок 22 – проверка (индикатор) сходимости.
Рис. 2.4
Проведем анализ предложенной схемы на примере системы (2.31) (n = 3, w = 1, e = 0,001):
= ; .
Блок 1. Вводим исходные данные A, , w, e, n: n = 3, w = 1, e = 0,001.
Цикл I. Задаем начальные значения векторов x0i и хi (i = 1, 2, 3).
Блок 5. Обнуляем счетчик числа итераций.
Блок 6. Обнуляем счетчик текущей погрешности.
В цикле II выполняется изменение номеров строк матрицы А и вектора .
Цикл II: i = 1: s = b1 = 2 (блок 8).
Переходим во вложенный цикл III, блок9 – счетчик номеров столбцов матрицы А: j = 1.
Блок 10: j = i, следовательно, возвращаемся к блоку 9 и увеличиваем j на единицу: j = 2.
В блоке 10 j ¹ i (2 ¹ 1) – выполняем переход к блоку 11.
Блок 11: s = 2 – (–1) × х02 = 2 – (–1) × 0 = 2, переходим к блоку 9, в котором j увеличиваем на единицу: j = 3.
В блоке 10 условие j ¹ i выполняется, поэтому переходим к блоку 11.
Блок 11: s = 2 – (–1) × х03 = 2 – (–1) × 0 = 2, после чего переходим к блоку 9, в котором j увеличиваем на единицу (j = 4). Значение j больше n (n = 3) – заканчиваем цикл и переходим к блоку 12.
Блок 12: s = s / a11 = 2 / 4 = 0,5.
Блок 13: w = 1; s = s + 0 = 0,5.
Блок 14: d = | xi – s | = | 1 – 0,5 | = 0,5.
Блок 15: xi = 0,5 (i = 1).
Блок 16. Проверяем условие d > de: 0,5 > 0, следовательно, переходим к блоку 17, в котором присваиваем de = 0,5 и выполняем возврат по ссылке «А» к следующему шагу цикла II – к блоку7, в котором i увеличиваем на единицу.
Цикл II:i = 2: s = b2 = 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 / a22 = 4 / 5 = 0,8.
Блок 13: w = 1; s = s + 0 = 0,8.
Блок 14: d = | 1 – 0,8 | = 0,2.
Блок 15: xi = 0,8 (i = 2).
Блок 16. Проверяем условие d > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «А» к следующему шагу цикла II – к блоку7.
Цикл II:i = 3: s = b3 = 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 / a33 = 6 / 4 = 1,5.
Блок 13: s = 1,5.
Блок 14: d = | 1 – 1,5 | = 0,5.
Блок 15: xi = 1,5 (i = 3).
Согласно блоку 16 (с учетом ссылок «А» и «С») выходим из цикла II и переходим к блоку18.
Блок 18. Увеличиваем число итераций it = it + 1 = 0 + 1 = 1.
В блоках 19 и 20 цикла IV заменяем начальные значения х0i полученными значениями х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 и выполняем рассмотренные вычисления с новыми начальными значениями х0i (i = 1, 2, 3).
После чего получим х1 = 1,075; х2 = 1,3; х3 = 1,175.
Блок 18. Увеличиваем число итераций it = it + 1 = 1 + 1 = 2.
В блоках 19 и 20 цикла IV заменяем начальные значения х0i полученными хi (i = 1, 2, 3).
Блок 21. Выполняем печать значений второй итерации: = (1,075; 1,3; 1,175)T, it = 2; de = 0,575 и т. д.
Метод Зейделя. Данный метод является модификацией метода простой итерации и для системы (2.26) выполняется по следующим формулам:
(2.33)
Его суть состоит в том, что при вычислении очередного приближения в системе (2.33) и в формуле (2.28а), если имеет место соотношение (2.28), вместо используются уже вычисленные ранее , т. е. (2. 28а) преобразуется к виду
, i = 1, …, n. (2.34)
Такое преобразование позволяет ускорить сходимость итераций почти в два раза. Оценка точности вычисления аналогична методу простой итерации. Схема алгоритма аналогична схеме метода простой итерации, если x0j заменить на xj и убрать строки x0i = 1, x0i = xi.
Пример 2.3. Методом Зейделя решить систему линейных уравнений с точностью e = 0,0001, приведя ее к виду, удобному для итераций:
(2.35)
Система не удовлетворяет условиям (2.28), поэтому приведем ее к соответствующему виду:
(2.36)
Здесь , значит, метод Зейделя сходится.
По формулам (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
Ответ: x1 = 0,248; x2 = 1,115; x3 = –0,224.
Замечание. Если для одной и той же системы методы простой итерации и Зейделя сходятся, то метод Зейделя предпочтительнее. Однако на практике области сходимости этих методов могут быть различными, т. е. метод простой итерации сходится, а метод Зейделя расходится и наоборот. Для обоих методов, если ||G|| близка к единице, скорость сходимости очень малая.
Для ускорения сходимости используется искусственный прием – так называемый метод релаксации. Суть его заключается в том, что полученное по методу итерации очередное значение xi(k) пересчитывается по формуле
, (2.37)
где w принято изменять в пределах от 0 до 2 (0 < w £ 2) с каким-либо шагом (h = 0,1 или 0,2). Параметр w подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.
Релаксация – постепенное ослабление какого-либо состояния тела после прекращения действия факторов, вызвавших это состояние (физ. техн.).
Пример 2.4. Рассмотрим результат пятой итерации с применением формулы релаксации. Возьмем w = 1,5:
Как видно, получен результат почти седьмой итерации.