線代膠囊──QR 分解

Posted on 05/06/2013 by ccjou

本文的閱讀等級：中級

假設 $m\times n$ 階實矩陣 $A$ 有線性獨立的行向量 (column vector)。如何求得 QR 分解 $A=QR$ ，其中 $m\times n$ 階矩陣 $Q$ 的行向量組成單範正交集 (orthonormal set)， $R$ 為 $n\times n$ 階上三角矩陣？

將 $A$ 和 $Q$ 以行向量表示，並以上三角矩陣 $R=[r_{ij}]$ 聯繫， $A=QR$ 即為

$\begin{bmatrix} \mathbf{a}_1&\mathbf{a}_2&\cdots&\mathbf{a}_n \end{bmatrix}=\begin{bmatrix} \mathbf{q}_1&\mathbf{q}_2&\cdots\mathbf{q}_n \end{bmatrix}\begin{bmatrix} r_{11}&r_{12}&\cdots&r_{1n}\\ 0&r_{22}&\cdots&r_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&r_{nn} \end{bmatrix}$ 。

乘開上式，

$\mathbf{a}_j=r_{1j}\mathbf{q}_1+r_{2j}\mathbf{q}_2+\cdots+r_{jj}\mathbf{q}_j,~~j=1,\ldots,n$ 。

我們的問題要解出 $\{r_{ij},i\le j\}$ 和 $\{\mathbf{q}_j\}$ 。但這不是一般所見的線性方程組，該怎麼辦呢？

線代箴言：「解題之道無他，求其放心而已矣。」意思是說，把失去的「本心」找回來就行了。單範正交集 $\{\mathbf{q}_1,\ldots,\mathbf{q}_n\}$ 滿足 $\mathbf{q}_i^T\mathbf{q}_j=\delta_{ij}$ ，這裡 $\delta_{ij}$ 是 Kronecker 記號： $\delta_{ij}=1$ 若 $i=j$ ， $\delta_{ij}=0$ 若 $i\neq j$ 。上式左乘 $\mathbf{q}_i^T$ ， $i<j$ ，使用正交性 $\mathbf{q}_i\perp\mathbf{q}_j$ ，可得

$\displaystyle \mathbf{q}_i^T\mathbf{a}_j=\mathbf{q}_i^T\left(\sum_{k=1}^jr_{kj}\mathbf{q}_k\right)=\sum_{k=1}^jr_{kj}\mathbf{q}_i^T\mathbf{q}_k=\sum_{k=1}^jr_{kj}\delta_{ik}=r_{ij},~~i=1,\ldots,j-1$ 。

再將前一式改寫為

$\displaystyle \mathbf{q}_j=\frac{1}{r_{jj}}\left(\mathbf{a}_j-r_{1j}\mathbf{q}_1-r_{2j}\mathbf{q}_2-\cdots-r_{j-1,j}\mathbf{q}_{j-1}\right),~~j=1,\ldots,n$ ，

其中 $r_{jj}\neq 0$ ，否則 $\mathrm{rank}A=\mathrm{rank}(QR)<n$ ，與假設 $\mathrm{rank}A=n$ 相矛盾。將上式括弧內的向量表示為 $\mathbf{u}_j=\mathbf{a}_j-\sum_{k=1}^{j-1}r_{kj}\mathbf{q}_k$ ，使用歸一性 $\Vert\mathbf{q}_j\Vert=1$ ，可得 $r_{jj}=\Vert\mathbf{u}_j\Vert$ 。至此所有的運算公式皆已找齊，剩下的工作不過是將它們整理成一個算法膠囊：

Gram-Schmidt 正交化

對於 $j=1,\ldots,n$ ，
對於 $k=1,\ldots,j-1$ ，
$r_{kj}\leftarrow\mathbf{q}_k^T\mathbf{a}_j$
$\mathbf{u}_j\leftarrow\mathbf{a}_j-\sum_{k=1}^{j-1}r_{kj}\mathbf{q}_k$
$r_{jj}\leftarrow\Vert\mathbf{u}_j\Vert$
$\mathbf{q}_j\leftarrow\frac{\mathbf{u}_j}{r_{jj}}$

