🔢 Численные методы35 минСложность 3/5+65 XP

Итерационные методы для СЛАУ: Якоби, Зейдель, релаксация

Q: Как быстро проверить, что Якоби и Зейдель сойдутся?

Пробежьте строки: если в каждой $|a_{ii}| > \sum_{j\ne i}|a_{ij}|$ — сходятся оба, и можно считать. Если преобладания нет, а матрица симметричная и положительно определённая — сойдётся Зейдель (Якоби — не факт). Во всех остальных случаях остаётся строгий критерий: спектральный радиус матрицы перехода меньше единицы.

Q: Что общего у итерационных методов СЛАУ и принципа Банаха?

Всё: метод простых итераций $x^{(k+1)} = Bx^{(k)} + c$ — это сжатое отображение, если $\|B\| < 1$ в какой-нибудь норме; Банах тогда гарантирует единственную неподвижную точку (решение системы) и сходимость из любого старта с геометрической скоростью. Спектральный радиус — точная версия «сжатости». Подробно — в уроке про [принцип сжатых отображений](/course/tfdp/princip-szhatyh-otobrazhenij/).

Как итерации уточняют решение системы, когда диагональное преобладание гарантирует сходимость, почему Зейдель обгоняет Якоби и как параметр релаксации ω = 1,03 сокращает счёт — с ручным расчётом трёх методов на одной системе.

2 интерактива3 квизаУрок 7 из 11Обновлено 05.10.2026

В обзоре численных методов для СЛАУ мы встретили Якоби и Зейделя мельком, в конце — как ответ на вопрос «что делать с миллионом неизвестных». Теперь разберём их всерьёз: откуда берутся их формулы, что именно гарантирует сходимость, почему Зейдель обычно обгоняет Якоби и куда встраивается третий игрок — метод релаксации с настраиваемым параметром $ω$ , способный ускорить счёт ещё в разы. База простая: вместо того чтобы решать систему сразу, угадываем ответ и улучшаем его простым правилом — тем самым способом, каким работает любой итерационный метод.

Формулы: разложение матрицы на три части#

Разложим матрицу $A$ на диагональ, нижний и верхний треугольники: $A = D - L - U$ , где $D$ — диагональ, $- L$ — элементы ниже диагонали, $- U$ — выше. Система $A x = b$ превращается в $D x = (L + U) x + b$ . Идея метода Якоби: в левой части взять новое приближение, в правой — старое:

x^{(k + 1)} = D^{- 1} (L + U) x^{(k)} + D^{- 1} b

метод Якоби: каждая компонента считается из старого слоя — компоненты независимы и параллельны

Зейдель делает маленькую, но хитрую правку: компоненты нумеруются по порядку, и свежепосчитанные сразу подставляются в правую часть — не дожидаясь конца итерации:

(D - L) x^{(k + 1)} = U x^{(k)} + b

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

Оба метода — частные случаи метода простых итераций $x^{(k + 1)} = B x^{(k)} + c$ с матрицей перехода $B$ . Вся теория сходимости живёт в спектре этой матрицы: итерации сходятся тогда и только тогда, когда спектральный радиус $ρ (B)$ — максимальный по модулю собственное значение — меньше единицы. Для Якоби $B_{J} = D^{- 1} (L + U)$ , для Зейделя — своя матрица перехода $B_{S} = (D - L)^{- 1} U$ ; как считать спектр приближённо, показано в уроке про численные собственные значения. Проверять радиус в лоб неудобно, поэтому на практике пользуются достаточными условиями.

Когда итерации гарантированно сходятся#

Первое условие — строгое диагональное преобладание: в каждой строке модуль диагонального элемента больше суммы модулей остальных, $∣ a_{ii} ∣ > \sum_{j \neq = i} ∣ a_{ij} ∣$ . Оно влечёт $ρ (B_{J}) < 1$ — сходятся и Якоби, и Зейдель. Чем больше отрыв диагонали, тем меньше радиус и быстрее сходимость: в системе $10 x + y = 12$ , $x + 10 y = 21$ радиус Якоби равен $0, 1$ — ошибка падает в десять раз за итерацию.

