Метод сопряжённых градиентов: формулы и пример

Метод сопряжённых градиентов - это итерационный способ минимизировать квадратичную функцию или, что то же самое, решить систему линейных уравнений $Ax = b$ с симметричной положительно определённой матрицей. Его ценят за главное свойство: на функции от $n$ переменных он находит точный минимум не более чем за $n$ шагов, тогда как обычный градиентный спуск может зигзагом идти сотнями итераций. Ниже разберём, из каких формул он состоит, что такое сопряжённость направлений, почему она ускоряет сходимость и где студенты чаще всего ошибаются при ручном счёте. Чтобы сразу увидеть разницу с градиентным спуском, покрути калькулятор ниже: он рисует линии уровня, траекторию обоих методов и график падения функции по итерациям.

Какую задачу решает метод

Метод работает с квадратичной функцией вида

$f(x) = \frac{1}{2}\,x^T A x - b^T x,$

где $A$ - симметричная положительно определённая матрица размера $n \times n$, а $x$ и $b$ - векторы. Её градиент равен $\nabla f(x) = A x - b$, и в точке минимума он обращается в ноль. Значит, минимизация $f$ полностью эквивалентна решению системы $A x = b$: где функция минимальна, там и выполняется уравнение. Именно поэтому метод сопряжённых градиентов одновременно считают и методом оптимизации, и методом решения СЛАУ - особенно ценным для больших разреженных матриц, где прямые методы вроде разложения Холецкого слишком дороги.

Рассчитать для своей задачи

Идея в том, что наивный спуск «строго вниз по склону» теряет уже сделанный прогресс: каждый новый шаг частично портит то, чего добились на предыдущем. Метод сопряжённых градиентов строит направления так, чтобы шаги не мешали друг другу.

Что такое сопряжённые направления

Два ненулевых вектора $d_i$ и $d_j$ называются $A$-сопряжёнными (или просто сопряжёнными относительно матрицы $A$), если

$d_i^T A d_j = 0, \qquad i \ne j.$

Это обобщение обычной ортогональности: если бы $A$ была единичной матрицей, условие превратилось бы в $d_i^T d_j = 0$, то есть в перпендикулярность. Геометрически сопряжённость учитывает «вытянутость» линий уровня: направления, ортогональные в искажённой метрике, заданной матрицей $A$.

Рассчитать для своей задачи

Ключевой факт: если у нас есть набор из $n$ взаимно сопряжённых направлений, то минимум квадратичной функции достигается ровно за $n$ точных одномерных шагов вдоль этих направлений. Минимизация по одному сопряжённому направлению не сбивает уже достигнутый минимум по предыдущим - вот почему прогресс не теряется.

Формулы шага метода

Метод сопряжённых градиентов строит сопряжённые направления на ходу, не зная их заранее. Введём остаток (он же антиградиент) $r_k = b - A x_k = -\nabla f(x_k)$. Стартуем с произвольной точки $x_0$, берём $r_0 = b - A x_0$ и первое направление $d_0 = r_0$. Дальше на каждой итерации:

$\alpha_k = \frac{r_k^T r_k}{d_k^T A d_k}, \qquad x_{k+1} = x_k + \alpha_k d_k,$

$r_{k+1} = r_k - \alpha_k A d_k, \qquad \beta_k = \frac{r_{k+1}^T r_{k+1}}{r_k^T r_k},$

$d_{k+1} = r_{k+1} + \beta_k d_k.$

Здесь $\alpha_k$ - это длина шага из точного одномерного поиска вдоль $d_k$ (минимум $f$ по этому направлению), а $\beta_k$ - коэффициент, который подмешивает старое направление к новому антиградиенту так, чтобы получившееся $d_{k+1}$ оказалось сопряжённым со всеми предыдущими. Приведённая формула для $\beta_k$ называется формулой Флетчера-Ривса. Обновление остатка $r_{k+1} = r_k - \alpha_k A d_k$ позволяет не пересчитывать $A x$ заново: за итерацию матрица умножается на вектор всего один раз, в произведении $A d_k$.

Почему он сходится за n шагов

На квадратичной функции от $n$ переменных направления $d_0, d_1, \dots, d_{n-1}$, построенные методом, попарно $A$-сопряжены, а остатки $r_k$ попарно ортогональны. Поскольку $n$ сопряжённых направлений образуют базис, после $n$ точных шагов вдоль них компонента ошибки по каждому направлению обнуляется - и метод приходит в точный минимум. Это его принципиальное отличие от градиентного спуска, который сопряжённость не использует и потому на вытянутых оврагах буксует.

Рассчитать для своей задачи