解讀如下：第一， $r_{kj}$ 是 $\mathbf{a}_j$ 在 $\mathbf{q}_k$ 方向的正交投影成分；第二， $\mathbf{u}_j$ 是 $\mathbf{a}_j$ 扣除在 $\mathbf{q}_1,\ldots,\mathbf{q}_{j-1}$ 方向的正交投影之後的殘餘量；第三， $r_{jj}$ 是向量 $\mathbf{u}_j$ 的長度；第四， $\mathbf{q}_j$ 是 $\mathbf{u}_j$ 方向的單位向量 (unit vector)。

最後我們用下面的膠囊表總結 Gram-Schmidt 正交化與 QR 分解的運算程序 (以 $n=4$ 為例)：

$\begin{array}{cccccc} &\vline& \mathbf{a}_1 &\mathbf{a}_2&\mathbf{a}_3&\mathbf{a}_4\\ \hline \mathbf{q}_1&\vline& & r_{12} &r_{13}&r_{14}\\ \mathbf{q}_2&\vline& & &r_{23} &r_{24}\\ \mathbf{q}_3&\vline& & & & r_{34}\\ \hline & \vline&\mathbf{u}_1&\mathbf{u}_2&\mathbf{u}_3&\mathbf{u}_4\\ \cline{3-6} \Vert\cdot\Vert & \vline&r_{11}&r_{22}&r_{33}&r_{44}\\ \hline / & \vline&\mathbf{q}_1&\mathbf{q}_2&\mathbf{q}_3&\mathbf{q}_4 \\ \hline \end{array}$

閱讀方式係由左而右，從上往下。第一個輸入向量 $\mathbf{a}_1$ 直接給出 $\mathbf{u}_1$ ，計算其長度 $r_{11}=\Vert\mathbf{u}_1\Vert$ ，兩者「相除」立得 $\mathbf{q}_1$ 。針對第二個輸入向量 $\mathbf{a}_2$ ，先計算 $r_{12}=\mathbf{q}_1^T\mathbf{a}_2$ ，接著從 $\mathbf{a}_2$ 扣除投影分量 $r_{12}\mathbf{q}_1$ 得到 $\mathbf{u}_2$ ，最後再計算 $r_{22}$ 和 $\mathbf{q}_2$ 。按此方式類推可得到完整的 $Q$ 和 $R$ 。

22 Responses to 線代膠囊──QR 分解

volzkzg says:

10/10/2015 at 11:29 pm

Column vector 应该是列向量吧。

Reply
- ccjou says:
  
  10/11/2015 at 6:06 am
  
  請下文說明：
  https://ccjou.wordpress.com/2012/04/17/%E5%85%A9%E5%B2%B8%E7%B7%9A%E6%80%A7%E4%BB%A3%E6%95%B8%E7%9A%84%E7%BF%BB%E8%AD%AF%E5%90%8D%E8%A9%9E%E5%8F%83%E7%85%A7/
  
  Reply
David says:

11/03/2015 at 4:37 pm

老師請問
若A 矩陣行向量沒有獨立的話 QR分解是否不存在或沒意義?
A = [1 0]T [0 1] 這樣也算QR分解嗎?
[1 0]T 為線性獨立的矩陣 [0 1]也為上三角矩陣但不為方陣
還麻煩請老師指導

