Матричное разложение

Матричное разложение (также факторизация матрицы) — это представление матрицы в виде произведения двух или более матриц, обладающих определёнными свойствами (например, треугольных, диагональных, ортогональных). Матричные разложения являются фундаментальным инструментом линейной алгебры и численных методов, используемым для решения систем линейных уравнений, вычисления собственных значений, сжатия данных, машинного обучения и многих других прикладных задач.

История

Истоки матричного разложения восходят к работам Карла Фридриха Гаусса (начало XIX века), который разработал метод исключения для решения линейных систем — по сути, это было неявное LU-разложение. В 1909 году Алан Маки (Alan Mackey) и независимо от него в 1920-х годах Эрнст Фишер (Ernst Fischer) и Рихард Курант (Richard Courant) заложили основы спектрального разложения симметричных матриц. Современная теория разложений, включая сингулярное разложение (SVD), была формализована в середине XX века в работах Джеймса Х. Уилкинсона, Джина Голуба и Уильяма Кахана. В СССР значительный вклад в развитие численных методов матричных разложений внесли академики А. Н. Тихонов, В. В. Воеводин и другие.

Основные виды матричных разложений

LU-разложение

LU-разложение (от англ. Lower-Upper) представляет матрицу \(A\) в виде произведения нижней треугольной матрицы \(L\) и верхней треугольной матрицы \(U\): \(A = LU\). Для невырожденных квадратных матриц это разложение существует, если не требуется перестановок строк. При необходимости перестановок используется разложение с перестановками \(PA = LU\), где \(P\) — матрица перестановок. LU-разложение лежит в основе метода Гаусса решения систем линейных уравнений и применяется для вычисления определителей и обратных матриц.

QR-разложение

QR-разложение (от англ. Orthogonal-Right triangular) представляет матрицу \(A\) в виде произведения ортогональной (или унитарной) матрицы \(Q\) и верхней треугольной матрицы \(R\): \(A = QR\). Для вещественных матриц \(Q\) ортогональна (\(Q^TQ = I\)), для комплексных — унитарна. QR-разложение строится с помощью методов Грама — Шмидта, отражений Хаусхолдера или вращений Гивенса. Оно используется для решения переопределённых систем методом наименьших квадратов, для вычисления собственных значений (QR-алгоритм) и в задачах обработки сигналов.

Сингулярное разложение (SVD)

Сингулярное разложение (SVD, от англ. Singular Value Decomposition) — это представление произвольной прямоугольной матрицы \(A\) размера \(m \times n\) в виде \(A = U\Sigma V^T\), где \(U\) — ортогональная матрица размера \(m \times m\), \(V\) — ортогональная матрица размера \(n \times n\), а \(\Sigma\) — диагональная матрица размера \(m \times n\) с неотрицательными элементами (сингулярными числами) на диагонали. SVD является одним из наиболее мощных и универсальных разложений, так как существует для любой матрицы. Оно применяется в сжатии изображений, латентно-семантическом анализе, рекомендательных системах, в машинном обучении (PCA — метод главных компонент) и в решении некорректных задач (регуляризация Тихонова).

Спектральное разложение (диагонализация)

Спектральное разложение (или диагонализация) применимо к квадратным матрицам, имеющим полный набор собственных векторов. Для симметричной (или эрмитовой) матрицы \(A\) существует представление \(A = Q\Lambda Q^T\), где \(Q\) — ортогональная матрица собственных векторов, а \(\Lambda\) — диагональная матрица собственных значений. Для несимметричных матриц, если они диагонализуемы, используется разложение \(A = P\Lambda P^{-1}\), где \(P\) — матрица собственных векторов. Спектральное разложение лежит в основе анализа устойчивости динамических систем, квантовой механики и теории графов.

Холецкого разложение

Разложение Холецкого — это частный случай LU-разложения для симметричных положительно определённых матриц. Оно представляет матрицу \(A\) в виде \(A = LL^T\) (или \(A = R^T R\)), где \(L\) — нижняя треугольная матрица с положительными диагональными элементами. Разложение Холецкого является одним из самых эффективных численных методов (в два раза быстрее LU-разложения) и широко используется в методе наименьших квадратов, в симуляции случайных процессов (метод Бокса — Мюллера) и в задачах оптимизации.

Другие разложения

• Разложение Шура (Schur decomposition): \(A = QTQ^T\), где \(Q\) — ортогональная, \(T\) — квазитреугольная (для вещественных матриц) или треугольная (для комплексных). Используется для вычисления собственных значений.
• Разложение Жордана (каноническая форма Жордана): \(A = PJP^{-1}\), где \(J\) — жорданова матрица. Применяется в теории дифференциальных уравнений и в функциональном анализе.
• Разложение неотрицательных матриц (NMF, от англ. Non-negative Matrix Factorization): \(A \approx WH\), где \(W\) и \(H\) — неотрицательные матрицы. Широко используется в машинном обучении для тематического моделирования и анализа изображений.

