Gram-Schmidt 正交化與 QR 分解

本文的閱讀等級:初級

\mathcal{X} 為幾何向量空間 \mathbb{R}^{m} 的一個子空間,\dim\mathcal{X}=nn\le m。假設 \{\mathbf{x}_1,\ldots,\mathbf{x}_n\} 為子空間 \mathcal{X} 的一組已知基底。在一些應用時機,例如最小平方法,我們希望從 \{\mathbf{x}_1,\ldots,\mathbf{x}_n\} 建構出另一組單範正交基底 (orthonormal basis) \{\mathbf{q}_1,\ldots,\mathbf{q}_n\},亦即每一 \Vert\mathbf{q}_i\Vert^2=\mathbf{q}_i^{T}\mathbf{q}_i=1\mathbf{q}_i^{T}\mathbf{q}_j=0i\neq j。底下先考慮實幾何向量空間,隨後再推廣至一般內積空間 (見“內積的定義”,“從幾何向量空間到函數空間”)。

 
Gram-Schmidt 正交化 (orthogonalization) 是基礎線性代數最常採用的方法,包含兩個部分:

  1. 正交化:對於 i=1,2,\ldots,n,由 \mathbf{x}_1,\ldots,\mathbf{x}_i 的線性組合產生 \mathbf{y}_i,使得 \{\mathbf{y}_1,\ldots,\mathbf{y}_n\} 為一個正交向量集,即 \mathbf{y}_i^T\mathbf{y}_j=0i\neq j
  2. 單位化:伸縮 \{\mathbf{y}_1,\ldots,\mathbf{y}_n\} 的長度,將每一 \mathbf{y}_i 替換為單位向量 \mathbf{q}_i=\mathbf{y}_i/\Vert\mathbf{y}_i\Vert,最後得到單範正交基底 \{\mathbf{q}_1,\ldots,\mathbf{q}_n\}

 
下面我採用歸納法推導從給定的一組基底 \{\mathbf{x}_1,\ldots,\mathbf{x}_n\} 產生一組正交基底 \{\mathbf{y}_1,\ldots,\mathbf{y}_n\} 的 Gram-Schmidt 正交化過程。為便於說明,考慮簡單情況 n=3。因為 \{\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3\} 包含線性獨立的基底向量,\mathbf{x}_1\neq\mathbf{0},首先令

\mathbf{y}_1=\mathbf{x}_1

見圖一,將 \mathbf{x}_2 正交投影至 \mathbf{y}_1 所指的直線的分量扣除就得到 \mathbf{y}_2 (參閱“正交投影──威力強大的線代工具”),算式如下:

\mathbf{y}_2=\mathbf{x}_2-\displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1

圖一中綠色虛線投影向量為 \frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1。明顯地,\mathbf{y}_1\perp\mathbf{y}_2。上式的扣除量 (投影量) 還有另一種表達方式,因為 \frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1} 是一個純量,利用矩陣乘法結合律可得

\begin{aligned} \displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1&=\mathbf{y}_1\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}=\frac{1}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1\mathbf{y}_1^T\mathbf{x}_2=\frac{\mathbf{y}_1\mathbf{y}_1^T}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{x}_2\end{aligned}

其中 \frac{\mathbf{y}_1\mathbf{y}_1^{T}}{\mathbf{y}_1^{T}\mathbf{y}_1} 是將 \mathbb{R}^n 向量投影至子空間 (直線) \mathrm{span}\{\mathbf{y}_1\}n\times n 階正交投影矩陣。

圖一 Gram-Schmidt 正交化的第一步驟

 
繼續下一個步驟,將 \mathbf{x}_3 投影至 \mathbf{y}_1\mathbf{y}_2 所擴張的子空間 (平面) 的分量扣除可得 \mathbf{y}_3。因為 \mathbf{y}_1 正交於 \mathbf{y}_2 (見圖二),

\mathbf{y}_3=\displaystyle\mathbf{x}_3-\frac{\mathbf{y}_1^T\mathbf{x}_3}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1-\frac{\mathbf{y}_2^T\mathbf{x}_3}{\mathbf{y}_2^T\mathbf{y}_2}\mathbf{y}_2

上式也有對應於正交投影矩陣的推導。設 Y=\begin{bmatrix}  \mathbf{y}_1&\mathbf{y}_2  \end{bmatrix},將 \mathbf{x}_3Y 的行空間 \mathrm{span}\{\mathbf{y}_1,\mathbf{y}_2\} 的投影量從 \mathbf{x}_3 扣除即得 \mathbf{y}_3,計算式如下:

\begin{aligned} \mathbf{y}_3&=\mathbf{x}_3-Y(Y^TY)^{-1}Y^{T}\mathbf{x}_3\\ &=\mathbf{x}_3-\begin{bmatrix}  \mathbf{y}_1&\mathbf{y}_2  \end{bmatrix}\begin{bmatrix}  \mathbf{y}_1^T\mathbf{y}_1&0\\  0&\mathbf{y}_2^T\mathbf{y}_2  \end{bmatrix}^{-1}\begin{bmatrix}  \mathbf{y}_1^T\\  \mathbf{y}_2^T  \end{bmatrix}\mathbf{x}_3\\ &=\mathbf{x}_3-\displaystyle\left(\frac{\mathbf{y}_1\mathbf{y}_1^T}{\mathbf{y}_1^T\mathbf{y}_1}+\frac{\mathbf{y}_2\mathbf{y}_2^T}{\mathbf{y}_2^T\mathbf{y}_2}\right)\mathbf{x}_3.\end{aligned}

最後再單位化正交向量集 \{\mathbf{y}_1,\mathbf{y}_2,\mathbf{y}_3\},令 \mathbf{q}_i=\mathbf{y}_i/\Vert\mathbf{y}_i\Verti=1,2,3

圖二 Gram-Schmidt 正交化的第二步驟

 
請注意,Gram-Schmidt 單位化過程顯示新基底向量 \mathbf{y}_i 可以表示為舊基底向量 \mathbf{x}_1,\ldots,\mathbf{x}_i 的線性組合。反過來說也成立,即 \mathbf{x}_i 可寫為 \mathbf{y}_1,\ldots,\mathbf{y}_i 的線性組合,如下:

\begin{aligned} \mathbf{x}_1&=\mathbf{y}_1\\  \mathbf{x}_2&=\displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1+\mathbf{y}_2\\  \mathbf{x}_3&=\frac{\mathbf{y}_1^T\mathbf{x}_3}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1+\frac{\mathbf{y}_2^T\mathbf{x}_3}{\mathbf{y}_2^T\mathbf{y}_2}\mathbf{y}_2+\mathbf{y}_3.\end{aligned}

如果進一步將單位化結果納入上式,直接替換 \mathbf{y}_i\mathbf{q}_i,就有下列形式:

\begin{aligned} \mathbf{x}_1&=r_{11}\mathbf{q}_1\\  \mathbf{x}_2&=r_{12}\mathbf{q}_1+r_{22}\mathbf{q}_2\\  \mathbf{x}_3&=r_{13}\mathbf{q}_1+r_{23}\mathbf{q}_2+r_{33}\mathbf{q}_3.\end{aligned}

利用 \{\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3\} 的單範正交性質,組合權重 r_{ij} 即為 \mathbf{q}_i\mathbf{x}_j 的內積,r_{ij}=\mathbf{q}_i^T\mathbf{x}_j,例如,

\begin{aligned} \mathbf{q}_2^T\mathbf{x}_3&=\mathbf{q}_2^T(r_{13}\mathbf{q}_1+r_{23}\mathbf{q}_2+r_{33}\mathbf{q}_3)=r_{23}\mathbf{q}_2^T\mathbf{q}_2=r_{23}\end{aligned}

將前述方程組寫成矩陣形式即得到著名的 QR 分解式:

\begin{aligned} A&=\begin{bmatrix}  \mathbf{x}_1&\mathbf{x}_2&\mathbf{x}_3  \end{bmatrix}\\ &=\begin{bmatrix}  \mathbf{q}_1&\mathbf{q}_2&\mathbf{q}_3  \end{bmatrix}\begin{bmatrix}  r_{11}&r_{12}&r_{13}\\  0&r_{22}&r_{23}\\  0&0&r_{33}  \end{bmatrix}\\  &=\begin{bmatrix}  \mathbf{q}_1&\mathbf{q}_2&\mathbf{q}_3  \end{bmatrix}\begin{bmatrix}  \mathbf{q}_1^T\mathbf{x}_1&\mathbf{q}_1^T\mathbf{x}_2&\mathbf{q}_1^T\mathbf{x}_3\\  0&\mathbf{q}_2^T\mathbf{x}_2&\mathbf{q}_2^T\mathbf{x}_3\\  0&0&\mathbf{q}_3^T\mathbf{x}_3  \end{bmatrix}\\ &=QR.\end{aligned}

因為 \mathbf{y}_i=\Vert\mathbf{y}_i\Vert\mathbf{q}_i\mathbf{q}_i\perp\hbox{span}\{\mathbf{y}_1,\ldots,\mathbf{y}_{i-1}\},主對角元 r_{ii} 亦可表示為

