Gram-Schmidt正交化

在線性代數中，如果內積空間上的一組向量能夠組成一個子空間，那麼這一組向量就稱為這個子空間的一個基。**Gram－Schmidt 正交化**提供了一種方法，能夠通過這一子空間上的一個基得出子空間的一個正交基，並可進一步求出對應的標準正交基。

這種正交化方法以約爾根・佩德森・格拉姆和艾哈德・施密特命名，然而比他們更早的拉普拉斯（Laplace）和柯西（Cauchy）已經發現了這一方法。在李群分解中，這種方法被推廣為岩澤分解（Iwasawa decomposition）。

在數值計算中，Gram－Schmidt 正交化是數值不穩定的，計算中累積的捨入誤差會使最終結果的正交性變得很差。因此在實際應用中通常使用豪斯霍爾德轉換或 Givens 旋轉進行正交化。可以用於矩陣計算。

## 記法

 * ${\boldsymbol {V}}^{n}$ ：維數為 _n_ 的內積空間
* ${\boldsymbol {v}}\in {\boldsymbol {V}}^{n}$ ： ${\boldsymbol {V}}^{n}$ 中的元素，可以是向量、函數，等等
* $\langle {\boldsymbol {v}}_{1},{\boldsymbol {v}}_{2}\rangle $ ： ${\boldsymbol {v}}_{1}$ **與 ${\boldsymbol {v}}_{2}$ 的內積**
* $\mathrm {span} \{{\boldsymbol {v}}_{1},{\boldsymbol {v}}_{2},\ldots ,{\boldsymbol {v}}_{n}\}$ ： ${\boldsymbol {v}}_{1}$ 、 ${\boldsymbol {v}}_{2}$ …… ${\boldsymbol {v}}_{n}$ 張成的子空間
* $\mathrm {proj} _{\boldsymbol {v}}\,{\boldsymbol {u}}={\langle {\boldsymbol {u}},{\boldsymbol {v}}\rangle  \over \langle {\boldsymbol {v}},{\boldsymbol {v}}\rangle }{\boldsymbol {v}}$ ： ${\boldsymbol {u}}$ 在 ${\boldsymbol {v}}$ 上的投影

## 基本思想

Gram-Schmidt 正交化的基本想法，是利用投影原理在已有正交基的基礎上構造一個新的正交基。

設 ${\boldsymbol {v}}\in {\boldsymbol {V^{n}}}$ 。 ${\boldsymbol {V}}^{k}$ 是 ${\boldsymbol {V}}^{n}$ 上的 $k$ 維子空間，其標準正交基為 $\{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{k}\}$ ，且 ${\boldsymbol {v}}$ 不在 ${\boldsymbol {V}}^{k}$ 上。由投影原理知， ${\boldsymbol {v}}$ 與其在 ${\boldsymbol {V}}^{k}$ 上的投影 $\mathrm {proj} _{\boldsymbol {V^{k}}}{\boldsymbol {v}}$ 之差

　
: ${\boldsymbol {\beta }}={\boldsymbol {v}}-\sum _{i=1}^{k}\mathrm {proj} _{{\boldsymbol {\eta }}_{i}}\,{\boldsymbol {v}}={\boldsymbol {v}}-\sum _{i=1}^{k}\langle {\boldsymbol {v}},{\boldsymbol {\eta }}_{i}\rangle {\boldsymbol {\eta }}_{i}$

 
是正交於子空間 ${\boldsymbol {V}}^{k}$ 的，亦即 ${\boldsymbol {\beta }}$ 正交於 ${\boldsymbol {V}}^{k}$ 的正交基 ${\boldsymbol {\eta }}_{i}$ 。因此只要將 ${\boldsymbol {\beta }}$ 單位化，即

　
: ${\boldsymbol {\eta }}_{k+1}={\frac {\boldsymbol {\beta }}{\|{\boldsymbol {\beta }}\|}}={\frac {\boldsymbol {\beta }}{\sqrt {\langle {\boldsymbol {\beta }},{\boldsymbol {\beta }}\rangle }}}$

那麼 $\{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{k},{\boldsymbol {\eta }}_{k+1}\}$ 就是 ${\boldsymbol {V}}^{k}$ 在 ${\boldsymbol {v}}$ 上擴展的子空間 $\mathrm {span} \{{\boldsymbol {v}},{\boldsymbol {\eta }}_{1},...,{\boldsymbol {\eta }}_{k}\}$ 的標準正交基。

