QR-розклад матриці

Розглянемо процес Грама — Шмідта застосований до стовпчиків матриці ${\displaystyle A=[\mathbf {a} _{1},\cdots ,\mathbf {a} _{n}]}$ з повним стовпчиковим рангом, де ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\top }\mathbf {w} }$ (або ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{*}\mathbf {w} }$ у комплексному випадку).

Визначимо проекцію вектора як:

${\displaystyle \mathrm {proj} _{\mathbf {e} }\mathbf {a} ={\frac {\left\langle \mathbf {e} ,\mathbf {a} \right\rangle }{\left\langle \mathbf {e} ,\mathbf {e} \right\rangle }}\mathbf {e} }$

тоді:

${\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {a} _{1},&\mathbf {e} _{1}&={\mathbf {u} _{1} \over \|\mathbf {u} _{1}\|}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}\,\mathbf {a} _{2},&\mathbf {e} _{2}&={\mathbf {u} _{2} \over \|\mathbf {u} _{2}\|}\\\mathbf {u} _{3}&=\mathbf {a} _{3}-\mathrm {proj} _{\mathbf {u} _{1}}\,\mathbf {a} _{3}-\mathrm {proj} _{\mathbf {u} _{2}}\,\mathbf {a} _{3},&\mathbf {e} _{3}&={\mathbf {u} _{3} \over \|\mathbf {u} _{3}\|}\\&\vdots &&\vdots \\\mathbf {u} _{k}&=\mathbf {a} _{k}-\sum _{j=1}^{k-1}\mathrm {proj} _{\mathbf {u} _{j}}\,\mathbf {a} _{k},&\mathbf {e} _{k}&={\mathbf {u} _{k} \over \|\mathbf {u} _{k}\|}\end{aligned}}}$

Тепер ми можемо виразити ${\displaystyle \mathbf {a} _{i}}$ через ново обчислений ортонормальний базис:

${\displaystyle {\begin{aligned}\mathbf {a} _{1}&=\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle \mathbf {e} _{1}\\\mathbf {a} _{2}&=\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle \mathbf {e} _{1}+\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle \mathbf {e} _{2}\\\mathbf {a} _{3}&=\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle \mathbf {e} _{1}+\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle \mathbf {e} _{2}+\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle \mathbf {e} _{3}\\&\vdots \\\mathbf {a} _{k}&=\sum _{j=1}^{k}\langle \mathbf {e} _{j},\mathbf {a} _{k}\rangle \mathbf {e} _{j}\end{aligned}}}$

де ${\displaystyle \langle \mathbf {e} _{i},\mathbf {a} _{i}\rangle =\|\mathbf {u} _{i}\|}$. Це можна записати у матричній формі:

${\displaystyle A=QR}$

де:

${\displaystyle Q=\left[\mathbf {e} _{1},\cdots ,\mathbf {e} _{n}\right]\qquad {\text{and}}\qquad R={\begin{pmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\ldots \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\ldots \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\ldots \\\vdots &\vdots &\vdots &\ddots \end{pmatrix}}.}$

Розглянемо декомпозицію

${\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}.}$

Згадаймо, що ортонормальна матриця ${\displaystyle Q}$ має таку властивість

${\displaystyle {\begin{matrix}Q^{T}\,Q=I.\end{matrix}}}$

Тоді, ми можемо обчислити ${\displaystyle Q}$ із застосувавши процес Грама — Шмідта так:

${\displaystyle U={\begin{pmatrix}\mathbf {u} _{1}&\mathbf {u} _{2}&\mathbf {u} _{3}\end{pmatrix}}={\begin{pmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{pmatrix}};}$

${\displaystyle Q={\begin{pmatrix}{\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}&{\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}&{\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\end{pmatrix}}={\begin{pmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{pmatrix}}.}$

Отже, ми маємо

${\displaystyle {\begin{matrix}Q^{T}A=Q^{T}Q\,R=R;\end{matrix}}}$

${\displaystyle {\begin{matrix}R=Q^{T}A=\end{matrix}}{\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}.}$

Відбиття Хаусхалдера для QR-розкладу: Ціллю є знаходження лінійного перетворення, що переводить вектор ${\displaystyle x}$ у вектор такої ж довжини колінеарний з ${\displaystyle e_{1}}$. Ми могли б використати ортогональну проекцію (Грам-Шмідт), але це було б чисельно нестабільно якщо вектори ${\displaystyle x}$ і ${\displaystyle e_{1}}$ майже ортогональні. Натомість, відбиття Хаусхолдера віддзеркалює щодо пунктирної лінії (обраної так, щоб розсікати навпіл кут між ${\displaystyle x}$ і ${\displaystyle e_{1}}$). Найбільший можливий кут у такій трансформації становить 45 градусів.

Перетворення Хаусхолдера — це трансформація, яка приймає вектор і відбиває його від певної площини або гіперплощини. Ми можемо використати цю операцію для обчислення QR-розкладу m-на-n матриці ${\displaystyle A}$ з m ≥ n.

Q можна використати, щоб відбивати вектор таким чином, щоб всі координати окрім однієї зникали.

Нехай ${\displaystyle \mathbf {x} }$ буде довільним дійсним m-вимірним вектором стовпчиком ${\displaystyle A}$ таким, що ${\displaystyle \|\mathbf {x} \|=|\alpha |}$ для скаляра α. Якщо алгоритм втілюється із використанням арифметики з рухомою комою, тоді потрібно надати α знак протилежний до знаку k-ї координати ${\displaystyle \mathbf {x} }$, де ${\displaystyle x_{k}}$ є опорною координатою після якої усі елементи дорівнюють нулю в кінцевій верхній трикутній формі матриці A, задля уникнення втрати розрядів. У комплексному випадку, встановіть

${\displaystyle \alpha =-\mathrm {e} ^{\mathrm {i} \arg x_{k}}\|\mathbf {x} \|}$

і замініть транспонування на спряжене транспонування під час побудови Q далі.

Тоді, ${\displaystyle \mathbf {e} _{1}}$ є вектором (1,0,...,0)^T, ||·|| є Евклідовою нормою і ${\displaystyle I}$ є m-by-m одиничною матрицею, встановимо

${\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},}$

${\displaystyle \mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|},}$

${\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{T}.}$

Або, якщо ${\displaystyle A}$ комплексна

${\displaystyle Q=I-(1+w)\mathbf {v} \mathbf {v} ^{H}}$, де ${\displaystyle w=\mathbf {x} ^{H}\mathbf {v} \mathbf {/} \mathbf {v} ^{H}\mathbf {x} }$

де ${\displaystyle \mathbf {x} ^{H}}$ — це ермітово-спряжений ${\displaystyle \mathbf {x} }$

${\displaystyle Q}$ є m-на-m матриця Хаусхолдера і

${\displaystyle Q\mathbf {x} =(\alpha ,0,\cdots ,0)^{T}.\,}$

Це можна використати, щоб поступово трансформувати m-на-n матрицю A у верхню трикутну форму. Спершу ми множимо A на матрицю Хаусхолдера Q₁ яку ми отримали для першого стовпчика. Це нам дає матрицю Q₁A з нулями в першому стовпчику окрім першого рядка.

${\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\dots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}}$

Це можна повторити для A′ (Q₁A без першого рядка і першого стовпчика), в результаті маємо матрицю Хаусхолдера Q′₂. Зауважте, що Q′₂ менше ніж Q₁. Оскільки ми бажаємо, щоб вона діяла на Q₁A, а не на A′ нам потрібно розширити її додавши у верхній лівий кут 1, узагальнюючи:

