格拉姆-施密特正交化

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

線性代數
${\displaystyle \mathbf {A} ={\begin{bmatrix}1&2\\3&4\end{bmatrix}}}$
向量 · 向量空間 · 基底  · 行列式  · 矩陣
向量 純量 · 向量 · 向量空間 · 向量投影 · 外積（叉積 · 七維叉積） · 內積（點積） · 二重向量 矩陣與行列式 矩陣 · 行列式 · 線性方程組 · 秩 · 核 · 跡 · 單位矩陣 · 初等矩陣 · 方塊矩陣 · 分塊矩陣 · 三角矩陣 · 非奇異方陣 · 轉置矩陣 · 逆矩陣 · 對角矩陣 · 可對角化矩陣 · 對稱矩陣 · 反對稱矩陣 · 正交矩陣 · 么正矩陣 · 埃爾米特矩陣 · 反埃爾米特矩陣 · 正規矩陣 · 伴隨矩陣 · 餘因子矩陣 · 共軛轉置 · 正定矩陣 · 冪零矩陣 · 矩陣分解 （LU分解 · 奇異值分解 · QR分解 · 極分解 · 特徵分解） · 子式和餘子式 · 拉普拉斯展開 · 克羅內克積 線性空間與線性轉換 線性空間 · 線性轉換 · 線性子空間 · 線性生成空間 · 基 · 線性映射 · 線性投影 · 線性無關 · 線性組合 · 線性泛函 · 行空間與列空間 · 對偶空間 · 正交 · 特徵向量 · 最小平方法 · 格拉姆-施密特正交化
閱 論 編

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

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

記法

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

基本思想

圖1 ${\displaystyle {\boldsymbol {v}}}$在${\displaystyle {\boldsymbol {V}}^{2}}$上投影，構造${\displaystyle {\boldsymbol {V}}^{3}}$上的正交基${\displaystyle {\boldsymbol {\beta }}}$

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

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

${\displaystyle {\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}}$

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

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

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

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

算法

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

	${\displaystyle {\boldsymbol {\beta }}_{1}={\boldsymbol {v}}_{1},}$		${\displaystyle {\boldsymbol {\eta }}_{1}={{\boldsymbol {\beta }}_{1} \over \|{\boldsymbol {\beta }}_{1}\|}}$
	${\displaystyle {\boldsymbol {\beta }}_{2}={\boldsymbol {v}}_{2}-\langle {\boldsymbol {v}}_{2},{\boldsymbol {\eta }}_{1}\rangle {\boldsymbol {\eta }}_{1},}$		${\displaystyle {\boldsymbol {\eta }}_{2}={{\boldsymbol {\beta }}_{2} \over \|{\boldsymbol {\beta }}_{2}\|}}$
	${\displaystyle {\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},}$		${\displaystyle {\boldsymbol {\eta }}_{3}={{\boldsymbol {\beta }}_{3} \over \|{\boldsymbol {\beta }}_{3}\|}}$
	${\displaystyle \vdots }$		${\displaystyle \vdots }$
	${\displaystyle {\boldsymbol {\beta }}_{n}={\boldsymbol {v}}_{n}-\sum _{i=1}^{n-1}\langle {\boldsymbol {v}}_{n},{\boldsymbol {\eta }}_{i}\rangle {\boldsymbol {\eta }}_{i},}$		${\displaystyle {\boldsymbol {\eta }}_{n}={{\boldsymbol {\beta }}_{n} \over \|{\boldsymbol {\beta }}_{n}\|}}$

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

例

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle \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.}$

將這些向量單位化：

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

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

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

不同的形式

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

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

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

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

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

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

${\displaystyle \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. （頁面存檔備份，存於互聯網檔案館）