電子學考試解答

Wednesday, September 04, 2013

Quaternion Algebra

這篇文章想來介紹一個比較特殊的東西,稱為四元數代數(Quaternion Algebra)。在先前的一篇文章中(http://bossborot.blogspot.tw/2013/08/blog-post.html),曾經介紹過代數系統的概念,簡單的說就是一個具備"環"結構的向量空間(亦即兩個向量的"乘法"是有意義的),可以稱為代數。由向量空間的定義,不難發現,向量加法的反元素必定存在,因此在一個代數中,可以討論兩個向量之間的加法、減法以及乘法。但是"環"結構並未要求乘法的反元素必須存在,因此在一般的代數系統中,不一定可以定義一個"合法"的除法運算。若在代數系統中,可以定義合法的除法運算(或者說向量乘法的反元素存在),則稱此代數系統為"可除代數"(Division Algebra)。數學家告訴我們,這個世界上僅存在三個具備結合性(associative,亦即$(\mathbf{ab})\mathbf{c}=\mathbf{a}(\mathbf{bc})$,$\mathbf{a}, \mathbf{b}, \mathbf{c}$為向量 )的可除代數,其中兩個大家應該都很熟悉,就是所有實數的集合$\mathbb{R}$,以及所有複數的集合$\mathbb{C}$,第三個就是這裡要介紹的四元數代數。

實數$\mathbb{R}$是一個體(field,因此也具備環結構),也可以視為一個一維的向量空間,因此若定義向量加法與乘法分別為一般的實數加法與乘法,則$\mathbb{R}$是一個代數。又因為$\mathbb{R}$是一個體,所以所有非零元素的乘法反元素皆存在,因此$\mathbb{R}$是一個可除代數。同樣的道理,各位讀者應該不難理解$\mathbb{C}$也是一個可除代數,這裡的向量加法和乘法就是一般複數的的加法與乘法。更進一步地,有修過線性代數的同學,應該可以理解,$\mathbb{C}$是一個佈於$\mathbb{R}$上的二維向量空間,他的一組基底為$\{1, \mathtt{i} \}$,其中$\mathtt{i}$是複數符號,滿足$\mathtt{i}^2= -1$。從這個概念繼續延伸,如果要找三維空間的可除代數(數學家已經告訴我們,三維空間不存在可除代數,這邊先當做不知道這回事),很自然的我們應該會想用三個符號$\{1, \mathtt{i}, \mathtt{j}\}$,$\mathtt{j}$是一個新的符號,我們需要決定$\mathtt{j}$的性質,並且定義適當的乘法運算,使得\[S=\{a+b\mathtt{i}+c\mathtt{j}|a, b, c\in\mathbb{R}\}\]變成一個可除代數。對這個問題,最早發現僅用$\{1, \mathtt{i}, \mathtt{j}\}$無法得到可除代數,並且提出四元數概念的是William R. Hamilton(謎之音:「你是說曾經和Jordan一起在巫師隊打球的...」「那是Richard Hamilton」「那是曾經拿過打擊王的...」「那是Josh Hamilton」「賣手錶的....」「那是James Hamilton」「喔,所以是開車的那個...」「他叫Lewis Hamilton」)。既然Hamilton都這麼說了,我們就先不看三維的向量空間,直接來看四維的吧。

考慮如下列形式的數值:\[a+b\mathtt{i}+c\mathtt{j}+d\mathtt{k}, \,\,\, a, b, c, d\in\mathbb{R}, \]其中$\mathtt{i}, \mathtt{j}, \mathtt{k}$是三個選定的符號,這邊其實可以把它視為三維空間的三個單位向量也無妨。上述這種形式的數值,稱為四元數,可以想成是複數的延伸,在數學上也稱為超複數(Hypercomplex Number)。對任意的四元素$\mathbf{q} = a+b\mathtt{i}+c\mathtt{j}+d\mathtt{k}$, $\mathbf{q}_1 = a_1+b_1\mathtt{i}+c_1\mathtt{j}+d_1\mathtt{k}$, $\mathbf{q}_2 = a_2+b_2\mathtt{i}+c_2\mathtt{j}+d_2\mathtt{k}$,若定義向量加法為\[\mathbf{q}_1+\mathbf{q}_2 = (a_1+b_1\mathtt{i}+c_1\mathtt{j}+d_1\mathtt{k}) +(a_1+b_1\mathtt{i}+c_1\mathtt{j}+d_2\mathtt{k}) \\
=(a_1+a_2)+(b_1+b_2)\mathtt{i}+(c_1+c_2)\mathtt{j}+(d_1+d_2)\mathtt{k}), \]
以及純量乘法為:\[\alpha\mathbf{q} =\alpha a+\alpha b\mathtt{i}+\alpha c\mathtt{j}+\alpha d\mathtt{k}, \,\,\,\, \forall\alpha\in\mathbb{R},\]則不難證明,所有四元數所形成的集合,以$\mathbb{H}$表示,是一個四維的向量空間,且$\{1, \mathtt{i}, \mathtt{j}, \mathtt{k}\}$是$\mathbb{H}$的一組基底。更進一步地,若再定義$\mathtt{i}, \mathtt{j}, \mathtt{k}$的乘法滿足下列關係:\[\mathtt{i}^2=-1, \mathtt{j}^2=-1, \mathtt{k}^2=-1, \\
\mathtt{ij}=\mathtt{k},\mathtt{ji}=-\mathtt{k}, \\
\mathtt{jk}=\mathtt{i},\mathtt{kj}=-\mathtt{i}, \\
\mathtt{ki}=\mathtt{j},\mathtt{ik}=-\mathtt{j}. \]
利用上述規則,可以計算任意兩個四元數$\mathbf{q}_1 = a_1+b_1\mathtt{i}+c_1\mathtt{j}+d_1\mathtt{k}$, $\mathbf{q}_2 = a_2+b_2\mathtt{i}+c_2\mathtt{j}+d_2\mathtt{k}$,相乘所得到的結果為:\[\mathbf{q}_1\mathbf{q}_2 = (a_1a_2-b_1b_2-c_1c_2-d_1d_2) + (a_1b_2+b_1a_2+c_1d_2-d_1c_2)\mathtt{i} \\
 + (a_1c_2 + c_1a_2 + d_1b_2 - b_1d_2)\mathtt{j} + (a_1d_2 + d_1a_2 +b_1c_2 - c_1b_2)\mathtt{k}. \]不難驗證,上述的乘法滿足結合性,以及乘法對加法的分配性。因此,依據我們在"線性代數是甚麼?"這篇文章提到的定義,$\mathbb{H}$事實上是一個代數,也就是所謂的四元數代數(Quaternion Algebra),在力學以及導航系統系統中,有許多重要的應用。
















