線代膠囊──QR 分解

本文的閱讀等級:中級

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

 
AQ 以行向量表示,並以上三角矩陣 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}=1i=j\delta_{ij}=0i\neq j。上式左乘 \mathbf{q}_i^Ti<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 正交化


  1. 對於 j=1,\ldots,n
  2.     對於 k=1,\ldots,j-1
  3.         r_{kj}\leftarrow\mathbf{q}_k^T\mathbf{a}_j
  4.     \mathbf{u}_j\leftarrow\mathbf{a}_j-\sum_{k=1}^{j-1}r_{kj}\mathbf{q}_k
  5.     r_{jj}\leftarrow\Vert\mathbf{u}_j\Vert
  6.     \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。按此方式類推可得到完整的 QR

相關閱讀:
廣告
本篇發表於 線性代數專欄, 內積空間 並標籤為 , , 。將永久鏈結加入書籤。

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

  1. volzkzg 說道:

    Column vector 应该是列向量吧。

  2. David 說道:

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

    • ccjou 說道:

      你何不自己驗證一下結果?
      http://www.bluebit.gr/matrix-calculator/

      • David 說道:

        以下是我試驗的結果
        A = QR
        QR分解 A不一定要行獨立
        Q與R不一定要為方陣 但Q之列向量為標準正交
        transpose(Q) Q = I

        結論為 任意矩陣均存在QR分解
        transpose(Q) Q = I
        R為上三角 不一定為方陣

        • ccjou 說道:

          不盡然如你所述。試輸入下列矩陣:
          A=\begin{bmatrix} 1&1\\ 1&1\\ 0&0 \end{bmatrix}
          A的行向量線性相關時,Q的行向量確實是標準正交,但方陣R的主對角包含零元。

      • David 說道:

        老師 您所貼的這個程式 是否有問題
        A 矩陣 第一行與第二行 均為1 1 0
        Q之第一行應該為 A之第一行的單位向量
        但程式跑出來確是加負號

        • ccjou 說道:

          這個答案是正確的,Q向量的方向不必與A相同。電腦程式未必使用Gram-Schmidt正交化程序,還有其他算法比較穩定。

          • David 說道:

            感謝老師

            matlab的QR分解 跟這個程式的QR分解所得到答案不同
            如 A:3*2 利用matlab所計算出來的Q為3*3 但網頁所算出來為3*2
            是否代表QR分解 有兩種定義

            另外台聯大線代 官方公佈解答
            他所說的QR分解的前題 都已經限定行獨立 如103台聯大B
            他有一題 官方公佈解答的前題已經為行獨立 但題目並沒有說
            這樣回使得答案不同
            其實有點無所適從

            • David 說道:

              感謝老師 詳述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 說道:

              你說的問題是這個嗎?
              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 說道:

              這裏做個修正 R為上三角 但不一定可逆 但Q R均為方陣

            • David 說道:

              謝謝老師 您解決了我 想了很久的問題 非常非常感激您

            • ccjou 說道:

              我看不出這個問題的涵義,到底是考正交矩陣、上三角矩陣的定義,還是問QR分解的性質?四個選項東拉西扯,跟QR分解完全無關。台聯大考題總是有個自保選項:None of the above are true. 題目出錯了沒答案也無妨。 

            • David 說道:

              因為這題公佈解答為 a c
              所以觀念上有點亂
              知道正確答案為a 那解決了一些觀念上的問題
              因為我是由答案去反推它的題目 才會說這題A為行獨立
              然後才會推出一些錯誤觀念
              再次謝謝老師 台灣若能多一些像您這樣的老師 學子讀線代將會更有動力

            • ccjou 說道:

              如果問題改成這樣那麼選項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 說道:

              我對線代蠻有興趣一直以來有空就是拜讀老師部落格

              因為台聯線代都會公佈解答
              所以會對自己測驗一下

              其實這題當年在看的時候就覺得很怪 這幾天偶然又看到老師這篇文章 斗膽請教
              沒想到老師回答如此詳細
              學生內心是很感動的 看了很多線代的書 有時候困惑的是名詞定義問題
              很遺憾學生時代沒能遇到您
              祝老師新年快樂

          • David 說道:

            若A的行向量為線性相關, 如老師舉的這題, 利用Gram-Schmidt正交化程序,
            其實也是無法得到答案的, 代入公式後第二個向量會是零向量, 此時只能任取跟第一個向量正交的向量當成Q之第二個向量, 所以電腦程式跑出來的才是如此

  3. David 說道:

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

  4. 張峻嘉 說道:

    若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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s