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

Матрица ${\displaystyle A}$ размера ${\displaystyle n\times n}$ с комплексными элементами может быть представлена в виде:

${\displaystyle A=QR,}$

где ${\displaystyle Q}$ — унитарная матрица размера ${\displaystyle n\times n}$, а ${\displaystyle R}$ — верхнетреугольная матрица размера ${\displaystyle n\times n}$.

В частном случае, когда матрица ${\displaystyle A}$ состоит из вещественных чисел, ${\displaystyle Q}$ является ортогональной матрицей (то есть ${\displaystyle Q^{T}Q=I}$, где ${\displaystyle I}$ — единичная матрица).

По аналогии, можно определить варианты этого разложения: ${\displaystyle QL}$-, ${\displaystyle RQ}$-, и ${\displaystyle LQ}$-разложения, где ${\displaystyle L}$ — нижнетреугольная матрица.

Если ${\displaystyle A}$ — квадратная невырожденная матрица, то существует единственное ${\displaystyle QR}$-разложение, если наложить дополнительное условие, что элементы на диагонали матрицы ${\displaystyle R}$ должны быть положительными вещественными числами.

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

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

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

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

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

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

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

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

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

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

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

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

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