Скорость зависит от числа обусловленности $\kappa = \lambda_{\max}/\lambda_{\min}$ - отношения наибольшего и наименьшего собственных чисел матрицы $A$. Для градиентного спуска число итераций растёт примерно как $\kappa$, а для сопряжённых градиентов - как $\sqrt{\kappa}$, что на плохо обусловленных задачах даёт огромный выигрыш. На практике из-за ошибок округления точную сходимость за $n$ шагов не всегда удаётся получить, поэтому метод применяют итерационно с критерием остановки по малости остатка $\|r_k\|$. Чтобы ускорить сходимость, матрицу часто предобуславливают, искусственно уменьшая $\kappa$.

Пример решения типовой задачи

Минимизируем $f(x) = \frac{1}{2} x^T A x$ с диагональной матрицей $A = \operatorname{diag}(12,\,1)$ (то есть $b = 0$, минимум в начале координат) из стартовой точки $x_0 = (4;\,3)$. Здесь $n = 2$, значит метод обязан сойтись за два шага.

Считаем остаток и первое направление:

$r_0 = -A x_0 = -(48;\, 3), \qquad d_0 = r_0 = (-48;\, -3).$

Длина первого шага:

$\alpha_0 = \frac{r_0^T r_0}{d_0^T A d_0} = \frac{48^2 + 3^2}{12\cdot 48^2 + 1\cdot 3^2} \approx 0{,}0837.$

Делаем шаг $x_1 = x_0 + \alpha_0 d_0 \approx (-0{,}014;\, 2{,}749)$ - точка ушла к длинной оси эллипса. Пересчитываем остаток $r_1 = r_0 - \alpha_0 A d_0$, коэффициент $\beta_0 = \dfrac{r_1^T r_1}{r_0^T r_0}$ и новое направление $d_1 = r_1 + \beta_0 d_0$. Второй шаг с длиной $\alpha_1$ приводит в точку $x_2 \approx (0;\, 0)$ - точный минимум. Градиентному же спуску при том же $\kappa = 12$ нужно около десяти итераций, чтобы подойти на ту же точность. Оба калькулятора выше собирают эту цепочку автоматически: первый строит траекторию и график сходимости, а кнопка разворачивает полный пошаговый вывод в чате.

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

• Применение к несимметричной или незнакоопределённой матрице. Базовый метод требует симметричной положительно определённой $A$. Для произвольных систем используют варианты вроде BiCG или CG для нормальных уравнений, а не исходную формулу.
• Неверный знак остатка. Остаток равен $r_k = b - A x_k$, это антиградиент. Если перепутать знак и взять $A x_k - b$, направления поедут в сторону роста функции.
• Пересчёт остатка через $A x$ вместо рекуррентной формулы. Формула $r_{k+1} = r_k - \alpha_k A d_k$ экономит умножения матрицы на вектор; считать $r_{k+1} = b - A x_{k+1}$ заново не ошибка по результату, но теряет смысл метода и накапливает погрешность иначе.
• Ожидание сходимости меньше чем за $n$ шагов в общем случае. За $n$ шагов гарантирован точный минимум, но не раньше, если только начальная ошибка не лежит в подпространстве меньшей размерности.
• Игнорирование обусловленности. На плохо обусловленной матрице без предобуславливателя даже сопряжённые градиенты могут потребовать много итераций из-за округления.

FAQ

Чем метод сопряжённых градиентов отличается от градиентного спуска? Градиентный спуск всегда идёт против градиента, поэтому соседние шаги перпендикулярны и траектория зигзагует по дну вытянутого оврага. Метод сопряжённых градиентов подмешивает к антиградиенту прошлое направление с коэффициентом $\beta_k$, делая шаги $A$-сопряжёнными, и за счёт этого на квадратике от $n$ переменных приходит в минимум за $n$ шагов.

Что такое A-сопряжённость направлений? Два вектора $A$-сопряжены, если $d_i^T A d_j = 0$. Это ортогональность в метрике, заданной матрицей $A$: такие направления учитывают вытянутость линий уровня, и минимизация вдоль одного не портит достигнутый минимум вдоль другого.

Зачем нужен коэффициент бета в формуле? Коэффициент $\beta_k = r_{k+1}^T r_{k+1} / (r_k^T r_k)$ задаёт, сколько прошлого направления подмешать к новому антиградиенту, чтобы получившееся направление оказалось сопряжённым со всеми предыдущими. Без него метод выродился бы в обычный спуск.

Коротко

Метод сопряжённых градиентов минимизирует квадратичную функцию $f(x) = \frac12 x^T A x - b^T x$ с симметричной положительно определённой $A$, что эквивалентно решению системы $A x = b$. Он строит $A$-сопряжённые направления по формулам $\alpha_k = r_k^T r_k / (d_k^T A d_k)$, $x_{k+1} = x_k + \alpha_k d_k$, $\beta_k = r_{k+1}^T r_{k+1} / (r_k^T r_k)$, $d_{k+1} = r_{k+1} + \beta_k d_k$ и за счёт сопряжённости находит точный минимум не более чем за $n$ шагов, обгоняя градиентный спуск на плохо обусловленных задачах.