Givens 旋轉於 QR 分解的應用

Posted on 02/18/2010 by ccjou

本文的閱讀等級：中級

給定 $\mathbb{R}^2$ 平面上的旋轉矩陣

$Q=\left[\!\!\begin{array}{cr} \mathrm{cos}\theta&-\mathrm{sin}\theta\\ \mathrm{sin}\theta&\mathrm{cos}\theta \end{array}\!\!\right]$ ，

向量 $Q\mathbf{x}$ 表示 $\mathbf{x}=\begin{bmatrix} x_1\\ x_2 \end{bmatrix}$ 在平面上逆時針旋轉 $\theta$ 弧度。假設 $\mathbf{x}\neq\mathbf{0}$ ，考慮這個問題：如何旋轉向量 $\mathbf{x}$ 至正X軸方向？

沒有必要明確計算出旋轉角 $\theta$ ，我們可以直接求旋轉矩陣 $Q$ 。令向量 $\mathbf{x}$ 的長度為 $r$ ，即 $r=\Vert\mathbf{x}\Vert=\sqrt{x_1^2+x_2^2}$ 。旋轉不改變向量長度，我們的問題是尋找 $c=\mathrm{cos}\theta$ 和 $s=\mathrm{sin}\theta$ 使得

$\left[\!\!\begin{array}{cr} c&-s\\ s&c \end{array}\!\!\right]\begin{bmatrix} x_1\\ x_2 \end{bmatrix}=\begin{bmatrix} r\\ 0 \end{bmatrix}$ 。

乘開上式並改寫成

$\left[\!\!\begin{array}{cr} x_1&-x_2\\ x_2&x_1 \end{array}\!\!\right]\begin{bmatrix} c\\ s \end{bmatrix}=\begin{bmatrix} r\\ 0 \end{bmatrix}$ ，

可解出

$\begin{aligned} c=\displaystyle\frac{x_1}{\sqrt{x_1^2+x_2^2}},~~ s=-\frac{x_2}{\sqrt{x_1^2+x_2^2}}\end{aligned}$ 。

另一個方法從平面幾何著手，設向量 $\mathbf{x}$ 與正X軸方向夾角為 $\phi$ ，由三角學可知

$\begin{aligned} \cos\phi=\displaystyle\frac{x_1}{\sqrt{x_1^2+x_2^2}},~~ \sin\phi=\frac{x_2}{\sqrt{x_1^2+x_2^2}}\end{aligned}$ 。

令 $\mathbf{x}$ 逆時針旋轉 $-\phi$ 弧度即可，因此旋轉矩陣為

$Q=\left[\!\!\begin{array}{rr} \mathrm{cos}(-\phi)&-\mathrm{sin}(-\phi)\\ \mathrm{sin}(-\phi)&\mathrm{cos}(-\phi) \end{array}\!\!\right]=\left[\!\!\begin{array}{rr} \mathrm{cos}\phi&\mathrm{sin}\phi\\ -\mathrm{sin}\phi&\mathrm{cos}\phi \end{array}\!\!\right]=\displaystyle\frac{1}{\sqrt{x_1^2+x_2^2}}\left[\!\!\begin{array}{rc} x_1&x_2\\ -x_2&x_1 \end{array}\!\!\right]$ 。

旋轉矩陣 $Q$ 將向量 $\mathbf{x}$ 轉至正X軸方向的效果在於引入零元於向量中，美國數學家吉文斯 (Wallace Givens) 率先將這個看似不起眼的結果應用於計算 QR 分解，此後平面旋轉矩陣便以其名稱之。下面我們討論如何將 $\mathbb{R}^2$ 旋轉矩陣推廣至 $\mathbb{R}^n$ ，並介紹它的實際用途。

吉文斯的想法是在向量空間 $\mathbb{R}^n$ 中選取兩個座標軸，假設是第 $i$ 軸與第 $j$ 軸， $i\neq j$ ，Givens 旋轉就是在這兩個座標軸所展開平面上旋轉，以如下形式的 $n$ 階方陣表示：

$Q_{ji}=\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}$ 。

我們用 $q_{kl}$ 代表 $Q_{ji}$ 的 $(k,l)$ 元，Givens 旋轉矩陣的設計規則十分簡單：如果第 $i$ 元為軸元，待消去者為第 $j$ 元， $Q_{ji}$ 替換 $n\times n$ 階單位矩陣 $I_n$ 的四個指定元 $q_{ii}=c$ ， $q_{jj}=c$ ， $q_{ij}=-s$ ， $q_{ji}=s$ 。下面是三階 Givens 旋轉的例子：

