QR分解

QR分解法是一種將矩陣分解的方式。這種方式，把矩陣分解成一個正交矩陣與一個上三角矩陣的積。QR分解經常用來解線性最小二乘法問題。QR分解也是特定特徵值算法即QR算法的基礎。

類別及定義

方陣

任何方塊矩陣A都可以分解為

$A=QR$

其中Q是正交矩陣（意味着Q^TQ = I）而R是上三角矩陣。如果A是非奇異的，且限定R的對角線元素為正，則這個因數分解是唯一的。

更一般的說，我們可以因數分解複數$m$×$n$矩陣（有着m ≥ n）為$m$×$n$幺正矩陣（在Q ^∗Q = I 的意義上，不需要是方陣）和$n$×$n$上三角矩陣的乘積。對m<n的情況，在Q是$m$×$m$方陣，而R則是$m$×$n$矩陣。

長方形矩陣

更一般地，我們可以將m×n的A矩陣，其中m ≥ n，分解成m×m酉矩陣Q和m×n三角矩陣R的乘積。由於m×n上三角矩陣的底部(m−n)行完全由零組成，因此對R或R和Q進行分解通常很有用：

$A=QR=Q{\begin{bmatrix}R_{1}\\0\end{bmatrix}}={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}{\begin{bmatrix}R_{1}\\0\end{bmatrix}}=Q_{1}R_{1},$

其中R₁是n×n上三角矩陣，0是(m − n)×n零矩陣，Q₁是m×n，Q₂是m×(m − n)，且Q₁和Q₂都是有正交列。

已隱藏部分未翻譯內容，歡迎參與翻譯。

Golub & Van Loan (1996，§5.2) call Q₁R₁ the thin QR factorization of A; Trefethen and Bau call this the reduced QR factorization. If A is of full rank n and we require that the diagonal elements of R₁ are positive then R₁ and Q₁ are unique, but in general Q₂ is not. R₁ is then equal to the upper triangular factor of the Cholesky decomposition of A* A (= A^TA if A is real).

QL、RQ 和 LQ 分解

類似的，我們可以定義A的QL，RQ和LQ分解。其中L是下三角矩陣。

QR分解的求法

QR分解的實際計算有很多方法，例如Givens旋轉、Householder變換，以及Gram-Schmidt正交化等等。每一種方法都有其優點和不足。

參見：格拉姆-施密特正交化

使用Householder變換

Householder變換

Householder變換將一個向量關於某個平面或者超平面進行反射。我們可以利用這個操作對$m\times n(m\geqq n)$的矩陣$A$進行QR分解。

矩陣$Q$可以被用於對一個向量以一種特定的方式進行反射變換，使得它除了一個維度以外的其他所有分量都化為0。

令$\mathbf {x}$為矩陣$A$的任一m維實列向量，且有$\|\mathbf {x} \|=|\alpha |$（其中$\alpha$為標量）。若該算法是通過浮點數實現的，則$\alpha$應當取和$\mathbf {x}$的第$k$維相反的符號（其中$x_{k}$是要保留不為0的項），這樣做可以避免精度缺失。對於複數的情況，令

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

(Stoer & Bulirsch 2002，第225頁)，並且在接下來矩陣$Q$的構造中要將矩陣轉置替換為共軛轉置。

接下來，設$\mathbf {e} _{1}$為單位向量$(1,0,\cdots ,0)^{T}$，||·||為歐幾里德範數，$I$為$m\times m$單位矩陣，令

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

$\mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|}$ ，

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

或者，若$A$為復矩陣，則

$Q=I-(1+w)\mathbf {v} \mathbf {v} ^{H}$，其中$w=\mathbf {x} ^{H}\mathbf {v} \mathbf {/} \mathbf {v} ^{H}\mathbf {x}$

式中$\mathbf {x} ^{H}$是$x$的共軛轉置（亦稱埃爾米特共軛或埃爾米特轉置）。

則$Q$為一個$m\times m$的Householder矩陣，它滿足

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

利用Householder矩陣，可以將一個$m\times n$的矩陣$A'$變換為上三角矩陣。 首先，我們將A左乘通過選取矩陣的第一列得到列向量$x$的Householder矩陣$Q_{1}$。這樣，我們得到的矩陣$Q_{1}A$的第一列將全部為0（第一行除外）：

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

這個過程對於矩陣$A'$（即$Q_{1}A$排除第一行和第一列之後剩下的方陣）還可以繼續做下去，從而得到另一個Householder矩陣$Q_{2}$。注意到$Q_{2}$其實比$Q_{1}$要小，因為它是在$Q_{1}A$而非$A$的基礎上得到的。因此，我們需要在$Q_{2}$的左上角補上1，或者，更一般地來說：

$Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}$

將這個迭代過程進行$t$次之後（$t=\min(m-1,n)$）,將有

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

其中R為一個上三角矩陣。因此，令

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

則$A=QR$為矩陣$A$的一個QR分解。

相比與Gram-Schmidt正交化，使用Householder變換具有更好的數值穩定性。

例子

現在要用Householder變換求解矩陣$A$的$QR$ 分解。

$A={\begin{bmatrix}0&3&1\\0&4&-2\\2&1&1\\\end{bmatrix}}$

因為$\alpha _{1}=[0,\ 0,\ 2]^{T}$, 令$a_{1}=||\alpha _{1}||_{2}=2$，則

$\omega _{1}={\frac {\alpha _{1}-a_{1}e_{1}}{||\alpha _{1}-a_{1}e_{1}||_{2}}}={\frac {1}{\sqrt {2}}}[-1,\ 0,\ 1]^{T}$

則有

$H_{1}=I-2\omega _{1}\omega _{1}^{H}={\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\\\end{bmatrix}}$

從而，

$H_{1}A={\begin{bmatrix}2&1&1\\0&4&-2\\0&3&1\\\end{bmatrix}}$

記$\beta =[4,\ 3]^{T}$, 則$b_{1}=||\beta _{2}||_{2}=5$。令

$\omega _{2}={\frac {\beta _{2}-b_{1}e_{1}}{||\beta _{2}-b_{1}e_{1}||_{2}}}={\frac {1}{\sqrt {10}}}[-1,\ 3]^{T}$

${\hat {H_{2}}}=I-2\omega _{2}\omega ^{H}={\frac {1}{5}}{\begin{bmatrix}4&3\\3&-4\\\end{bmatrix}}$

記，

$H_{2}={\begin{bmatrix}1&0^{T}\\0&{\hat {H_{2}}}\\\end{bmatrix}}={\begin{bmatrix}1&0&0\\0&{\frac {4}{5}}&{\frac {3}{5}}\\0&{\frac {3}{5}}&-{\frac {4}{5}}\\\end{bmatrix}}$

則，

$R=H_{2}(H_{1}A)={\begin{bmatrix}2&1&1\\0&5&-1\\0&0&-2\\\end{bmatrix}}$

那麼

$Q=H_{1}H_{2}={\frac {1}{5}}{\begin{bmatrix}0&3&-4\\0&4&3\\5&0&0\\\end{bmatrix}}$

使用吉文斯旋轉

吉文斯旋轉

吉文斯旋轉表示為如下形式的矩陣

$G(i,j,\theta )={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &c&\cdots &-s&\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &s&\cdots &c&\cdots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}}$

這裡的 c = cos(θ) 和 s = sin(θ) 出現在第 i 行和第 j 行與第 i 列和第 j 列的交叉點上。就是說，吉文斯旋轉矩陣的所有非零元定義如下：:

${\begin{aligned}g_{k\,k}&{}=1\qquad {\text{for}}\ k\neq i,\,j\\g_{i\,i}&{}=c\\g_{j\,j}&{}=c\\g_{i\,j}&{}=s\\g_{j\,i}&{}=-s\end{aligned}}$

乘積 G(i, j, θ)x 表示向量 x 在 (i,j)平面中的逆時針旋轉 θ 弧度。

吉文斯旋轉作用於QR分解

對於一個向量

${\begin{array}{lcl}A&=&{\begin{bmatrix}a\\b\\\end{bmatrix}}\\\end{array}}$

如果，$r={\sqrt {a^{2}+b^{2}}}$ , $c={\frac {a}{r}}$ , $s=-{\frac {b}{r}}$ , 那麼，就存在旋轉矩陣G，使$A$ 底部轉成0。

$A_{2\_Sub}={\begin{bmatrix}c&-s\\s&c\\\end{bmatrix}}{\begin{bmatrix}a\\b\\\end{bmatrix}}={\begin{bmatrix}r\\0\\\end{bmatrix}}$

每一次的旋轉，吉文斯旋轉都可以將一個元素化成0，直到將原始矩陣轉成一個上三角矩陣，則完成分解。

$A=QR$

$Q=G_{1}^{T}G_{2}^{T}\cdots G_{k}^{T}$

例子

$A_{1}={\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix}}$

$r={\sqrt {6^{2}+5^{2}}}\approx 7.8102$

$c=6/r\approx 0.7682$

$s=-5/r\approx -0.6402$

