10/14/2012

[系統理論] 閉迴路系統的暫態響應 與 eigenvalue/eigenvector 關係

首先考慮  $n$階 線性微分方程如下
\[
\dot {\bf x}(t) = G{\bf x}(t); \;\; { \bf x}(0) ={\bf x}_0
\]上式一般表示為 無外力輸入 $u$ 的系統。且我們可對其求解得到
\[{\bf x}(t) = e^{Gt} {\bf x}_0 \ \ \ \ \ \ (*)
\] 我們可進一步將上式的解 $(*)$ 重新用 矩陣 $G$ 的 eigenvalues/eigenvectors 表示; i.e., 若 $G$ 為 $n \times n$ 則 下式 eigenvalue-eigenvector 關係需被滿足
\[G{{\bf{v}}_i} = {\lambda _i}{{\bf{v}}_i}, \text{ for $i=1,2,...,n$}
\]其中 $\lambda_i$ 為 $G$ 的 eigenvalues 且 $v_i$ 為對應的 eigenvectors。 注意到在此我們假設 $G$ 的 eigenvalues 均相異。現在使用這些 eigenvectors, $v_i$,建構  非奇異轉換矩陣 或稱 modal matrix  $M$ 如下
\[M: = \left[ {\begin{array}{*{20}{c}}
{{{\bf{v}}_1}}&{{{\bf{v}}_2}}& \cdots &{{{\bf{v}}_n}}
\end{array}} \right]
\]注意到 $M$ 為 nonsingular 因為 $\{v_i\}$ 彼此線性獨立 (因為相異 eigenvalue 對應 線性獨立的 eigenvector) ;現在使用 $M$,定義下列新狀態 $\bf z$ 轉換
\[
{\bf x} = M {\bf z}
\]將上述新的狀態關系代入原系統 $\dot {\bf x}(t) = G{\bf x}(t)$ 我們可以改寫如下
\[\begin{array}{l}
{\bf{\dot x}}(t) = G{\bf{x}}(t)\\
 \Rightarrow M{\bf{\dot z}}\left( t \right) = GM{\bf{z}}(t)\\
 \Rightarrow {\bf{\dot z}}\left( t \right) = {M^{ - 1}}GM{\bf{z}}(t)
\end{array}
\]其中初始值 (Initial Condition, I.C.) 為 $\begin{array}{l}
{\bf{z}}(0) = {M^{ - 1}}{\bf{x}}(0)\\
\end{array}$
上述轉換又稱對角化,故我們得到 $G$ 如下
\[{M^{ - 1}}GM = \left[ {\begin{array}{*{20}{c}}
{{\lambda _1}}&{}&{}&{}\\
{}&{{\lambda _2}}&{}&{}\\
{}&{}& \ddots &{}\\
{}&{}&{}&{{\lambda _n}}
\end{array}} \right]: = \Lambda \]因此,若我們求解 ${{\bf{\dot z}}\left( t \right) = {M^{ - 1}}GM{\bf{z}}(t)}$ 可得
\[{\bf{z}}(t) = {e^{{M^{ - 1}}GMt}}{\bf{z}}(0) = {e^{\Lambda t}}{\bf{z}}(0)
\]現在將上述結果轉回原本的狀態 $\bf x$
\[{\bf{x}}(t) = M\underbrace {{\bf{z}}(t)}_{ = {e^{\Lambda t}}{\bf{z}}(0)} = M{e^{\Lambda t}}\underbrace {{\bf{z}}(0)}_{ = {M^{ - 1}}{\bf{x}}(0)} = M{e^{\Lambda t}}{M^{ - 1}}{\bf{x}}(0) \ \ \ \ \ (**)
\] 其中
\[\begin{array}{*{20}{l}}
{M{e^{\Lambda t}} = \left[ {\begin{array}{*{20}{c}}
{{{\bf{v}}_1}}&{{{\bf{v}}_2}}&{...}&{{{\bf{v}}_n}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{e^{{\lambda _1}t}}}&0& \cdots &0\\
0&{{e^{{\lambda _2}t}}}&{}& \vdots \\
 \vdots &{}& \ddots &0\\
0& \cdots &0&{{e^{{\lambda _n}t}}}
\end{array}} \right]}\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \left[ {\begin{array}{*{20}{c}}
{{e^{{\lambda _1}t}}{{\bf{v}}_1}}&{{e^{{\lambda _2}t}}{{\bf{v}}_2}}&{...}&{{e^{{\lambda _n}t}}{{\bf{v}}_n}}
\end{array}} \right]}
\end{array}
\]另外我們觀察 $M^{-1}$ 定義 $L:= M^{-1}$ 具有 rows 向量為 $l_i$; i.e.,
\[L = {M^{ - 1}} = \left[ {\begin{array}{*{20}{c}}
{{{{{l}}}_1}}\\
{{{{l}}_2}}\\
 \vdots \\
{{{{l}}_n}}
\end{array}} \right]\]
因此我們可以更進一步改寫 $(**)$ 如下
\[\begin{array}{l}
{\bf{x}}(t) = M{e^{\Lambda t}}{M^{ - 1}}{\bf{x}}(0)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \left[ {\begin{array}{*{20}{c}}
{{e^{{\lambda _1}t}}{{\bf{v}}_1}}&{{e^{{\lambda _2}t}}{{\bf{v}}_2}}&{...}&{{e^{{\lambda _n}t}}{{\bf{v}}_n}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{l_1}}\\
{{l_1}}\\
 \vdots \\
{{l_n}}
\end{array}} \right]{\bf{x}}(0)
\end{array}
\]或者更簡潔的表示成矩陣的形式
\[{\bf{x}}(t) = \sum\limits_{i = 1}^n {{e^{{\lambda _i}t}}{{\bf{v}}_i}{l_i}} {\bf{x}}(0) \ \ \ \ (\star)
\] 也就是說
\[{\bf x}(t) = e^{Gt} {\bf x}_0 = \sum\limits_{i = 1}^n {{e^{{\lambda _1}t}}{{\bf{v}}_i}{\alpha _i}}\]
現在我們觀察 $(\star)$ 整理結果如下:上述的(自由響應 (free response) )解 與下列三者有關:

  1. ${\bf eigenvalues}$:用以決定 系統自由響應 的 衰減率/增長率 
  2. ${\bf eigenvectors}$: 用以決定 系統自由響應的 " shape "
  3. ${\bf Initial Condition.}$: 用以決定哪一個系統的 mode 參與自由響應的程度

