## Givens 旋轉於 QR 分解的應用

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

$\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}

\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_{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$ 階單位矩陣的四個指定元 $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]$

\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}

$\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}$

\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}

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

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}

\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}

\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$

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

$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]$

\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}

\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}

\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}

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

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

This entry was posted in 線性代數專欄, 內積空間 and tagged , , , , , , . Bookmark the permalink.

### 13 則回應給 Givens 旋轉於 QR 分解的應用

1. 文龙 說：

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

• ccjou 說：

$Q=\begin{bmatrix} c&-s\\ s&c \end{bmatrix}$ 不正是上文的旋轉矩陣？你說的是另一個矩陣嗎？

• Vahi Chen 說：

文龙 指的应该是$Q=\begin{bmatrix}c&s\\-s&c\end{bmatrix}$
两者都是旋转矩阵，区别在于一个是顺时针旋转，一个是逆时针旋转。

2. Tim 說：

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

• ccjou 說：

謝謝指正。

3. 陳學豪 說：

老師你好
假如有一個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的目的是甚麼 ?

謝謝

• ccjou 說：

請重讀上文，Givens 旋轉的目的在使A變換為一個上三角矩陣。

4. 林偉傑 說：

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

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

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

謝謝大師

5. ccjou 說：

請三讀上文。

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

6. 林偉傑 說：

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

謝謝老師

7. 林偉傑 說：

老師你好
我自己去計算摸索了好久
好像有一點解題的感覺又好像不太懂
我自己所認知的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的位置 所以不知道旋轉矩陣怎麼去設

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

• ccjou 說：

上文已經回答了你提出的問題，就是這一段：

$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$，其他每個元皆不受影響。