線代膠囊──QR 分解

本文的閱讀等級:中級

m\times n 階實矩陣 A 有線性獨立的行向量 (column vector)。如何求得 QR 分解 A=QR,其中 m\times n 階矩陣 Q 的行向量組成單範正交集 (orthonormal set),R 為一 n\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

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

9 則回應給 線代膠囊──QR 分解

  1. volzkzg 說:

    Column vector 应该是列向量吧。

  2. David 說:

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

  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