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

Метод Зейделя отличается от метода простой итерации тем, что уже на первой итерации значение , найденное из первого уравнения системы (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
	3/2	4/3
	5/6	8/9
	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, выполняется условие

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