跳到主要內容

[線性代數] 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$

留言

這個網誌中的熱門文章

[數學分析] 淺談各種基本範數 (Norm)

這次要介紹的是數學上一個重要的概念:

Norm:一般翻譯成範數
(在英語中 norm 有規範的意思,比如我們說normalization就是把某種東西/物品/事件 做 正規化,也就是加上規範使其正常化),不過個人認為其實翻譯成 範數 也是看不懂的...這邊建議把 Norm 想成長度就好 (事實上norm是長度的抽象推廣),

也許讀者會認為好端端的長度不用,為何又要發明一個 norm 來自討苦吃?? 既抽象又艱澀。

事實上想法是這樣的:
比如說現在想要比較兩個數字 $3$ , $5$ 之間的大小,則我們可以馬上知道 $ 3 < 5 $;同樣的,如果再考慮小數與無理數如 $1.8753$ 與 $\pi$,我們仍然可以比較大小 $1.8753 < \pi = 3.1415...$ 故可以發現我們有辦法對 "純量" 做明確的比大小,WHY? 因為前述例子中 $3$, $5$, $1.8753$ or $\pi$ 其各自的大小有辦法被 "measure "!

但是如果是現在考慮的是一組數字 我們如何去measure 其大小呢?? 比如說
\[x:=[1, -2, 0.1, 0 ]^T
\]上式的大小該是多少? 是 $1$? $-2$? $0.1$???
再者如果更過分一點,我們考慮一個矩陣
\[A = \left[ {\begin{array}{*{20}{c}}
1&2\\
3&4
\end{array}} \right]
\],想要知道這個矩陣的大小又該怎麼辦?? 是 $1$ ? $2$ 還是 $4$ ?..其實現階段我們說不清楚。

也正是如此,可以發現我們確實需要新的 "長度" 的定義來幫助我們如何去 measure 矩陣/向量/甚至是函數的大小。

故此,我們首先定義甚麼是Norm,(也就是把 "長度" or "大小" 的本質抽離出來)

==================
Definition: Norm
考慮 $V$ 為一個向量空間(Vector space),則我們說  Norm 為一個函數 $||\cdot|| : V \rightarrow \mathbb{R}$ 且滿足下列性質:

(a) $||v|| \geq 0$, $||v||=…

[數學分析] 什麼是若且唯若 "if and only if"

數學上的 if and only if
 (此文不討論邏輯學中的 if and only if,只討論數學上的 if and only if。)

中文翻譯叫做 若且唯若 (or 當且僅當),記得當初剛接觸這個詞彙的時候,我是完全不明白到底是甚麼意思,查了翻譯也是愛莫能助,畢竟有翻跟沒翻一樣,都是有看沒有懂。

在數學上如果看到 if and only if  這類的句子,其實是表示一種雙條件句,通常可以直接將其視為"定義(Definition)"待之,今天要分享的是這樣的一個句子如何用比較直觀的方法去看他

假設我們現在有 兩個邏輯陳述句 A 與  B.
注意到,在此我們不必考慮這兩個陳述句到底是什麼,想表達什麼,或者到底是否為真(true),這些都不重要。只要知道是兩個陳述即可。

現在,考慮新的陳述:  "A if and only if B"
好了,現在主角登場,我們可以怎麼看待這個句子呢?
事實上我們可以很直覺的把這句子拆成兩部分看待,也就是
"( A if B ) and ( A only if B )"

那麼先針對第一個部分 A if B 來看,
其實這句就是說 if B then A,
更直白一點就是 "if B is true, then A is also true". 
在數學上等價可以寫為 "B implies A". 
或者更常用一個箭頭符號來表示 "B $\Rightarrow$  A" 

現在針對第二個部分 A only if B
此句意指 "If B is not true, then A is also not true".
所以如果已知 A is true, 那麼按照上句不難推得 B is also true
也就是說 A only if B 等價為 "If A is true then B is also true".
同樣,也可以寫作"A implies B"
或者用箭頭表示 "A $\Rightarrow$  B".

所以現在總結如下,下列七個 if and only if 陳述完全等價:

"A if and only if B" "A iff…