Обзор других разложений и задач

Содержание

3.5. Обзор других разложений и задач#

В данном разделе приведены некоторые разложения матриц и их применение.

3.5.1. LU-разложение#

LU-разложение можно применять не только для решения линейных систем. Зная разложение, несложно вычислить детерминант матрицы.

\[\det{\mathbf{AB}} = \det{\mathbf{A}}\det{\mathbf{B}},\quad \det{\mathbf{L}} = \prod_{i} L_{ii}.\]

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{A}_{m\times n} = \mathbf{Q R},\]

где \(\mathbf{Q}\) – ортогональная матрица, а \(\mathbf{R}\) – верхнетреугольная.

Данное разложение применятся для переопределённых систем (число уравнений превышает число неизвестных), например, в методе наименьших квадратов. Кроме того, разложение позволяет найти ядро преобразования и пространство столбцов. А в случае квадратной матрицы \(\mathbf{A}_{n\times n}\) разложение применимо для решения линейной системы, как и LU-разложение.

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

Вычислительная сложность \(\propto 2mn^2 - \frac{2}{3} n^3\).

3.5.3. Разложение Холецкого#

Данное разложение применяется для квадратной симметричной положительно-определённой матрицы \(\mathbf{x}^\top \mathbf{A} \mathbf{x} > 0\)

\[\mathbf{A}_{n\times n} = \mathbf{L}\mathbf{L}^\top,\]

где \(\mathbf{L}\) – нижнетреугольная матрица.

Подобные матрицы возникают, например, в задаче оптимизации (нахождение минимума функции \(f(\mathbf{x})\)), где ноль градиента и положительная определённость гессиана определяют локальный минимум.

Разложение используется для решения линейных систем, проверки матрицы на положительную определённость, нахождение детерминанта и обращении матриц.

Также часто используется модифицированное разложение Холецкого, которое находит близкую положительно-определённую матрицу к исходной, не обязательно положительно-определённой. Эта матрица может использоваться как приближение гессиана.

Вычислительная стоимость \(\propto \frac{1}{3} n^3\) флопс.

3.5.4. Спектральное разложение#

Существует целое семейство разложений, где в качестве множителей присутствуют матрицы из собственных векторов и значений. Одно из них – спектральное.

Спектральное разложение представляет квадратную матрицу \(\mathbf{A}\) в виде

\[\mathbf{A}_{n\times n} = \mathbf{VDV}^{-1},\]

где \(\mathbf{V}\) – матрица, составленная из собственных векторов матрицы \(\mathbf{A}\), а \(\mathbf{D}\) – диагональная матрица из собственных значений \(\mathbf{A}\).

Как следует из определения, разложение применяется для нахождения собственных значений и векторов матрицы. Такая задача может возникнуть, например, при решении системы обыкновенных дифференциальных уравнений.

Обобщением является сингулярное разложения (SVD-разложение).