\begin{aligned} r_{ii}&=\mathbf{q}_i^T\mathbf{x}_i=\mathbf{q}_i^T\mathbf{y}_i=\mathbf{q}_i^T(\Vert\mathbf{y}_i\Vert\mathbf{q}_i)=\Vert\mathbf{y}_i\Vert\end{aligned}

 
下面用一個例子來說明 Gram-Schmidt 正交化演算程序,考慮

A=\left[\!\!\begin{array}{rrr}  1&2&-1\\  1&-1&2\\  -1&1&1\\  1&-1&2  \end{array}\!\!\right]

矩陣 A 的行向量 (column vector) 就是 \mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3,下面用演算法形式記錄計算步驟。

1. 正交化:

\begin{aligned} \mathbf{y}_1&\leftarrow\mathbf{x}_1=\left[\!\!\begin{array}{r}  1\\  1\\  -1\\  1  \end{array}\!\!\right],~~\Vert\mathbf{y}_1\Vert=2\\  \mathbf{y}_2&\leftarrow\mathbf{x}_2-\displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\Vert\mathbf{y}_1\Vert^2}\mathbf{y}_1=\frac{3}{4}\left[\!\!\begin{array}{r}  3\\  -1\\  1\\  -1  \end{array}\!\!\right],~~\Vert\mathbf{y}_2\Vert=\frac{3\sqrt{3}}{2}\\  \mathbf{y}_3&\leftarrow\mathbf{x}_3-\frac{\mathbf{y}_1^T\mathbf{x}_3}{\Vert\mathbf{y}_1\Vert^2}\mathbf{y}_1-\frac{\mathbf{y}_2^T\mathbf{x}_3}{\Vert\mathbf{y}_2\Vert^2}\mathbf{y}_2=\begin{bmatrix}  0\\  1\\  2\\  1  \end{bmatrix},~~\Vert\mathbf{y}_3\Vert=\sqrt{6}.\end{aligned}

2. 單位化:

\begin{aligned} \mathbf{q}_1&\leftarrow\frac{\mathbf{y}_1}{\Vert\mathbf{y}_1\Vert}=\frac{1}{2}\left[\!\!\begin{array}{r}  1\\  1\\  -1\\  1  \end{array}\!\!\right]\\  \mathbf{q}_2&\leftarrow\frac{\mathbf{y}_2}{\Vert\mathbf{y}_2\Vert}=\frac{1}{2\sqrt{3}}\left[\!\!\begin{array}{r}  3\\  -1\\  1\\  -1  \end{array}\!\!\right]\\  \mathbf{q}_3&\leftarrow\frac{\mathbf{y}_3}{\Vert\mathbf{y}_3\Vert}=\frac{1}{\sqrt{6}}\begin{bmatrix}  0\\  1\\  2\\  1  \end{bmatrix}.\end{aligned}

合併結果便得到 Q 矩陣:

\begin{aligned} Q&=\displaystyle\begin{bmatrix}  \mathbf{q}_1&\mathbf{q}_2&\mathbf{q}_3  \end{bmatrix}=\left[\!\!\begin{array}{rrc}  \frac{1}{2}&\frac{3}{2\sqrt{3}}&0\\[0.3em]  \frac{1}{2}&-\frac{1}{2\sqrt{3}}&\frac{1}{\sqrt{6}}\\[0.3em]  -\frac{1}{2}&\frac{1}{2\sqrt{3}}&\frac{2}{\sqrt{6}}\\[0.3em]  \frac{1}{2}&-\frac{1}{2\sqrt{3}}&\frac{1}{\sqrt{6}}  \end{array}\!\!\right]\end{aligned}

R 矩陣的上三角元還需要耗費一些計算:

\begin{aligned} R&=\displaystyle\begin{bmatrix}  \Vert\mathbf{y}_1\Vert&\mathbf{q}_1^T\mathbf{x}_2&\mathbf{q}_1^T\mathbf{x}_3\\  0&\Vert\mathbf{y}_2\Vert&\mathbf{q}_2^T\mathbf{x}_3\\  0&0&\Vert\mathbf{y}_3\Vert  \end{bmatrix}=\left[\!\!\begin{array}{ccr}  2&-\frac{1}{2}&1\\[0.3em]  0&\frac{3\sqrt{3}}{2}&-\sqrt{3}\\  0&0&\sqrt{6}  \end{array}\!\!\right]\end{aligned}

 
上述實矩陣的 QR 分解可以推廣至廣義內積空間 \mathcal{V},作法是把幾何內積算式 \mathbf{x}^T\mathbf{y} 取代為廣義內積 \left\langle\mathbf{x},\mathbf{y}\right\rangle,將數字 3 代回 n,再加上一些「\cdots」即可。設 m\times n 階矩陣 A 包含 m 維線性獨立行向量 \mathbf{x}_1,\ldots,\mathbf{x}_n,其 QR 分解式為

