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

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

Определение

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

A = Q R , {displaystyle A=QR,}

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

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

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

Свойства

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

Алгоритмы

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

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

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

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

A = {displaystyle {mathsf {mathrm {A} }}=} ( 1 2 4 3 3 2 4 1 3 ) {displaystyle {egin{pmatrix}1&2&43&3&24&1&3end{pmatrix}}}

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

a 1 = ( 1 3 4 ) , {displaystyle a_{1}={egin{pmatrix}134end{pmatrix}},} a 2 = ( 2 3 1 ) , {displaystyle a_{2}={egin{pmatrix}231end{pmatrix}},} a 3 = ( 4 2 3 ) {displaystyle a_{3}={egin{pmatrix}423end{pmatrix}}}

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

e 1 = ( 26 26 3 26 26 4 26 26 ) , {displaystyle e_{1}={egin{pmatrix}{frac {sqrt {26}}{26}}{frac {3{sqrt {26}}}{26}}{frac {4{sqrt {26}}}{26}}end{pmatrix}},} e 2 = ( 37 3614 3614 33 3614 3614 − 34 3614 3614 ) , {displaystyle e_{2}={egin{pmatrix}{frac {37{sqrt {3614}}}{3614}}{frac {33{sqrt {3614}}}{3614}}-{frac {34{sqrt {3614}}}{3614}}end{pmatrix}},} e 3 = ( 9 139 139 − 7 139 139 3 139 139 ) {displaystyle e_{3}={egin{pmatrix}{frac {9{sqrt {139}}}{139}}-{frac {7{sqrt {139}}}{139}}{frac {3{sqrt {139}}}{139}}end{pmatrix}}}

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

Q = ( 26 26 37 3614 3614 9 139 139 3 26 26 33 3614 3614 − 7 139 139 4 26 26 − 34 3614 3614 3 139 139 ) . {displaystyle Q={egin{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}}.} Полученная матрица является ортогональной, это означает, что Q − 1 = Q T . {displaystyle Q^{-1}=Q^{T}.}

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

R = ( 26 3 2 13 + 9 26 11 2 13 0 20 2 1807 + 99 3614 56 2 1807 0 0 31 139 ) {displaystyle R={egin{pmatrix}{sqrt {26}}&3{sqrt {frac {2}{13}}}+{frac {9}{sqrt {26}}}&11{sqrt {frac {2}{13}}}&20{sqrt {frac {2}{1807}}}+{frac {99}{sqrt {3614}}}&56{sqrt {frac {2}{1807}}}&0&{frac {31}{sqrt {139}}}end{pmatrix}}} – искомая верхнетреугольная матрица.

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