Второе условие — симметричность и положительная определённость матрицы: для таких систем Зейдель сходится всегда, даже если преобладания нет. А вот Якоби — не обязан: классическая ловушка, когда преобладания нет, система SPD, Зейдель ползёт к ответу, а Якоби расходится. Проверка преобладания — одна строка: обойти строки, сравнить модули. Сеточные матрицы из задач теплопроводности преобладают почти всегда — поэтому итерационные методы там и живут.

Мост к теории высшего уровня: метод простых итераций — это сжатие в подходящей норме, и существование сходимости выдаёт принцип сжатых отображений Банаха, разобранный в курсе ТФДП: чем меньше $ρ (B)$ , тем сильнее сжатие и быстрее сходится последовательность приближений.

Релаксация: параметр, который разгоняет Зейделя#

Метод верхней релаксации (SOR) берёт зейделевский шаг и перешагивает его: новое значение — смесь старого и зейделевского с весом $ω$ :

x_{i}^{(k + 1)} = (1 - ω) x_{i}^{(k)} + ω \cdot \tilde{x}_{i}^{(k + 1)}, \tilde{x}_{i}^{(k + 1)} = \frac{1}{a _{ii}} (b_{i} - j < i \sum a_{ij} x_{j}^{(k + 1)} - j > i \sum a_{ij} x_{j}^{(k)})

SOR:

ω = 1

— обычный Зейдель,

ω < 1

— нижняя релаксация (осторожность),

ω > 1

— верхняя (перешагивание)

Граница жёсткая: при любом $ω \in / (0, 2)$ метод расходится — теорема Кахана. Для трёхдиагональных матриц с диагональным преобладанием существует оптимальный вес

ω_{опт} = \frac{2}{1 + 1 - ρ _{J}^{2}}, ρ_{J} = ρ (D^{- 1} (L + U))

оптимальный параметр релаксации через спектральный радиус метода Якоби

Формула обещает больше, чем кажется: при $ρ_{J}$ близком к единице (а у сеточных задач именно так) $ω_{опт}$ подбирается к двойке, и асимптотическая скорость сжатия ошибки улучшается с $ρ_{J}^{2}$ до $ω_{опт} - 1$ — на сетках разница измеряется кратами.

Ручной пример: одна система, три метода#

Система: $4 x + y = 6$ , $x + 4 y + z = 12$ , $y + 4 z = 14$ с решением $(1; 2; 3)$ . Проверка: $4 + 2 = 6$ , $1 + 8 + 3 = 12$ , $2 + 12 = 14$ — сходится. Диагональное преобладание есть: $4 > 1$ , $4 > 2$ , $4 > 1$ . Для трёхдиагональной матрицы спектральный радиус Якоби известен точно: $ρ_{J} = 2 /4 \approx 0, 354$ ; Зейдель даёт $ρ_{J}^{2} = 0, 125$ ; оптимальный вес $ω_{опт} = 2/ (1 + 1 - 2/16) = 1, 0334$ . Стартуем с нуля и считаем до ошибки $1 0^{- 4}$ .

$k$	Якоби: $x;\ y;\ z$	Зейдель: $x;\ y;\ z$	SOR ($\omega = 1{,}0334$)
1	1,5; 3; 3,5	1,5; 2,625; 2,8438	1,5501; 2,6997; 2,9194
2	0,75; 1,75; 2,75	0,8438; 2,0781; 2,9805	0,8009; 2,0489; 2,9901
3	1,0625; 2,125; 3,0625	0,9805; 2,0098; 2,9976	0,9940; 2,0025; 2,9997
4	0,9844; 1,9531; 2,9844	0,9951; 2,0024; 2,9994	0,9996; 2,0001; 3,0000
итог	10 итераций	6 итераций	5 итераций

Итерации до точности 1e−4: все числа проверены счётом; старт с (0; 0; 0)

