Линейная алгебра
Матричные разложения: QR, LU, Холецкого
numpy, scipy, LAPACK не хранят обратные матрицы - они хранят разложения. LU для решения систем, QR для задач наименьших квадратов, Холецкого для ковариационных матриц. Выбор разложения под задачу - это разница между кодом, который работает, и кодом, который не потеряет точность.
- scipy.linalg.solve: внутри LU-разложение с частичным выбором ведущего элемента
- Линейная регрессия: QR-разложение вместо (XᵀX)⁻¹ - численно устойчивее в 2 раза по κ
- Фильтр Калмана: разложение Холецкого матрицы ковариации - гарантирует SPD
- Байесовская оптимизация: Холецкий для гауссовских процессов в sklearn/GPyTorch
- Рандомизированный SVD: sketching + QR + EVD - обработка матриц не влезающих в RAM
Сравнение разложений
Выбор разложения определяется структурой матрицы и задачей. Общая матрица → LU. Прямоугольная (МНК) → QR. SPD → Холецкого (в 2× быстрее LU). Разреженная → специализированные разложения (CHOLMOD, SuperLU). Низкоранговое приближение → SVD или randomized SVD.
Вычислительные аспекты
На практике важны не только математические свойства, но и вычислительная эффективность. BLAS (Basic Linear Algebra Subprograms) - это стандартный интерфейс для операций над матрицами: GEMM (матричное умножение) достигает 90%+ теоретического пика на GPU. LAPACK строится поверх BLAS и реализует все стандартные разложения.
Когда матрица разрежена (большинство элементов - нули), плотные разложения расточительны. Используют разреженные варианты: CHOLMOD для SPD, UMFPACK (SuperLU) для общих матриц. scipy.sparse.linalg предоставляет интерфейс к этим библиотекам.
QR-разложение
**LAPACK (используется в NumPy, MATLAB, Julia) реализует QR-разложение за O(mn²) операций - для матрицы 10 000×1 000 это 10¹⁰ операций, выполняемых за секунды на GPU.** Матричные разложения - это не просто математические трюки: они определяют вычислительную сложность и числовую устойчивость алгоритмов. QR решает задачи наименьших квадратов, LU решает линейные системы, Холецкого ускоряет работу с симметричными положительно определёнными матрицами в задачах оптимизации и фильтрации Калмана.
QR-разложение
QR-разложение представляет матрицу A размера m×n как произведение ортогональной матрицы Q (m×m) и верхнетреугольной матрицы R (m×n). Столбцы Q образуют ортонормированный базис. Это разложение лежит в основе алгоритма QR для вычисления собственных значений и метода наименьших квадратов.
Почему QR-разложение предпочтительнее нормальных уравнений в МНК?
Нормальные уравнения AᵀAx = Aᵀb используют матрицу с числом обусловленности cond(AᵀA) = cond(A)². QR работает напрямую с A, сохраняя cond(A). Для плохо обусловленных задач это разница между точным решением и численным шумом.
LU-разложение
LU-разложение
LU-разложение представляет матрицу как произведение нижнетреугольной (L) и верхнетреугольной (U) матриц. С частичным выбором ведущего элемента: PA = LU, где P - матрица перестановок. Это самый эффективный метод для однократного решения системы при многократных правых частях: O(n³) на разложение, O(n²) на каждую новую правую часть.
Зачем нужна перестановочная матрица P в разложении PA = LU?
P переставляет строки так, чтобы на диагонали оказывался наибольший по модулю элемент столбца. Без этого деление на малый элемент приводит к катастрофической потере точности. np.linalg.lu_factor возвращает именно PLU.
Разложение Холецкого
Разложение Холецкого
Для симметричных положительно определённых матриц (SPD) существует разложение Холецкого: A = LLᵀ. Оно вдвое быстрее LU (работает только с нижним треугольником) и численно устойчивее. SPD-матрицы повсюду: ковариационные матрицы в статистике, матрица Хессе в выпуклой оптимизации, системы уравнений в фильтре Калмана, ядровые матрицы в гауссовских процессах.
Применения: **QR** - МНК, QR-итерации для собственных значений, ортогонализация признаков; **LU** - прямое решение систем, вычисление детерминанта (det = ∏uᵢᵢ), обращение матриц; **Холецкого** - фильтр Калмана (обновление ковариации), гауссовские процессы (GP regression), выборка из многомерного нормального распределения, решение задач выпуклой оптимизации второго порядка.
Почему разложение Холецкого работает только для симметричных положительно определённых матриц?
Формула l_jj = sqrt(a_jj - sum(l_jk² for k<j)) требует положительного аргумента корня. Это эквивалентно положительной определённости. На несимметричной или знаконеопределённой матрице алгоритм даст комплексные числа или NaN.