$A_{2}=G_{1}A_{1}={\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\\\end{bmatrix}}{\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix}}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3.0729\\0&4&3\\\end{bmatrix}}$

對於:$A_{2}$子矩陣 :$A_{2\_Sub}$

$A_{2\_Sub}={\begin{bmatrix}-2.4327&3.0729\\4&3\\\end{bmatrix}}$

$r={\sqrt {(-2.4327)^{2}+4^{2}}}\approx 4.6817$

$c=-2.4327/r\approx -0.5196$

$s=-5/r\approx -0.8544$

$G_{2}A_{2}={\begin{bmatrix}1&0&0\\0&c&-s\\0&s&c\\\end{bmatrix}}{\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3.0729\\0&4&3\\\end{bmatrix}}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&4.6817&0.9664\\0&0&-4.1843\\\end{bmatrix}}$

$R=G_{2}A_{2}=G_{2}G_{1}A_{1}$

$Q=G_{1}^{T}G_{2}^{T}={\begin{bmatrix}0.7682&0.3327&0.5470\\0.6402&-0.3992&-0.6564\\0&0.8544&-0.5196\\\end{bmatrix}}$

使用格拉姆-施密特正交化方法

基本思想

圖1 ${\boldsymbol {v}}$在${\boldsymbol {V}}^{2}$上投影，構造${\boldsymbol {V}}^{3}$上的正交基${\boldsymbol {\beta }}$

格拉姆-施密特正交化的基本想法，是利用投影原理在已有正交基的基礎上構造一個新的正交基。

設${\boldsymbol {v}}\in {\boldsymbol {V^{n}}}$。${\boldsymbol {V}}^{k}$是${\boldsymbol {V}}^{n}$上的$k$維子空間，其標準正交基為$\{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{k}\}$，且${\boldsymbol {v}}$不在${\boldsymbol {V}}^{k}$上。由投影原理知，${\boldsymbol {v}}$與其在${\boldsymbol {V}}^{k}$上的投影$\mathrm {proj} _{\boldsymbol {V^{k}}}{\boldsymbol {v}}$之差

${\boldsymbol {\beta }}={\boldsymbol {v}}-\sum _{i=1}^{k}\mathrm {proj} _{{\boldsymbol {\eta }}_{i}}\,{\boldsymbol {v}}={\boldsymbol {v}}-\sum _{i=1}^{k}\langle {\boldsymbol {v}},{\boldsymbol {\eta }}_{i}\rangle {\boldsymbol {\eta }}_{i}$

是正交於子空間${\boldsymbol {V}}^{k}$的，亦即${\boldsymbol {\beta }}$正交於${\boldsymbol {V}}^{k}$的正交基${\boldsymbol {\eta }}_{i}$。因此只要將${\boldsymbol {\beta }}$單位化，即

${\boldsymbol {\eta }}_{k+1}={\frac {\boldsymbol {\beta }}{\|{\boldsymbol {\beta }}\|}}={\frac {\boldsymbol {\beta }}{\sqrt {\langle {\boldsymbol {\beta }},{\boldsymbol {\beta }}\rangle }}}$

那麼$\{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{k},{\boldsymbol {\eta }}_{k+1}\}$就是${\boldsymbol {V}}^{k}$在${\boldsymbol {v}}$上擴展的子空間$\mathrm {span} \{{\boldsymbol {v}},{\boldsymbol {\eta }}_{1},...,{\boldsymbol {\eta }}_{k}\}$的標準正交基。

根據上述分析，對於向量組$\{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{m}\}$張成的空間${\boldsymbol {V}}^{m}$ ($m<n$)，只要從其中一個向量（不妨設為${\boldsymbol {v}}_{1}$）所張成的一維子空間$\mathrm {span} \{{\boldsymbol {v}}_{1}\}$開始（注意到${\boldsymbol {v}}_{1}$就是$\mathrm {span} \{{\boldsymbol {v}}_{1}\}$的正交基），重複上述擴展構造正交基的過程，就能夠得到${\boldsymbol {V}}^{n}$ 的一組正交基。這就是格拉姆-施密特正交化。

格拉姆-施密特正交化算法

