電子學考試解答

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 )$構成一個線性代數。

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


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