Метод сопряженных градиентов: прорыв в решении гигантских систем

От градиентного спуска к сопряженным направлениям

Идея метода начинается с перевода алгебраической задачи на язык оптимизации. Решение системы AX = B (где A — симметричная положительно определенная матрица) математически эквивалентно нахождению точки минимума многомерной квадратичной функции f(X) = 1/2 * X^T * A * X - B^T * X. Простейший способ найти минимум — использовать метод наискорейшего спуска, двигаясь против вектора градиента (который равен невязке системы: r = B - AX). Однако для вытянутых «овражных» функций градиентный спуск совершает множество зигзагообразных, неэффективных шагов. Метод сопряженных градиентов решает эту проблему гениальным образом: он требует, чтобы каждое новое направление поиска было не просто ортогональным предыдущему (как в градиентном спуске), а А-ортогональным (сопряженным) ко всем предыдущим направлениям.

Подпространства Крылова и свойство оптимальности

А-ортогональность означает, что скалярное произведение двух векторов направлений P_i и P_j с весовой матрицей A равно нулю (P_i^T * A * P_j = 0). Благодаря этому свойству, метод CG не делает зигзагов: он находит точный минимум вдоль каждого сопряженного направления ровно за один шаг и больше никогда к нему не возвращается. Математически доказано, что на k-й итерации метод находит абсолютно лучшее (оптимальное) приближение к ответу из всех возможных векторов, лежащих в подпространстве Крылова размерности k. Подпространство Крылова генерируется путем последовательного умножения начальной невязки на матрицу A (r, Ar, A^2r и так далее). В идеальной арифметике без округлений алгоритм нашел бы точное решение системы из n уравнений максимум за n шагов.

Проблема обусловленности и предобуславливание (PCG)

Скорость сходимости метода сопряженных градиентов жестко зависит от спектра (набора собственных значений) матрицы A, а точнее — от ее числа обусловленности. Чем ближе число обусловленности к единице, тем быстрее метод «схлопывается» к правильному ответу. Если же собственные значения распределены плохо, количество итераций может стать огромным. Чтобы обойти это физическое ограничение, инженеры используют метод предобусловленных сопряженных градиентов (Preconditioned Conjugate Gradients, PCG). Суть предобуславливания заключается в умножении исходной системы на специальную матрицу M^(-1), которая аппроксимирует A^(-1), но при этом легко вычисляется. Это преобразование сжимает спектр матрицы, превращая вытянутый овраг квадратичной формы в аккуратную чашу, где метод CG сходится за считанные итерации.

Обобщения для несимметричных матриц (GMRES и BiCGSTAB)

Классический метод сопряженных градиентов работает только для симметричных положительно определенных матриц, что накладывает существенные ограничения (например, он не подходит для задач конвекции в гидродинамике, где матрицы несимметричны). Для обхода этой проблемы были созданы обобщенные алгоритмы в подпространствах Крылова. Самыми известными из них являются метод обобщенных минимальных невязок (GMRES) и метод бисопряженных градиентов со стабилизацией (BiCGSTAB). Они используют более сложные схемы ортогонализации (например, процесс Арнольди вместо процесса Ланцоша), требуют больше памяти для хранения базисных векторов, но зато способны «проглатывать» абсолютно любые невырожденные матрицы гигантских размеров.