Метод Зейделя: условие сходимости и итерации

Метод Зейделя (метод Гаусса-Зейделя) - это итерационный способ решения систем линейных уравнений, в котором новое приближение каждой неизвестной сразу же используется для пересчёта следующих. Именно эта деталь отличает его от метода простой итерации (Якоби) и обычно ускоряет сходимость. Но работает метод не всегда: если коэффициенты системы выбраны неудачно, приближения не приближаются к решению, а разбегаются. Поэтому центральный вопрос темы - условие сходимости: когда итерации Зейделя гарантированно сходятся, а когда нет. Ниже разберём формулу итераций, два рабочих критерия сходимости (диагональное преобладание и спектральный радиус), решим типовой пример и покажем частые ошибки. Чтобы сразу почувствовать связь коэффициентов и сходимости, покрутите калькулятор ниже: он проверяет преобладание, считает спектральный радиус и рисует лесенку итераций к решению.

Формула метода Зейделя

Пусть дана система линейных уравнений $A\mathbf{x} = \mathbf{b}$. Чтобы построить итерации, каждое $i$-е уравнение разрешают относительно своей диагональной неизвестной $x_i$. Для системы из двух уравнений

$a_{11}x + a_{12}y = b_1, \qquad a_{21}x + a_{22}y = b_2$

итерационные формулы Зейделя выглядят так:

$x^{(k+1)} = \frac{b_1 - a_{12}\,y^{(k)}}{a_{11}}, \qquad y^{(k+1)} = \frac{b_2 - a_{21}\,x^{(k+1)}}{a_{22}}.$

Обратите внимание на верхний индекс во второй формуле: для пересчёта $y$ берётся уже обновлённый $x^{(k+1)}$, а не старый $x^{(k)}$. В этом и состоит идея метода: как только координата уточнена, она немедленно идёт в дело. В общем случае для системы порядка $n$ формула одной итерации записывается компактно:

$x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j<i} a_{ij}\,x_j^{(k+1)} - \sum_{j>i} a_{ij}\,x_j^{(k)}\right).$

Здесь первая сумма уже использует новые значения этой итерации, а вторая - значения с прошлого шага. Стартуют обычно с нулевого приближения $x^{(0)} = 0$ и повторяют пересчёт, пока поправка не станет меньше заданной точности.

Геометрия итераций: лесенка к решению

Для системы из двух уравнений у метода есть наглядная геометрическая картинка. Каждое уравнение задаёт на плоскости $(x, y)$ прямую, а решение системы - точка их пересечения. Обновление $x$ при фиксированном $y$ переносит точку по горизонтали на первую прямую; обновление $y$ при новом $x$ переносит её по вертикали на вторую прямую. Получается ломаная-лесенка, которая шаг за шагом подходит к пересечению, если метод сходится.

Рассчитать для своей задачи

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

Условие сходимости: диагональное преобладание

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

$|a_{ii}| > \sum_{j \ne i} |a_{ij}|, \quad i = 1, \dots, n.$

Для системы 2x2 это два простых неравенства: $|a_{11}| > |a_{12}|$ и $|a_{22}| > |a_{21}|$. Если они выполнены, метод Зейделя сходится при любом начальном приближении. Слово «достаточное» здесь важно: преобладание гарантирует сходимость, но его отсутствие ещё не гарантирует расходимость. Бывают системы без диагонального преобладания, для которых метод всё равно сходится, поэтому одного этого критерия иногда мало.

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

Спектральный радиус: точный критерий

Диагональное преобладание удобно, но грубо. Точное необходимое и достаточное условие сходимости формулируется через матрицу перехода. Метод Зейделя приводится к виду $\mathbf{x}^{(k+1)} = G\,\mathbf{x}^{(k)} + \mathbf{c}$, где $G = -(D+L)^{-1}U$ ($D$ - диагональ матрицы $A$, $L$ и $U$ - её нижняя и верхняя треугольные части). Итерации сходятся тогда и только тогда, когда спектральный радиус этой матрицы меньше единицы:

$\rho(G) = \max_i |\lambda_i| < 1,$

где $\lambda_i$ - собственные числа $G$. Чем меньше спектральный радиус, тем быстрее сходимость: ошибка убывает примерно как $\rho^k$. Для системы 2x2 этот критерий упрощается до удобной формулы, которой и пользуется калькулятор выше:

$\rho = \left|\frac{a_{12}\,a_{21}}{a_{11}\,a_{22}}\right|.$

