Линейная алгебра
Разложение Холецкого и форма Шура
Разложение Холецкого - это «квадратный корень» для матриц: оно ускоряет линейные системы в 2 раза и лежит в основе каждого сэмплирования из многомерного нормального. Форма Шура даёт то, чего нет у диагонализации - стабильный числовой алгоритм для любой матрицы.
- **Байесовские нейросети и GP:** Stan, TensorFlow Probability и JAX используют разложение Холецкого внутри каждой итерации MCMC при работе с ковариационными матрицами размером до 10^5
- **AlphaFold 3:** в 2023 году DeepMind применил Холецкий для ковариационных матриц 10^5×10^5 при предсказании структур белков - главный узкий момент по памяти и времени
- **MATLAB и Julia:** функция `eig` вычисляет собственные значения через форму Шура (LAPACK `dgees`), а не через прямую диагонализацию - именно из-за числовой устойчивости
- **Control systems:** анализ устойчивости линейной системы x' = Ax в MATLAB Control Toolbox строится на форме Шура: собственные значения на диагонали T, матрица Q ортогональна
Предварительные знания
- LU-разложение: прямая и обратная подстановка, пивотирование
- QR-разложение: ортогональные матрицы и QR-итерации
- Собственные значения и диагонализация симметричных матриц
- Положительная определённость: критерий Сильвестра и квадратичные формы
Разложение Холецкого
Stan (статистический компилятор Гарварда) и TensorFlow Probability используют разложение Холецкого для всех сэмплирований из многомерного нормального распределения. Задача оптимизации Newton-CG в scipy - тоже на Холецком. В 2023 году AlphaFold 3 от DeepMind использовал Холецкий для коварационных матриц размером 10⁵ × 10⁵.
Для какого класса матриц гарантированно существует разложение Холецкого?
Холецкий требует A = Aᵀ ≻ 0. Существование проверяется попыткой разложения: если встречается неположительный диагональный элемент - матрица не PD.
Форма Шура и нормальные матрицы
Форма Шура - фундамент современных алгоритмов собственных значений. LAPACK dgees (используется в MATLAB и Julia) вычисляет форму Шура для нахождения собственных значений общих матриц. Устойчивость алгоритма к численным ошибкам - следствие того, что преобразование Q ортогонально.
Какое условие необходимо и достаточно для того, чтобы форма Шура матрицы A была диагональной?
T диагональна ⟺ A нормальна: A*A = AA*. Класс нормальных матриц включает унитарные, симметричные, косо-симметричные матрицы.
Место разложений в линейной алгебре
Холецкий и Шур - два специализированных разложения, дополняющих LU и QR. Каждое оптимально для своей задачи: Холецкий для симметричных PD-матриц, Шур для вычисления собственных значений любых матриц.
- SVD — SVD обобщает форму Шура на прямоугольные матрицы; сингулярные числа - корни собственных значений A^T A
- Жорданова форма — Форма Шура - числовая замена жордановой: она непрерывна при возмущениях, жорданова - нет
- Случайные матрицы — Холецкий используется для сэмплирования из многомерного нормального, лежащего в основе теории GOE/GUE
- Оптимизация — Newton-CG использует Холецкий для решения систем с гессианом на каждой итерации
Итоги
- **Холецкий A = LL^T:** существует и единственен для симметричных положительно определённых матриц; вдвое дешевле LU за счёт симметрии
- **Сэмплирование:** x = μ + Lz при z ~ N(0,I) даёт выборку из N(μ, A) без явного вычисления A^{-1}
- **Форма Шура A = QTQ*:** существует для любой квадратной матрицы; Q унитарна, T верхнетреугольна с собственными значениями на диагонали
- **Нормальные матрицы:** A*A = AA* тогда и только тогда, когда T диагональна; симметричные, унитарные, косо-симметричные - все нормальны
- **Алгоритм:** приведение к форме Хессенберга, затем QR-итерации - O(n^3) с константой ~25n^3 в LAPACK