[線性代數] Orthonormal Basis 與 Gram-Schmidt Process (1)

延續前篇 [線性代數] Orthonormal Basis 與 Gram-Schmidt Process (0) 的問題，以下我們正式引入 Gram-Schmidt Process


Theorem: Gram-Schmidt Process
令 $V$ 為 有限維度內積空間 且 令 $W\neq \{ {\bf 0}\}$ 為 $V$中的 $m$-維子空間。則此子空間 $W$ 存在一組正交基底 $T =\{{\bf w}_1,...{\bf w}_m\}$

Proof:
我們首先建構一組 orthogonal basis $T^* :=\{{\bf v}_1,{\bf v}_2...,{\bf v}_m\}$ for $W$。由於 $W$ 為 $V$ 的子空間，故我們可在 $W$ 其上選取一組基底，令 $S=\{{\bf u}_1,...,{\bf u}_m\} $ 接著我們選取其中任意一個向量，比如說 ${\bf u}_1 \in S$ 並稱此向量為 ${\bf v}_1$ 亦即我們重新定義
\[
{\bf v}_1 := {\bf u}_1
\]注意到此 ${\bf v}_1 \in  W_1:=span\{ v_1 \}$ 其中 $W_1$ 為 $W$ 的子空間

接著我們要尋找 ${\bf v}_2$，我們希望此向量 ${\bf v}_2$ 落在 $W$ 子空間 $W_2 = span\{ {\bf u}_1, {\bf u}_2\} $ 且 ${\bf v}_2$ 與 ${\bf v}_1$ 彼此 orthogonal。但注意到我們有 ${\bf v}_1 := {\bf u}_1 $ 故 ${\bf v}_2  \in W_2 = span\{ {\bf u}_1 , {\bf u}_2\}  =  span\{ {\bf v}_1, {\bf u}_2\} $  也就是說 ${\bf v}_2$ 可透過 ${\bf v}_1$ 與 ${\bf u}_2$ 做線性組合
\[
{\bf v}_2 = a_1 {\bf v}_1 + a_2 {\bf u}_2
\]其中 $a_1, a_2$ 待定。 注意到由於我們要讓 ${\bf v}_2$ 與 ${\bf v}_1$ 彼此 orthogonal 故 $\langle {\bf v}_2, {\bf v}_1 \rangle = 0$ 故現在觀察
\[\begin{array}{l}
\langle {{\bf{v}}_2},{{\bf{v}}_1}\rangle  = 0\\
 \Rightarrow \langle {a_1}{{\bf{v}}_1} + {a_2}{{\bf{u}}_2},{{\bf{v}}_1}\rangle  = 0\\
 \Rightarrow {a_1}\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle  + {a_2}\langle {{\bf{u}}_2},{{\bf{v}}_1}\rangle  = 0\\
 \Rightarrow {a_1} =  - {a_2}\frac{{\langle {{\bf{u}}_2},{{\bf{v}}_1}\rangle }}{{\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle }} \;\;\;\; (*)
\end{array}\]注意到上式中 $\langle {\bf v}_1, {\bf v}_2 \rangle \neq 0$ 因為 ${\bf v}_1 = {\bf u}_1 \in S$ 且 $S$ 為 非零子空間 $W$ 的基底 。注意到 $(*)$ 為一條方程式兩個未知數 $a_1,a_2$ 故可任意令 $a_2 \in \mathbb{R}^1$ 為自由變數解得 $a_1$ 。為了計算方便起見我們選 $a_2 :=1$ 則
\[{a_1} =  - \frac{{\langle {{\bf{u}}_2},{{\bf{v}}_1}\rangle }}{{\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle }}
\]此說明了
\[\begin{array}{l}
{{\bf{v}}_2} = {a_1}{{\bf{v}}_1} + {a_2}{{\bf{u}}_2}\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} =  - \frac{{\langle {{\bf{u}}_2},{{\bf{v}}_1}\rangle }}{{\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle }}{{\bf{v}}_1} + {{\bf{u}}_2} = {{\bf{u}}_2} - \frac{{\langle {{\bf{u}}_2},{{\bf{v}}_1}\rangle }}{{\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle }}{{\bf{v}}_1}
\end{array}\]至此我們有了一組 orthogonal subset $\{{\bf v}_1, {\bf v}_2\}$ for $W$。