\begin{aligned} A&=QR=\begin{bmatrix}  \mathbf{q}_1&\mathbf{q}_2&\cdots&\mathbf{q}_n  \end{bmatrix}\begin{bmatrix}  \Vert\mathbf{y}_1\Vert&\left\langle\mathbf{q}_1,\mathbf{x}_2\right\rangle&\cdots&\left\langle\mathbf{q}_1,\mathbf{x}_n\right\rangle\\  0&\Vert\mathbf{y}_2\Vert&\cdots&\left\langle\mathbf{q}_2,\mathbf{x}_n\right\rangle\\  \vdots&\vdots&\ddots&\vdots\\  0&0&\cdots&\Vert\mathbf{y}_n\Vert  \end{bmatrix}\end{aligned}

其中 m\times n 階矩陣 Q 包含單範正交的行向量,R 則為 n\times n 階上三角矩陣,主對角元的計算如下:\Vert\mathbf{y}_1\Vert=\Vert\mathbf{x}_1\Vert,當 i>1

\Vert\mathbf{y}_i\Vert=\Vert\mathbf{x}_i-\left\langle\mathbf{q}_1,\mathbf{x}_i\right\rangle\mathbf{q}_1-\cdots\left\langle\mathbf{q}_{i-1},\mathbf{x}_i\right\rangle\mathbf{q}_{i-1}\Vert

矩陣 A 的行空間與 Q 的行空間相等,可知 R 為可逆矩陣,也就是說 R 的主對角元皆不為零。

 
利用 QR 分解可化簡線性方程 A\mathbf{x}=\mathbf{b}。將 A=QR 代入前式,QR\mathbf{x}=\mathbf{b}。等號兩邊左乘 Q^{T},利用 Q^TQ=I_n,就有

R\mathbf{x}=Q^{T}\mathbf{b}

先算出 \mathbf{c}=Q^T\mathbf{b},再使用反向迭代即能解出 R\mathbf{x}=\mathbf{c}。讀者或許納悶:以高斯消去法解線性方程比 QR 分解簡單容易,何須如此費事呢?從表面上看,似乎如此。然而,在一些特定的問題中,QR 分解的精確度比高斯消去法高;另外,QR 分解有它自己的典型應用──解最小平方法。當方程式 A\mathbf{x}=\mathbf{b} 無解時,我們可以考慮它的最小平方近似解:

\displaystyle \min_{\mathbf{x}}\Vert A\mathbf{x}-\mathbf{b}\Vert^2

問題轉而求正規方程 A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b} 的解 (見“從線性變換解釋最小平方近似”)。若 \hbox{rank}A=n,即 m\times n 階矩陣 A 有線性獨立的行向量,將 A=QR 代入正規方程式,等號左邊是 A^TA\hat{\mathbf{x}}=(QR)^{T}QR\hat{\mathbf{x}}=R^TQ^TQR\hat{\mathbf{x}}=R^TR\hat{\mathbf{x}},等號右邊是 A^T\mathbf{b}=R^{T}Q^{T}\mathbf{b}。因為 R 是可逆的,R^TR\hat{\mathbf{x}}=R^TQ^T\mathbf{b} 左乘 (R^T)^{-1},即得等價的正規方程

R\hat{\mathbf{x}}=Q^T\mathbf{b}

這與之前化簡線性方程得到的式子相同。

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

5 Responses to Gram-Schmidt 正交化與 QR 分解

  1. d897203 說道:

    在將 x_3 寫成 y_1, y_2 和 y_3 的線性組合那一段,
    y_3 的係數好像有打錯字。

  2. 計組小粉絲 說道:

    明顯地,\mathbf{y}_1\perp\mathbf{y}_2。上式的扣除量 (投影量) 還有另一種表達方式,因為 \frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1} 是一個純量,利用矩陣乘法結合律可得

    \begin{aligned} \displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1&=\mathbf{y}_1\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}=\frac{1}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1\mathbf{y}_1^T\mathbf{x}_2=\frac{\mathbf{y}_1\mathbf{y}_1^T}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{x}_2\end{aligned}

    第三個式子的分母 y^T 和 y 忘了加上下標 “1″

  3. 計組小粉絲 說道:

    抱歉

    \begin{aligned} \displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1&=\mathbf{y}_1\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}=\frac{1}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1\mathbf{y}_1^T\mathbf{x}_2=\frac{\mathbf{y}_1\mathbf{y}_1^T}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{x}_2\end{aligned}

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s