10/13/2012

[控制理論] 狀態回授控制(1)- Eigenstructure Assignment

控制理論中最重要的本質 便是 回授控制 (feedback control),在實現上,回授控制具有下列四種主要功能:

  1. 改善/保證 系統穩定度
  2. 降低系統的 敏感度(提升強健性)
  3. 改善系統 抑制 低頻外在干擾 或者 抑制 高頻雜訊 的能力
  4. 改善 系統暫態響應

而 Eigenstructure Assignment (同時給定 eigenvalue 與 eigenvector )主要是透過回授控制達成第四個目標:改善 系統的 暫態響應。以下我們介紹 全狀態回授 (Full State Feedback) 的 Eigenstructure Assignment。


考慮系統
\[\dot x\left( t \right) = Ax\left( t \right) + Bu\left( t \right)
\] 其中 $x(t) \in \mathbb{R}^n$; $u(t) \in \mathbb{R}^m$

且狀態回授控制器 $u(t) = F x(t)$。
則將控制器帶入系統,可得閉迴路系統如下
\[\dot x\left( t \right) = \left( {A + BF} \right)x\left( t \right)
\]
現在令 $\lambda_i$ 為系統 $A+BF$ 的 eigenvalue,且 $v_i$ 為對應的 eigenvector,則我們有 eigenvalue-eigenvector relationship 如下
\[
(A+BF) v_i = \lambda_i v_i
\] 上式可改寫為
\[\begin{array}{l}
(A + BF){v_i} = {\lambda _i}{v_i}\\
 \Rightarrow \left( {{\lambda _i}I - A} \right){v_i} - BF{v_i} = 0
\end{array}\]

