Метод сопряжённых градиентов

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

История

Метод сопряжённых градиентов был впервые предложен в 1952 году американскими математиками Магнусом Хестенсом и Эдуардом Штифелем. Первоначально он разрабатывался для решения систем линейных уравнений, возникающих при численном моделировании в геофизике и гидродинамике. В 1964 году британский математик Роберт Флетчер и американский математик Майкл Ривз независимо друг от друга адаптировали этот метод для задач нелинейной оптимизации, что значительно расширило область его применения.

В 1970-х годах метод был усовершенствован для решения задач с несимметричными матрицами (обобщённый метод сопряжённых градиентов, GMRES) и для задач с ограничениями. В 1980-х годах появились варианты с предобусловливанием, что позволило существенно ускорить сходимость для плохо обусловленных систем.

Основные принципы

Геометрическая интерпретация

Метод сопряжённых градиентов основан на идее минимизации квадратичной функции:

\[ f(x) = \frac{1}{2} x^T A x - b^T x + c \]

где \(A\) — симметричная положительно определённая матрица. Градиент этой функции равен \( \nabla f(x) = Ax - b \), а решение системы \(Ax = b\) соответствует точке минимума \(f(x)\).

В отличие от метода наискорейшего спуска, где на каждой итерации выбирается направление антиградиента, метод сопряжённых градиентов использует направления, которые являются \(A\)-сопряжёнными (или \(A\)-ортогональными). Два вектора \(p\) и \(q\) называются \(A\)-сопряжёнными, если:

\[ p^T A q = 0 \]

Это свойство гарантирует, что минимизация вдоль одного направления не нарушает уже достигнутый минимум вдоль предыдущих направлений.

Алгоритм для линейных систем

Для решения системы \(Ax = b\) с симметричной положительно определённой матрицей \(A\) алгоритм выглядит следующим образом:

1. Выбрать начальное приближение \(x_0\)
2. Вычислить начальный невязку \(r_0 = b - A x_0\)
3. Установить начальное направление \(p_0 = r_0\)
4. Для \(k = 0, 1, 2, \dots\) до сходимости:

• Вычислить шаг: \(\alpha_k = \frac{r_k^T r_k}{p_k^T A p_k}\)
• Обновить приближение: \(x_{k+1} = x_k + \alpha_k p_k\)
• Обновить невязку: \(r_{k+1} = r_k - \alpha_k A p_k\)
• Вычислить коэффициент: \(\beta_k = \frac{r_{k+1}^T r_{k+1}}{r_k^T r_k}\)
• Обновить направление: \(p_{k+1} = r_{k+1} + \beta_k p_k\)

Ключевое свойство: в точной арифметике метод сходится за не более чем \(n\) итераций, где \(n\) — размерность системы. На практике из-за ошибок округления может потребоваться больше итераций.

Алгоритм для нелинейной оптимизации

Для минимизации произвольной (не обязательно квадратичной) функции \(f(x)\) используется нелинейный метод сопряжённых градиентов. Наиболее распространённые варианты:

• Метод Флетчера-Ривза: \(\beta_k = \frac{\nabla f(x_{k+1})^T \nabla f(x_{k+1})}{\nabla f(x_k)^T \nabla f(x_k)}\)
• Метод Полака-Рибьера: \(\beta_k = \frac{\nabla f(x_{k+1})^T (\nabla f(x_{k+1}) - \nabla f(x_k))}{\nabla f(x_k)^T \nabla f(x_k)}\)
• Метод Хестенса-Штифеля: \(\beta_k = \frac{\nabla f(x_{k+1})^T (\nabla f(x_{k+1}) - \nabla f(x_k))}{p_k^T (\nabla f(x_{k+1}) - \nabla f(x_k))}\)

В нелинейном случае метод не гарантирует сходимость за конечное число шагов, но часто оказывается эффективнее градиентного спуска.

Варианты и модификации

Предобусловленный метод сопряжённых градиентов (PCG)

Для ускорения сходимости при плохо обусловленных матрицах используется предобусловливание. Вместо системы \(Ax = b\) решается система \(M^{-1}Ax = M^{-1}b\), где \(M\) — предобусловливатель, близкий к \(A\) в некотором смысле. Популярные предобусловливатели:

• Неполное разложение Холецкого (Incomplete Cholesky)
• Диагональное предобусловливание (Jacobi)
• Многосеточные методы (Multigrid)

Обобщённый метод сопряжённых градиентов (GMRES)

Для несимметричных матриц используется метод GMRES, предложенный в 1986 году. Он строит ортонормированный базис подпространства Крылова и минимизирует невязку на этом подпространстве. Требует хранения всех предыдущих направлений, что может быть затратно для больших задач.

Метод сопряжённых градиентов для нормальных уравнений (CGNR)

Применяется для решения систем с произвольными (в том числе прямоугольными) матрицами путём сведения к системе \(A^T A x = A^T b\). Матрица \(A^T A\) симметрична и положительно определена, что позволяет использовать стандартный метод.

Применение

Численное решение дифференциальных уравнений

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

Оптимизация и машинное обучение

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

Обработка изображений

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

Геофизика и сейсмология

Метод применяется для решения обратных задач геофизики, в частности для инверсии сейсмических данных и моделирования распространения волн.

Свойства и ограничения

Преимущества

• Конечная сходимость в точной арифметике для линейных систем
• Низкая потребность в памяти — хранятся только несколько векторов
• Хорошая масштабируемость для разреженных матриц
• Отсутствие параметров (в отличие от градиентного спуска с шагом)

Недостатки

• Чувствительность к ошибкам округления — на практике может потребоваться рестарт алгоритма
• Требование симметричности и положительной определённости для линейного варианта
• Медленная сходимость для плохо обусловленных матриц без предобусловливания
• Необходимость вычисления матрично-векторного произведения на каждой итерации

Сравнение с другими методами

Реализации

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

• MATLAB: функция pcg (предобусловленный метод)
• Python: модуль scipy.sparse.linalg.cg в библиотеке SciPy
• PETSc: библиотека для параллельных вычислений, содержит реализацию метода
• Trilinos: библиотека для решения больших разреженных систем
• CUDA: реализация для графических процессоров в библиотеке cuSPARSE

Источники

• Хестенс М., Штифель Э. «Методы сопряжённых градиентов для решения линейных систем» (1952)
• Флетчер Р., Ривз М. «Функциональная минимизация методом сопряжённых градиентов» (1964)
• Самарский А. А., Гулин А. В. «Численные методы» (1989)
• Голуб Дж., Ван Лоун Ч. «Матричные вычисления» (1996)
• Шевчук И. А. «Метод сопряжённых градиентов» (2007)