Wednesday, August 21, 2013

Kalman Filter (2)

接下來我們來看看當系統有雜訊時,如何設計觀測器。考慮如下所示之離散時間動態系統: \[ \begin{array}{rcl} {\bf x}(k+1) & = & {\bf F}(k){\bf x}(k)+{\bf G}(k){\bf u}(k)+{\bf w}(k) \\ {\bf y}(k) & = & {\bf H}(k){\bf x}(k)+{\bf v}(k) \end{array} \] 其中,${\bf x},{\bf y},{\bf u},{\bf F},{\bf G},{\bf H}$與前一篇文章中完全相同(參考Kalman Filter (1)),${\bf w}(k)$與${\bf v}(k)$為系統的雜訊干擾,在工程的應用上,一般可假設${\bf w}$與${\bf v}$為高斯雜訊。雜訊在工程上是以隨機程序來表示,可以想成是一個時間的函數,只是它的函數值無法確定,僅能用機率的方式來表示。

依據上一篇的概念,我們同樣試著設計一個觀測器如下:
\[ \begin{array}{rcl} \hat{\bf x}(k+1) & = & {\bf F}(k)\hat{\bf x}(k)+{\bf G}(k){\bf u}(k) + {\bf L}(k)({\bf y}(k)-\hat{\bf y}(k)) \\ \hat{\bf y}(k) & = & {\bf H}(k)\hat{\bf x}(k) \end{array} \] (備註:此處可以先令${\bf u}$為零,得到的結果是一樣的)其中$\hat{\bf x}$代表觀測器的狀態,用以估測實際的系統狀態${\bf x}$,${\bf L}$則是一個待決定的參數,稱為觀測器增益向量(observer gain vector)。這邊值得注意的是在觀測器中並沒有雜訊項,這是合理的,因為我們無從得知或者預測系統的雜訊是長成何種德性。同樣地,再依據上一篇的概念,定義觀測器誤差為:$\delta{\bf x}(k) := {\bf x} - \hat{\bf x}$,將前面的兩組方程式相減之後,可得到觀測誤差的動態方程式為:
\[ \delta{\bf x}(k+1) = ({\bf F}(k) - {\bf L}(k){\bf H}(k))\delta{\bf x}(k). \]上式很明顯應該會受到雜訊影響,但為了方便起見,我們省略掉雜訊項,或者說將雜訊的影響,包含在$\delta{\bf x}(k)$裡面,換句話說$\delta{\bf x}(k)$是一個隨機程序。接下來的問題一樣就是要選擇${\bf L}$使得$\delta{\bf x}$可以收斂,但是因為$\delta{\bf x}$是隨機程序,所以既使${\bf F}(k) - {\bf L}(k){\bf H}(k)$是穩定矩陣,也無法保證$\delta{\bf x}$會收斂(事實上在雜訊存在的情況下,$\delta{\bf x}$不可能收斂到零),是否有其他的性能指標,可以用來判斷觀測器的優劣。在這裡,Kalman想到的辦法就是選擇${\bf L}(k)$使得$\delta{\bf x}(k)$的協方差(covariance)為最小,也就是要選擇${\bf L}(k)$,使得\[ trace({\bf P}_k) = trace\left( E\left[\delta{\bf x}(k)\delta{\bf x}^T(k)\right]\right)\]
為最小;其中$trace(\cdot)$為矩陣的跡數,$E[\cdot]$表示期望值。將上面這個方程式對${\bf L}(k)$微分,並令微分結果為零,即可求出此最佳增益值,一般也稱為Kalman gain。這邊我們先暫時避開數學的推導,假設求得的增益值為$\hat{\bf L}(k)$,帶入觀測器之中得到的就是所謂的Kalman濾波器,\[ \begin{array}{rcl} \hat{\bf x}(k+1) & = & {\bf F}(k)\hat{\bf x}(k)+{\bf G}(k){\bf u}(k) + \hat{\bf L}(k)({\bf y}(k)-\hat{\bf y}(k)) \\ \hat{\bf y}(k) & = & {\bf H}(k)\hat{\bf x}(k) \end{array} \]也可將上述方程式改寫為:\[ \begin{array}{rcl} \hat{\bf x}(k+1) & = & {\bf F}(k)\hat{\bf x}(k)+ \hat{\bf L}(k){\bf e}(k)+{\bf G}(k){\bf u}(k)  \\ {\bf e}(k) & = & {\bf y}(k) - {\bf H}(k)\hat{\bf x}(k) \end{array} \] 其中,${\bf e}(k)$就是在估測理論中,非常有名的"innovation process"。

