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

1. Описание метода.

Пусть система (6.1) приведена к виду (6.4) с коэффициентами, вычисленными по формулам (6.5).

Метод Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что при вычислении очередного приближения к неизвестному при используют уже найденные приближения к неизвестным а не приближения, как методе Якоби.

На итерации компоненты приближения вычисляются по формулам

Введем нижнюю и верхнюю треугольные матрицы

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

Заметим, что и поэтому решение х исходной системы удовлетворяет равенству

Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений. 2. Достаточные условия сходимости.

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

Доказательство этой теоремы опускаем. Оно довольно громоздкое, хотя и не сложное. Приведем более компактное доказательство следующей теоремы, близкое к доказательству теоремы 6.1. Теорема 6.4. Пусть выполнено условие

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

Вычитая из равенства (6.24) равенство (6.25), имеем

Вычисляя нормы левой и правой частей этого равенства и используя свойства норм, получим

Следовательно,

Так как это неравенство верно для всех то из него следует

оценка (6.27). В силу условия (6.26) имеем Поэтому при

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

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

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

3. Апостериориая оценка погрешности.

Предложение 6.2. Если выполнено условие то для метода Зейделя справедлива апостериорная оценка погрешности

Положим и запишем равенство (6.28) в следующем виде:

Тогда

откуда и следует неравенство (6.29).

Полученное неравенство позволяет сформулировать простой критерий окончания итерационного процесса. Если требуется найти решение с точностью то итерации метода Зейделя следует вести до выполнения неравенства или эквивалентного ему неравенства

где

4. Геометрическая интерпретация метода.

Приведем геометрическую интерпретацию метода Зейделя в случае т.е. в случае решения системы

Первое уравнение задает на плоскости прямую второе — прямую Расчетные формулы метода принимают вид

где

Рис. 6.1

Пусть приближение уже найдено. Тогда при определении координата фиксируется и точка х перемещается параллельно оси до пересечения с прямой Координата точки пересечения принимается за Затем точка х перемещается вдоль прямой пересечения с прямой Координата точки пересечения принимается за

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

Пример 6.2. Используя метод Зейделя, найдем решение системы (6.15) с точностью

После приведения системы к виду (6.16) убеждаемся, что и поэтому в силу теоремы 6.2 метод Зейделя сходится

Положим и будем вычислять последовательные приближения по формулам

Здесь

Будем вести итерации до выполнения критерия окончания (6.30), где Значения приближений с четырьмя цифрами после десятичной точки приведены в табл. 6.2.

Таблица 6.2 (см. скан)

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

Замечание. Существует устойчивое заблуждение, связанное с представлением о том, что метод Зейделя сходится быстрее, чем метод Якоби. Это действительно так, если матрица А симметрична и положительно определена (мы убедились в преимуществе метода Зейделя для системы уравнений с такой матрицей, решая примеры 6.1 и 6.2). Однако в общем случае возможны ситуации, когда метод Якоби сходится, а метод Зейделя сходится медленнее или вообще расходится. Возможны и противоположные ситуации. Дело в том, что эти методы ориентированы на решение разных классов систем: метод Якоби — на системы с матрицами, близкими к диагональным, а метод Зейделя — на системы с матрицами, близкими к нижним треугольным.