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

Почему прямых методов бывает недостаточно?

Ранее мы рассматривали метод Гаусса как основной инструмент для точного решения систем линейных алгебраических уравнений (СЛАУ). Однако на практике, особенно при численном решении дифференциальных уравнений в частных производных (например, в задачах теплопроводности или гидродинамики), возникают системы колоссальных размеров — миллионы и даже миллиарды уравнений. Матрицы таких систем являются разреженными: подавляющее большинство их элементов равно нулю. Использование прямого метода Гаусса для таких матриц нецелесообразно. Во-первых, он требует гигантского объема памяти (заполнение нулей ненулевыми элементами в процессе исключения), а во-вторых, вычислительная сложность прямого метода растет пропорционально кубу размерности матрицы (O(N^3)). В этих случаях спасают итерационные методы.

Итерационные методы не пытаются найти точное решение за конечное число шагов. Вместо этого они строят бесконечную последовательность векторов, которая с каждым шагом все больше приближается (сходится) к истинному решению. Вычисления останавливаются, когда разница между двумя последовательными итерациями становится меньше наперед заданной малой величины (погрешности).

Метод простой итерации (Метод Якоби)

Метод Якоби является концептуально самым простым итерационным методом. Идея заключается в том, чтобы выразить из первого уравнения системы первую неизвестную x_1, из второго — x_2, и так далее до x_n. Таким образом, мы получаем систему уравнений, где слева стоят неизвестные, а справа — выражения, зависящие от всех остальных неизвестных.

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

Метод Гаусса-Зейделя и условия сходимости

Метод Гаусса-Зейделя представляет собой логическое улучшение метода Якоби. Немецкий математик Филипп Людвиг фон Зейдель заметил, что в процессе вычисления нового вектора мы можем использовать уже обновленные значения компонент. То есть, вычислив новую компоненту x_1, при вычислении x_2 мы подставляем не старое значение x_1 с предыдущей итерации, а только что найденное, более точное. Благодаря этому метод Гаусса-Зейделя сходится в среднем в два раза быстрее метода Якоби и требует меньше оперативной памяти для хранения промежуточных векторов.

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