這裡介紹的是最基本Kalman濾波器(KF)的概念,這幾年來衍伸出各種不同的KF,例如AKF, EKF, UKF, 大KF, 小KF, 不大不小中KF等,雖然形式不同,但是本質上都是在設計一個濾波器,使得估測誤差$\delta{\bf x}(k)$的協方差為最小。




(待續)

Tuesday, August 13, 2013

線性代數是什麼?

線性代數和微積分應該可以說是一切數學的基礎,而由於數學在理工科系中佔有舉足輕重的地位,因此線性代數與微積分也成了多數理工科系的基礎課程。大多數同學大概都知道微積分在討論的是什麼,可是線性代數咧,線性代數到底是什麼?除了它的英文發音聽起來很像是在罵人之外。

我們其實從小學就開始在學"代數",例如整數、實數以及多項式等的四則運算,這些都屬於代數的範疇。從比較不專業的角度來看,只要是與數字的四則運算有關的數學,都可以説是"代數"。另一方面,有學過線性代數的同學應該知道,在線性代數中,一個重要的概念就是向量空間。這些東西湊在一起,可以説線性代數討論的就是向量空間裏面,向量的四則運算。這樣的定義還是有點籠統,或許可以從"稍微"數學一點的角度來定義"線性代數"。

數學上,通常將想要討論的對象收集起來,形成一個集合(Set),再搭配適當定義的二元運算(Binary Operation),即構成一個代數系統,可以說是一個具備特殊結構的集合。代數系統中,二元運算是一個重要的工具,我們先來看看如何定義二元運算。

