Итерационные методы

Граф нейронной сети может содержать миллионы узлов. Лапласиан - матрица 10⁶ × 10⁶. LU-разложение требует петабайты памяти. Метод сопряжённых градиентов решает ту же систему за минуты на одной GPU.

• **Graph Neural Networks:** разреженные системы с лапласианом решаются CG; scipy.sparse.linalg.cg используется в спектральной кластеризации
• **PyTorch sparse:** torch.sparse.mm для разреженных матриц; CG и GMRES интегрированы в физические солверы
• **FEM солверы:** предобусловленный CG (PCG) - стандарт для эллиптических PDE; AMG-предобусловитель даёт O(n) сложность

Предварительные знания

• Direct Methods: LU, Cholesky, QR

Якоби и Гаусс-Зейдель

Итерационные методы - альтернатива прямым для больших разреженных систем, где LU слишком дорог. Идея: представить A = M − N, где система Mx = Nxₙ + b легко решается. Метод Якоби обновляет все переменные параллельно, Гаусс-Зейдель немедленно использует новые значения.

**Метод Якоби:** xᵢ(ₙ₊₁) = (bᵢ − Σⱼ≠ᵢ aᵢⱼ xⱼ(ₙ)) / aᵢᵢ Матричная форма: xₙ₊₁ = D⁻¹(b − (L + U)xₙ), D = diag(A) **Гаусс-Зейдель** использует обновлённые значения немедленно - быстрее, но не параллелизуется. **Условие сходимости:** спектральный радиус ρ(B) < 1. Для диагонально доминантных матриц сходимость гарантирована.

Якоби и Гаусс-Зейдель медленно сходятся для плохо обусловленных матриц. Для реальных задач используют CG или GMRES.

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

Метод сопряжённых градиентов (CG) - оптимальный итерационный метод для SPD матриц. За n шагов он находит точное решение (в теории), но на практике сходится намного раньше. Каждый шаг ортогонален всем предыдущим направлениям поиска в метрике A.

**CG алгоритм (Hestenes-Stiefel, 1952):** Инициализация: r₀ = b − Ax₀, p₀ = r₀ Для k = 0, 1, 2, ...: αₖ = rₖᵀrₖ / (pₖᵀApₖ) xₖ₊₁ = xₖ + αₖpₖ rₖ₊₁ = rₖ − αₖApₖ βₖ = rₖ₊₁ᵀrₖ₊₁ / rₖᵀrₖ pₖ₊₁ = rₖ₊₁ + βₖpₖ **Сходимость:** ||eₖ||_A ≤ 2·((√κ−1)/(√κ+1))ᵏ·||e₀||_A, κ = κ(A).

CG сходится за O(√κ) итераций, каждая - умножение A на вектор O(nnz). Для разреженных n×n матриц с O(n) ненулей: O(n√κ) против O(n³/3) для LU. При κ ≈ 10⁴ и n = 10⁶ разница огромна.

GMRES и предобусловливание

GMRES (Generalized Minimal RESidual) - метод Крылова для несимметричных систем. Строит базис Арнольди в пространстве Крылова {b, Ab, A²b, ...} и ищет приближение x, минимизирующее ||Ax − b||. Применим к любым квадратным системам.

**Предобусловливание:** вместо Ax = b решаем M⁻¹Ax = M⁻¹b Цель: κ(M⁻¹A) << κ(A) Популярные предобусловители: - **Jacobi (D⁻¹):** просто, не всегда эффективно - **ILU (неполное LU):** хранит элементы только в шаблоне разреженности - **AMG (алгебраический мультисетка):** мощный для PDE, O(n) сложность - **ICC (неполный Cholesky):** для SPD матриц

Ключевые идеи

• **Якоби / Гаусс-Зейдель:** линейная сходимость при ρ(B) < 1; Гаусс-Зейдель ≈ 2× быстрее Якоби
• **CG:** O(√κ) итераций для SPD матриц; оптимален в классе Крылова; одно умножение A·v за итерацию
• **GMRES:** для несимметричных; строит базис Арнольди; используйте GMRES(m) с рестартом для экономии памяти
• **Предобусловливание:** цель κ(M⁻¹A) << κ(A); ILU, Jacobi, AMG - популярные выборы

Связанные темы

Итерационные методы работают через умножение матрицы на вектор:

• Разреженные матрицы — Итерационные методы работают через A·v - для разреженных матриц это O(nnz) на итерацию
• Прямые методы: LU, Cholesky, QR — Прямые методы лучше для малых n; при больших n итерационные методы быстрее и экономнее по памяти

Вопросы для размышления

• Почему CG находит точное решение за ровно n шагов теоретически, но сходится намного быстрее на практике?
• Как выбрать параметр restart в GMRES(m)? Какой компромисс между памятью и скоростью?
• Почему для GNN и kernel SVM итерационные методы часто предпочтительнее прямых?

Связанные уроки

• la-06-gauss