Читаем таблицу. Якоби качается вокруг решения с амплитудой, падающей примерно на треть за шаг. Зейдель уже на первом шаге ближе: свежая компонента $x = 1, 5$ сразу снижает правую часть второго уравнения. Релаксация с небольшим перешагиванием вырывается вперёд на финишной прямой. Но самый громкий эффект — на другой стороне: тот же SOR с $ω = 1, 8$ добирается до той же точности за $48$ итераций — почти десятикратный проигрыш только из-за жадного веса. Релаксация — инструмент точной настройки, а не «больше значит лучше».

Первый шаг SOR по компонентам

Открывай шаги

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

Метод Якоби: итерации сходятся или разлетаются

СЛАУ

Метод Якоби решает систему Ax = b итерациями xᵢ⁽ᵏ⁺¹⁾ = (bᵢ − Σ_{j≠i} aᵢⱼ·xⱼ⁽ᵏ⁾)/aᵢᵢ — все компоненты обновляются сразу из старого приближения. Жмите «Шаг» и следите за нормой ошибки ||x⁽ᵏ⁾ − x*||: при диагональном преобладании она падает к нулю, без него — улетает.

Сходится 3×3

Система A·x = b

511161117

101624

x* = (1; 2; 3)

есть диагональное преобладание

Текущее приближение x⁽0⁾

x₁

x₂

x₃

Итерации

k	x₁⁽ᵏ⁾	x₂⁽ᵏ⁾	x₃⁽ᵏ⁾	‖x⁽ᵏ⁾−x*‖
0	0	0	0	3,7417

итерация k

‖x⁽ᵏ⁾ − x*‖

3,7417

‖x⁽ᵏ⁺¹⁾ − x⁽ᵏ⁾‖

● ‖x⁽ᵏ⁾ − x*‖ — норма ошибки◆ ‖x⁽ᵏ⁺¹⁾ − x⁽ᵏ⁾‖ — норма приращения

Скорость автопрогона6 — шаг каждые 0,80 с

Диагональное преобладание (|aᵢᵢ| > Σ_{j≠i}|aᵢⱼ|) — простое достаточное условие сходимости: оно гарантирует ρ(D⁻¹R) < 1. Сходиться можно и без него, а вот расходиться с ним — нельзя.

Критерий остановки: когда бросать итерации#

Практический вопрос: сколько шагов считать? Стоп-сигнал «приближения почти перестали меняться» обманчив — при медленной сходимости (радиус $0, 99$ ) разность соседних итераций крошечная, а до решения ещё далеко. Надёжнее нормировать приращение на запас: для преобладающих матриц работает апостериорная оценка $∥ x^{(k + 1)} - x^{*} ∥ \leq \frac{ρ}{1 - ρ} ∥ x^{(k + 1)} - x^{(k)} ∥$ — при радиусе, близком к единице, знаменатель $1 - ρ$ раздувает ошибку, и разность итераций ложно выглядит приторно малой. Плюс независимый контроль: подставить приближение в исходную систему и посмотреть невязку $∥ A x^{(k)} - b ∥$ — она обязана убывать со скоростью, предсказанной радиусом.

Ситуация	Метод выбора	Почему
Маленькая плотная система	Гаусс	Прямой метод точен за конечное число шагов
Огромная разреженная, преобладание есть	Зейдель или SOR	Дёшево на итерацию, память только на ненулевые
Матрица симметричная положительно определённая	Зейдель / сопряжённые градиенты	Сходимость гарантирована без преобладания
Много правых частей, одна матрица	LU-разложение	Факторизация один раз, дальше дёшево
Нужна максимальная скорость на сетке	SOR с настроенным $ω$	Асимптотика $ω_{опт} - 1$ против $ρ_{J}^{2}$

Шпаргалка выбора стратегии

Практикуйтесь руками: возьмите систему из задачника, проверьте преобладание, посчитайте две-три итерации Якоби и Зейделя, а потом прогоните её в тренажёре СЛАУ — расхождение ручного счёта с машиной сразу покажет, где потеряли знак. Пошаговый алгоритм решения систем от постановки до проверки есть в разборе задач на СЛАУ.

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

