跳到主要內容

General Solution Of Eigen System In Linear Algebra

本文從淺白的角度回顧線性代數(Linear Algebra),了解特徵值(eigenvalue),特徵向量(eigenvector),還有特徵多項式(Characteristic Polynomial) 的框架,並推廣其概念,還有它在解差分方程式,微分方程式,差分方程組,微分方程組的關係。
-----------------------------------------------------------
[預備知識]   
向量空間(vector space) $V$,field over $\mathbb{C}$ ,線性獨立(linear independent),SpanBasis 等概念。
線性函數的定義為 $L : V \longrightarrow V$ , $$\forall \alpha , \beta  \in \mathbb{C} , v_1 ,v_2 \in V \quad L(\alpha v_1 + \beta v_2) =\alpha L(v_1) + \beta L(v_2) $$
其中 $L(0) = 0 \in V$
其中 $+$ 都是$V$裡的加法,線性函數空間記做 $L \in \mathcal{L}^{V}$
其中存在 $O \in \mathcal{L}^{V}$ 零函數 $O(V) = \{0\}$ ,即 $\forall v \in V ,  O(v) = 0 \in V $
其中存在 $I \in \mathcal{L}^{V}$ 送到自己函數 ,即 $\forall v \in V ,  I(v) = v \in V $
-----------------------------------------------------------
[主要動機]
給定 $b \in V$ ,  $L \in \mathcal{L}^{V}$ 如何解線性系統 $L(x) = b$ ,換句話說就是構造出 $$ S_{b}:= \left\{x \in V : L(x) = b  \right\} $$ ,而 $Ker(L) := S_{0}$ (Kernel)

註: 構造出 $S_0$ 我們稱為解 homogeneous system ,構造出 $S_b$ 我們稱為解 non-homogeneous system
-----------------------------------------------------------
[Fact 1 : Superposition Principle in $S_0$]
假設我們運氣很好得到兩個解 $v_1,v_2 \in S_{0}$,即 $L(v_1),L(v_2) = 0$ ,則可以計算其線性組合 $v^{new}:=\alpha v_1 + \beta v_2$ ,結果我們找到新的解 $v^{new} \in S_{0}$ !!
原因如下:

$$ L(v^{new}) = L(\alpha v_1 + \beta v_2) \underset{L \text{ is Linear}}{=}   \alpha \underbrace{L(v_1)}_{=0} + \beta \underbrace{L(v_2)}_{=0} = 0   $$
而事實上 $v^{new} \in Span\{v_1 , v_2\}$
推廣來說: 所有的解 $v_0 \in S_0$ 可以寫成 $$v_0 =  \sum_{j\in J}c_j v_j  \in Span \{v_j : j \in J \}$$
其中 $c_j \in \mathbb{C} \quad  \{v_j\}$ ,彼此線性獨立,又生成整個$S_0$,稱為 basis of $S_0$