$Q_{31}=\left[\!\!\begin{array}{ccr} c&0&-s\\ 0&1&0\\ s&0&c \end{array}\!\!\right],~~ Q_{23}=\left[\!\!\begin{array}{crc} 1&0&0\\ 0&c&s\\ 0&-s&c \end{array}\!\!\right]$ 。

類似二階旋轉矩陣，你不須明確算出轉角 $\theta$ 便可以得到符合要求的 $Q_{ji}$ 矩陣。令

$\begin{aligned} c=\displaystyle\frac{x_i}{\sqrt{x_i^2+x_j^2}},~ s=-\frac{x_j}{\sqrt{x_i^2+x_j^2}}\end{aligned}$ 。

直接計算驗證 $Q_{ji}\mathbf{x}$ 的效果就是以 $\mathbf{x}$ 的第 $i$ 元為軸旋轉使消滅第 $j$ 元：

$\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}\begin{bmatrix} x_1\\ \vdots\\ x_i\\ \vdots\\ x_j\\ \vdots\\ x_n \end{bmatrix}=\begin{bmatrix} x_1\\ \vdots\\ \sqrt{x_i^2+x_j^2}\\ \vdots\\ 0\\ \vdots\\ x_n \end{bmatrix}$ 。

藉由特殊設計的 Givens 旋轉，我們可以選擇消滅向量中的任何一個元──此例為第 $j$ 元，除了 $x_i$ 和 $x_j$ ，其他每個元皆不受影響。一旦我們選定某個 $x_i$ 當作軸元，只要施行一連串的 Givens 旋轉便可將 $x_i$ 底下 (以及上面) 的所有元悉數消滅。

舉例來說，假設 $x_1$ 為軸元，執行以下一序列乘法運算將第 $2$ 至第 $n$ 元消去：

$\begin{aligned} Q_{21}\mathbf{x}&=\begin{bmatrix} \sqrt{x_1^2+x_2^2}\\ 0\\ x_3\\ \vdots\\ x_n \end{bmatrix}\\ Q_{31}Q_{21}\mathbf{x}&=\begin{bmatrix} \sqrt{x_1^2+x_2^2+x_3^2}\\ 0\\ 0\\ \vdots\\ x_n \end{bmatrix}\\ &\vdots\\ Q_{n1}\cdots Q_{31}Q_{21}\mathbf{x}&=\begin{bmatrix} \sqrt{x_1^2+x_2^2+\cdots+x_n^2}\\ 0\\ 0\\ \vdots\\ 0 \end{bmatrix}=\begin{bmatrix} \Vert\mathbf{x}\Vert\\ 0\\ 0\\ \vdots\\ 0 \end{bmatrix}=\Vert\mathbf{x}\Vert\begin{bmatrix} 1\\ 0\\ 0\\ \vdots\\ 0 \end{bmatrix}.\end{aligned}$

類似 $\mathbb{R}^2$ 平面上旋轉，我們也有辦法將 $\mathbb{R}^n$ 向量旋轉至第一軸方向。事實上，此法不僅適用於第一軸，連續施行 $n-1$ 次平面旋轉可將向量 $\mathbf{x}$ 旋轉至第 $i$ 軸方向，如下：

$Q_{ni}\cdots Q_{i+1,i}Q_{i-1,i}\cdots Q_{1i}\mathbf{x}=\Vert\mathbf{x}\Vert\mathbf{e}_i$ ，

其中 $\mathbf{e}_i$ 代表第 $i$ 軸方向的標準單位向量 (第 $i$ 元為 $1$ ，其餘元為零)。

QR 分解是數值線性代數的一個重要矩陣分解式，目前已知有三種計算方法：Gram-Schmidt 正交化，Householder 變換，以及 Givens 旋轉 (見“QR 分解的數值計算方法比較”)。為方便說明，底下以一個例子展示利用 Givens 旋轉實現 QR 分解的過程。考慮這個 $3$ 階方陣

$A=\left[\!\!\begin{array}{crr} 0&-15&14\\ 4&32&2\\ 3&-1&4 \end{array}\!\!\right]$ 。

Givens 旋轉的目標要消滅矩陣主對角線以下的所有元，選擇消滅的次序與高斯消去法相同。首先攻擊 $A$ 的 $(2,1)$ 元，對應的旋轉矩陣即為 $Q_{21}$ ，以 $A$ 的第一行 $\begin{bmatrix} 0\\4\\3 \end{bmatrix}$ 來設定 $Q_{21}$ 的旋轉參數，

