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

🎯 Зачем это нужно?

Представь, что ты настраиваешь нейросеть с миллионом параметров 🧠. Обычный градиентный спуск “ползёт” к минимуму как слепой в лабиринте — делает много лишних шагов. А метод сопряжённых градиентов (Conjugate Gradient) — это GPS-навигатор для оптимизации!

🔥 Где это жарко используется:

• Обучение больших линейных моделей — ridge regression с миллионами фичей
• Решение СЛАУ — Ax = b, где A размером 10⁶ × 10⁶
• Физические симуляции — от анимации жидкости в играх до прогноза погоды
• Предобуславливание — ускоряет другие методы в 10-100 раз!

📚 История вопроса

В 1952 году математики Хестенс и Штифель придумали CG для решения систем линейных уравнений. Хотели решить задачи размером 20×20 — казалось невозможным! 😅

Прикол в том, что метод “забывали” и переоткрывали несколько раз. В 1970-х его адаптировали для нелинейной оптимизации, и теперь он живёт в каждом солвере от NumPy до PyTorch.

Fun fact: Google использует CG для обучения своих гигантских моделей — экономит месяцы вычислений! 💰

💡 Интуиция

Обычный градиентный спуск — это как искать выход из долины, всё время идя по самому крутому склону. Проблема: часто “зигзагишь” туда-сюда!

[МЕДИА: image_01] Описание: Сравнение траекторий градиентного спуска (зигзагообразная) и сопряжённых градиентов (прямые линии к минимуму) Промпт: “optimization trajectory comparison, gradient descent zigzag path vs conjugate gradient straight efficient path, 3D surface plot, technical visualization, clean modern style”

CG решает эту проблему умно: 1️⃣ Память о прошлом — помнит предыдущие направления 2️⃣ Сопряжённые направления — новое направление “ортогонально” к старым в специальном смысле
3️⃣ Финишная гарантия — для квадратичных функций найдёт точный минимум за ≤ n шагов!

Это как если бы ты запоминал все повороты в лабиринте и больше никогда не ходил по тем же местам дважды! 🎯

📐 Формальное определение

Для задачи минимизации квадратичной функции: f(x) = ½x^T A x - b^T x + c

где A — положительно определённая матрица.

Алгоритм CG:

1. r₀ = b - Ax₀, p₀ = r₀  
2. Для k = 0, 1, 2, ...
   αₖ = (rₖ^T rₖ)/(pₖ^T A pₖ)     # размер шага
   xₖ₊₁ = xₖ + αₖ pₖ                # новая точка  
   rₖ₊₁ = rₖ - αₖ A pₖ              # новый остаток
   βₖ = (rₖ₊₁^T rₖ₊₁)/(rₖ^T rₖ)     # коэффициент сопряжения
   pₖ₊₁ = rₖ₊₁ + βₖ pₖ               # новое направление

Ключевое свойство: направления p₀, p₁, … взаимно A-ортогональны: pᵢ^T A pⱼ = 0 для i ≠ j

🔍 Примеры с разбором

Пример 1: Простая система 2×2

Решим систему:

4x₁ + x₂ = 1
x₁ + 3x₂ = 2  

Это эквивалентно минимизации: f(x) = ½x^T A x - b^T x

где A = [[4,1], [1,3]], b = [1,2]

[МЕДИА: image_02] Описание: Пошаговая визуализация метода сопряжённых градиентов для системы 2x2, контурные линии и траектория Промпт: “step-by-step conjugate gradient visualization, 2x2 system, contour plot with elliptical level curves, iteration path marked with arrows, mathematical annotations”

Итерация 0:

• x₀ = [0,0] (начальная точка)
• r₀ = b - Ax₀ = [1,2]
• p₀ = r₀ = [1,2]

Итерация 1:

• α₀ = (r₀^T r₀)/(p₀^T A p₀) = 5/15 = 1/3
• x₁ = [0,0] + (1/3)[1,2] = [1/3, 2/3]
• r₁ = [1,2] - (1/3)A[1,2] = [0, 1/3]

Итерация 2:

• β₀ = ||r₁||²/||r₀||² = (1/9)/5 = 1/45
• p₁ = r₁ + β₀p₀ = [1/45, 1/3 + 2/45] = [1/45, 17/45]
• Один шаг — и готово! x₂ = точное решение

Пример 2: Сравнение с градиентным спуском

Для плохо обусловленной матрицы A = [[100,0], [0,1]]:

🐌 Градиентный спуск: 50+ итераций
🚀 CG: 2 итерации точно!

Почему? CG адаптируется к “вытянутости” функции автоматически!

🎮 Практика

Базовый уровень 🟢

Задача 1: Для системы 2x₁ + x₂ = 3, x₁ + 2x₂ = 3, вычисли первое направление поиска p₀, если начинаем с x₀ = [0,0].

Задача 2: Почему для n×n системы CG найдёт точное решение максимум за n шагов?

Задача 3: В чём разница между “обычной” ортогональностью и A-ортогональностью векторов?

Задача 4: Оцени, сколько итераций потребуется CG для матрицы 1000×1000 с числом обусловленности κ(A) = 100.

Продвинутый уровень 🟡

Задача 5: Реализуй один шаг CG для произвольной системы Ax = b:

def cg_step(A, b, x_k, r_k, p_k):
    # твой код здесь
    alpha_k = ?
    x_new = ?
    r_new = ?  
    beta_k = ?
    p_new = ?
    return x_new, r_new, p_new

Задача 6: Докажи, что остатки r₀, r₁, r₂, … взаимно ортогональны: rᵢ^T rⱼ = 0 для i ≠ j.

Задача 7: Как изменится сходимость CG, если матрица A плохо обусловлена? Предложи способ ускорения.

Задача 8: Сравни количество операций на итерацию: CG vs градиентный спуск vs метод Ньютона.

Челлендж 🔴

Задача 9: Адаптируй CG для нелинейной оптимизации (метод Fletcher-Reeves). В чём основные отличия от линейного случая?

Задача 10: Почему CG может “сломаться” при наличии ошибок округления? Как это исправить перезапусками?

Задача 11: Докажи, что в методе CG выполняется: span{r₀, r₁, …, rₖ} = span{r₀, Ar₀, …, A^k r₀} (пространства Крылова).

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

❌ Ошибка: “CG всегда быстрее градиентного спуска” ✅ Правильно: CG лучше для квадратичных/близких к квадратичным функций 💡 Почему: Для сильно нелинейных функций CG может вести себя хуже

❌ Ошибка: Использовать CG для матриц с отрицательными собственными значениями
✅ Правильно: A должна быть положительно определённой 💡 Почему: Иначе αₖ может стать отрицательным или бесконечным

❌ Ошибка: Не учитывать ошибки округления при длинных итерациях ✅ Правильно: Перезапускать CG каждые n шагов 💡 Почему: Накапливается потеря ортогональности направлений

❌ Ошибка: Думать, что βₖ всегда положительное ✅ Правильно: βₖ ≥ 0 только теоретически, на практике может “плавать” 💡 Почему: Ошибки округления нарушают точные соотношения

🎓 Главное запомнить

✅ CG = градиентный спуск с памятью и умными направлениями ✅ Ключевая формула: pₖ₊₁ = rₖ₊₁ + βₖ pₖ (новое направление) ✅ Применяется: большие СЛАУ, квадратичная оптимизация, предобуславливание

🔗 Связь с другими темами

🔙 Опирается на: Градиентный спуск (урок 288), собственные значения матриц 🔜 Ведёт к: BFGS, L-BFGS, квази-ньютоновские методы 🔄 Связано с: SVD, QR-разложение, итерационные методы линейной алгебры