接著我們尋找 ${\bf v}_3 \in W_3 := span\{{\bf u}_1, {\bf u}_2, {\bf u}_3\}$ 且 ${\bf v}_3$ 與 ${\bf v}_1, {\bf v}_2$ 為 orthogonal。注意到
\[{W_3}: = span\{ {{\bf{u}}_1},{{\bf{u}}_2},{{\bf{u}}_3}\}  = span\{ {{\bf{v}}_1},{{\bf{v}}_2},{{\bf{u}}_3}\} \]故
\[\begin{array}{l}
{{\bf{v}}_3} \in span\{ {{\bf{v}}_1},{{\bf{v}}_2},{{\bf{u}}_3}\} \\
 \Rightarrow {{\bf{v}}_3} = {b_1}{{\bf{v}}_1} + {b_2}{{\bf{v}}_2} + {b_3}{{\bf{u}}_3}
\end{array}\]且又因為我們要求  ${\bf v}_3$ 與 ${\bf v}_1, {\bf v}_2$ 為 orthogonal故
\[\begin{array}{l}
{{\bf{v}}_3},{{\bf{v}}_1}\rangle  = 0\\
 \Rightarrow \langle {b_1}{{\bf{v}}_1} + {b_2}{{\bf{v}}_2} + {b_3}{{\bf{u}}_3},{{\bf{v}}_1}\rangle  = 0\\
 \Rightarrow {b_1}\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle  + {b_2}\langle {{\bf{v}}_2},{{\bf{v}}_1}\rangle  + {b_3}\langle {{\bf{u}}_3},{{\bf{v}}_1}\rangle  = 0\\
\\
\langle {{\bf{v}}_3},{{\bf{v}}_2}\rangle  = 0\\
 \Rightarrow \langle {b_1}{{\bf{v}}_1} + {b_2}{{\bf{v}}_2} + {b_3}{{\bf{u}}_3},{{\bf{v}}_2}\rangle  = 0\\
 \Rightarrow {b_1}\langle {{\bf{v}}_1},{{\bf{v}}_2}\rangle  + {b_2}\langle {{\bf{v}}_2},{{\bf{v}}_2}\rangle  + {b_3}\langle {{\bf{u}}_3},{{\bf{v}}_2}\rangle  = 0
\end{array}\]也就是說我們有一組聯立方程
\[\begin{array}{l}
\left\{ {\begin{array}{*{20}{l}}
{\langle {{\bf{v}}_3},{{\bf{v}}_1}\rangle  = 0}\\
{\langle {{\bf{v}}_3},{{\bf{v}}_2}\rangle  = 0}
\end{array}} \right.\\
 \Rightarrow \left\{ {\begin{array}{*{20}{l}}
{{b_1}\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle  + {b_2}\underbrace {\langle {{\bf{v}}_2},{{\bf{v}}_1}\rangle }_{ = 0} + {b_3}\langle {{\bf{u}}_3},{{\bf{v}}_1}\rangle  = 0}\\
{{b_1}\underbrace {\langle {{\bf{v}}_1},{{\bf{v}}_2}\rangle }_{ = 0} + {b_2}\langle {{\bf{v}}_2},{{\bf{v}}_2}\rangle  + {b_3}\langle {{\bf{u}}_3},{{\bf{v}}_2}\rangle  = 0}
\end{array}} \right.\\
 \Rightarrow \left\{ {\begin{array}{*{20}{l}}
{{b_1}\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle  + {b_3}\langle {{\bf{u}}_3},{{\bf{v}}_1}\rangle  = 0}\\
{{b_2}\langle {{\bf{v}}_2},{{\bf{v}}_2}\rangle  + {b_3}\langle {{\bf{u}}_3},{{\bf{v}}_2}\rangle  = 0}
\end{array}} \right.
\end{array}\]注意到 ${\bf v}_2 \neq {\bf 0}$ 因為 ${\bf v}_2$ 需與 ${\bf v}_1$ 正交，故兩條方程三個未知數 $b_1,b_2,b_3$，可指定一自由變數，故選 $b_3 :=1 \in \mathbb{R}^1$ 則我們可解得 $b_1, b_2$ 如下
\[\left\{ {\begin{array}{*{20}{l}}
{{b_1} =  - \frac{{\langle {{\bf{u}}_3},{{\bf{v}}_1}\rangle }}{{\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle }}}\\
{{b_2} =  - \frac{{\langle {{\bf{u}}_3},{{\bf{v}}_2}\rangle }}{{\langle {{\bf{v}}_2},{{\bf{v}}_2}\rangle }}}
\end{array}} \right.\]
也就是說
\[\begin{array}{l}
{{\bf{v}}_3} = {b_1}{{\bf{v}}_1} + {b_2}{{\bf{v}}_2} + {b_3}{{\bf{u}}_3}\\
 \Rightarrow {{\bf{v}}_3} =  - \frac{{\langle {{\bf{u}}_3},{{\bf{v}}_1}\rangle }}{{\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle }}{{\bf{v}}_1} - \frac{{\langle {{\bf{u}}_3},{{\bf{v}}_2}\rangle }}{{\langle {{\bf{v}}_2},{{\bf{v}}_2}\rangle }}{{\bf{v}}_2} + {{\bf{u}}_3}\\
 \Rightarrow {{\bf{v}}_3} = {{\bf{u}}_3} - \frac{{\langle {{\bf{u}}_3},{{\bf{v}}_1}\rangle }}{{\langle {{\bf{v}}_1},{{\bf{v}}_1}\rangle }}{{\bf{v}}_1} - \frac{{\langle {{\bf{u}}_3},{{\bf{v}}_2}\rangle }}{{\langle {{\bf{v}}_2},{{\bf{v}}_2}\rangle }}{{\bf{v}}_2}
\end{array}
\]至此我們有了一組 orthogonal subset $\{{\bf v}_1,{\bf v}_2,{\bf v}_3\} $ for $W$

重複上述步驟 (by induction)我們可建構一組 orthogonal basis $T^* :=\{{\bf v}_1,{\bf v}_2,...,{\bf v}_m\}$ 最後我們對每一組 ${\bf v}_i$ 做正規化，定義
\[
{\bf w}_i := \frac{1}{||{\bf v}_i||} {\bf v}_i
\]則我們得到一組 orthonormal basis $T := \{{\bf w}_1,...,{\bf w}_m\}$

讀者可用以下幾個例子做練習

Example 1: 令 $S=\{[1\;\;2]^T, [-3\;\;4]^T\}$ 為 ordered basis for $ V:= \mathbb{R}^2$ 且其上內積為標準內積。
(a) 試利用 Gram-Schmidt process 找出 orthogonal basis
(b) 試利用 Gram-Schmidt process 找出 orthonormal basis

Example 2: 令 $V := P_3$ 且其上的內積定義為
\[
\langle p(t), q(t) \rangle := \int_0^1 p(t) q(t) dt
\] 現在令 $W$ 為 $P_3$ 子空間且基底為 $\{t,t^2\}$ 試求 orthonormal basis for $W$

[線性代數] Orthonormal Basis 與 Gram-Schmidt Process (0)

首先引入 一組向量彼此互為標準正交的定義

===================
Definition: Orthonormal Set
令 $V$ 為有限維度的內積空間 且 令 $S$ 為 $V$ 上的一組 集合滿足 $S =\{{\bf v}_1,..{\bf v}_n\}$ 。則我們稱 $S$ 為 orthonormal set 若
\[\left\langle {{{\bf{v}}_i},{{\bf{v}}_j}} \right\rangle  = \left\{ \begin{array}{l}
0\begin{array}{*{20}{c}}
{}&{}
\end{array}i \ne j\\
1\begin{array}{*{20}{c}}
{}&{}
\end{array}i = j
\end{array} \right.\]其中 $\left\langle {{{\bf{v}}_i},{{\bf{v}}_j}} \right\rangle $ 為 $V$ 上的內積運算。
====================

Comment:
1. 給定一個向量空間我們如果有 orthonormal basis 則其上的任意向量將可以被非常容易地表示 (why?) 比如說我們考慮 $V:= \mathbb{R}^2$ 且 具備一組標準基底 $S:=\{{\bf s}_1, {\bf s}_2\} = \{[1 \;0]^T, [0\;1]^T\}$ 則此基底為 orthonormal 。現在若給訂任意向量 ${\bf v} := [100, -99]^T\in V$ 則此向量可以非常容易透過 基底 $S$ 做線性組合來組出 ${\bf v}$亦即
\[\underbrace {\left[ \begin{array}{l}
100\\
 - 99
\end{array} \right]}_{ = {\bf{v}}} = 100\underbrace {\left[ \begin{array}{l}
1\\
0
\end{array} \right]}_{ = {{\bf{s}}_1}} + \left( { - 99} \right)\underbrace {\left[ \begin{array}{l}
0\\
1
\end{array} \right]}_{ = {{\bf{s}}_2}}\]
2. 上述觀點事實上到無窮維仍然成立，也就是說我們可以將正交的概念推廣到函數空間上面，並且說明什麼叫做兩個"函數" 彼此正交。以下我們看個無窮維函數空間的例子：


Example (Infinite-dimension Case)
令 $V:= C[0, 2 \pi]$ 且配備內積 \[
(f(t),g(t)) := \frac{1}{2 \pi}\int_0^{2 \pi} f(t) \bar{g} (t) dt
\]則 下列集合
\[
S :=\{f_n(t): f_n(t) := e^{jnt} =\cos nt + j \sin nt, \; n \in \mathbb{Z}\}
\]為 orthonormal set
Proof:
取 $f_n(t), g_m(t) \in S$ 觀察
\[\begin{array}{l}
({f_n}(t),{g_m}(t)) = \frac{1}{{2\pi }}\int_0^{2\pi } {{f_n}} (t){{\bar g}_m}(t)dt\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \frac{1}{{2\pi }}\int_0^{2\pi } {{e^{jnt}}} {e^{ - jmt}}dt\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \frac{1}{{2\pi }}\int_0^{2\pi } {{e^{j\left( {n - m} \right)t}}} dt\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \frac{1}{{2\pi }}\int_0^{2\pi } {\left[ {\cos \left( {\left( {n - m} \right)t} \right) + j\sin \left( {\left( {n - m} \right)t} \right)} \right]} dt\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \frac{1}{{2\pi }}\int_0^{2\pi } {\cos \left( {\left( {n - m} \right)t} \right)} dt + \frac{j}{{2\pi }}\int_0^{2\pi } {\sin \left( {\left( {n - m} \right)t} \right)} dt\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \left\{ \begin{array}{l}
1,\begin{array}{*{20}{c}}
{}&{}
\end{array}n = m\\
0,\begin{array}{*{20}{c}}
{}&{}
\end{array}n \ne m
\end{array} \right. \;\;\;\;\;\;\;\;\; \square
\end{array}\]

=====================
Definition: Orthonormal Basis
若 $S$ 為 內積空間$V$上的一組有序基底，且 $S$ 為 orthnormal set 則我們稱此 $S$ 為 Orthnormal basis。
=====================

以下定理給出了 orthonormal basis 可以快速決定任意向量用該基底做線性組合的係數。

====================
Theorem: 
令 $S = \{{\bf u}_1, {\bf u}_2,...,{\bf u}_n\}$ 為一組 orthonormal basis 對有限維度向量空間 $V$ 且令 ${\bf v} \in V$ 則
\[
{\bf v} = c_1{\bf u}_1 + c_2 {\bf u}_2 + ... + c_n {\bf u}_n
\]其中 $c_i = \left \langle {\bf v}, {\bf u}_i \right \rangle \;\;\;\; \forall i=1,2,...,n$
====================

Comment:
上述定理中提及的 $c_i = \left \langle {\bf v}, {\bf u}_i \right \rangle$ 在幾何意義上為 ${\bf v}$ 在 ${\bf u}_i$ 上的分量，且 $c_i$ 在數學上又稱為 Fourier Coefficient


以下我們給出證明：

Proof:
由於 ${\bf v} \in V$故此向量 ${\bf v}$ 可透過 $V$ 上的基底作唯一線性組合表示。
\[
{\bf v} = c_1{\bf u}_1 + c_2 {\bf u}_2 + ... + c_n {\bf u}_n
\]
故我們只需證明 $c_i = \left \langle {\bf v}, {\bf u}_i \right \rangle \;\;\;\; \forall i=1,2,...,n$

現在固定任意 $i$ ，並且觀察
\[\begin{array}{l}
\left\langle {{\bf{v}},{{\bf{u}}_i}} \right\rangle  = \left\langle {{c_1}{{\bf{u}}_1} + {c_2}{{\bf{u}}_2} + ... + {c_n}{{\bf{u}}_n},{{\bf{u}}_i}} \right\rangle \\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \left\langle {{c_1}{{\bf{u}}_1},{{\bf{u}}_i}} \right\rangle  + \left\langle {{c_2}{{\bf{u}}_2},{{\bf{u}}_i}} \right\rangle  + ... + \left\langle {{c_i}{{\bf{u}}_i},{{\bf{u}}_i}} \right\rangle  + ... + \left\langle {{c_n}{{\bf{u}}_n},{{\bf{u}}_i}} \right\rangle \\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {c_1}\left\langle {{{\bf{u}}_1},{{\bf{u}}_i}} \right\rangle  + {c_2}\left\langle {{{\bf{u}}_2},{{\bf{u}}_i}} \right\rangle  + ... + {c_i}\left\langle {{{\bf{u}}_i},{{\bf{u}}_i}} \right\rangle  + ... + {c_n}\left\langle {{{\bf{u}}_n},{{\bf{u}}_i}} \right\rangle \\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {c_1}\underbrace {\left\langle {{{\bf{u}}_1},{{\bf{u}}_i}} \right\rangle }_{ = 0} + {c_2}\underbrace {\left\langle {{{\bf{u}}_2},{{\bf{u}}_i}} \right\rangle }_{ = 0} + ... + {c_i}\underbrace {\left\langle {{{\bf{u}}_i},{{\bf{u}}_i}} \right\rangle }_{ = 1} + ... + {c_n}\underbrace {\left\langle {{{\bf{u}}_n},{{\bf{u}}_i}} \right\rangle }_{ = 0}\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {c_i}
\end{array}
\]注意到上述結果使用了 $S$ 基底為 orthonormal 故當 $i\neq j$ 時候， $\langle {\bf u_i}, {\bf u}_j\rangle =0$  $\square$

以下我們看個例子
Example 1:
令 $S = \{{\bf u}_1, {\bf u}_2\}$ 為 $\mathbb{R}^2$ 的一組基底，其中
\[{{\bf{u}}_1} = \frac{1}{\sqrt{2} }\left[ {\begin{array}{*{20}{c}}
1\\
1
\end{array}} \right];{{\bf{u}}_1} = \frac{1}{\sqrt{2}}\left[ {\begin{array}{*{20}{c}}
{ - 1}\\
1
\end{array}} \right]\]
(a) 確認 $S$ 為一組 orthonormal basis
(b) 令 ${\bf v} := [3\;\;4]^T$ 試決定其透過 $S$ 基底所構成的線性組合

Proof:
(a) 注意到 $\mathbb{R}^2$ 為內積空間，我們可在其上定義內積運算為
\[
\langle {\bf u}, {\bf v} \rangle := {\bf u}^T {\bf v}
\]
 現在我們檢驗內積 $\langle {\bf u}_1, {\bf u}_2 \rangle$
\[\langle {{\bf{u}}_1},{{\bf{u}}_2}\rangle  = \frac{1}{2} \left[ {\begin{array}{*{20}{c}}
1&1
\end{array}} \right] \left[ {\begin{array}{*{20}{c}}
{ - 1}\\
1
\end{array}} \right] = 0\]故此說明了 ${\bf u}_1, {\bf u}_2$ 為 orthogonal 接著我們驗證此基底具有 unit length
\[\left\| {{{\bf{u}}_1}} \right\| = \sqrt {\langle {{\bf{u}}_1},{{\bf{u}}_1}\rangle }  = 1;\begin{array}{*{20}{c}}
{}&{}
\end{array}\left\| {{{\bf{u}}_2}} \right\| = \sqrt {\langle {{\bf{u}}_2},{{\bf{u}}_2}\rangle }  = 1\]
綜上所述， $S$ 為 orthonormal basis。

(b) 現在令 ${\bf v}:= [3\;\;4]^T \in \mathbb{R}^2$ 故此向量可透過 $S$ 基底做線性組合表示
\[
{\bf v} = c_1 {\bf u}_1 + c_2 {\bf u}_2
\] 又因為 $S$ 為 orthonormal basis 故由前述定理可知 上式中的係數可透過內積求得
\[\begin{array}{l}
{c_1} = \langle {\bf{v}},{{\bf{u}}_1}\rangle  = {{\bf{v}}^T}{{\bf{u}}_1} = \left[ {\begin{array}{*{20}{c}}
3&4
\end{array}} \right]\left( {\frac{1}{\sqrt{2}}\left[ {\begin{array}{*{20}{c}}
1\\
1
\end{array}} \right]} \right) = \frac{7}{\sqrt{2}}\\
{c_2} = \langle {\bf{v}},{{\bf{u}}_2}\rangle  = {{\bf{v}}^T}{{\bf{u}}_2} = \left[ {\begin{array}{*{20}{c}}
3&4
\end{array}} \right]\left( {\frac{1}{\sqrt{2}}\left[ {\begin{array}{*{20}{c}}
{ - 1}\\
1
\end{array}} \right]} \right) = \frac{1}{\sqrt{2}}\;\;\;\;\; \square
\end{array}\]

現在我們可以考慮以下問題：
若給定一個有限維度向量空間 $V$ 伴隨一組基底 $S$。那麼我們想進一步詢問是否可從這組基底 $S$ 中找出另外一組基底 $T$ 且 $T$ 基底元素彼此互相正交 且 單位長度為 $1$ ? 亦即我們想問是否可以從一組不是 orthonormal basis $S$ 來建構一組 orthonormal basis $T$ ，答案是肯定的，此構造方法稱為 Gram-Schmidt Process 我們之後會再行介紹。