3.5. Обзор других разложений и задач#
В данном разделе приведены некоторые разложения матриц и их применение. Для углублённого изучения вычислительной линейной алгебры мы можем посоветовать следующие материалы.
Driscoll, Tobin A., and Richard Braun. 2018. Fundamentals of Numerical Computation. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-1-61197-507-9.
Trefethen, Lloyd N., and David Bau. 1997. Numerical Linear Algebra. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-361-9.
Golub, Gene H., and Charles F. Van Loan. 2013. Matrix Computations. Fourth edition. Johns Hopkins Studies in the Mathematical Sciences. Baltimore: The Johns Hopkins University Press. ISBN 978-1-4214-0859-0.
3.5.1. LU-разложение#
LU-разложение можно применять не только для решения линейных систем. Зная разложение, несложно вычислить детерминант матрицы.
A = [
2 0 4 3;
-4 5 -7 10;
1 15 2 -4;
-2 0 2 -13
]
L, U, p = plufact(A)
@show prod(diag(L)) * prod(diag(U)) p det(A);
prod(diag(L)) * prod(diag(U)) = -3510.0
p = [2, 3, 4, 1]
det(A) = 3510.0
Знак детерминанта определяется чётностью перестановки. В данном случае для «сортировки» вектора перестановок p требуется три операции, поэтому необходимо домножение на \((-1)^3\).
Вычисление детерминанта из определения через миноры стоит \(O(n!)\) флопс, тогда как вычисление через LU-разложение \(O(n^3)\) флопс.
Алгоритм также используется для проверки матрицы на обратимость.
3.5.2. QR-разложение#
QR-разложение можно получить из ортогонализации по Граму-Шмидту. Оно применяется для прямоугольной матрицы
где \(\mathbf{Q}\) – ортогональная матрица, а \(\mathbf{R}\) – верхнетреугольная (строки \(i > m\) нулевые). Это разложение «раскладывает» столбцы матрицы \(\mathbf{A}\) по ортогональному базису из столбцов матрицы \(\mathbf{Q}\).
QR-разложение применяется для решения переопределённых систем (число уравнений превышает число неизвестных), например, в методе наименьших квадратов. Кроме того, разложение позволяет найти ядро преобразования и пространство столбцов. А в случае квадратной матрицы \(\mathbf{A}_{n\times n}\) разложение применимо для решения линейной системы (\(\mathbf{R} \mathbf{x} = \mathbf{Q}^{\top} \mathbf{b}\)), как и LU-разложение.
В одном из вариантов метода Бройдена решения нелинейной системы уравнений эффективней (по времени работы) использовать QR-разложение вместо LU-разложения. Подобная ситуация встречается и в других алгоритмах: иногда одно разложение несёт больше необходимой алгоритму информации, что обычно экономит количество вычислений.
Вычислительная сложность \(\propto 2mn^2 - \frac{2}{3} n^3\).
3.5.3. Разложение Холецкого#
Разложение Холецкого (Cholesky decomposition) применимо для квадратной симметричной положительно-определённой матрицы \(\mathbf{x}^\top \mathbf{A} \mathbf{x} > 0\)
где \(\mathbf{L}\) – нижнетреугольная матрица.
Подобные матрицы возникают, например, при нахождении минимума функции \(f(\mathbf{x})\) (задача оптимизации), где ноль градиента и положительная определённость гессиана \(\mathbf{A}\) определяют локальный минимум.
Разложение используется для решения линейных систем, проверки матрицы на положительную определённость, нахождение детерминанта и обращении матриц.
Также часто используется модифицированное разложение Холецкого, которое находит близкую положительно-определённую матрицу к исходной, не обязательно положительно-определённой. Эта матрица может использоваться как приближение гессиана.
Вычислительная стоимость \(\propto \frac{1}{3} n^3\) флопс.
3.5.4. Спектральное разложение#
Спектральное разложение (eigenvalue или spectral decomposition) представляет квадратную матрицу \(\mathbf{A}\) в виде
где \(\mathbf{V}\) – матрица, составленная из собственных векторов матрицы \(\mathbf{A}\), а \(\mathbf{D}\) – диагональная матрица из собственных значений матрицы \(\mathbf{A}\).
Как следует из определения, разложение применяется для нахождения собственных значений и векторов матрицы. Такая задача может возникнуть, например, при решении системы обыкновенных дифференциальных уравнений.
3.5.5. Сингулярное разложение#
Сингулярное разложение (singular value decomposition, SVD) представляет матрицу в виде
где матрицы \(\mathbf{U}\) и \(\mathbf{V}\) ортогональны, а матрица \(\mathbf{\Sigma}\) диагональна (строки \(m > n\) нулевые). Диагональные элементы матрицы \(\mathbf{\Sigma}\) называют сингулярными значениями \(\sigma_i\), которые упорядочивают по неубыванию.
SVD-разложение имеет геометрическую интерпретацию. Она состоит в том, что всякое линейное преобразование может быть представлено в виде комбинации поворота и растяжений. Так, в двумерном случае единичная окружность с ортогональными полуосями \(\mathbf{v}_1\) и \(\mathbf{v}_2\) при преобразовании \(\mathbf{A}\) переходит в эллипс с полуосями \(\mathbf{A} \mathbf{v}_{1,2} = \sigma_{1,2} \mathbf{u}_{1,2}\).
SVD-разложение имеет фундаментальную важность для вычислительной линейной алгебры и имеет множество применений. Мы упомянем одно из них: приближение матрицы матрицей меньшего ранга (low-rank approximation). Матрицу \(\mathbf{A}\) можно записать в виде суммы внешних произведений
где \(r = \mathrm{rank}(\mathbf{A})\) это ранг матрицы \(\mathbf{A}\). Определим теперь матрицу \(\mathbf{A}_{\nu}\) как сумму первых \(\nu\) слагаемых из уравнения выше
Тогда
(Для корректности в случае \(\nu = r\): \(\sigma_{\nu + 1} = 0\).)
Таким образом, матрицу \(\mathbf{A}\) можно приближать другими матрицами, меньшего ранга. Например, в ситуации матрицы с сильным отличием сингулярных значений \(\sigma_{1 \dots 10} \gg \sigma_{11 \dots 100}\) достаточно использовать лишь одну десятую (\(\nu = 10\)) от всей размерности пространства. Это может использоваться в уменьшении количества вычислений (model order reduction) или, например, в алгоритмах сжатия данных (пример).
3.5.6. Разложения матриц в Julia#
Большинство упомянутых разложений входят в стандартный Julia пакет LinearAlgebra.
Разложение |
Ссылка |
|---|---|
LU |
|
QR |
|
Холецкого |
|
Холецкого (модифицированное) |
|
Спектральное |
|
Сингулярное |
|