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

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

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

Определение

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

[math]\displaystyle{ A=QR, }[/math]

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

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

[math]\displaystyle{ A=LP, }[/math]

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

Алгоритмы

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

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

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

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

[math]\displaystyle{ \mathsf{\Alpha} = }[/math] [math]\displaystyle{ \begin{pmatrix} 1 & 2 & 4 \\ 3 & 3 & 2 \\ 4 & 1 & 3 \end{pmatrix} }[/math]

Через [math]\displaystyle{ a_1, a_2, a_3 }[/math] обозначим векторы-столбцы заданной матрицы [math]\displaystyle{ \mathsf{\Alpha}. }[/math] Получаем следующий набор векторов:

[math]\displaystyle{ a_1 = \begin{pmatrix} 1 \\ 3 \\ 4\end{pmatrix}, }[/math] [math]\displaystyle{ a_2 = \begin{pmatrix} 2 \\ 3 \\ 1\end{pmatrix}, }[/math] [math]\displaystyle{ a_3 = \begin{pmatrix} 4 \\ 2 \\ 3\end{pmatrix} }[/math]

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

[math]\displaystyle{ e_1 = \begin{pmatrix}\frac{\sqrt{26}}{26} \\ \frac{3\sqrt{26}}{26} \\ \frac{4\sqrt{26}}{26}\end{pmatrix}, }[/math] [math]\displaystyle{ e_2 = \begin{pmatrix}\frac{37\sqrt{3614}}{3614} \\ \frac{33\sqrt{3614}}{3614} \\ -\frac{34\sqrt{3614}}{3614}\end{pmatrix}, }[/math] [math]\displaystyle{ e_3 = \begin{pmatrix}\frac{9\sqrt{139}}{139} \\ -\frac{7\sqrt{139}}{139} \\ \frac{3\sqrt{139}}{139}\end{pmatrix} }[/math]

Из полученных векторов [math]\displaystyle{ e_1, e_2, e_3 }[/math] составляем по столбцам матрицу Q из разложения:

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

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

[math]\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} }[/math] — искомая верхнетреугольная матрица.

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

Литература

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