Gram-Schmidt 正交化與 QR 分解

本文的閱讀等級：初級

令 $\mathcal{X}$ 為幾何向量空間 $\mathbb{R}^{m}$ 的一個子空間， $\dim\mathcal{X}=n$ ， $n\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=0$ ， $i\neq j$ 。底下先考慮實幾何向量空間，隨後再推廣至一般內積空間 (見“內積的定義”，“從幾何向量空間到函數空間”)。

Jørgen Pedersen Gram (1850-1916) From http://upload.wikimedia.org/wikipedia/commons/a/ab/Jorgen_Gram.jpg

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

正交化：對於 $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=0$ ， $i\neq j$ 。
單位化：伸縮 $\{\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\}$ 。

Erhard Schmidt (1876-1959) From http://www-history.mcs.st-andrews.ac.uk/BigPictures/Schmidt_2.jpeg

下面我採用歸納法推導從給定的一組基底 $\{\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}_3$ 至 $Y$ 的行空間 $\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\Vert$ ， $i=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}$ 。

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

繼續閱讀：

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

d897203 says:

05/17/2015 at 11:45 pm

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

- ccjou says:
  
  05/18/2015 at 8:25 am
  
  謝謝，已訂正。
  
計組小粉絲 says:

01/03/2017 at 10:35 am

明顯地，\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”

計組小粉絲 says:

01/03/2017 at 10:41 am

抱歉
是
$\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}$

- ccjou says:
  
  01/03/2017 at 12:03 pm
  
  謝謝指正，已修訂。
  
bao says:

11/25/2017 at 5:42 pm

老师好，r(i,i) 推导的第二等号没懂？

- 牟家宏 says:
  
  10/14/2022 at 5:09 pm
  
  This is my two cents, we start from:
  x1 = y1;
  x2 = x2 of y1 + y2
  x3 = x3 of y1 + x3 of y2 + y3
  
  As you can see, x is y when they are representing the same vector;
  that is how we can have x(i)=y(i);

	Alexander Lin on 矩陣的四個基本子空間基底算法
	snowmanfat (@snowman… on 基底變換
	snowmanfat (@snowman… on 基底變換
	王偉 on Givens 旋轉於 QR 分解的應用
	猜猜看、 on 分塊矩陣的行列式
	牟家宏 on Gram-Schmidt 正交化與 QR 分解