Reply
- ccjou says:
  
  11/03/2015 at 5:03 pm
  
  你何不自己驗證一下結果？
  http://www.bluebit.gr/matrix-calculator/
  
  Reply
  - David says:
    
    11/03/2015 at 5:22 pm
    
    以下是我試驗的結果
    A = QR
    QR分解 A不一定要行獨立
    Q與R不一定要為方陣但Q之列向量為標準正交
    transpose(Q) Q = I
    
    結論為任意矩陣均存在QR分解
    transpose(Q) Q = I
    R為上三角不一定為方陣
    
    Reply
    - ccjou says:
      
      11/03/2015 at 9:47 pm
      
      不盡然如你所述。試輸入下列矩陣：
      $A=\begin{bmatrix} 1&1\\ 1&1\\ 0&0 \end{bmatrix}$ 。
      當 $A$ 的行向量線性相關時， $Q$ 的行向量確實是標準正交，但方陣 $R$ 的主對角包含零元。
      
      Reply
  - David says:
    
    01/31/2017 at 7:17 pm
    
    老師您所貼的這個程式是否有問題
    A 矩陣第一行與第二行均為1 1 0
    Q之第一行應該為 A之第一行的單位向量
    但程式跑出來確是加負號
    
    Reply
    - ccjou says:
      
      02/01/2017 at 9:25 am
      
      這個答案是正確的，Q向量的方向不必與A相同。電腦程式未必使用Gram-Schmidt正交化程序，還有其他算法比較穩定。
      
      Reply
      - David says:
        
        02/04/2017 at 1:17 pm
        
        感謝老師
        
        matlab的QR分解跟這個程式的QR分解所得到答案不同
        如 A：3*2 利用matlab所計算出來的Q為3*3 但網頁所算出來為3*2
        是否代表QR分解有兩種定義
        
        另外台聯大線代官方公佈解答
        他所說的QR分解的前題都已經限定行獨立如103台聯大B
        他有一題官方公佈解答的前題已經為行獨立但題目並沒有說
        這樣回使得答案不同
        其實有點無所適從
        
        Reply
        
        ccjou says:
        
        02/04/2017 at 2:53 pm
        
        QR 分解有兩種形式，請參考下文：
        https://ccjou.wordpress.com/2011/06/03/qr-%E5%88%86%E8%A7%A3%E7%9A%84%E6%95%B8%E5%80%BC%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95%E6%AF%94%E8%BC%83/
        
        David says:
        
        02/05/2017 at 9:09 am
        
        感謝老師詳述QR分解的兩種定義
        
        其實在看台聯大線代題目遇到QR分解的時候都會怕怕的因為題目並不會說明是那一種定義
        
        如103台聯大B卷選擇題裡面敘述說 A為m by n 且A=QR 其中Q為orthogonal matrix R為上三角矩陣
        
        他的a選項說 m大約等於n
        我的想法是 R為上三角而依上三角矩陣的定義他為方陣且主對角線均不為0 所以Q與R均可逆故A可逆且A為方陣
        所以m應該跟n相等
        但公佈解答確有a
        
        請問老師我這樣思考是否正確
        
        ccjou says:
        
        02/05/2017 at 8:59 pm
        
        你說的問題是這個嗎？
        Let $A$ be ( $m\times n$ ) matrix, which can be factored into a matrix-product $QR$ , where $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix. Which of the following statements are true?
        a) $m\ge n$
        b) The system of linear equations $Ax=b$ must be a consistent system for any vector $b\in\mathbb{R}^m$ .
        c) The right null space of $A$ contains only the all-zero vector.
        d) If $m=n$ , then $A$ is diagonalizable.
        e) None of the above are true.
        
        如果 $Q$ 是正交矩陣，則 $Q$ 是方陣； $R$ 是上三角矩陣，則 $R$ 也是方陣。因此， $m=n$ ，故(a)是對的。如果 $m=2$ ，我說 $m\ge 2$ 也沒錯，是吧？
        因為沒有指明 $R$ 是可逆的，故(b)是錯的。
        (c)說 $N(A)=\{0\}$ ，即 $A$ 是可逆的，這未必成立，(c)是錯的。
        (d)說 $A$ 可對角化，當然不總是成立，(d)是錯的。
        
        David says:
        
        02/05/2017 at 8:59 pm
        
        這裏做個修正 R為上三角但不一定可逆但Q R均為方陣
        
        David says:
        
        02/05/2017 at 9:02 pm
        
        謝謝老師您解決了我想了很久的問題非常非常感激您
        
        ccjou says:
        
        02/05/2017 at 9:10 pm
        
        我看不出這個問題的涵義，到底是考正交矩陣、上三角矩陣的定義，還是問QR分解的性質？四個選項東拉西扯，跟QR分解完全無關。台聯大考題總是有個自保選項：None of the above are true. 題目出錯了沒答案也無妨。　
        
        David says:
        
        02/05/2017 at 9:13 pm
        
        因為這題公佈解答為 a c
        所以觀念上有點亂
        知道正確答案為a 那解決了一些觀念上的問題
        因為我是由答案去反推它的題目才會說這題A為行獨立
        然後才會推出一些錯誤觀念
        再次謝謝老師台灣若能多一些像您這樣的老師學子讀線代將會更有動力
        
        ccjou says:
        
        02/05/2017 at 9:23 pm
        
        如果問題改成這樣那麼選項a,c是正確的：
        Let $A$ be ( $m\times n$ ) matrix, which can be factored into a matrix-product $QR$ , where $Q^TQ=I$ and $R$ is a nonsingular upper triangular matrix. Which of the following statements are true?
        a) $m\ge n$
        b) The system of linear equations $Ax=b$ must be a consistent system for any vector $b\in\mathbb{R}^m$ .
        c) The right null space of A contains only the all-zero vector.
        d) If $m=n$ , then A is diagonalizable.
        e) None of the above are true.
        
        $Q^TQ=I$ 說明 $Q$ 有orthonormal的行向量，因此 $m\ge n$ 。
        $R$ 是可逆上三角矩陣，故 $\hbox{rank}A=n$ ，因此 $\dim N(A)=0$ 。
        
        David says:
        
        02/05/2017 at 9:24 pm
        
        我對線代蠻有興趣一直以來有空就是拜讀老師部落格
        
        因為台聯線代都會公佈解答
        所以會對自己測驗一下
        
        其實這題當年在看的時候就覺得很怪這幾天偶然又看到老師這篇文章斗膽請教
        沒想到老師回答如此詳細
        學生內心是很感動的看了很多線代的書有時候困惑的是名詞定義問題
        很遺憾學生時代沒能遇到您
        祝老師新年快樂
      - David says:
        
        09/21/2017 at 7:06 pm
        
        若A的行向量為線性相關, 如老師舉的這題, 利用Gram-Schmidt正交化程序,
        其實也是無法得到答案的, 代入公式後第二個向量會是零向量, 此時只能任取跟第一個向量正交的向量當成Q之第二個向量, 所以電腦程式跑出來的才是如此
        
        Reply