首先需要確定已有基底向量的順序，不妨設為$\{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{n}\}$。Gram-Schmidt正交化的過程如下：

	${\boldsymbol {\beta }}_{1}={\boldsymbol {v}}_{1},$		${\boldsymbol {\eta }}_{1}={{\boldsymbol {\beta }}_{1} \over \|{\boldsymbol {\beta }}_{1}\|}$
	${\boldsymbol {\beta }}_{2}={\boldsymbol {v}}_{2}-\langle {\boldsymbol {v}}_{2},{\boldsymbol {\eta }}_{1}\rangle {\boldsymbol {\eta }}_{1},$		${\boldsymbol {\eta }}_{2}={{\boldsymbol {\beta }}_{2} \over \|{\boldsymbol {\beta }}_{2}\|}$
	${\boldsymbol {\beta }}_{3}={\boldsymbol {v}}_{3}-\langle {\boldsymbol {v}}_{3},{\boldsymbol {\eta }}_{1}\rangle {\boldsymbol {\eta }}_{1}-\langle {\boldsymbol {v}}_{3},{\boldsymbol {\eta }}_{2}\rangle {\boldsymbol {\eta }}_{2},$		${\boldsymbol {\eta }}_{3}={{\boldsymbol {\beta }}_{3} \over \|{\boldsymbol {\beta }}_{3}\|}$
	$\vdots$		$\vdots$
	${\boldsymbol {\beta }}_{n}={\boldsymbol {v}}_{n}-\sum _{i=1}^{n-1}\langle {\boldsymbol {v}}_{n},{\boldsymbol {\eta }}_{i}\rangle {\boldsymbol {\eta }}_{i},$		${\boldsymbol {\eta }}_{n}={{\boldsymbol {\beta }}_{n} \over \|{\boldsymbol {\beta }}_{n}\|}$

這樣就得到$\mathrm {span} \{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{n}\}$上的一組正交基$\{{\boldsymbol {\beta }}_{1},\ldots ,{\boldsymbol {\beta }}_{n}\}$，以及相應的標準正交基$\{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{n}\}$。

例子

現在要用格拉姆-施密特變換求解矩陣$A$的$QR$ 分解。

$A={\begin{bmatrix}1&2&4\\0&0&5\\0&3&6\\\end{bmatrix}}$

令， $a=[1,0,0]$

$q_{1}={\frac {a}{||a||}}={\begin{bmatrix}1\\0\\0\\\end{bmatrix}}$

${\hat {q_{2}}}=b-(b*q_{1})q_{1}={\begin{bmatrix}2\\0\\3\\\end{bmatrix}}-2{\begin{bmatrix}1\\0\\0\\\end{bmatrix}}={\begin{bmatrix}0\\0\\3\\\end{bmatrix}}$

$q_{2}={\frac {\hat {q_{2}}}{||{\hat {q_{2}}}||}}={\begin{bmatrix}0\\0\\1\\\end{bmatrix}}$

${\hat {q_{3}}}=c-(c*q_{1})q_{1}-(c*q_{2})q_{2}={\begin{bmatrix}4\\5\\6\\\end{bmatrix}}-4{\begin{bmatrix}1\\0\\0\\\end{bmatrix}}-6{\begin{bmatrix}0\\0\\1\\\end{bmatrix}}={\begin{bmatrix}0\\5\\0\\\end{bmatrix}}$

$q_{3}={\frac {\hat {q_{3}}}{||{\hat {q_{3}}}||}}={\begin{bmatrix}0\\1\\0\\\end{bmatrix}}$

那麼可知，

$Q={\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\\\end{bmatrix}}$

由$A=QR$，可知，

$R={\begin{bmatrix}1&2&4\\0&3&6\\0&0&5\\\end{bmatrix}}$

Matlab

MATLAB以qr函數來執行QR分解法，其語法為

$[Q,R]=qr(A)$

其中Q代表正規正交矩陣，

而R代表上三角形矩陣。

此外，原矩陣A不必為正方矩陣； 如果矩陣A大小為$m\times n$，則矩陣Q大小為$m\times m$，矩陣R大小為$m\times n$。

用途

解線性方程組

對於直接求解線性方程組的逆，用QR分解的方法求解會更具有數據的穩定性。 對於求解一個線性系統$Ax=b$, 這裡$A$的維度是$m\times n$。

如果$m\leq n$, 那麼$A^{T}=QR$,這裡$Q^{T}=Q^{-1}$)。

$R$ 的形式是 $R={\begin{bmatrix}R_{1}\\0\end{bmatrix}}$，$R_{1}$是$R$上不為0的部分。 那麼對於

$x=Q{\begin{bmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}b\\0\end{bmatrix}}$

如果$m>n$, 那麼$A=QR$,這裡$Q^{T}=Q^{-1}$)。本質是最小化$||A{\hat {x}}-b||$

${\hat {x}}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}b\right)$

外部連結

• MIT. QR Decomposition. Youtube. [2020-07-01]. （原始內容存檔於2020-07-27）. 
• Poujh. QR Decomposition Givens旋转. Youtube. [2020-07-01]. （原始內容存檔於2020-09-01）.