$\begin{aligned} c&=\displaystyle\frac{0}{\sqrt{0^2+4^2}}=0\\ s&=-\frac{4}{\sqrt{0^2+4^2}}=-1,\end{aligned}$

旋轉後得到

$\begin{aligned} Q_{21}A&=\left[\!\!\begin{array}{rcc} 0&1&0\\ -1&0&0\\ 0&0&1 \end{array}\!\!\right]\left[\!\!\begin{array}{crr} 0&-15&14\\ 4&32&2\\ 3&-1&4 \end{array}\!\!\right]=\left[\!\!\begin{array}{crr} 4&32&2\\ 0&15&-14\\ 3&-1&4 \end{array}\!\!\right]\end{aligned}$ 。

第二步要殲滅 $Q_{21}A$ 的 $(3,1)$ 元，稱該旋轉為 $Q_{31}$ ，由 $Q_{21}A$ 的第一行 $\begin{bmatrix} 4\\ 0\\ 3 \end{bmatrix}$ 得到旋轉參數：

$\begin{aligned} c&=\displaystyle\frac{4}{\sqrt{4^2+3^2}}=\frac{4}{5}\\ s&=-\frac{3}{\sqrt{4^2+3^2}}=-\frac{3}{5},\end{aligned}$

旋轉結果為

$\begin{aligned} Q_{31}Q_{21}A&=\left[\!\!\begin{array}{rcr} \frac{4}{5}&0&\frac{3}{5}\\ 0&1&0\\ -\frac{3}{5}&0&\frac{4}{5} \end{array}\!\!\right]\left[\!\!\begin{array}{crr} 4&32&2\\ 0&15&-14\\ 3&-1&4 \end{array}\!\!\right]=\left[\!\!\begin{array}{crr} 5&25&4\\ 0&15&-14\\ 0&-20&2 \end{array}\!\!\right]\end{aligned}$ 。

最後趕盡殺絕 $Q_{31}Q_{21}A$ 的 $(3,2)$ 元， $Q_{31}Q_{21}A$ 的第二行 $\left[\!\!\begin{array}{r} 25\\ 15\\ -20 \end{array}\!\!\right]$ 給出 $Q_{32}$ 的旋轉參數：

$\begin{aligned} c&=\displaystyle\frac{15}{\sqrt{15^2+(-20)^2}}=\frac{3}{5}\\ s&=-\frac{-20}{\sqrt{15^2+(-20)^2}}=\frac{4}{5},\end{aligned}$

經旋轉得到上三角矩陣：

$\begin{aligned} Q_{32}Q_{31}Q_{21}A&=\left[\!\!\begin{array}{crr} 1&0&0\\ 0&\frac{3}{5}&-\frac{4}{5}\\[0.3em] 0&\frac{4}{5}&\frac{3}{5} \end{array}\!\!\right]\left[\!\!\begin{array}{crr} 5&25&4\\ 0&15&-14\\ 0&-20&2 \end{array}\!\!\right]=\left[\!\!\begin{array}{crr} 5&25&4\\ 0&25&-10\\ 0&0&-10 \end{array}\!\!\right]\end{aligned}$ 。

令 $R$ 代表上式等號右邊的上三角矩陣，連續三次 Givens 旋轉可表示為

$Q_{32}Q_{31}Q_{21}A=R$ ，

故 $A$ 可寫成分解式

$A=(Q_{21}^{-1}Q_{31}^{-1}Q_{32}^{-1})R$ 。

旋轉矩陣是正交矩陣 (orthogonal matrix)， $Q_{ij}^{T}=Q_{ij}^{-1}$ ，因此矩陣 $A$ 的 QR 分解即為

$A=(Q_{21}^TQ_{31}^{T}Q_{32}^T)R=QR$ ，

其中 $Q=Q_{21}^TQ_{31}^{T}Q_{32}^T$ 。正交矩陣的積仍為正交矩陣，不難驗證 $Q^T=Q^{-1}$ 。

必須一提的是，Givens 旋轉得到的 QR 分解形式不同於 Gram-Schmidt 正交化得到的 QR 分解。對於 $m\times n$ 階矩陣 $A$ ，Gram-Schmidt 正交化給出的 $Q$ 為包含單範正交 (orthonormal) 行向量 (column vector) 的 $m\times n$ 階矩陣，而 $R$ 為 $n\times n$ 階上三角矩陣。但在 Givens 旋轉產生的 QR 分解式中， $Q$ 為 $m\times m$ 階正交矩陣， $R$ 則為 $m\times n$ 階矩陣。用前面的例子來說明，若