${\displaystyle Q_{k}={\begin{pmatrix}I_{k-1}&0\\0&Q_{k}'\end{pmatrix}}.}$

Після ${\displaystyle t}$ ітерацій цього процесу, ${\displaystyle t=\min(m-1,n)}$,

${\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A}$

є верхньою трикутною матрицею. Отже, з

${\displaystyle Q=Q_{1}^{T}Q_{2}^{T}\cdots Q_{t}^{T},}$

${\displaystyle A=QR}$ є QR-розкладом ${\displaystyle A}$.

Цей метод має більшу числову стійкість ніж метод Грама-Шмідта.

Наступна таблиця наводить кількість операцій на k-му кроці QR-розкладення із використанням перетворення Хаусхолдера, припускаючи квадратну матрицю розміру n.

Операція	Кількість на k-му кроці
множення	${\displaystyle 2(n-k+1)^{2}}$
додавання	${\displaystyle (n-k+1)^{2}+(n-k+1)(n-k)+2}$
ділення	${\displaystyle 1}$
взяття кореня	${\displaystyle 1}$

Додаючи ці числа для усіх n − 1 кроків (для квадратної матриці розміру n), складність алгоритму (кількість множень з рухомою комою) задається

${\displaystyle {\frac {2}{3}}n^{3}+n^{2}+{\frac {1}{3}}n-2=O(n^{3}).}$

Обчислимо розклад для

${\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}.}$

Перше, нам потрібно знайти відбиття, що перетворює перший стовпчик матриці A, вектор ${\displaystyle \mathbf {a} _{1}=(12,6,-4)^{T}}$, у ${\displaystyle \|\mathbf {a} _{1}\|\;\mathrm {e} _{1}=(14,0,0)^{T}.}$

Тепер,

${\displaystyle \mathbf {u} =\mathbf {x} +\alpha \mathbf {e} _{1},}$

і

${\displaystyle \mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|}.}$

Тут,

${\displaystyle \alpha =-14}$ and ${\displaystyle \mathbf {x} =\mathbf {a} _{1}=(12,6,-4)^{T}}$

Отже

${\displaystyle \mathbf {u} =(-2,6,-4)^{T}=({2})(-1,3,-2)^{T}}$ and ${\displaystyle \mathbf {v} ={1 \over {\sqrt {14}}}(-1,3,-2)^{T}}$, and then

${\displaystyle Q_{1}=I-{2 \over {\sqrt {14}}{\sqrt {14}}}{\begin{pmatrix}-1\\3\\-2\end{pmatrix}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}}$

${\displaystyle =I-{1 \over 7}{\begin{pmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{pmatrix}}}$

${\displaystyle ={\begin{pmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{pmatrix}}.}$

Спостережемо що:

${\displaystyle Q_{1}A={\begin{pmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{pmatrix}},}$

Отже, ми вже маємо майже трикутну матрицю. Нам лише потрібен нуль у чарунці (3, 2).

Візьмемо мінор (1, 1) і знову застосуємо процес до

${\displaystyle A'=M_{11}={\begin{pmatrix}-49&-14\\168&-77\end{pmatrix}}.}$

Таким саме методом як і вище, отримуємо матрицю перетворення Хаусхолдера

${\displaystyle Q_{2}={\begin{pmatrix}1&0&0\\0&-7/25&24/25\\0&24/25&7/25\end{pmatrix}}}$

після розширення.

Тепер, знайдемо

${\displaystyle Q=Q_{1}^{T}Q_{2}^{T}={\begin{pmatrix}6/7&-69/175&58/175\\3/7&158/175&-6/175\\-2/7&6/35&33/35\end{pmatrix}}}$

Тоді

${\displaystyle Q=Q_{1}^{T}Q_{2}^{T}={\begin{pmatrix}0.8571&-0.3943&0.3314\\0.4286&0.9029&-0.0343\\-0.2857&0.1714&0.9429\end{pmatrix}}}$

${\displaystyle R=Q_{2}Q_{1}A=Q^{T}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{pmatrix}}.}$

Матриця Q є ортогональною і R є верхньою трикутною, отже A = QR і є шуканим QR-розкладом.