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

Для термина «QR» см. также другие значения.

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

Определение

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

$A=QR,$

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

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

$A=LP,$

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

Алгоритмы

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

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

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

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

${\mathsf {\mathrm {A} }}=$ ${\begin{pmatrix}1&2&4\\3&3&2\\4&1&3\end{pmatrix}}$

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

$a_{1}={\begin{pmatrix}1\\3\\4\end{pmatrix}},$ $a_{2}={\begin{pmatrix}2\\3\\1\end{pmatrix}},$ $a_{3}={\begin{pmatrix}4\\2\\3\end{pmatrix}}$

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

$e_{1}={\begin{pmatrix}{\frac {\sqrt {26}}{26}}\\{\frac {3{\sqrt {26}}}{26}}\\{\frac {4{\sqrt {26}}}{26}}\end{pmatrix}},$ $e_{2}={\begin{pmatrix}{\frac {37{\sqrt {3614}}}{3614}}\\{\frac {33{\sqrt {3614}}}{3614}}\\-{\frac {34{\sqrt {3614}}}{3614}}\end{pmatrix}},$ $e_{3}={\begin{pmatrix}{\frac {9{\sqrt {139}}}{139}}\\-{\frac {7{\sqrt {139}}}{139}}\\{\frac {3{\sqrt {139}}}{139}}\end{pmatrix}}$

Из полученных векторов $e_{1},e_{2},e_{3}$ составляем по столбцам матрицу Q из разложения:

$Q={\begin{pmatrix}{\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{pmatrix}}.$ Полученная матрица является ортогональной, это означает, что $Q^{-1}=Q^{T}.$

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

$R={\begin{pmatrix}{\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{pmatrix}}$ — искомая верхнетреугольная матрица.

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

Литература

• Horn, R. A., Johnson C. R.. Matrix analysis (англ.). — Cambridge University Press, 1990. — ISBN 0-521-30586-1.