Применение

Решение систем линейных уравнений

Матричные разложения (LU, QR, Холецкого) лежат в основе прямых методов решения систем \(Ax = b\). LU-разложение позволяет решать системы с одной и той же матрицей \(A\) для разных правых частей \(b\) за \(O(n^2)\) операций после начальной \(O(n^3)\) факторизации. QR-разложение предпочтительно для переопределённых систем (метод наименьших квадратов).

Вычисление собственных значений и собственных векторов

QR-алгоритм, основанный на QR-разложении, является стандартным методом для нахождения всех собственных значений плотной матрицы. Для симметричных матриц часто используется разложение Ланцоша (итерационный метод, основанный на построении трёхдиагональной матрицы).

Сжатие данных и уменьшение размерности

Сингулярное разложение (SVD) используется для сжатия изображений: отбрасывание малых сингулярных чисел позволяет значительно уменьшить объём данных при незначительной потере качества. В машинном обучении SVD лежит в основе метода главных компонент (PCA) и латентно-семантического анализа (LSA) для обработки текстов.

Обработка сигналов и изображений

Разложение Холецкого применяется в адаптивной фильтрации (например, алгоритм RLS — рекурсивный метод наименьших квадратов). QR-разложение используется в алгоритмах MIMO-систем (множественный вход — множественный выход) в радиосвязи.

Машинное обучение и искусственный интеллект

В рекомендательных системах (например, Netflix Prize) используется разложение матрицы рейтингов на произведение двух матриц меньшего ранга (матричная факторизация). В нейронных сетях разложение весовых матриц применяется для сжатия моделей (например, с помощью SVD или QR-разложения). В тематическом моделировании (LDA) используется неотрицательное матричное разложение (NMF).

Численная устойчивость и вычислительная сложность

При выборе метода разложения важны численная устойчивость и вычислительная сложность. LU-разложение с частичным выбором главного элемента устойчиво для большинства матриц, но может давать большие ошибки для плохо обусловленных систем. QR-разложение с помощью отражений Хаусхолдера обладает лучшей численной устойчивостью, но требует примерно в два раза больше операций (\(O(2n^3)\) против \(O(2n^3/3)\) для LU). Разложение Холецкого для симметричных положительно определённых матриц является самым быстрым и устойчивым. SVD является наиболее дорогим (\(O(mn^2)\) для прямоугольных матриц), но даёт наиболее полную информацию о структуре матрицы.

Программная реализация

Матричные разложения реализованы во всех основных библиотеках линейной алгебры:

• LAPACK (Linear Algebra PACKage) — библиотека на Фортране, являющаяся стандартом для численных методов.
• BLAS (Basic Linear Algebra Subprograms) — низкоуровневые операции.
• NumPy (Python) — функции numpy.linalg.lu, numpy.linalg.qr, numpy.linalg.svd, numpy.linalg.cholesky.
• MATLAB — встроенные функции lu, qr, svd, chol.
• Eigen (C++) — библиотека шаблонов, поддерживающая все основные разложения.
• Intel MKL (Math Kernel Library) — оптимизированная библиотека для процессоров Intel.

Интересные факты

• Сингулярное разложение (SVD) было независимо открыто несколькими математиками: Эудженио Бельтрами (1873), Камиллом Жорданом (1874) и Джеймсом Сильвестром (1889). Однако широкое применение SVD получило только после работ Джина Голуба и Уильяма Кахана в 1960-х годах.
• Разложение Холецкого названо в честь французского офицера Андре-Луи Холецкого (1875–1918), который использовал его для решения геодезических задач. Метод был опубликован посмертно в 1924 году.
• В России и СССР значительный вклад в теорию и практику матричных разложений внёс В. В. Воеводин, автор монографии «Численные методы линейной алгебры» (1977).
• SVD используется в алгоритме PageRank компании Google (организация признана экстремистской и запрещена в РФ) для анализа связей между веб-страницами, хотя в основе лежит не SVD, а решение задачи на собственные значения.

Источники

1. Голуб Дж., Ван Лоун Ч. Матричные вычисления. — М.: Мир, 1999.
2. Воеводин В. В. Численные методы линейной алгебры. — М.: Наука, 1977.
3. Тыртышников Е. Е. Матричный анализ и линейная алгебра. — М.: Физматлит, 2007.
4. Strang G. Introduction to Linear Algebra. — 5th ed. — Wellesley-Cambridge Press, 2016.
5. Деммель Дж. Вычислительная линейная алгебра. — М.: Мир, 2001.