故我們現在定義 $S_{\lambda_i }:= [\lambda_i I - A \;\; B]$ 且定義其對應的分割矩陣
\[{K_{{\lambda _i}}}: = \left[ {\begin{array}{*{20}{c}}
{{N_{{\lambda _i}}}}\\
{{M_{{\lambda _i}}}}
\end{array}} \right]\]此 $K_{\lambda_i}$ spans $\ker\{S_{\lambda_i}\}$

Theorem: (Moore, 1976) 令 $\{\lambda_i, i=1,...,n\}$ 為 self-conjugate 且 相異的特徵值所形成的集合。我們說 存在控制矩陣 $F$ 使得 對任意 $i=1,...n$ 而言,我們有 $(A+BF) v_i = \lambda_i v_i$  若且為若 對任意 $i=1,...n$,下列三個條件成立
1. (線性獨立) $v_i$ 彼此線性獨立
2. (共顎條件) $\lambda_i = \lambda_j^* \Rightarrow v_i = v_j^*$
3. $v_i \in \text{span}\{N_{\lambda_i}\}= \left\{ {\sum\limits_{i = 1}^n {{c_i}{v_i}} :{v_i} \in {N_{{\lambda _i}}},{c_i} \in \mathbb{R}} \right\}$

Proof: 
$(\Rightarrow)$ 假設 存在控制矩陣 $F$ 使得 對任意 $i=1,...n$ 而言,我們有 $(A+BF) v_i = \lambda_i v_i$,我們要證明三個條件成立;由於前面兩個條件由線性代數的理論可得;故我們只需檢驗條件 3. 假設 $(A+BF)v_i = \lambda_i v_i$, 則我們有
\[\begin{array}{l}
(A + BF){v_i} = {\lambda _i}{v_i}\\
\Rightarrow \left( {{\lambda _i}I - A} \right){v_i} - BF{v_i} = 0\\
\Rightarrow \underbrace {\left[ {\begin{array}{*{20}{c}}
{{\lambda _i}I - A}&B
\end{array}} \right]}_{{S_{{\lambda _i}}}}\underbrace {\left[ {\begin{array}{*{20}{c}}
{{v_i}}\\
{ - F{v_i}}
\end{array}} \right]}_{{\in K_{{\lambda _i}}}} = 0
\end{array}\] 由於 $K_{\lambda_i}$ 的 columns 做為基底建構 $\ker \{ {S_{{\lambda _i}}}\}  = \ker \left\{ {\left[ {\begin{array}{*{20}{c}}
{{\lambda _i}I - A}&B
\end{array}} \right]} \right\}$ ,故 $v_i \in \text{span}\{N_{\lambda_i}\}$.

$(\Leftarrow)$ 假設前述 Theorem 三個條件成立, 我們要證明存在一個實數矩陣 $F$ 使得對 $1 \le i \le n$,下式 eigenvalue-eigenvector relation 滿足
\[
(A+BF)v_i = \lambda_i v_i.
\]現在選 $v_i, \; 1\le i \le n$ 滿足 3 條件; i.e., 對 $1\le i \le n$

  1. $v_i$ 彼此線性獨立
  2. $\lambda_i = \lambda_j^* \Rightarrow v_i = v_j^*$
  3. $v_i \in \text{span}\{N_{\lambda_i}\}$

