11.4. Итерационные методы решения слау
11.4.1. Метод простой итерации
Простейшим итерационным методом решения систем линейных уравнений является метод простой итерации. Для применения данного метода система уравнений (11.1), в предположении, что диагональные элементы матрицы системы не равны нулю, преобразуется к эквивалентному виду
(11.20)
Теперь
возьмем некоторое нулевое приближение
к решению системы (11.20), обозначив его 
.
Подставим это нулевое приближение в
правую часть системы (11.20) и вычислим
новое значение неизвестных
(11.21)
На
этом первая итерация завершилась. На
второй итерации найденные значения
снова подставляем в правую часть системы
(11.20) и вычисляем следующее приближение 
.
Итерационный процесс продолжается до
тех пор, пока разность
не станет достаточно мала для всех
i=1,2,…,n.
Обычно критерий близости задают для
относительного значения разности двух
решений
(11.22)
где ε – некоторое положительное число.
Алгоритм метода простой итерации легко реализуется на ЭВМ, однако в описанном виде он применяется редко, так как существует возможность улучшить его сходимость за счет незначительного усложнения алгоритма без увеличения требуемого количества арифметических операций и ячеек машинной памяти. Такой улучшенный вариант алгоритма называется метод Зейделя.
11.4.2. Метод Зейделя
Метод
Зейделя отличается от метода простой
итерации тем, что уже на первой итерации
значение
,
найденное из первого уравнения системы
(11.21), подставляется во все нижележащие
уравнения вместо
.
В свою очередь
,
найденное из второго уравнения, с уже
имеющимся там
,
подставляется во все нижележащие
уравнения и т.д. Тогда вместо системы
(11.21) для первой итерации имеем
(11.23)
На рисунке 2 приведена блок схема алгоритма, реализующего метод Зейделя. Обозначения элементов матрицы системы, свободных членов и неизвестных на блок схеме соответствуют ранее использованным.
Переменная
целого типа Iter
содержит номер текущей итерации, индексы
i,
j
обозначают номер строки и номер столбца
матрицы соответственно. Вещественная
переменная
обозначает требуемую максимальную
абсолютную ошибку в определении
неизвестных, целая переменная MaxI
задает максимально возможное число
итераций. Вещественная переменная MaxE
предназначена для хранения максимального
модуля разности решений 
и
,
полученных на последней (текущей) и
предпоследней итерации. Сначала ей
присваивается нулевое значение, а затем
для каждого i
с ней сравнивается модуль разности
.
Если какая-либо разность оказывается
больше MaxE,
то прежнее значение MaxE
заменяется этой разностью. Вспомогательная
переменная TMP
служит для временного хранения решения,
получаемого на текущей итерации при
вычислении MaxE.
Рассмотрим вопрос о сходимости метода Зейделя. Наиболее наглядно условия сходимости можно показать на примере системы из двух уравнений
(11.24)
Покажем сначала геометрическую интерпретацию метода Зейделя. Для определенности конкретизируем коэффициенты при неизвестных и свободные члены, например
(11.25)
Графическое представление этой системы, точное решение которой равно x=1, y=1 показано на рис.3.
Рис.2 Блок схема алгоритма решения СЛАУ методом Зейделя
Рис.3. Графическое представление случая сходимости метода Зейделя для системы двух уравнений
Результаты последовательных итераций при начальном приближении x=0, y=0 составляют
-
Итерация
x
y
0
0
0
1
3/2
4/3
2
5/6
8/9
3
19/18
56/54
Процесс поиска решения начинается из начала координат. На первой итерации из первого уравнения, подставив туда y=0, получим x=3/2 (точка A на графике рис.3). Подставив найденное значение x во второе уравнение, получим значение y=4/3 (точка B на графике рис.3). На этом первая итерация заканчивается. На рис.3 первой итерации соответствует путь OAB. Повторяя описанные действия, на второй итерации находим новые значения x и y (точки C и D на графике рис.3). Второй итерации будет соответствовать путь BCD, а третьей соответственно DEF. Из рисунка 3 видно, что итерационный процесс поиска решения сходится к точке x=1, y=1.
Попробуем теперь поменять уравнения местами и повторить описанные действия. В этом случае система примет вид
. (11.26)
Нетрудно убедиться, что процесс поиска решения системы (11.26) методом Зейделя будет расходиться. Если за начальное приближение для системы (11.26), уравнения в которой, по сравнению с системой (11.25), поменяли местами, взять точку F (см. рис. 3), то из нее мы переместимся в точку E, далее в D, затем в С и т.д. Тогда мы будем двигаться по той же спирали, показанной на рисунке 3, но в обратном направлении. Отличие систем (11.25) и (11.26) состоит лишь в том, что в первой из них наибольшие по модулю коэффициенты при неизвестных расположены на главной диагонали матрицы системы.
Приведем
теорему о достаточном условии сходимости
метода Зейделя для системы из n
уравнений с n
неизвестными. Итерационный метод Зейделя
сходится к решению системы уравнений
(11.1), если для всех
выполняется условие
и, по крайней мере для одного i, выполняется условие
Следует подчеркнуть, что приведенные условия сходимости метода Зейделя не являются необходимыми. Поэтому невыполнение этих достаточно жестких условий не всегда означает расходимость метода Зейделя. Кроме этого, многие задачи линейной алгебры сводятся к решению систем, для которых приведенные выше условия выполняются.