Метод Зейделя или метод Якоби: в чём разница и что быстрее

Две формулы отличаются одним индексом. В методе Якоби все компоненты очередного приближения считаются из старых: подставил вектор прошлого шага целиком — получил новый вектор разом. В методе Зейделя компоненты обновляются по очереди, и только что посчитанная величина немедленно идёт в дело при вычислении соседней. На бумаге — мелочь. На практике — вдвое меньше итераций, потерянный параллелизм и пара матриц, на которых оба метода дружно летят в пропасть. Ниже — таблицы итераций с точностью до третьего знака, счёт до $10^{-6}$, спектральные радиусы двух показательных матриц и честный ответ на вопрос «кто быстрее».

Обозначения всюду одинаковые: матрицу системы раскладывают в сумму A = D + L + U, где D — диагональ, L и U — строгие нижний и верхний треугольники. Оба метода — итерационные в строгом смысле слова, см. термин итерационный метод: они не дают ответа за конечное число шагов, а строят последовательность приближений, сходящуюся к решению при удачной матрице. Общая механика разобрана в уроке численные методы для СЛАУ; рядом стоит прямой метод Гаусса — конечный, но дорогой для больших разреженных систем, ради которых итерации и придуманы.

Одновременные или последовательные обновления: в чём разница на бумаге#

Якоби в матричной записи:

Зейдель:

Расшифруем словами. У Якоби шаг начинается с полного среза старого вектора: пока не посчитаны все компоненты нового, шаг не закончен, поэтому нужны два массива памяти. У Зейделя массив один — старые значения перезаписываются по мере готовности. Обратная сторона та же: вторую компоненту не посчитать, пока не готова первая. Вычислительная цепочка жёсткая, компонента за компонентой, слева направо. Это и есть вся разница — дальше она только умножается на свойства матрицы.

Когда это вообще сходится: преобладание и симметрия#

Условие, закрывающее оба метода сразу, — строгое диагональное преобладание: в каждой строке диагональный элемент по модулю больше суммы модулей остальных, $|a_{ii}|>{\sum }_{j\ne i}|a_{ij}|$. Такое отображение сжимающее, и оба метода сходятся с любого стартового вектора. Проверка занимает минуту: пробежали по строкам — и понятно, с чем имеете дело. Учебный пример — матрица [[2, 1], [1, 2]] из численного примера ниже: диагональная двойка перекрывает единицу в каждой строке.

Для Зейделя список гарантий длиннее. Если матрица симметрична и положительно определена, метод Гаусса—Зейделя сходится всегда — преобладание не требуется, хватило положительной определённости. У Якоби на тех же матрицах своё условие: должна быть положительно определённой матрица 2D − A, и выполняется оно не всегда. Практический вывод: на симметричных задачах (регуляризация, сети, конечные элементы) Зейдель — выбор по умолчанию, а Якоби требует отдельной проверки. На несимметричных матрицах всё решает спектральный радиус — сейчас посчитаем его руками.

Числами: система 2x + y = 3, x + 2y = 0#

Точное решение — (2, −1), проверяется подстановкой. Разрешаем первое уравнение относительно x, второе относительно y: $x=(3-y)/2$, $y=-x/2$. Это и есть обе итерационные формулы; вся разница между методами — в том, какой x подставлять в правую часть для y. Стартуем с нулевого вектора и считаем пять итераций с точностью до трёх знаков.

Смотрите, как ведёт себя ошибка в максимум-норме. У Якоби она делится пополам за итерацию: 1; 0,5; 0,25; 0,125; 0,0625 — геометрическая прогрессия со знаменателем 0,5. У Зейделя — делится на четыре: 0,5; 0,125; 0,031; 0,008. Двойка в знаменателе против четвёрки — и на дистанции это ровно вдвое меньше итераций: до $10^{-6}$ Якоби добирается за 21 шаг, Зейдель — за 11. Свежая y уже на первой итерации ускорила Зейдель, и фора сохраняется до самого конца.

