格拉姆-施密特正交化

在線性代數中，如果內積空間上的一組向量能夠組成一個子空間，那麼這一組向量就稱為這個子空間的一個基。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}$上的投影

## 基本思想

<image>

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}$之差

$$<pre> \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正交化的過程如下：

$\boldsymbol{\beta}_1 = \boldsymbol{v}_1,$｜$\boldsymbol{\eta}_1 = {\boldsymbol{\beta}_1 \over \|\boldsymbol{\beta}_1\|}$

$\boldsymbol{\beta}_2 = \boldsymbol{v}_2-\langle \boldsymbol{v}_2, \boldsymbol{\eta}_1 \rangle \boldsymbol{\eta}_1,$｜$\boldsymbol{\eta}_2 = {\boldsymbol{\beta}_2 \over \|\boldsymbol{\beta}_2\|}$

$\boldsymbol{\beta}_3 = \boldsymbol{v}_3 - \langle \boldsymbol{v}_3, \boldsymbol{\eta}_1 \rangle \boldsymbol{\eta}_1 - \langle \boldsymbol{v}_3, \boldsymbol{\eta}_2 \rangle \boldsymbol{\eta}_2 ,$｜$\boldsymbol{\eta}_3 = {\boldsymbol{\beta}_3 \over \|\boldsymbol{\beta}_3\|}$

$\vdots$｜$\vdots$

$\boldsymbol{\beta}_n = \boldsymbol{v}_n-\sum_{i=1}^{n-1}\langle \boldsymbol{v}_n, \boldsymbol{\eta}_i \rangle \boldsymbol{\eta}_i,$｜$\boldsymbol{\eta}_n = {\boldsymbol{\beta}_n\over\|\boldsymbol{\beta}_n\|}$

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

例

考察如下歐幾里得空間Rn中向量的集合，歐氏空間上內積的定義為 = bTa：

$$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 = -\frac65 + \frac65 = 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正交化就具有不同的形式。

## 外部連結

- 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.