定義1:假設$S$是一個非空集合,$S$上的一個二元運算 $\ast : S\times S\rightarrow S$ 是一個函數,其定義域為$S\times S$,值域為$S$,且$\ast$滿足:
\[ a\ast b\in S, \,\,\,\,\, \forall a, b \in S\]
亦即二元運算具備封閉性。

從上述定義,不難發現其實我們小時候學的加法、乘法就是一種二元運算。一個集合,搭配一個合法的二元運算,就構成一個代數系統 (algebraic systems),或者稱為代數結構 (algebraic structure)。

定義2:令$S$為一個非空集合,$\ast$是$S$上的一個二元運算,則稱$(S, \ast )$為一個代數系統或者代數結構。

若進一步地,該二元運算除了封閉性之外又滿足其他更多的性質,則賦予該代數結構不同的名稱。

定義3:令$S$為一個非空集合,$\ast$是$S$上的一個具有封閉性的二元運算。
(1) 若$\ast$具備結合性 (associative),亦即
\[a\ast (b\ast c) = (a\ast b)\ast c, \,\,\,\, \forall a, b, c\in S\]
則稱$(S,\ast )$為半群 (semigroup)。

(2) 若$\ast$具備結合性以及單位元素性,亦即
  • (結合性) $a\ast (b\ast c) = (a\ast b)\ast c,$ $\forall a, b, c\in S$。且,
  • (單位元素性) 對所有的$a\in S$,存在一個元素$e\in S$,使得$a\ast e = e\ast a = a$。(此時稱$e$為$(S, \ast )$的單位元素。)
則稱$(S,\ast )$為單群 (monoid)。

(3) 若$\ast$具備結合性、單位元素性以及反元素性,亦即
  • (結合性) $a\ast (b\ast c) = (a\ast b)\ast c,$ $\forall a, b, c\in S$。且,
  • (單位元素性) 對所有的$a\in S$,存在一個元素$e\in S$,使得$a\ast e = e\ast a = a$。以及,
  • (反元素性) 對任意的$a\in S$,存在$a'\in S$,使得$a\ast a' = a'\ast a = e$。(此時稱$S$具有反元素性,且稱$a'$為$a$的反元素。)
則稱$(S,\ast )$為群 (group)。

另一個重要的性質稱為交換性 (commutative),定義如下。

定義4:集合$S$上的二元運算$\ast$,若對所有的$a, b\in S$,滿足$a\ast b = b\ast a$,則稱$\ast$具備交換性。

一般而言,半群、單群或者群不一定具備交換性。若確實具備交換性,則分別稱為交換半群,交換單群以及交換群。

群可以說是最基本的代數結構,由群可以再延伸出各種更複雜的代數結構。群僅與一個二元運算有關,接下來我們要介紹更複雜的代數系統,稱為環 (ring),則是與兩個二元運算有關。這裡我們以$\ast$,以及$+$來表示這兩個二元運算,可以稱$\ast$為乘法運算,以及$+$為加法運算。

定義5:考慮一個非空集合$S$以及兩個二元運算$+$,以及$\ast$,分別稱為加法以及乘法運算。若$(S, +, \ast)$滿足:
  1. $(S, +)$為交換群;
  2. $(S, \ast)$為半群;
  3. $\ast$ 對 $+$ 具備分配性 (distributive),亦即對所有的$a, b, c\in S$,滿足$a\ast (b+c) = (a\ast b) + (a\ast c)$,且$(a+b)\ast c = (a\ast c)+(b\ast c)$。