Спектральный радиус: честный подсчёт для матрицы [[1, 2], [2, 1]]#

Красивая матрица той же размерности, но диагональ теперь перекрыта: единица против двойки в каждой строке. Преобладания нет, о гарантиях речи нет — остаётся мерить спектральный радиус итерационных матриц. Для Якоби это $-D^{-1}(L+U)$, для Зейделя $-(D+L{)}^{-1}U$; метод сходится тогда и только тогда, когда радиус меньше единицы.

Считаем; для матрицы 2×2 собственные числа берутся аналитически. У Якоби T = [[0, −2], [−2, 0]] — собственные числа плюс-минус два, значит ${\rho }_J=2$. У Зейделя T = [[0, −2], [0, 4]] — матрица треугольная, собственные числа сидят на диагонали: 0 и 4, значит ${\rho }_S=4$. Честный ответ на вопрос «кто сходится»: никто. Оба радиуса больше единицы, причём Зейдель улетает вдвое агрессивнее: за одну итерацию его ошибка растёт вчетверо против удвоения у Якоби.

Мораль ровно та, которой пугают преподаватели: «Зейдель быстрее» — не универсальное свойство метода, а свойство пары «матрица и оба метода». Там, где сходятся оба (для матриц со свойством согласованности обычно ${\rho }_S={\rho }_J^2$), Зейдель выигрывает по числу итераций — как в таблице выше: 11 против 21. Где не сходятся оба — он просто быстрее доходит до переполнения. Проверяйте радиус, а не надейтесь на имя метода. Кстати, спасение иногда в одном движении: переставьте строки системы местами — получится [[2, 1], [1, 2]], на которой оба метода сходятся.

Число итераций связано с радиусом простой оценкой: чтобы уменьшить ошибку в $10^m$ раз, нужно примерно $m\cdot \ln 10/(-\ln \rho )$ шагов. Радиус 0,5 — около $3,3m$ шагов; радиус 0,9 — уже около $22m$. Отсюда диагноз «метод есть, а толку нет»: формально сходящаяся матрица с $\rho =0,98$ потребует сотен итераций, и лечится это не терпением, а переупорядочением уравнений или предобусловливанием. Как чувствительность задачи связана с её числами — в терминах число обусловленности.

1. 1
   Шаг 1: разложите матрицу на D, L, U и проверьте диагональное преобладание. Есть строгое — оба метода сходятся, дальше можно не считать.
2. 2
   Шаг 2: матрица симметрична и положительно определена? Тогда Зейдель сходится всегда; для Якоби отдельно проверьте положительную определённость 2D − A.
3. 3
   Шаг 3: посчитайте радиусы: ${\rho }_J$ для $-D^{-1}(L+U)$ и ${\rho }_S$ для $-(D+L{)}^{-1}U$. Радиус меньше единицы — метод жив, больше — мёртв при любом начальном приближении.
4. 4
   Шаг 4: из живых кандидатов берите того, у кого $-\ln \rho$ больше; при равенстве решайте железо: параллельная машина — Якоби, последовательная — Зейдель.

Параллелизм: где Якоби отыгрывается#

Итерация Якоби embarrassingly parallel: каждая компонента нового вектора считается независимо — это матрично-векторное умножение, миллион потоков GPU без синхронизации. Поэтому Якоби живёт в графических решателях и сеточных методах, где шагов много, а каждый шаг дешёвый. У Зейделя компонента ждёт предыдущую — цепочка, которая на видеокарте оборачивается простоем тысяч ядер. Компромисс известен: красно-чёрное упорядочение. Узлы сетки красят в шахматном порядке, обновляют сначала все красные (они друг от друга не зависят), затем все чёрные. Выходит гибрид: параллелизм Якоби внутри цвета, зейделевский характер сходимости между цветами.

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