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

Шаблон:Значения термина $QR$-разложение матрицы — представление матрицы в виде произведения унитарной (или ортогональной матрицы) и верхнетреугольной матрицы. QR-разложение является основой одного из методов поиска собственных векторов и чисел матрицы — QR-алгоритмаШаблон:Sfn.

Определение

Матрица $A$ размера $n\times m$, где $n⩾m$, с комплексными элементами может быть представлена в виде

$A=QR,$

где $Q$ — матрица размера $n\times m$ с ортонормированными столбцами, а $R$ — верхнетреугольная матрица размера $m\times m$. При $n=m$ матрица $Q$ унитарная. Если при этом $A$ невырождена, то $QR$-разложение единственно и матрица $R$ может быть выбрана так, чтобы её диагональные элементы были положительными вещественными числами. В частном случае, когда матрица $A$ состоит из вещественных чисел, матрицы $Q$ и $R$ также могут быть выбраны вещественными, причём $Q$ является ортогональнойШаблон:Sfn.

По аналогии, если $A$ — матрица размера $n\times m$, где $n⩽m$, то она может быть разложена как

$A=LP,$

где матрица $L$ порядка $n$ — нижнетреугольная, а матрица $P$ размера $n\times m$ имеет ортонормированные строкиШаблон:Sfn.

Алгоритмы

$QR$-разложение может быть получено различными методами. Проще всего оно может быть вычислено, как побочный продукт в процессе Грама — ШмидтаШаблон:Sfn. На практике следует использовать модифицированный алгоритм Грама ― Шмидта, поскольку классический алгоритм обладает плохой численной устойчивостьюШаблон:Sfn.

Альтернативные алгоритмы для вычисления $QR$-разложения основаны на отражениях Хаусхолдера и вращениях ГивенсаШаблон:Sfn.

Пример QR-разложения

Рассмотрим матрицу:

$\mathrm{A}=$ $\left(\begin{array}{ccc}1& 2& 4\\ 3& 3& 2\\ 4& 1& 3\end{array}\right)$

Через $a_1,a_2,a_3$ обозначим векторы-столбцы заданной матрицы $\mathrm{A}.$ Получаем следующий набор векторов:

$a_1=\left(\begin{array}{c}1\\ 3\\ 4\end{array}\right),$ $a_2=\left(\begin{array}{c}2\\ 3\\ 1\end{array}\right),$ $a_3=\left(\begin{array}{c}4\\ 2\\ 3\end{array}\right)$

Далее, применяем алгоритм ортогонализации Грама — Шмидта и нормируем полученные вектора, получаем следующий набор:

$e_1=\left(\begin{array}{c}\frac{\sqrt{26}}{26}\\ \frac{3\sqrt{26}}{26}\\ \frac{4\sqrt{26}}{26}\end{array}\right),$ $e_2=\left(\begin{array}{c}\frac{37\sqrt{3614}}{3614}\\ \frac{33\sqrt{3614}}{3614}\\ -\frac{34\sqrt{3614}}{3614}\end{array}\right),$ $e_3=\left(\begin{array}{c}\frac{9\sqrt{139}}{139}\\ -\frac{7\sqrt{139}}{139}\\ \frac{3\sqrt{139}}{139}\end{array}\right)$

Из полученных векторов $e_1,e_2,e_3$ составляем по столбцам матрицу Q из разложения:

$Q=\left(\begin{array}{ccc}\frac{\sqrt{26}}{26}& \frac{37\sqrt{3614}}{3614}& \frac{9\sqrt{139}}{139}\\ \frac{3\sqrt{26}}{26}& \frac{33\sqrt{3614}}{3614}& -\frac{7\sqrt{139}}{139}\\ \frac{4\sqrt{26}}{26}& -\frac{34\sqrt{3614}}{3614}& \frac{3\sqrt{139}}{139}\end{array}\right).$ Полученная матрица является ортогональной, это означает, что $Q^{-1}=Q^T.$

Найдем матрицу $R$ из выражения $R=Q^{-1}A=Q^{T}A$:

$R=\left(\begin{array}{ccc}\sqrt{26}& 3\sqrt{\frac{2}{13}}+\frac{9}{\sqrt{26}}& 11\sqrt{\frac{2}{13}}\\ 0& 20\sqrt{\frac{2}{1807}}+\frac{99}{\sqrt{3614}}& 56\sqrt{\frac{2}{1807}}\\ 0& 0& \frac{31}{\sqrt{139}}\end{array}\right)$ — искомая верхнетреугольная матрица.

Получили разложение $A=QR$.

Литература

• Шаблон:Книга