根據上述分析，對於向量組 $\{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{m}\}$ 張成的空間 ${\boldsymbol {V}}^{m}$ ( $m<n$ )，只要從其中一個向量（不妨設為 ${\boldsymbol {v}}_{1}$ ）所張成的一維子空間 $\mathrm {span} \{{\boldsymbol {v}}_{1}\}$ 開始（注意到 ${\boldsymbol {v}}_{1}$ 就是 $\mathrm {span} \{{\boldsymbol {v}}_{1}\}$ 的正交基），重複上述擴展構造正交基的過程，就能夠得到 ${\boldsymbol {V}}^{n}$ 的一組正交基。這就是 **Gram-Schmidt 正交化**。

## 算法

首先需要確定已有基底向量的順序，不妨設為 $\{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{n}\}$ 。Gram-Schmidt 正交化的過程如下：

這樣就得到 $\mathrm {span} \{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{n}\}$ 上的一組正交基 $\{{\boldsymbol {\beta }}_{1},\ldots ,{\boldsymbol {\beta }}_{n}\}$ ，以及相應的標準正交基 $\{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{n}\}$ 。

 

**例**

考察如下歐幾里得空間 **R**n 中向量的集合，歐氏空間上內積的定義為 <_**a**_, _**b**_> = _**b**_T_**a**_：

　
: $S=\lbrace {\boldsymbol {v}}_{1}={\begin{pmatrix}3\\1\end{pmatrix}},{\boldsymbol {v}}_{2}={\begin{pmatrix}2\\2\end{pmatrix}}\rbrace .$

下面作 Gram－Schmidt 正交化，以得到一組正交向量：

　
: ${\boldsymbol {\beta }}_{1}={\boldsymbol {v}}_{1}={\begin{pmatrix}3\\1\end{pmatrix}}$

　
: ${\boldsymbol {\beta }}_{2}={\boldsymbol {v}}_{2}-\mathrm {proj} _{{\boldsymbol {\beta }}_{1}}\,{\boldsymbol {v}}_{2}={\begin{pmatrix}2\\2\end{pmatrix}}-\mathrm {proj} _{\begin{pmatrix}3\\1\end{pmatrix}}\,{\begin{pmatrix}2\\2\end{pmatrix}}={\begin{pmatrix}-2/5\\6/5\end{pmatrix}}$

下面驗證向量 ${\boldsymbol {\beta }}_{1}$ 與 ${\boldsymbol {\beta }}_{2}$ 的正交性：

　
: $\langle {\boldsymbol {\beta }}_{1},{\boldsymbol {\beta }}_{2}\rangle =\left\langle {\begin{pmatrix}3\\1\end{pmatrix}},{\begin{pmatrix}-2/5\\6/5\end{pmatrix}}\right\rangle =-{\frac {6}{5}}+{\frac {6}{5}}=0.$

將這些向量單位化：

　
: ${\boldsymbol {\eta }}_{1}={1 \over {\sqrt {10}}}{\begin{pmatrix}3\\1\end{pmatrix}}$

　
: ${\boldsymbol {\eta }}_{2}={1 \over {\sqrt {8 \over 5}}}{\begin{pmatrix}-2/5\\6/5\end{pmatrix}}$

於是 $\{{\boldsymbol {\eta }}_{1},{\boldsymbol {\eta }}_{2}\}$ 就是 $\mathrm {span} \{{\boldsymbol {v}}_{1},{\boldsymbol {v}}_{2}\}$ 的一組標準正交基底。

## 不同的形式

隨著內積空間上內積的定義以及構成內積空間的元素的不同，Gram-Schmidt 正交化也表現出不同的形式。

例如，在實向量空間上，內積定義為：

　
: $\langle {\boldsymbol {a}},{\boldsymbol {b}}\rangle ={\boldsymbol {b}}^{T}{\boldsymbol {a}}$

在複向量空間上，內積定義為：

　
: $\langle {\boldsymbol {a}},{\boldsymbol {b}}\rangle ={\boldsymbol {b}}^{H}{\boldsymbol {a}}$

函數之間的內積則定義為：

　
: $\langle f(x),g(x)\rangle =\int _{-\infty }^{\infty }f(x)g(x)dx$

與之對應，相應的 Gram－Schmidt 正交化就具有不同的形式。

## 參見

* 內積空間
* 內積
* 正交
* QR 分解

## 外部連結

* Hazewinkel, Michiel (編), Orthogonalization, 数学百科全书，Springer, 2001, ISBN 978-1-55608-010-4
* Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm
* Earliest known uses of some of the words of mathematics: G （頁面存檔備份，存於網際網路檔案館）
* Demos: Gram Schmidt process in plane and Gram Schmidt process in space
* Gram-Schmidt orthogonalization applet （頁面存檔備份，存於網際網路檔案館）
* NAG Gram–Schmidt orthogonalization of n vectors of order m routine （頁面存檔備份，存於網際網路檔案館）
* Proof: Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org. （頁面存檔備份，存於網際網路檔案館）