QR-разложение
[math]\displaystyle{ QR }[/math]-разложение матрицы — представление матрицы в виде произведения унитарной (или ортогональной матрицы) и верхнетреугольной матрицы. QR-разложение является основой одного из методов поиска собственных векторов и чисел матрицы — QR-алгоритма[1].
Определение
Матрица [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] является ортогональной[2].
По аналогии, если [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] имеет ортонормированные строки[1].
Алгоритмы
[math]\displaystyle{ QR }[/math]-разложение может быть получено различными методами. Проще всего оно может быть вычислено, как побочный продукт в процессе Грама — Шмидта[2]. На практике следует использовать модифицированный алгоритм Грама ― Шмидта, поскольку классический алгоритм обладает плохой численной устойчивостью[3].
Альтернативные алгоритмы для вычисления [math]\displaystyle{ QR }[/math]-разложения основаны на отражениях Хаусхолдера и вращениях Гивенса[4].
Пример 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].
Примечания
- ↑ 1,0 1,1 Horn, Johnson, 1990, p. 114.
- ↑ 2,0 2,1 Horn, Johnson, 1990, p. 112.
- ↑ Horn, Johnson, 1990, p. 116.
- ↑ Horn, Johnson, 1990, p. 117.
Литература
- Horn, R. A., Johnson C. R. Matrix analysis (англ.). — Cambridge University Press, 1990. — ISBN 0-521-30586-1.