Givens 旋轉於 QR 分解的應用

本文的閱讀等級:中級

給定 \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}\thetas=\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}=cq_{jj}=cq_{ij}=-sq_{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_ix_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 階矩陣,而 Rn\times n 階上三角矩陣。但在 Givens 旋轉產生的 QR 分解式中,Qm\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=nm\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}_2Q^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

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

Advertisements
本篇發表於 線性代數專欄, 內積空間 並標籤為 , , , , , , 。將永久鏈結加入書籤。

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

  1. 文龙 說道:

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

  2. Tim 說道:

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

  3. 通告: Solve the QR Decomposition with Givens Rotation | Mengjiao's Space

  4. 陳學豪 說道:

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

    謝謝

  5. 林偉傑 說道:

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

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

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

    謝謝大師

  6. ccjou 說道:

    請三讀上文。

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

  7. 林偉傑 說道:

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

    謝謝老師

  8. 林偉傑 說道:

    老師你好
    我自己去計算摸索了好久
    好像有一點解題的感覺又好像不太懂
    我自己所認知的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_ix_j,其他每個元皆不受影響。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s