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

QR-розклад матриці — представлення матриці у вигляді добутку унітарної та правої трикутної матриці.

Матриця A розміру m×n може бути представлена у вигляді

$A=QR,$

де Q — унітарна матриця розміру m×m, R — верхня трикутна матриця розміру m×n.

Також можливі представлення QL, RQ, та LQ (де L — нижня трикутна матриця).

Для m×n матриці A, з m ≥ n нижні (m−n) рядків m×n верхньої трикутної матриці усі нульові, тому часто буває корисно розбити R, або R і Q:

$A=QR=Q\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]=\left[\begin{array}{c}{Q}_1,Q_2\end{array}\right]\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]=Q_1{R}_1,$

де R₁ — це n×n верхня трикутна матриця, 0 — це (m − n)×n нульова матриця, Q₁ — це m×n, Q₂ — це m×(m − n) і Q₁ та Q₂ обидві мають ортогональні стовпчики.

Обчислення

Розклад матриці може отримуватись за допомогою різних методів:

• Процес Грама — Шмідта,
• Перетворення Хаусхолдера,
• Поворот Ґівенса.

Використовуючи процес Грама — Шмідта

Розглянемо процес Грама — Шмідта застосований до стовпчиків матриці $A=[{𝐚}_1,\cdots ,{𝐚}_n]$ з повним стовпчиковим рангом, де $⟨𝐯,𝐰⟩={𝐯}^{\mathrm{\top }}𝐰$ (або $⟨𝐯,𝐰⟩={𝐯}^{*}𝐰$ у комплексному випадку).

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

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐞}𝐚=\frac{⟨𝐞,𝐚⟩}{⟨𝐞,𝐞⟩}𝐞$

тоді:

$\begin{array}{cccc}{𝐮}_1& ={𝐚}_1,& {𝐞}_1& =\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }\\ {𝐮}_2& ={𝐚}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}{𝐚}_2,& {𝐞}_2& =\frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }\\ {𝐮}_3& ={𝐚}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}{𝐚}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}{𝐚}_3,& {𝐞}_3& =\frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }\\ & ⋮& & ⋮\\ {𝐮}_k& ={𝐚}_k-\sum _{j=1}^{k-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_j}{𝐚}_k,& {𝐞}_k& =\frac{{𝐮}_k}{\Vert {𝐮}_k\Vert }\end{array}$

Тепер ми можемо виразити ${𝐚}_i$ через ново обчислений ортонормальний базис:

$\begin{array}{cc}{𝐚}_1& =⟨{𝐞}_1,{𝐚}_1⟩{𝐞}_1\\ {𝐚}_2& =⟨{𝐞}_1,{𝐚}_2⟩{𝐞}_1+⟨{𝐞}_2,{𝐚}_2⟩{𝐞}_2\\ {𝐚}_3& =⟨{𝐞}_1,{𝐚}_3⟩{𝐞}_1+⟨{𝐞}_2,{𝐚}_3⟩{𝐞}_2+⟨{𝐞}_3,{𝐚}_3⟩{𝐞}_3\\ & ⋮\\ {𝐚}_k& =\sum _{j=1}^k⟨{𝐞}_j,{𝐚}_k⟩{𝐞}_j\end{array}$

де $⟨{𝐞}_i,{𝐚}_i⟩=\Vert {𝐮}_i\Vert$. Це можна записати у матричній формі:

$A=QR$

де:

$Q=[{𝐞}_1,\cdots ,{𝐞}_n]\text{and}R=\left(\begin{array}{cccc}⟨{𝐞}_1,{𝐚}_1⟩& ⟨{𝐞}_1,{𝐚}_2⟩& ⟨{𝐞}_1,{𝐚}_3⟩& \dots \\ 0& ⟨{𝐞}_2,{𝐚}_2⟩& ⟨{𝐞}_2,{𝐚}_3⟩& \dots \\ 0& 0& ⟨{𝐞}_3,{𝐚}_3⟩& \dots \\ ⋮& ⋮& ⋮& \ddots \end{array}\right).$

Приклад

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

$A=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right).$

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

$\begin{array}{c}{Q}^{T}Q=I.\end{array}$

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

