Численные методы
Прямые методы: LU, Cholesky, QR
numpy.linalg.solve, sklearn.LinearRegression, scipy.optimize - все они под капотом используют LU, Cholesky или QR разложения. Выбор разложения определяет точность, скорость и применимость к конкретной матрице.
- **numpy.linalg.solve:** использует LAPACK's dgesv - LU с частичным выбором; O(n³/3) для плотных матриц
- **Линейная регрессия в sklearn:** решается через QR (LAPACK's dgels) - более стабильно, чем нормальные уравнения
- **Kernel-методы в ML (SVM, Gaussian Processes):** матрица ядра K SPD → разложение Холецкого для решения Kα = y
Предварительные знания
LU-разложение
LU-разложение факторизует матрицу A в произведение нижнетреугольной L и верхнетреугольной U матриц: PA = LU, где P - матрица перестановок (частичный выбор главного элемента). Главная мотивация: решить систему Ax = b один раз, а потом быстро решать для разных b, переиспользуя разложение.
**PA = LU (частичный выбор главного элемента):** 1. Разложение: O(n³/3) - однократно 2. Подстановка Ly = Pb: O(n²) 3. Подстановка Ux = y: O(n²) 4. Решение для нового b: O(n²) - без повторного O(n³)! **Частичный выбор:** перестановка P ставит на главную диагональ наибольший элемент в столбце → стабильность, |lᵢⱼ| ≤ 1. Numpy: `scipy.linalg.lu(A)` или `np.linalg.solve(A, b)` (LU под капотом).
LU подходит для **плотных матриц** произвольного вида. Для разреженных матриц LU порождает заполнение (fill-in) - нулевые элементы становятся ненулевыми. Используйте `scipy.sparse.linalg.spsolve` с переупорядочиванием (AMD, nested dissection) для разреженных систем.
Для чего нужна матрица перестановок P в разложении PA = LU?
Разложение Холецкого
Для **симметричной положительно определённой** (SPD) матрицы A = Aᵀ с положительными собственными значениями существует специальное разложение Холецкого: A = LLᵀ, где L - нижнетреугольная матрица с положительными диагональными элементами. Оно вдвое быстрее LU и требует вдвое меньше памяти.
**Разложение Холецкого A = LLᵀ:** - Применимо ТОЛЬКО для SPD матриц (A = Aᵀ, все eigenvalues > 0) - Сложность: O(n³/6) - вдвое быстрее LU (O(n³/3)) - Память: n(n+1)/2 элементов (только нижний треугольник) - Без перестановок: Холецкий всегда устойчив для SPD матриц - Проверка SPD: если Холецкий не завершился - матрица НЕ SPD `numpy.linalg.cholesky(A)` или `scipy.linalg.cholesky(A)`.
| Свойство | LU | Холецкий |
|---|---|---|
| Применимость | Любая невырожденная | Только SPD |
| Сложность | O(n³/3) | O(n³/6) |
| Память | n² элементов | n(n+1)/2 |
| Перестановки | Нужны для стабильности | Не нужны |
| Применение в ML | Общие системы | Normal equations, kernel methods |
Матрица X ∈ ℝ¹⁰⁰ˣ²⁰ содержит признаки. Является ли матрица Грама G = XᵀX SPD?
QR-разложение
QR-разложение представляет матрицу A как произведение ортогональной матрицы Q (QᵀQ = I) и верхнетреугольной R: A = QR. Два основных алгоритма: **Грам-Шмидт** (концептуально прост, численно нестабилен) и **отражения Хаусхолдера** (стабильный, стандартный). QR - ключ к задаче наименьших квадратов.
**Задача наименьших квадратов через QR:** Минимизировать ||Ax − b||² для A ∈ ℝᵐˣⁿ, m > n: 1. A = QR (тонкое QR: Q ∈ ℝᵐˣⁿ, R ∈ ℝⁿˣⁿ) 2. x* = R⁻¹ Qᵀ b (или решаем Rx = Qᵀb) **Преимущество перед нормальными уравнениями** AᵀAx = Aᵀb: - Число обусловленности: κ(AᵀA) = κ(A)² - QR более стабильно! - QR: O(mn²), нормальные уравнения: O(mn² + n³) - сопоставимо
QR-разложение также является основой **алгоритма Фрэнсиса** для вычисления собственных значений (тема nm-09). Идея: повторное QR-разложение матрицы A → A сходится к треугольной (Шур) форме, на диагонали которой стоят собственные значения.
Почему для линейной регрессии QR-разложение предпочтительнее нормальных уравнений AᵀAx = Aᵀb?
Ключевые идеи
- **LU (PA = LU):** любая невырожденная матрица; O(n³/3); частичный выбор для стабильности; повторное использование для нескольких b
- **Cholesky (A = LLᵀ):** только SPD; вдвое быстрее LU; no pivoting; провал = матрица не SPD
- **QR (A = QR):** задача наименьших квадратов; стабильнее нормальных уравнений (κ(AᵀA) = κ(A)²); Хаусхолдер > Грам-Шмидт
- **Выбор:** LU для общих, Cholesky для SPD (ML kernels), QR для overdetermined least squares
Связанные темы
Прямые методы - фундамент для итерационных и спектральных задач:
- Итерационные методы — Итерационные методы (CG, GMRES) применяются когда прямые O(n³) слишком дороги для больших разреженных матриц
- Численное вычисление собственных значений — QR-алгоритм для собственных значений повторно применяет QR-разложение
Вопросы для размышления
- Зачем хранить разложение LU, а не обратную матрицу A⁻¹, если нужно часто решать Ax = b для разных b?
- Как проверить, является ли матрица XᵀX + λI (ridge regression) SPD при любом λ > 0?
- Почему в GLM (обобщённые линейные модели) чаще используют QR, а не Cholesky?