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

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

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

Определение

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

${\displaystyle A=QR,}$

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

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

${\displaystyle A=LP,}$

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

Алгоритмы

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

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

Пример 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}$.

Примечания

1. Horn, Johnson, 1990, p. 114.
2. Horn, Johnson, 1990, p. 112.
3. Horn, Johnson, 1990, p. 116.
4. Horn, Johnson, 1990, p. 117.

Литература

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