則稱$(S, +, \ast )$為環。進一步地,若$\ast$也具備交換性,則稱為交換環。

由於$(S, +)$為交換群,因此具備加法單位元素以及反元素,加法單位元素記為$0$,對任意的$a\in S$,其加法反元素記作$-a$。接下來,介紹另一種結構,稱為體 (field),我們會用到一個符號,記作$S\backslash \{ 0 \}$,表示$S$集合中,排除掉$0$這個元素。

定義6:考慮一個非空集合$S$以及兩個二元運算$+$,以及$\ast$,分別稱為加法以及乘法運算。若$(S, +, \ast)$滿足:
  1. $(S, +)$為交換群;
  2. $(S\backslash\{ 0\}, \ast)$為交換群,$0$為加法單位元素;
  3. $\ast$ 對 $+$ 具備分配性 (distributive),亦即對所有的$a, b, c\in S$,滿足$a\ast (b+c) = (a\ast b) + (a\ast c)$,且$(a+b)\ast c = (a\ast c)+(b\ast c)$。
則稱$(S, +, \ast )$為體。

若我們將$+$,$\ast$定義唯一般的加法與乘法,不難發現,$(\mathbb{R}, +, \ast )$以及$(\mathbb{C}, +, \ast )$都是體,這兩個也是在數學上最常用的體。(註:$\mathbb{R}$, $\mathbb{C}$分別代表所有實數以及所有複數所形成的集合。)

接下來,我們來看向量空間 (vector space),這也是在線性代數中,最重要的一種代數結構。在向量空間中,我們討論的對象進一步變成兩個集合,以及兩個二元運算。

定義7:考慮兩個非空集合$\mathbb{F}$, $V$,以及兩個二元運算,$+: V\times V\rightarrow V$,$\bullet :\mathbb{F}\times V\rightarrow V$;其中,$\mathbb{F}$為一體,$\mathbb{F}$中的元素稱為純量 (scalar),$V$中的元素稱為向量(vector),$+$稱為向量加法 (vector addition),$\bullet$稱為純量積 (scalar multiplication)。向量加法與純量積具備封閉性,亦即對任意的$\mathbf{u}, \mathbf{v}\in V$,存在唯一的向量$\mathbf{u}+\mathbf{v}\in V$,以及對任意的$\alpha\in\mathbb{F}$與任意的$\mathbf{v}\in V$,存在唯一的向量$\alpha\bullet\mathbf{v}$(通常亦簡記為$\alpha\mathbf{v}$) $\in
V$。若$(V, +, \bullet)$滿足下列八個性質,則稱$(V, +, \bullet)$為佈於$\mathbb{F}$上的一個向量空間 ($V$ is a vector space over $\mathbb{F}$),或者也稱為線性空間。

  1. 對所有的$\mathbf{u}, \mathbf{v}\in V$,恆有$\mathbf{u}+\mathbf{v} = \mathbf{v}+\mathbf{u}$。
  2. 對任意的$\mathbf{u}, \mathbf{v}, \mathbf{w}\in V$,恆有$(\mathbf{u}+\mathbf{v})+\mathbf{w}=\mathbf{u}+(\mathbf{v}+\mathbf{w})$。
  3. 存在一個向量$\mathbf{0}\in V$,使得對所有的$\mathbf{v}\in V$,恆有$\mathbf{v}+ \mathbf{0} = \mathbf{0}+\mathbf{v} = \mathbf{v}$。此時稱$\mathbf{0}$為$V$中的零向量。
  4. 對任意的$\mathbf{v}\in V$,存在$\mathbf{x}\in V$,使得$\mathbf{v}+\mathbf{x} = \mathbf{x} + \mathbf{v} = \mathbf{0}$。此時稱$\mathbf{x}$為$\mathbf{v}$的加法反元素,記作$-\mathbf{v}$。
  5. 對任意的$\alpha\in\mathbb{F}$,以及所有的$\mathbf{u}, \mathbf{v}\in V$,恆有$\alpha (\mathbf{u}+\mathbf{v}) = \alpha\mathbf{u}+\alpha\mathbf{v}$。
  6. 對任意的$\alpha, \beta\in\mathbb{F}$,以及任意的$\mathbf{v}\in V$,恆有$(\alpha + \beta)\mathbf{v} = \alpha\mathbf{v} + \beta\mathbf{v}$。
  7. 對任意的$\alpha, \beta\in\mathbb{F}$,以及任意的$\mathbf{v}\in V$,恆有$(\alpha\beta)\mathbf{v} = \alpha (\beta\mathbf{v})$。
  8. 對每一個$\mathbf{v}\in V$,$1\bullet\mathbf{v} = 1\mathbf{v} = \mathbf{v}$,其中$1$為$\mathbb{F}$的乘法單位元素。