$A=\left[\!\!\begin{array}{cr} 0&-15\\ 4&32\\ 3&-1 \end{array}\!\!\right]$ ，

由矩陣乘法的行向量運算規則可知

$Q_{32}Q_{31}Q_{21}\left[\!\!\begin{array}{cr} 0&-15\\ 4&32\\ 3&-1 \end{array}\!\!\right]=\left[\!\!\begin{array}{rr} 50&25\\ 0&25\\ 0&0 \end{array}\!\!\right]$ 。

為使記號一致，仍稱等號右邊的 $2\times 2$ 階上三角子陣為 $R$ ，亦即 $R=\begin{bmatrix} 50&25\\ 0&25 \end{bmatrix}$ ，故 $A$ 的 QR 分解為

$\begin{aligned} A&=Q_{21}^TQ_{31}^TQ_{32}^T\begin{bmatrix} R\\ 0 \end{bmatrix}=Q\begin{bmatrix} R\\ 0 \end{bmatrix}\end{aligned}$ 。

最後我們討論如何應用 Givens 旋轉導出的 QR 分解於計算最小平方近似解。當 $A$ 是滿行秩時， $\mathrm{rank}A=n$ 且 $m\ge n$ ，因為 $Q$ 是正交矩陣，也就有 $\mathrm{rank}A=\mathrm{rank}\begin{bmatrix} R\\ 0 \end{bmatrix}=\mathrm{rank}R=n$ ，推知 $n\times n$ 階子陣 $R$ 是可逆的。將 QR 分解代入正規方程式 $A^TA\hat{\mathbf{x}}=A^T\mathbf{b}$ ，化簡係數矩陣 $A^TA$ 可得

$\begin{aligned} A^TA&=\begin{bmatrix} R^T&0 \end{bmatrix}Q^TQ\begin{bmatrix} R\\ 0 \end{bmatrix}=\begin{bmatrix} R^T&0 \end{bmatrix}\begin{bmatrix} R\\ 0 \end{bmatrix}=R^TR\end{aligned}$ ，

並化簡常數向量 $A^T\mathbf{b}$ ，如下：

$\begin{aligned} A^T\mathbf{b}&=\begin{bmatrix} R^T&0 \end{bmatrix}Q^T\mathbf{b}=\begin{bmatrix} R^T&0 \end{bmatrix}\begin{bmatrix} \mathbf{c}_1\\ \mathbf{c}_2 \end{bmatrix}=R^T\mathbf{c}_1\end{aligned}$ 。

上式中， $\mathbf{c}_1$ 代表由 $Q^T\mathbf{b}$ 的前 $n$ 個元所構成的向量， $\mathbf{c}_2$ 為 $Q^T\mathbf{b}$ 的後 $m-n$ 個元組成的向量。原來的正規方程式變成

$R^TR\hat{\mathbf{x}}=R^T\mathbf{c}_1$ 。

又因為 $R^T$ 是可逆的，左乘 $(R^T)^{-1}$ 得到

$R\hat{\mathbf{x}}=\mathbf{c}_1$ ，

最後再以反向迭代即可順利求出最小平方近似解。

This entry was posted in 線性代數專欄, 內積空間 and tagged Givens 旋轉, Gram-Schmidt 正交化, Householder 矩陣, QR 分解, 旋轉, 最小平方法, 正交矩陣. Bookmark the permalink.

15 Responses to Givens 旋轉於 QR 分解的應用

文龙 says:

01/10/2013 at 3:27 pm

这个旋转矩阵Q 是不是也可以是 [ c -s
s c] ?

Reply
- ccjou says:
  
  01/10/2013 at 6:27 pm
  
  $Q=\begin{bmatrix} c&-s\\ s&c \end{bmatrix}$ 不正是上文的旋轉矩陣？你說的是另一個矩陣嗎？
  
  Reply
  - Vahi Chen says:
    
    09/18/2015 at 3:16 am
    
    文龙指的应该是 $Q=\begin{bmatrix}c&s\\-s&c\end{bmatrix}$ 。
    两者都是旋转矩阵，区别在于一个是顺时针旋转，一个是逆时针旋转。
    
    Reply
Tim says:

04/18/2014 at 12:25 am

例子說明中有誤應為Q21*A=[Col1(4,0,3),Col2(32,15,-1),Col3(2,-14,4)}

Reply
- ccjou says:
  
  04/18/2014 at 10:24 am
  
  謝謝指正。
  
  Reply
Pingback: Solve the QR Decomposition with Givens Rotation | Mengjiao's Space
陳學豪 says:

08/22/2016 at 1:29 am