Условие $\rho < 1$ здесь означает, что произведение внедиагональных коэффициентов по модулю меньше произведения диагональных - снова та же мысль о «сильной диагонали», но уже в точной форме. На графике сходимости в калькуляторе видно, как при $\rho < 1$ ошибка по итерациям падает прямой линией в логарифмическом масштабе, а при $\rho > 1$ - растёт.

Рассчитать для своей задачи

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

Пример решения типовой задачи

Решим методом Зейделя систему

$2x + y = 4, \qquad x + 2y = 5.$

Сначала проверим условие сходимости. Диагональные коэффициенты $a_{11} = 2$, $a_{22} = 2$, внедиагональные $a_{12} = 1$, $a_{21} = 1$. Преобладание есть: $|2| > |1|$ в обеих строках. Спектральный радиус $\rho = |1 \cdot 1 / (2 \cdot 2)| = 0{,}25 < 1$, значит, метод сходится. Запишем итерационные формулы:

$x^{(k+1)} = \frac{4 - y^{(k)}}{2}, \qquad y^{(k+1)} = \frac{5 - x^{(k+1)}}{2}.$

Стартуем с $x^{(0)} = 0$, $y^{(0)} = 0$ и считаем шаги:

$$\begin{aligned} &k=1:\ x = \tfrac{4-0}{2} = 2{,}00,\quad y = \tfrac{5-2}{2} = 1{,}50; \\ &k=2:\ x = \tfrac{4-1{,}5}{2} = 1{,}25,\quad y = \tfrac{5-1{,}25}{2} = 1{,}875; \\ &k=3:\ x = \tfrac{4-1{,}875}{2} = 1{,}0625,\quad y = \tfrac{5-1{,}0625}{2} = 1{,}969. \end{aligned}$$

Уже на третьей итерации приближение $(1{,}06;\ 1{,}97)$ близко к точному решению $(1;\ 2)$, а поправки быстро уменьшаются. Ещё пара шагов даёт совпадение с точным решением до четырёх знаков. Точное решение легко проверить подстановкой: $2 \cdot 1 + 2 = 4$ и $1 + 2 \cdot 2 = 5$ - оба уравнения обращаются в верные равенства.

Частые ошибки

• Не проверяют условие сходимости. Прежде чем считать итерации, убедитесь, что есть диагональное преобладание или что спектральный радиус меньше единицы. Иначе можно бесконечно итерировать расходящийся процесс.
• Используют старое значение вместо нового. Главная особенность Зейделя - подставлять уже обновлённую координату в следующую формулу. Если брать значения только с прошлого шага, получится метод Якоби, а не Зейделя.
• Забывают переставить уравнения. Если преобладания нет, систему часто можно переписать перестановкой строк так, чтобы большие коэффициенты встали на диагональ. Этот шаг пропускают и зря объявляют метод неприменимым.
• Путают достаточное и необходимое условие. Отсутствие диагонального преобладания не означает расходимость: окончательный ответ даёт спектральный радиус.
• Берут слишком грубую точность остановки. Критерий $|x^{(k+1)} - x^{(k)}| < \varepsilon$ должен использовать норму поправки по всем неизвестным, а не по одной координате.

FAQ

Чем метод Зейделя отличается от метода Якоби? В методе Якоби все неизвестные на новой итерации считаются по значениям с прошлого шага. В методе Зейделя уже пересчитанные координаты немедленно подставляются в следующие уравнения той же итерации. Поэтому при выполнении условий сходимости Зейдель обычно сходится быстрее Якоби.

Всегда ли диагональное преобладание гарантирует сходимость? Да, строгое диагональное преобладание - достаточное условие: при нём метод Зейделя сходится при любом начальном приближении. Но это не необходимое условие, метод может сходиться и без него, если спектральный радиус матрицы перехода меньше единицы.

Что делать, если метод расходится? Проверьте спектральный радиус и попробуйте переставить уравнения или неизвестные так, чтобы наибольшие по модулю коэффициенты оказались на диагонали. Если перестановка не помогает, для той же системы стоит сравнить итерации с методом Якоби для решения СЛАУ: у него спектральный радиус матрицы перехода другой, и иногда сходится именно он.

Коротко

Метод Зейделя решает систему линейных уравнений итерациями, в которых уже уточнённые неизвестные сразу идут в пересчёт следующих. Его сходимость определяется двумя критериями: достаточным условием диагонального преобладания $|a_{ii}| > \sum_{j \ne i}|a_{ij}|$ и точным условием $\rho(G) < 1$ на спектральный радиус матрицы перехода. Геометрически итерации образуют лесенку, которая сходится к точке пересечения прямых при $\rho < 1$ и расходится при $\rho > 1$. Если преобладания нет, систему часто спасает перестановка уравнений так, чтобы сильные коэффициенты встали на диагональ.