與前面的群結構比較之下,可以發現事實上$(V, +)$係一個滿足向量加法的交換群。這邊要特別注意,純量積與前面定義的環裡面的乘法運算不同。環裡面的乘法運算,兩個運算元都是取自同一個集合$S$,而向量空間裡面的純量積,運算元分別取自兩個不同的集合$\mathbb{F}$和$V$。這時候,或許讀者會發現一個問題:我是不是可以再定義一個向量乘法運算,使得$V$變成一個環呢?答案是肯定的,這時候$V$就變成一個"Algebra"也就是代數。換句話說,一個向量空間若同時又具備環的結構,就稱為一個代數。

定義8:假設$\mathbb{F}$為一體,$V$為非空集合,$+$以及$\ast$為$V$上的兩個二元運算,分別稱為向量加法以及向量乘法,$\bullet :\mathbb{F}\times V\rightarrow V$為純量積。若

  1. $(V, +, \ast )$為環;
  2. $(V, +, \bullet )$為佈於$\mathbb{F}$上的向量空間;
  3. 對任意的$\alpha\in\mathbb{F}$,以及任意的$\mathbf{u}, \mathbf{v}\in V$,恆有$\alpha (\mathbf{u}\ast\mathbf{v})$ = $(\alpha\mathbf{u})\ast\mathbf{v}$ = $ \mathbf{u}\ast(\alpha\mathbf{v})$。
則稱$(V, +, \ast , \bullet )$為佈於$\mathbb{F}$上的線性代數,或者簡稱為代數。

瞭解代數系統的含義之後,我們來看幾個在線性代數的書中,常用到的algebra。

範例1:令$\mathbb{R}^{n\times n}$表示所有$n\times n$的實數矩陣所形成的集合,若定義$+$, $\ast$分別為矩陣的一般加法與乘法,且定義$\bullet$為矩陣與實數的純量積。則$(\mathbb{R}^{n\times n}, +, \ast, \bullet)$為一個線性代數。

範例2:令$\mathcal{L}(\mathbb{F}^n)$表示所有從$\mathbb{F}^n$映射至$\mathbb{F}^n$的線性映射所形成的集合。定義$+$, $\circ$兩個二元運算如下:
\[ (T+U)(\mathbf{v}) := T(\mathbf{v}) + U(\mathbf{v}), \,\,\, \forall T, U\in \mathcal{L}(\mathbb{F}^n), \forall \mathbf{v}\in\mathbb{F}^n, \\
(T\circ U)(\mathbf{v}) := T(U(\mathbf{v})), \,\,\, \forall T, U\in \mathcal{L}(\mathbb{F}^n), \forall \mathbf{v}\in\mathbb{F}^n.  \]
且定義純量積$\bullet$為:
\[ (\alpha\bullet T)(\mathbf{v}) := \alpha T(\mathbf{v}), \,\,\, \forall T \in \mathcal{L}, \forall \alpha\in\mathbb{F}. \]
則$(\mathcal{L}(\mathbb{F}^n), +, \circ , \bullet )$構成一個線性代數。

大學一年級的線性代數課程,討論的就是矩陣以及線性映射這兩個線性代數。(這句話的結構很像"新阿姆斯特朗旋風噴射阿姆斯特朗砲")


寫的不是很專業,請各位讀者多多批評指教。