首先由條件 3 可知 $v_i \in \text{span}\{N_{\lambda_i}\}$ (the subspace spanned by colmuns of $N_{\lambda_i}$ and $v_i$ is the member of such subspace. ), 存在一個向量 $k_i$ (real or complex) 使得
\[
v_i = N_{\lambda_i} k_i
\]接著由於
\[{K_{{\lambda _i}}} = \left[ {\begin{array}{*{20}{c}}
{{N_{{\lambda _i}}}}\\
{{M_{{\lambda _i}}}}
\end{array}} \right] = \ker \left\{ {\left[ {\begin{array}{*{20}{c}}
{{\lambda _i}I - A}&{B}
\end{array}} \right]} \right\}\]故暗示了
\[
 \left( {{\lambda _i}I - A} \right){N_{{\lambda _i}}}{k_i} - B{M_{{\lambda _i}}}{k_i} = 0
\] 上述結果暗示了 若我們選 $F$ 使得 $ - {M_{{\lambda _i}}}{k_i} = F{v_i}$ 則 可得
\[\begin{array}{l}
\left( {{\lambda _i}I - A} \right){v_i} + B{M_{{\lambda _i}}}{k_i} = 0\\
\Rightarrow \left( {{\lambda _i}I - A} \right){v_i} + B\left( { - F{v_i}} \right) = 0\\
\Rightarrow \left[ {{\lambda _i}I - \left( {A + BF} \right)} \right]{v_i} = 0
\end{array}
\]亦即我們需要的結果。故剩下的證明便是要證明我們可以永遠建構出一控制矩陣 $F$ 滿足
\[F\left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{{w_1}}&{{w_2}}& \cdots &{{w_n}}
\end{array}} \right]\]其中 $w_i := -M_{\lambda_i} k_i$ ; i.e., 若這樣的 $F$ 存在 則必定滿足
\[F\left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{ - {M_{{\lambda _1}}}{k_1}}&{ - {M_{{\lambda _2}}}{k_2}}& \cdots &{ - {M_{{\lambda _n}}}{k_n}}
\end{array}} \right]\]

現在我們分成兩種情況討論

${\bf CASE 1: }$ 特徵值皆為實數的情況
若任意相異的 $\lambda_i$ 為實數,則 $v_i, w_i$ 亦為實數,且矩陣 $\left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right]$ 之反矩陣存在 (由條件 1),故可得控制力矩陣 $F$ 為
\[\begin{array}{l}
F = \left[ {\begin{array}{*{20}{c}}
{{w_1}}&{{w_2}}& \cdots &{{w_n}}
\end{array}} \right]{\left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right]^{ - 1}}\\
\begin{array}{*{20}{c}}
{}
\end{array} = \left[ {\begin{array}{*{20}{c}}
{ - {M_{{\lambda _1}}}{k_1}}&{ - {M_{{\lambda _2}}}{k_2}}& \cdots &{ - {M_{{\lambda _n}}}{k_n}}
\end{array}} \right]{\left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right]^{ - 1}}
\end{array}\]