老師你好
假如有一個A矩陣
13
24

我要用GIVENS旋轉讓4變0
所以要先算C和S
3/5 4/5
-4/5 3/5
相乘結果為

11/5 5
2/5 0

這樣算是一個GIVENS ROTATION的範例嗎
想再問一個就是把一個元素變0的目的是甚麼 ?

謝謝

Reply
- ccjou says:
  
  08/22/2016 at 7:23 am
  
  請重讀上文，Givens 旋轉的目的在使A變換為一個上三角矩陣。
  
  Reply
林偉傑 says:

08/23/2016 at 3:48 pm

老師我想請問一下
Givens旋轉是想讓哪個元素變0都可以嗎
還是一定是成為一個上三角矩陣

就以上面的題目來說
對應的旋轉矩陣Q11
要怎麼表示 ?

還有Givens旋轉除了讓元素變0
還有甚麼用途?

謝謝大師

Reply
ccjou says:

08/23/2016 at 4:16 pm

請三讀上文。

Givens旋轉是想讓哪個元素變0都可以嗎?
(上文說明： $Q_{ji}\mathbf{x}$ 的效果就是以 $\mathbf{x}$ 的第 $i$ 元為軸旋轉使消滅第 $j$ 元)
就以上面的題目來說，對應的旋轉矩陣Q11，要怎麼表示 ?
(上文說明： $i\neq j$ ，所以不存在Q11)
還有Givens旋轉除了讓元素變0，還有甚麼用途?
(我不知道)

Reply
林偉傑 says:

09/04/2016 at 2:13 pm

假如 i 不等於 j
對角線的元素要怎麼算怎麼變0 ?

謝謝老師

Reply
林偉傑 says:

09/05/2016 at 12:51 am

老師你好
我自己去計算摸索了好久
好像有一點解題的感覺又好像不太懂
我自己所認知的GIVENS旋轉可以把消除任何一個位元

@ 第一個問題就是可以往下消成0(以最上面那行為軸)，那可以往上消成0嗎 ? 要怎麼做(老師可以給個方向嗎)?

就以上面的例子來說
0 -15 14
4 32 2
3 -1 4

我想要做的是(我只是單純的想消除為0)
假如我想把 -15 變成 0
@ 那我的旋轉矩陣是叫Q12嗎 ? ( 我自己感覺怪怪的，我有自己去算過，Xi是32，Xj是-15(這樣i,j好像顛倒了==)，算出來-15的確變成0，但我不知道這樣做是不是正確的)

像例子中 0 32 4 要消除這三個變成0的旋轉矩陣=Q11 Q22 Q33( 但 i 不能等於 j )
那我要怎麼樣消除這幾個元素要怎麼去設他的旋轉矩陣，還是用其他方法(先將某個元素變0，再多轉幾次?)

我自己也有試過假如我要消除 14 2 4的4
是要先將2變0 在把4變0嗎? 還是可以直接把4變0 ?
就因為他是在33的位置所以不知道旋轉矩陣怎麼去設

我可能不是描述的很清楚，希望老師給我指點一下
謝謝

Reply
- ccjou says:
  
  09/05/2016 at 9:53 am
  
  上文已經回答了你提出的問題，就是這一段：
  
  $Q_{ji}\mathbf{x}$ 的效果就是以 $\mathbf{x}$ 的第 $i$ 元為軸旋轉使消滅第 $j$ 元：
  
  $\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}\begin{bmatrix} x_1\\ \vdots\\ x_i\\ \vdots\\ x_j\\ \vdots\\ x_n \end{bmatrix}=\begin{bmatrix} x_1\\ \vdots\\ \sqrt{x_i^2+x_j^2}\\ \vdots\\ 0\\ \vdots\\ x_n \end{bmatrix}$ 。
  
  藉由特殊設計的 Givens 旋轉，我們可以選擇消滅向量中的任何一個元──此例為第 $j$ 元，除了 $x_i$ 和 $x_j$ ，其他每個元皆不受影響。
  
  Reply
AllEnter says:

06/20/2017 at 12:50 am

I regarded the “Givens rotation” like this:
Q_{ji} act just like the 2–dimensional rotation operator on [v_i; v_j] \in R^2.
This rotation rotates the vector [v_i; v_j] to ahead e_i direction.
Other components along e_1, … , e_n except e_i, e_j are fixed as the same.

Reply
王偉 says:

11/10/2022 at 9:07 am

小註解：數值上用Givens方法用來算某些sparse matrix的qr分解還挺不賴的（比如tridiagonal matrix）

Reply

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