Линейная алгебра
Итерационные методы: сопряжённые градиенты и Крылов
Матрица 10 миллионов уравнений не влезает в RAM для прямого LU. Итерационные методы решают такие системы, используя только умножение матрицы на вектор. CG (Conjugate Gradient) лежит в основе физических симуляций, FEM-солверов и оптимизаторов в ML.
- Физические симуляции: FEM-система 10M уравнений решается CG за 100 итераций
- Google PageRank: степенная итерация - простейший итерационный метод для eigenvector
- Pytorch L-BFGS: квази-ньютон метод использует матрично-векторные произведения с Гессе
- Компьютерная графика: предобусловленный CG для деформируемых объектов в реальном времени
- Спектральная кластеризация: ARPACK решает задачу на собственные значения итеративно
Итерационные методы в ML и науке: **CG** - решение нормальных уравнений в линейной регрессии на больших данных, оптимизация в PDE-constraint задачах; **GMRES** - CFD (вычислительная гидродинамика), электромагнитное моделирование; **PageRank** - итерация по методу степенного разложения (Power Method) - частный случай метода Крылова; **Krylov в нейросетях** - K-FAC (Kronecker-Factored Approximate Curvature) использует CG для умножения на обратный Хессе.
Якоби и Гаусс-Зейдель
**Метод сопряжённых градиентов решает системы Ax=b с n=10⁶ уравнениями за √κ(A) итераций - Google PageRank (n=3·10¹⁰) использует именно итерационные методы.** Прямые методы (LU, QR) требуют O(n³) операций и хранения плотной матрицы - для систем миллионного порядка это невозможно. Итерационные методы работают только с умножением матрицы на вектор: для разреженных матриц это O(nnz) операций вместо O(n²).
Метод простых итераций и сходимость
Перед CG исторически существовали простые стационарные методы: Якоби, Гаусс-Зейдель, SOR. Они сходятся медленнее (линейно с коэффициентом ρ(M)), но просты в реализации и полезны как предобусловлители.
Чем метод Гаусса-Зейделя отличается от метода Якоби?
Якоби обновляет все x_i из старого вектора x^(k). Гаусс-Зейдель использует свежие x_1,...,x_{i-1} из текущей итерации при обновлении x_i. Это даёт примерно вдвое более быструю сходимость и не требует хранения старого вектора.
GMRES и пространства Крылова
Пространства Крылова и GMRES
CG работает только для SPD-матриц. Для несимметричных систем используют GMRES (Generalized Minimal RESidual) - метод минимальной невязки в пространстве Крылова. GMRES на каждой итерации ортогонализирует новый вектор A^k b относительно уже построенного базиса (процесс Арнольди) и находит наилучшее приближение.
Какое подпространство порождается за k итераций метода Крылова?
Подпространство Крылова K_k(A, b) = span(b, Ab, ..., A^(k-1) b). GMRES ищет приближённое решение x_k в этом подпространстве, минимизируя норму остатка ‖b - Ax_k‖. Сходится за k << n итераций на хорошо обусловленных задачах.
Метод сопряжённых градиентов
Метод сопряжённых градиентов (CG)
Для симметричной положительно определённой матрицы A решение Ax=b эквивалентно минимизации квадратичной функции f(x). Метод сопряжённых градиентов - это метод оптимизации, который выбирает направления поиска так, чтобы они были A-ортогональны (сопряжены): dᵢᵀAdⱼ = 0 при i≠j. Это гарантирует сходимость за не более чем n шагов в точной арифметике.
Предобусловливание
Предобусловливание - ключевая техника для ускорения итерационных методов. Вместо Ax=b решают M⁻¹Ax=M⁻¹b, где M≈A но M⁻¹ вычисляется дёшево. Идеальный предобусловлитель: M=A, тогда κ=1 и сходимость за 1 шаг. Практичный предобусловлитель: неполное разложение Холецкого (IC) или неполное LU (ILU).
Скорость сходимости и спектр
Скорость сходимости CG определяется спектром матрицы A. Если собственные значения кластеризованы (мало различных значений), сходимость быстрее теоретического предела √κ. Это объясняет почему CG для задач из физики (собственные значения группируются) сходится намного быстрее, чем для искусственных матриц с равномерным спектром.
Итерационные методы в ML и науке: **CG** - решение нормальных уравнений в линейной регрессии на больших данных, оптимизация в PDE-constraint задачах; **GMRES** - CFD (вычислительная гидродинамика), электромагнитное моделирование; **PageRank** - итерация по методу степенного разложения (Power Method) - частный случай метода Крылова; **Krylov в нейросетях** - K-FAC (Kronecker-Factored Approximate Curvature) использует CG для умножения на обратный Хессе.
Для какого класса матриц CG гарантированно сходится за n шагов в точной арифметике?
CG минимизирует квадратичную форму (1/2) xᵀAx - bᵀx, корректную только для SPD-матриц A. В точной арифметике сходится за не более чем n шагов; на практике за ~sqrt(cond(A)) при наличии предобуславливателя.