${\bf CASE 2: }$ 特徵值具有共顎複數情況
若特徵值有共顎複數,在此我們假設 $\lambda_1 = \lambda_2^*$. 由條件2可知 $v_1 = v_2^*$ 故可推知 $w_1 = w_2^*$. 因此,設其他剩餘的特徵值皆為實數,則控制力矩陣 $F$ 必定需滿足
\[ \small
F\left[ {\begin{array}{*{20}{c}}
{{v_{1R}} + j{v_{1I}}}&{{v_{1R}} - j{v_{1I}}}& {{v_3}}& \cdots &{{v_n}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{{w_{1R}} + j{w_{1I}}}&{{w_{1R}} - j{w_{1I}}}& {{w_3}}& \cdots &{{w_n}}
\end{array}} \right]
\]其中 $w_i := -M_{\lambda_i} k_i$. 現在兩邊同乘下式 的非奇異矩陣
\[\left[ {\begin{array}{*{20}{c}}
{1/2}&{}&{ - j1/2}& {}\\
{1/2}&{}&{j1/2}& 0\\
\hline
{}&0&{}& I
\end{array}} \right]\]
則我們可得
\[F\left[ {\begin{array}{*{20}{c}}
{{v_{1R}}}&{{v_{1I}}}& {{v_3}}& \cdots &{{v_n}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{{w_{1R}}}&{{w_{1I}}}& {{w_3}}& \cdots &{{w_n}}
\end{array}} \right]\]
現在由於 $\{v_i\}_{i=1}^n$ 彼此獨立,故矩陣
\[V:=\left[ {\begin{array}{*{20}{c}}
{{v_{1R}}}&{{v_{1I}}}& {{v_3}}& \cdots &{{v_n}}
\end{array}} \right]
\] 之反矩陣存在,故我們可如前計算 $F$. (by taking inverse of $V$). $\square$

10/11/2012

[機率論] Almost Sure Convergence

固定 機率空間 $(\Omega, \mathcal{B}, P)$。我們說 隨機事件 $A$  almost surely (a.s.) 成立,若下列條件成立:
存在一個事件 $N \in \mathcal{B}$ 且 $P(N)=0$ 使得 若 $\omega \in N^c$ 事件 $A$ 都成立。


Example 1: Two r.v. equal Almost Surely
令 $X, X'$ 為兩個隨機變數,則 $X=X'$ almost surely 亦即
\[
P(\omega: X(\omega) = X'(\omega)) = 1
\]亦即,存在事件 $N \in \mathcal{B}$ 使得 $P(N)=0$ 且  $\omega \in N^c \Rightarrow X(\omega) = X(\omega)'$ 都成立。$\square$


Example 2: 
令 $X, X'$ 為兩個隨機變數,則 $X \le X'$ almost surely 亦即
\[
P(\omega: X(\omega) \le X'(\omega)) = 1
\]亦即,存在事件 $N \in \mathcal{B}$ 使得 $P(N)=0$ 且  $\omega \in N^c \Rightarrow X(\omega) \le X(\omega)'$ 都成立。$\square$


Example 3: random variable sequence
若' $\{X_n\}$ 為 隨機變數的 sequence,則 $\lim_{n\rightarrow \infty}X_n$存在 almost surly 意指 存在事件 $N \in \mathcal{B}$ 使得 $P(N)=0$ 且  $\omega \in N^c \Rightarrow \lim_{n\rightarrow \infty}X_n$ 存在 ;此陳述等價為
\[
\limsup_{n \rightarrow \infty} X_n(\omega) = \liminf_{n\rightarrow \infty }X_n(\omega)
\]我們會寫作 $\lim_{n \rightarrow \infty}X_n = X$ almost surely 或者 $X_n \rightarrow X$ a.s. $\square$


Example 3: random series
若' $\{X_n\}$ 為 隨機變數的 sequence,則 $\sum_n X_n$ converges almost surly 意指 存在事件 $N \in \mathcal{B}$ 使得 $P(N)=0$ 且  $\omega \in N^c \Rightarrow  \sum_n X_n$ converges  存在  $\square$

基於 almost sure equality,大部分隨機變數的機率性質都不改變。比如說 若 $X = X'$ almost surely,則若 $X \in L^1$ 若且唯若 $X' \in L^1$ 且 $EX = EX'$


注意到 隨機變數 sequence 儘管有 almost surely convergence 並不表示 convergence everywhere。現在我們看個例子:

Example: Almost Sure Convergence fails to be Convergence Everywhere
考慮機率空間 $([0,1], \mathcal{B}_{[0,1]}, \lambda)$ 且 $\lambda$ 為 Lebesgue measure。現在定義隨機變數
\[{X_n}(\omega ): = \left\{ \begin{array}{l}
n,\begin{array}{*{20}{c}}
{}
\end{array}0 \le \omega  \le \frac{1}{n}\\
0,\begin{array}{*{20}{c}}
{}
\end{array}\frac{1}{n} < \omega  \le 1
\end{array} \right.\]試證 $X_n \rightarrow 0$ almost surely;但 $X_n$ 並非 converge everywhere。
Proof:
若 $N = \{0\}$ 則 $\omega \in N^c \Rightarrow X_n(\omega ) \rightarrow 0$;

但是若我們現在關注 $\omega = 0$ 這一點時,可以發現 $X_n(0) = n \rightarrow \infty \neq 0$ $\square$

===================
Proposition: 令 $\{X_n\}$ 為 i.i.d. 隨機變數 且具有共同的 分布函數 $F(x)$。假設 $F(x) <1$;令
\[
M_n := \max\{X_1,X_2,...,X_n\}
\]則 $M_n \rightarrow \infty$ almost surely 當 $n\rightarrow \infty$。
===================

Proof: 我們要證  $M_n \rightarrow \infty$ almost surely 當 $n\rightarrow \infty$;亦即要證明 存在事件 $N$ 使得 $P(N)=0$ 且若 $\omega \in N^c$ 我們有 $M_n \rightarrow \infty$ 。我們需要證明 存在事件 $N \in \mathcal{B}$ 使得 $P(N) =0$ 且若 $\omega \in N^c$ 我們有
\[
\lim_{n \rightarrow \infty} M_n(\omega) = \infty
\]由 $lim$ 定義,上述可改寫為 要證明 對任意 $j>0$, 存在 $n_0$ 使得若 $n \ge n_0$ 則 $M_n(\omega) \ge j$。

首先注意到 由於 $\{X_n\}$ 為 i.i.d. 隨機變數 且具有共同的 分布函數 $F(x)$,故我們可寫
\[\begin{array}{l} P\left( {{M_n} \le x} \right) = P\left( {\max \left( {{X_1},{X_2},...,{X_n}} \right) \le x} \right)\\ \begin{array}{*{20}{c}} {}&{}&{}&{} \end{array} = P\left( {{X_1} \le x,{X_2} \le x,...,{X_n} \le x} \right)\\ \begin{array}{*{20}{c}} {}&{}&{}&{} \end{array} = \prod\limits_{i = 1}^n {P\left( {{X_i} \le x} \right)} = {F^n}\left( x \right) \end{array}
\] 故注意到由於 $F(x)<1$ 我們有
\[
\sum_n P(M_n \le j) = \sum_n F^n(j) < \infty
\]故由 Borel-Cantelli Lemma 可知
\[P\left( {\left\{ {{M_n} \le j} \right\}i.o.} \right) = 0\]亦即
\[P\left( {\mathop {\lim \sup }\limits_{n \to \infty } \left\{ {{M_n} \le j} \right\}} \right) = 0
\]故現在定義 事件 ${\mathop {\lim \sup }\limits_{n \to \infty } \left\{ {{M_n} \le j} \right\}}$ 則我們有 $P(N_j) = 0$ 對任意 $j$。

且注意到 ${N_j}^c: = \mathop {\lim \inf }\limits_{n \to \infty } \left\{ {{M_n} > j} \right\}$,故對任意 $\omega \in N_j^c$,若有夠大的 $n$,則我們有 $M_n(\omega) >j$。

現在定義 $N:= \cup_j N_j$ 則
\[
P(N) \le \sum_j P(N_j) =0
\] 且若 $\omega \in N^c$,我們有對任意 $j$,若 有夠大的 $n$,則 $M_n(\omega) >j$ 。 $\square$

[最佳化] C^2 函數一階逼近的餘項積分表示

令 $f: \mathbb{R}^m \to \mathbb{R}$ 為 $C^2$-函數。對 $f$ 在 $y$ 附近使用一階泰勒展開: \[ T_y(x) := f(y) + \nabla f(y)^\top (x - y) \] 則其餘項 $R(x,y)$ 訂為 $$R(...