$U=\left(\begin{array}{ccc}{𝐮}_1& {𝐮}_2& {𝐮}_3\end{array}\right)=\left(\begin{array}{ccc}12& -69& -58/5\\ 6& 158& 6/5\\ -4& 30& -33\end{array}\right);$

$Q=\left(\begin{array}{ccc}\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }& \frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }& \frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }\end{array}\right)=\left(\begin{array}{ccc}6/7& -69/175& -58/175\\ 3/7& 158/175& 6/175\\ -2/7& 6/35& -33/35\end{array}\right).$

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

$\begin{array}{c}{Q}^{T}A=Q^{T}QR=R;\end{array}$

$\begin{array}{c}R=Q^{T}A=\end{array}\left(\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& 35\end{array}\right).$

Використовуючи перетворення Хаусхолдера

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

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

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

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

$\alpha =-{\mathrm{e}}^{\mathrm{i}\arg x_k}\Vert 𝐱\Vert$

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

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

$𝐮=𝐱-\alpha {𝐞}_1,$

$𝐯=\frac{𝐮}{\Vert 𝐮\Vert },$

$Q=I-2𝐯{𝐯}^T.$

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

$Q=I-(1+w)𝐯{𝐯}^H$, де $w={𝐱}^H𝐯/{𝐯}^H𝐱$

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

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

$Q𝐱=(\alpha ,0,\cdots ,0{)}^T.$

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

$Q_{1}A=\left[\begin{array}{cccc}{\alpha }_1& \star & \dots & \star \\ 0& & & \\ ⋮& & A^{\prime }& \\ 0& & & \end{array}\right]$

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

$Q_k=\left(\begin{array}{cc}{I}_{k-1}& 0\\ 0& {Q_k}^{\prime }\end{array}\right).$

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

$R=Q_t\cdots Q_2{Q}_{1}A$

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

$Q=Q_1^T{Q}_2^T\cdots Q_t^T,$

$A=QR$ є QR-розкладом $A$.

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

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

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

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

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

Приклад

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

$A=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right).$

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

Тепер,

$𝐮=𝐱+\alpha {𝐞}_1,$

і

$𝐯=\frac{𝐮}{\Vert 𝐮\Vert }.$

Тут,

$\alpha =-14$ and $𝐱={𝐚}_1=(12,6,-4{)}^T$

Отже

$𝐮=(-2,6,-4{)}^T=(2)(-1,3,-2{)}^T$ and $𝐯=\frac{1}{\sqrt{14}}(-1,3,-2{)}^T$, and then

$Q_1=I-\frac{2}{\sqrt{14}\sqrt{14}}\left(\begin{array}{c}-1\\ 3\\ -2\end{array}\right)\left(\begin{array}{ccc}-1& 3& -2\end{array}\right)$

$=I-\frac{1}{7}\left(\begin{array}{ccc}1& -3& 2\\ -3& 9& -6\\ 2& -6& 4\end{array}\right)$

$=\left(\begin{array}{ccc}6/7& 3/7& -2/7\\ 3/7& -2/7& 6/7\\ -2/7& 6/7& 3/7\end{array}\right).$

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

$Q_{1}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& -49& -14\\ 0& 168& -77\end{array}\right),$

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

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

$A^{\prime }=M_{11}=\left(\begin{array}{cc}-49& -14\\ 168& -77\end{array}\right).$

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

$Q_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& -7/25& 24/25\\ 0& 24/25& 7/25\end{array}\right)$

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

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

$Q=Q_1^T{Q}_2^T=\left(\begin{array}{ccc}6/7& -69/175& 58/175\\ 3/7& 158/175& -6/175\\ -2/7& 6/35& 33/35\end{array}\right)$

Тоді

$Q=Q_1^T{Q}_2^T=\left(\begin{array}{ccc}0.8571& -0.3943& 0.3314\\ 0.4286& 0.9029& -0.0343\\ -0.2857& 0.1714& 0.9429\end{array}\right)$

$R=Q_2{Q}_{1}A=Q^{T}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& -35\end{array}\right).$

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

Див. також

• QR-алгоритм

Джерела

• Шаблон:Гантмахер.Теорія матриць