QR分解法

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

## 定義

實數矩陣 _A_ 的 **QR 分解**是把 _A_ 分解為

　
: $A=QR$

這裡的 _Q_ 是正交矩陣（意味著 _Q_T_Q_ = _I_）而 _R_ 是上三角矩陣。類似的，我們可以定義 A 的 QL, RQ 和 LQ 分解。

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

如果 _A_ 是非奇異的，且限定 _R_ 的對角線元素為正，則這個因數分解是唯一的。

## 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，p.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}}$

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

#### 基本思想

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

設 ${\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 正交化的過程如下：

這樣就得到 $\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)$

## 外部連結