[Fact 2: Particular Solution in $S_b$ ]
假如我們運氣很好得到一個解 $v_p \in S_b$ ,我們要怎麼製造更多的解呢? ,答案是我們可以的隨便拿一個 $v_0 \in S_0$  計算 $v^{new} = v_h + v_0 $ 你會發現 $L(v_b + v_0) = L(v_b) + L(v_0) = b + 0 = b  \Longrightarrow  v^{new} \in S_b$ !!
------------------------------------------------------------
根據上面 Fact 1 , Fact2 等等,最後我們可以得到下面結果 $ S_b := v_b + S_0  $
也就是說,所有的解就是
$$ S_b := \left\{ v_b + \sum_{j \in J}c_j v_j  : \forall c_j \in \mathbb{C} \right\}  \quad  (E_1)$$
其中 $dim(S_b) = |J| , \{ v_j\}\subset S_0 $ 為線性獨立集 !! ,所以我們要先找到 $|J|$ 個線性獨立的集合 $\{ v_j\}$ !!
--------------------------------------------------------------
[Eigen System]
今天我們定義一個基本線性函數$E \in \mathcal{L}^{V}$,參數化向量 $v_{\lambda} \in V \quad $ ($v_\lambda$ 隨著 $\lambda$ 不同而不同)
如果對於 $\forall \lambda \in \mathbb{C}$   找的到 $v_\lambda \quad \exists n \geq 1$
$$\left\{\begin{array}{l}[E(v_\lambda) - \lambda \cdot v_\lambda]^{n}= 0 \\ [E(v_\lambda) - \lambda \cdot v_\lambda]^{n-1}\neq 0   \\ \end{array}\right.    \quad (E2)$$ (注意這邊的 "$\cdot$" 是 $V$ 的 scalar multiplication ) , $\lambda$ 就是熟知的 eigenvalue , $v_\lambda$ 就是熟知的 廣義特徵向量(generalized eigenvector)  ,如果 $n=1$ 稱為 eigenvector


[求解多項式問題]
假如 $L \in \mathcal{L}^{V}$ 是 $E$ 的 $K$ 次多項式合成運算構成的 !!  即$$L = p(E) = \sum^{K}_{k=0} a_k {E}^k = a_k \cdot \underbrace{E \circ E \circ E \circ ... E}_{k \text{ 次}} $$
[註 : 兩個線性函數的合成運算後還是線性 !!]
代數基本定理(多項式分解)我們知道任何多項式,$p(E) $ 可以分解成 $$p(E) = \prod^{K}_{k=1}(E-\lambda_k I)^{\mu_k}  \quad  \mu_k \in \mathbb{N}\cup \{0\} , \lambda_{k} \in \mathbb{C} , \sum_{k=1}^{K}\mu_k  = K  $$
[註:我們只考慮 $\mu_k >0$ 的那些 $\lambda_k$ , $\mu_k >1$ 代表有重根]
考慮   $\lambda = \lambda_k$ 的 generalized eigenvector   很明顯   for each $k$,$p(E)(v_{\lambda_k}) = ...(E - \lambda_kI)^{\mu_k}(v_{\lambda_k}) = 0  \Longrightarrow   v_{\lambda_k} \in Ker(L) = S_0 $
而根據線性代數的知識,如果 $\lambda$ 不同 !! 則產生的 $\{v_\lambda\}$ 彼此線性獨立 !!
這代表我們只要找到所有的 $\text{Basis}{(\lambda_k)} := \{v_{\lambda_k}\}$ 則 Span 就能找到解!!
即 $$ Span \left\{\bigcup_{k \in K : m_k >0}\text{Basis}{(\lambda_k)}\right\}  \subseteq S_{0} $$
[註:  我們找到的解未必是所有的解,證明$=S_0$是重要議題,如微分方程可參考 Wronskian ]
而恰好要找到那些$\lambda$ ,我們只要求解 $p(\lambda) = 0$ !! 也就是
$$\underset{ k \in K}{\bigvee} (\lambda =  \lambda_k) \Longleftrightarrow  \prod^{n}_{k=1}\left(\lambda-\lambda_{k} \right)^{\mu_k}=0 $$
註:我們稱  $p(\lambda)$ 為 特徵函數 Characteristic Polynomial ,$\mu_k$ 為代數重數 !! 
註 :  如果 $p(E)=E=A$ 則純矩陣系統,特徵函數為 $det(A-\lambda I) = 0$
至於 for each $k$ 如何產生 $\text{Basis}{(\lambda_k)}$ 我們必須找到 $\mu_k$ 個線性獨立的向量
$$v^{n}_{\lambda_{k}}  :  \text{滿足}(E1)  ,  n=1,2,3,....m_k$$
註: $v^{n}_{\lambda_{k}}$ 的 $n$ 為 index

[找到 $\text{Basis}{(\lambda_k)}$]
首先找到最小的$m_k \leq \mu_k$ 滿足 $(E-\lambda_k I)^{m_k} = O $
以及計算 $\rho_k = dim(Ker(E-\lambda_kI)^{l}) - dim(Ker(E-\lambda_kI)^{l-1})  \quad l=1,2,3,...m_k$
其中 $\displaystyle{\sum_{l=1}^{m_k} \rho^{l}_k = \mu_k} $,$\rho^1_{k}$ 稱為幾何重數,註: $ dim(Ker(E-\lambda_kI)^{0}) = dim(Ker(I)) = 0 $
相當於求解下列方程組 : $(E3)$
$$
\left\{\begin{array}{llll}
\text{ 找到 } \rho^{1}_{k} \text{ 個線性獨立 } v^{1}_{\lambda_{k}}  &(E-\lambda_k I)(v^{1}_{\lambda_{k}}) = 0 & & (C1) \\
\text{ 找到 } \rho^{2}_{k} \text{ 個線性獨立 } v^{2}_{\lambda_{k}}&(E-\lambda_k I)^2(v^{2}_{\lambda_{k}}) = 0 &  (E-\lambda_k I) (v^{2}_{\lambda_{k}})\neq 0 &(C2) \\
&(E-\lambda_k I)^3(v^{3}_{\lambda_{k}}) = 0 & (E-\lambda_k I)^{2}(v^{3}_{\lambda_{k}})\neq 0 & (C3)\\
.. &... &... \\
\text{ 找到 } \rho^{m_k-1}_{k} \text{ 個線性獨立 } v^{m_k-1}_{\lambda_{k}}&(E-\lambda_k I)^{m_k-1}(v^{m_k-1}_{\lambda_{k}}) = 0 & (E-\lambda_k I)^{m_k-2}(v^{m_k-1}_{\lambda_{k}})\neq 0 &(C_{m_k-1}) \\
\text{ 找到 } \rho^{m_k}_{k} \text{ 個線性獨立 } v^{m_k}_{\lambda_{k}}&(E-\lambda_k I)^{m_k}(v^{m_k}_{\lambda_{k}}) = 0 & (E-\lambda_k I)^{m_k-1}(v^{m_k}_{\lambda_{k}})\neq 0 &(C_{m_k})  \\
\end{array}\right.
$$

如果我們把左邊的方程組,代換 $v^{n}_{\lambda_k} =  (E-\lambda_k I)(v^{n+1}_{\lambda_{k}}) \quad n = 1,2,3,4,...m_k-1 \ (E4)$ 即 Jordan Chain
你會發現如果滿足 $(C_{n})$ 則滿足 $(C_{n+1})$ ,所以我們只要找到滿足 $(C_{m_k})$ 的 $v^{m_k}_{\lambda_{k}}$ 就可以了!!
改寫$(E4)$ 成 $ E(v^{n+1}_{\lambda_{k}})  =  \lambda_k v^{n+1}_{\lambda_{k}} + v^{n}_{\lambda_k}  $ 並把 $(E3)$ 寫成 $\mu_k \times \mu_k$矩陣的樣子
===============================
例如 : $\mu_k = 6$ , $m_k = 3$ , $\rho^1_{k} = 3$ , $\rho^{2}_k = 2$  , $\rho^{3}_k = 1$

$$  E \left[\begin{array}{c}
 v^{3}_{\lambda_k}\\ \hline v^{22}_{\lambda_k} \\ v^{21}_{\lambda_k} \\ \hline v^{13}_{\lambda_k} \\v^{12}_{\lambda_k} \\ v^{11}_{\lambda_k} \\
\end{array}\right]
=  \left[\begin{array}{c|cc|ccc}
\lambda_{k}&1 &0 & & &  \\
\hline
&\lambda_{k} &0 &1 &0 & 0 \\
& &\lambda_{k} &0 &1 &0  \\
\hline
& & &\lambda_{k} &0 &0  \\
& & & &\lambda_{k} &0  \\
& & & & & \lambda_{k}  \\
\end{array}\right]\cdot
 \left[\begin{array}{c}
  v^{3}_{\lambda_k}\\ \hline v^{22}_{\lambda_k} \\ v^{21}_{\lambda_k} \\ \hline v^{13}_{\lambda_k} \\v^{12}_{\lambda_k} \\ v^{11}_{\lambda_k} \\
\end{array}\right]
$$

$Span \text{ of Basis}{(\lambda_k)}= \left\{c_1 \cdot   v^{11}_{\lambda_k}+ c_2 \cdot  v^{12}_{\lambda_k}  + c_3 \cdot v^{13}_{\lambda_k} + c_4 \cdot  v^{21}_{\lambda_k}  + c_5 \cdot v^{22}_{\lambda_k}  + c_6   \cdot v^{3}_{\lambda_k} : c_1,...c_6 \in \mathbb{C} \right\}$
================================
有以上應用我們知道可以從 eigenvector 去造  generalized eigenvector !!

[線性代數在各個層面的應用]
可由以下表格了解 !!
$$ \begin{array}{c|c|c|c|c|c|c}
\text{通俗名稱 } & V & E&  \text{ 齊次問題 } L(v) = 0 &  \text{特徵方程} & \text{eigenvector }  &  \\
\hline
\text{線性聯立方程組 } & x \in \mathbb{R}^n & E(x):=Ax &  E = O   & det(A-\lambda I)= 0   & x_{\lambda}: Ax_{\lambda} = \lambda x_{\lambda} &  \\
\text{線性遞迴方程式}   & a_n \in \mathbb{R}^{\mathbb{N}}&   E(a_{n}) := a_{n+1} & p(E) = O  & p(\lambda) = 0  & \lambda^{n} : n \in \mathbb{N} &  \\
\text{線性微分方程式}&f \in C^{\infty}(\mathbb{R})&E(f(t)) := \frac{d}{dt}f(t)  & p(E) = O  & p(\lambda) = 0   & e^{\lambda t} : t\in \mathbb{R} & \\
\text{線性遞迴方程組}& a_n \in \prod^{m}_{i=1}\mathbb{R}^{\mathbb{N}}& E(a_{n}) := [a^{i}_{n+1}]^{m}_{i=1}  & (E-A) = O  &  det(A-\lambda I)= 0 & {\lambda}^{n}x_\lambda : Ax_{\lambda} = \lambda x_{\lambda}   & \\
\text{線性微分方程組}& f \in \prod^{m}_{i=1}C^{\infty}(\mathbb{R})& E(f(t)) := [ \frac{d}{dt}f_{i}(t)]^{m}_{i=1} &  (E-A) = O & det(A-\lambda I)= 0  & e^{\lambda t}x_\lambda : Ax_{\lambda} = \lambda x_{\lambda}  &  \\
\end{array}$$

[小結]
線性代數不只是 "矩陣",事實上解微分,差分方程都用的到線性代數的概念,而最關鍵的步驟是 找
(1) scalar multiplication  $\lambda$ 來替換線性$E$
(2) 尋找 eigenvector $v_{\lambda} $  of $L$ 或 $E$
(3) 構造 $L$ 的特徵多項式($L=O$ 的充分條件),可用來找 eigenvalues


[以上純為學術經驗交流知識分享,如有錯誤或建議可留言~~] 
by Plus & Minus 2017.09






留言

這個網誌中的熱門文章

Linear Regression By Using Linear Programming

當拿到一筆資料準備玩統計,往往會想要做線性迴歸( Linear Regression ),找出一個模型( mathematical model )來解釋變數間的關係,一般都是使用平方距離,但是如果我們採用絕對值距離呢?? 而剛好在工業工程( Industrial Engineering ),作業研究( Operation Research ) 領域,發展成熟的線性規劃( Linear Programming ) 恰好可以來解決,是一個跨領域的應用 !! 已經存在有許多商業或open source 軟體,如: Gurobi , Cplex , Xpress , Mosek , SCIP  可以輕易求解大型的線性規劃問題。而不僅如此也可以利用整數規劃( Integer Programming )來做特徵選擇 ( Feature Selection ),甚至可以偵測離群值( Detect Outlier ) !! 本文只介紹最小絕對值和,關於 Feature Selection , Detect Outlier 可以參考 Mixed-Integer Linear Programming Robust Regression with Feature Selection , Oleksii Omelchenko , 2010 的論文。 [Data Fitting Problem] 給定$n$筆實數型訓練資料 (training data) $\{(x^{k},y^{k})\}^{n}_{k=1} = \mathcal{D} , x^{k} =(x^{k}_1,x^{k}_2, ... , x^{k}_{p})\in \mathbb{R}^{p}$ , $y^{k} \in \mathbb{R}$ , 我們目標是想要找到一個函數 $f_{\mathcal{D}} : \mathbb{R}^p \rightarrow \mathbb{R}$ 使得  $\forall x \in \mathbb{R}^{p} , f_{\mathcal{D}}(x) \approx y$ , 精確來說: $$ \text{Find } f_{\mathcal{D}} \text{ such that } f_{\mathcal{D}}(x)\approx \left\{

Chain Rule & Identity Function Trick

本文為筆者學習微積分,函數概念與Chain Rule 的時候,遇到的一些概念大坑。本文一一澄清一些個人看法,並分享 Chain Rule 廣義的樣子,以及對於遞迴系統該如何計算...等等看法。 [坑1 : 變數/值符號的認識] 一切從 $y = f(x)$ 開始,我們習慣把 Input 變數用"括號"刮起來,Output y 代表值,f 代表函數。或是可以想成這樣:   $$ x \overset{f}{\longrightarrow} y $$ 這種表示法概念上很嚴謹,但缺點是你必須要用三個符號 $x$,$y$,$f$ 而在微分方程領域出現這種寫法 $y = y(x)$  (把 $f$ 換成 $y$) ,這種寫法就頗簡潔,Chain Rule 通常都是這類表示法。缺點是心裡要能確實明白在哪個場合 $y$ 到底是給定的"值"還是"函數"(註: 通常大多代表函數 $y$,值的話通常會這樣寫 $y(x_{0})$,$y_{0}$) ============================================================== [Bonus] $y=y(x)$這種表示法還有一個好處,如果允許 $f$ 是一對多,那麼 $y(x)$ 就是 $y \text{ is depend on } x$ 的意思,如果你喜歡用集合論來表示可以先定義$f$ 的定義域/對應域 $$ f : X \rightarrow Y$$ 然後 $y(x)$ 可以寫成這樣 $y \in Y_{x}$,其中值域為 $$ f(X):=\bigcup_{x \in X}Y_{x} \subseteq Y$$ ============================================================== [坑2 : Input 的變數到底是哪些] 這邊舉兩個例子提醒: (Ex1) 代換法會重新改變函數的 Input 例如 : $y = f(x) = x+1$ , $ z = g(y) = 2y$  可以代換一下,寫成 $z = g[f(x)] = 2(x+1)$ 如果你用簡記你會發現 $y(x) , z(y) , z(y(x)) \equiv z

Probability Model Of Bingo Game

本文介紹經典的"賓果 Bingo" 遊戲,機率與期望值的解析計算公式的計算概念,相關的數學建模....等等 [遊戲情境] 總共有 $n$ 個相異的號碼彩球,號碼集為 $S:=\{1,2,3,....n\}$,今玩家可以花$1$元,買$1$張賓果卡 ($5 \times 5$) 位置座標集 $Z$, $|Z|=25$,然後從$S$ 隨機均勻選擇 $25$個相異的號碼並排列到一個佇列(queue),而開球只會開前 $m$ 顆球,$25 \leq m\leq n$,而給定獎項圖形集 $\color{red}{p \in P := \{Bingo,王,十,一_1,一_2,...,一_5  \}}$ (可自行設計) ,以及已知賠率表向量 $odds_{P}$。開完球後,把Bingo 卡上的中獎的號碼圈起來形成"中獎圖形" ===================================================== 其中獎項圖形 : "$Bingo$" 代表$25$個號碼全中 "十"代表第 $3$ 列(row)  第 $3$ 行 (column) 有中 (共$9$個號碼) "王"代表第 $1$ , $3$ , $5$ 列(row)  第 $3$ 行 (column) 有中 (共$17$個號碼) "$一_k$" 代表第 $k$ 列有中 (共$5$個號碼) ===================================================== 若中獎圖形有涵蓋獎項圖形大致會獲得,賠率 $odds_{p} \times 1 $ 元,但有些合理規則: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ $[ 規則 1 ]$ 若獎項圖形 $p_1,p_2$ 有完全重疊$(p_1 \subseteq p_2)$,則以大圖形 $odds_{p_2}$ 賠率算 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ $$\color{green}{ 重要假設: 合理的