Считать преобладание обязательным. Нет преобладания — это не приговор: SPD-матрицы сходятся в Зейделе без него. Верная цепочка проверки: преобладание → если нет, симметрия и положительная определённость → если и этого нет, оценивать спектральный радиус или переставлять уравнения.
Якоби там, где Зейдель обязан. Для SPD-систем Якоби может расходиться при сходящемся Зейделе — выбор «по привычке к параллелизму» обходится дорого.
$ω = 2$ или выше. За границей $0 < ω < 2$ сходимости не бывает ни для какой матрицы с ненулевой диагональю — теорема Кахана. $ω = 1, 8$ на нашем примере съел десятикратное время счёта.
Остановка по малости приращения при медленной сходимости. При $ρ = 0, 99$ разность соседних итераций мала ещё задолго до решения; контролируйте невязку $∥ A x - b ∥$ и делите приращение на $1 - ρ$ .
Забыть, что итерации — приближение. Ответ итерационного метода подставляют дальше в расчёт как точный. Проверка подстановкой в исходную систему обязательна, как и в любом численном методе из обзора методов СЛАУ.

Проверь себя+10 XP

Чем метод Зейделя отличается от метода Якоби?

Проверь себя+10 XP

Для трёхдиагональной системы с $ρ_{J} = 0, 5$ каков оптимальный параметр релаксации и во сколько раз его асимптотика лучше зейделевской?

Проверь себя+10 XP

Итерации остановлены: разность соседних приближений $1 0^{- 6}$ , спектральный радиус $ρ = 0, 99$ . Насколько можно доверять ответу?

Частые вопросы

Как быстро проверить, что Якоби и Зейдель сойдутся?

Пробежьте строки: если в каждой $∣ a_{ii} ∣ > \sum_{j \neq = i} ∣ a_{ij} ∣$ — сходятся оба, и можно считать. Если преобладания нет, а матрица симметричная и положительно определённая — сойдётся Зейдель (Якоби — не факт). Во всех остальных случаях остаётся строгий критерий: спектральный радиус матрицы перехода меньше единицы.

Почему Зейдель обычно сходится быстрее Якоби?

Он использует свежую информацию сразу: компоненты считаются по порядку, и каждая новая сразу участвует в правых частях остальных. Для трёхдиагональных матриц эффект точный: радиус Зейделя равен квадрату якобиевского — на нашей системе $0, 125$ против $0, 354$ . Платой за скорость теряется параллелизм: порядок компонент нельзя ломать.

Как выбрать параметр релаксации ω на практике?

Если матрица трёхдиагональная с преобладанием — по формуле $ω_{опт} = 2/ (1 + 1 - ρ_{J}^{2})$ ; $ρ_{J}$ оценивают по модели задачи (для сеток это $cos (π h)$ с точностью до множителя). Если формула недоступна — прогоняют счёт с двумя-тремя пробными $ω$ (например, $1, 0$ ; $1, 2$ ; $1, 5$ ) и смотрят, где падает невязка быстрее. Выходить за $ω > 1, 9$ без формулы рискованно: даже в пределах теоретической границы счёт резко затягивается.

Что общего у итерационных методов СЛАУ и принципа Банаха?

Всё: метод простых итераций $x^{(k + 1)} = B x^{(k)} + c$ — это сжатое отображение, если $∥ B ∥ < 1$ в какой-нибудь норме; Банах тогда гарантирует единственную неподвижную точку (решение системы) и сходимость из любого старта с геометрической скоростью. Спектральный радиус — точная версия «сжатости». Подробно — в уроке про принцип сжатых отображений.

Итерационная философия — «улучшайзинг вместо формулы» — выходит далеко за пределы линейной алгебры: тот же механизм решает нелинейные уравнения (разбор метода), а его теоретический фундамент — сжатие в полном метрическом пространстве. Куда двигаться дальше по численным методам: численное решение ОДУ или обратная дорога — из квадратичной оптимизации в градиентный спуск, о котором следующий урок.

Готовитесь к контрольной?

Чеклист тем по «Численные методы»: что вы уже умеете, что повторить и в каком порядке.

Открыть чеклист предмета →

Проверьте себя в бою

Босс-экзамен по «Численные методы»: квизы всех уроков плюс бесконечный поток сгенерированных задач. Каждая попытка — новый расклад.

Начать босс-экзамен →