David says:

11/04/2015 at 1:24 am

感謝老師提點
我改成
Q之行向量必定為標準正交
transpose Q*Q=I
R不一定為上三角
但R之 aij =0 , i>j. aij>=0 ,i<j

Reply
張峻嘉 says:

04/01/2016 at 9:09 pm

若Ax=b 無解且A是mxn矩陣，A的columns 是線性獨立時
如果用QR分解代入方程式去做
即 QRx=b
=> (transpose Q)*QRx=( transpose Q)*b (等號兩邊同乘Q的轉置)
Rx=(transpose Q)* b
x=(R的反矩陣)＊(transpose Q) * b 唯ㄧ解（R是upper triangular matrix 對角線元素必為正數所以必定可逆）
問題： “無解”的線性方程組Ax=b 卻解出答案！！
為何？？？
我的想法是
第一步無法逆推！
所以 QRx=b 與 (transpose Q)*QRx=( transpose Q)*b
的solution set 是不同
後者的解集合包含於前者的解集合
故依此方式解出來的x 不是原方程組Ax=b的解
而是least square solution

Reply
- ccjou says:
  
  04/06/2016 at 10:28 am
  
  你的推論是正確的。
  $Ax=b$ 同義於 $QRx=b$ ，但 $Q$ 不一定是一個方陣，因此 $Ax=b$ 與 $Q^\ast QRx=Rx=Q^\ast b$ 有不同的解，除非 $Q^\ast$ 可逆。
  
  你已經指出 $Rx=Q^\ast b$ 的解就是最小平方解。請參考下文：
  https://ccjou.wordpress.com/2013/07/05/%E5%B7%A6%E9%80%86%E8%88%87%E5%8F%B3%E9%80%86/
  
  Reply

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