Русская Википедия:QR-разложение

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Значения термина <math>QR</math>-разложение матрицы — представление матрицы в виде произведения унитарной (или ортогональной матрицы) и верхнетреугольной матрицы. QR-разложение является основой одного из методов поиска собственных векторов и чисел матрицы — QR-алгоритмаШаблон:Sfn.

Определение

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

<math>A=QR,</math>

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

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

<math>A=LP,</math>

где матрица <math>L</math> порядка <math>n</math> — нижнетреугольная, а матрица <math>P</math> размера <math>n \times m</math> имеет ортонормированные строкиШаблон:Sfn.

Алгоритмы

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

Альтернативные алгоритмы для вычисления <math>QR</math>-разложения основаны на отражениях Хаусхолдера и вращениях ГивенсаШаблон:Sfn.

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

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

<math>\mathsf{\Alpha} = </math> <math>\begin{pmatrix} 1 & 2 & 4 \\ 3 & 3 & 2 \\ 4 & 1 & 3 \end{pmatrix}</math>

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

<math>a_1 = \begin{pmatrix} 1 \\ 3 \\ 4\end{pmatrix},</math> <math>a_2 = \begin{pmatrix} 2 \\ 3 \\ 1\end{pmatrix}, </math> <math>a_3 = \begin{pmatrix} 4 \\ 2 \\ 3\end{pmatrix} </math>

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

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

Из полученных векторов <math>e_1, e_2, e_3</math> составляем по столбцам матрицу Q из разложения:

<math>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>Q^{-1} = Q^T.</math>

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

<math>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>A = QR</math>.

Литература

• Шаблон:Книга