不使用行列式的特徵值和特徵向量算法 (中)

本文的閱讀等級:中級

給定一 n\times n 階矩陣 A,若 n 維向量 \mathbf{x}\neq\mathbf{0} 使得 A\mathbf{x}=\lambda\mathbf{x},即 (A-\lambda I)\mathbf{x}=\mathbf{0},則 \lambda 稱為特徵值,\mathbf{x} 是對應的特徵向量。因為 A-\lambda I 的零空間包含非零向量,可知 A-\lambda I 不可逆,所以 \det(\lambda I-A)=0。根據此事實,我們定義 A 的特徵多項式為 p_A(t)=\det(tI-A),特徵值 \lambda 即是 p_A(t) 的根。從課堂演習的角度來看,這個基於行列式的特徵值算法的最大缺點在於,當 n 增大時,自行列式表達 p_A(t)=\det(tI-A) 到標準式

p_A(t)=t^n+a_{n-1}t^{n-1}+\cdots+a_1t+a_0

往往需要耗費大量的計算 (這解釋了何以多數線性代數教科書僅見 2\times 23\times 3 階的數值例子)。因為這個緣故,我們將箭頭瞄準不使用行列式的特徵值和特徵向量算法。下面先檢視幾種無須計算即可獲取特徵多項式的特殊形態矩陣,然後設法推導從任意矩陣至特殊形態矩陣的相似變換。

 
愛因斯坦說:「盡可能簡化事情,但不要更簡單。」(Make everything as simple as possible, but not simpler.) 就取得特徵多項式而言,甚麼是「最簡單的矩陣,且不必更簡單」?答案是上 (或下) 三角矩陣:

U=\begin{bmatrix}  u_{11}& &\ast \\  &\ddots & \\  0& & u_{nn}  \end{bmatrix}

根據行列式性質,上三角矩陣的主對角元即為特徵值,特徵多項式具有完全分解形式 p_U(t)=(t-u_{11})\cdots(t-u_{nn})。任一 n\times n 階矩陣 A 皆可被上三角化 (見“不變子空間──解構線性算子的利器”),也就是說,存在一可逆矩陣 S 使得 U=S^{-1}AS 是上三角矩陣。兩相似矩陣有相同的特徵多項式 (見“相似變換下的不變性質”),因為 A 相似於 U,故 p_A(t)=p_U(t)。不幸的是,找尋可使 A 上三角化的可逆矩陣 S 不是一件容易的工作。

 
退而求其次,除了上三角矩陣,還有哪些矩陣可以立刻讀出特徵多項式?答案是相伴矩陣 (companion matrix),如下:

C=\begin{bmatrix}    0&0&\cdots&0&-c_0\\    1&0&\cdots&0&-c_1\\    \vdots&\ddots&\ddots&\vdots&\vdots\\    0&\cdots&1&0&-c_{n-2}\\    0&0&\cdots&1&-c_{n-1}    \end{bmatrix}

此矩陣的特徵多項式是 p_C(t)=t^n+c_{n-1}t^{n-1}+\cdots+c_1t+c_0 (見“多項式的相伴矩陣”)。若 n=1p_C(t)=t+c_0 對應 1\times 1 階相伴矩陣 [-c_0]。給定一 n 階方陣 A,設可逆矩陣 S=\begin{bmatrix}  \mathbf{v}_1&\cdots&\mathbf{v}_n  \end{bmatrix} 使得 AS=SC,如下:

A\begin{bmatrix}  \mathbf{v}_1&\mathbf{v}_2&\cdots&\mathbf{v}_{n-1}&\mathbf{v}_n  \end{bmatrix}=\begin{bmatrix}  \mathbf{v}_1&\mathbf{v}_2&\cdots&\mathbf{v}_{n-1}&\mathbf{v}_n  \end{bmatrix}\begin{bmatrix}    0&0&\cdots&0&-c_0\\    1&0&\cdots&0&-c_1\\    \vdots&\ddots&\ddots&\vdots&\vdots\\    0&\cdots&1&0&-c_{n-2}\\    0&0&\cdots&1&-c_{n-1}    \end{bmatrix}

乘開上式可得方程組:

\begin{aligned}  A\mathbf{v}_1&=\mathbf{v}_2\\  A\mathbf{v}_2&=\mathbf{v}_3\\  &\vdots\\  A\mathbf{v}_{n-1}&=\mathbf{v}_n\\  A\mathbf{v}_n&=-c_0\mathbf{v}_1-c_1\mathbf{v}_2-\cdots-c_{n-2}\mathbf{v}_{n-1}-c_{n-1}\mathbf{v}_n.\end{aligned}

因此,\mathbf{v}_2=A\mathbf{v}_1\mathbf{v}_3=A\mathbf{v}_2=A^2\mathbf{v}_1,依此類推,\mathbf{v}_k=A^{k-1}\mathbf{v}_11<k\le n。這種由「種子」\mathbf{v}_1 屢乘 A 而生的子空間 \mathrm{span}\{\mathbf{v}_1,A\mathbf{v}_1,A^2\mathbf{v}_1,\ldots,\} 稱為循環子空間 (見“利用循環子空間計算特徵多項式”)。若 \mathbf{v}_1 使得 \{\mathbf{v}_1,A\mathbf{v}_1,\ldots,A^{n-1}\mathbf{v}_1\} 成為 \mathbb{C}^n 的一組基底 (這時 p_A(t)=p_C(t)),則 \mathbf{v}_1 稱為循環向量 (cyclic vector)。然而,現實是矩陣 A 未必相似於一相伴矩陣 C,換句話說,循環向量未必存在。即使 A 相似於一相伴矩陣,我們也不知道循環向量究竟為何。在循環子空間的生成過程中,當第一次發生 \{\mathbf{v}_1,A\mathbf{v}_1,\ldots,A^k\mathbf{v}_1\} 是線性相關向量集時,也就是存在 d_1,\ldots,d_{k-1} 使得 A^k\mathbf{v}_1=d_1\mathbf{v}_1+\cdots+d_{k-1}A^{k-1}\mathbf{v}_1,即宣告由 \mathbf{v}_1 生成的循環子空間已達到「飽和」狀態。上式繼續左乘 A,很容易確認對於 j\ge kA^j\mathbf{v}_1\in\mathrm{span}\{\mathbf{v}_1,A\mathbf{v}_1,\ldots,A^{k-1}\mathbf{v}_1\},因此得知 \{\mathbf{v}_1,A\mathbf{v}_1,\ldots,A^{k-1}\mathbf{v}_1\} 是種子 \mathbf{v}_1 所能生成的最大線性獨立集。

 
從以上討論,我們知道 (1) 任一矩陣皆可被上三角化,但使之實現的基底幾不可尋;(2) 循環子空間可產生容易閱讀特徵多項式的相伴矩陣,但未必能獲致完整的 \mathbb{C}^n 基底。於是我們有了結合上三角矩陣和相伴矩陣的想法,兩者可合成分塊上三角 (block upper triangular) 矩陣,稱為 Frobenius 矩陣,如下:

F=\begin{bmatrix}  F_{11}& &\ast \\  &\ddots & \\  0& & F_{kk}  \end{bmatrix}

其中主對角分塊 F_{ii} 具備相伴矩陣型態。根據分塊上三角矩陣的行列式性質,Frobenius 矩陣的特徵多項式有不完全分解形式 p_F(t)=p_1(t)\cdots p_k(t),這裡 p_i(t) 代表相伴分塊 F_{ii} 的特徵多項式。如同上三角矩陣,任何方陣 A 皆相似於一 Frobenius 矩陣 F,因此 p_A(t)=p_F(t)。我們介紹的不使用行列式的特徵值和特徵向量算法即建立在此性質上,而算法本身等同提供一個建構性的證明。

 
下面我用一個例子來說明如何找尋一組基底使得給定矩陣 A 相似於 Frobenius 矩陣。設 A 是一 6\times 6 階矩陣,S=\begin{bmatrix}  \mathbf{v}_1&\cdots\mathbf{v}_6  \end{bmatrix} 可逆且 AS=SF,其中 F 就是 A 參考基底 \mathfrak{B}=\{\mathbf{v}_1,\ldots,\mathbf{v}_6\} 的表示矩陣,如下:

F=\left[\!\!\begin{array}{crcccrcc}  0&3&\vline&1&2&3&&2\\  1&-2&\vline&2&4&6&&0\\ \cline{1-6}  0&0&\vline &0&0&0&\vline&1\\  0&0&\vline &1&0&6&\vline&3\\  0&0&\vline &0&1&-1&\vline&2\\ \cline{4-8}  0&0& &0&0&0&\vline&4  \end{array}\!\!\right]

Frobenius 矩陣 F 包含3個主對角相伴分塊,其特徵多項式是

p_F(t)=(t^2+2t-3)(t^3+t^2-6t)(t-4)

考慮 AS=SF,乘開可得

\begin{aligned}  A\mathbf{v}_1&=\mathbf{v}_2\\  A\mathbf{v}_2&=3\mathbf{v}_1-2\mathbf{v}_2\\  A\mathbf{v}_3&=\mathbf{v}_1+2\mathbf{v}_2+\mathbf{v}_4\\  A\mathbf{v}_4&=2\mathbf{v}_1+4\mathbf{v}_2+\mathbf{v}_5\\  A\mathbf{v}_5&=3\mathbf{v}_1+6\mathbf{v}_2+6\mathbf{v}_4-\mathbf{v}_5\\  A\mathbf{v}_6&=2\mathbf{v}_1+\mathbf{v}_3+3\mathbf{v}_4+2\mathbf{v}_5+4\mathbf{v}_6.\end{aligned}

設想有序基底向量 \mathbf{v}_1,\ldots,\mathbf{v}_6 按照指標順序產生。第一個式子 \mathbf{v}_2=A\mathbf{v}_1 提示 \mathbf{v}_2\mathbf{v}_1 生成,\mathbf{v}_1 是第一個主對角分塊的種子。第二式指出 A\mathbf{v}_2\mathbf{v}_1\mathbf{v}_2 的線性組合,這意味 A\mathbf{v}_2 不能加入既成的線性獨立集 \{\mathbf{v}_1,\mathbf{v}_2\},宣告由種子 \mathbf{v}_1 起始的基底生成至此告一段落。我們另起爐灶,挑選一個不屬於子空間 \mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2\} 的新種子 \mathbf{v}_3,並期待 \mathbf{v}_3 可以按照前述方式依序生成 \mathbf{v}_4=A\mathbf{v}_3\mathbf{v}_5=A\mathbf{v}_4 (因為第二個主對角分塊對應3,4,5元)。可惜事與願違,第三式和第四式打碎了我們的美夢。有甚麼補救措施呢?最直接的作法是更換一組新基底 \mathfrak{B}'=\{\mathbf{v}'_1,\ldots,\mathbf{v}'_6\} 使得 (1) A\mathbf{v}'_i 等於 \mathbf{v}'_{i+1} (代表種子的基底生成序列進行中) 或 (2) A\mathbf{v}'_i\mathbf{v}'_1,\ldots,\mathbf{v}'_i 的線性組合 (代表種子的基底生成序列結束)。我們稱滿足此條件的基底為「良好基底」。令 \mathbf{v}'_4=A\mathbf{v}'_3\mathbf{v}'_5=A\mathbf{v}'_4,其餘基底向量維持不變,套用上面的方程組,可得

\begin{aligned}  \mathbf{v}'_4&=A\mathbf{v}'_3=A\mathbf{v}_3=\mathbf{v}_1+2\mathbf{v}_2+\mathbf{v}_4\\  \mathbf{v}'_5&=A\mathbf{v}'_4=A(\mathbf{v}_1+2\mathbf{v}_2+\mathbf{v}_4)=A\mathbf{v}_1+2A\mathbf{v}_2+A\mathbf{v}_4\\  &=\mathbf{v}_2+2(3\mathbf{v}_1-2\mathbf{v}_2)+2\mathbf{v}_1+4\mathbf{v}_2+\mathbf{v}_5=8\mathbf{v}_1+\mathbf{v}_2+\mathbf{v}_5.\end{aligned}

將基底變換關係表示成矩陣形式:

\begin{aligned}  S'&=\begin{bmatrix}  \mathbf{v}'_1&\mathbf{v}'_2&\mathbf{v}'_3&\mathbf{v}'_4&\mathbf{v}'_5&\mathbf{v}'_6  \end{bmatrix}\\  &=\begin{bmatrix}  \mathbf{v}_1&\mathbf{v}_2&\mathbf{v}_3&\mathbf{v}_4&\mathbf{v}_5&\mathbf{v}_6  \end{bmatrix}\begin{bmatrix}  1&0&0&1&8&0\\  0&1&0&2&1&0\\  0&0&1&0&0&0\\  0&0&0&1&0&0\\  0&0&0&0&1&0\\  0&0&0&0&0&1\end{bmatrix}\\  &=SM.\end{aligned}

因為 M 可逆,以 S=S'M^{-1} 代入 AS=SF,就有 AS'M^{-1}=S'M^{-1}F,右乘 M,即得 AS'=S'(M^{-1}FM)。所以,A 參考新基底 \mathfrak{B}' 的表示矩陣是 F'=M^{-1}FM,如下:

F'=\left[\!\!\begin{array}{crcccrcr}  0&3&\vline&0&0&8&&-17\\  1&-2&\vline&0&0&1&&-8\\ \cline{1-6}  0&0&\vline &0&0&0&\vline&1\\  0&0&\vline &1&0&6&\vline&3\\  0&0&\vline &0&1&-1&\vline&2\\ \cline{4-8}  0&0& &0&0&0&\vline&4  \end{array}\!\!\right]

檢查 Frobenius 矩陣 F' 的行向量,可確認新的有序基底 \{\mathbf{v}'_1,\ldots,\mathbf{v}'_6\} 符合良好基底的條件。

 
從上例可以歸納出一個簡易的良好基底算法使得 A 相似於一 Frobenius 矩陣。令 A 為一 n\times n 階矩陣 (n>1),選擇任一 n 維非零向量 \mathbf{v}_1,稱為種子。若 \{\mathbf{v}_1,A\mathbf{v}_1\} 為一線性獨立集,設 \mathbf{v}_2=A\mathbf{v}_1,否則重新選擇 \mathbf{v}_2\notin\mathrm{span}\{\mathbf{v}_1\}。假設我們已得到 i 個線性獨立向量 \{\mathbf{v}_1,\ldots,\mathbf{v}_i\},算出 A\mathbf{v}_i。若 \{\mathbf{v}_1,\ldots,\mathbf{v}_i,A\mathbf{v}_i\} 構成線性獨立集,則設 \mathbf{v}_{i+1}=A\mathbf{v}_i,否則 (若 n>i) 重新選擇 \mathbf{v}_{i+1}\notin\{\mathbf{v}_1,\ldots,\mathbf{v}_i\} 作為種子。重複此程序,直到找齊 n 個線性獨立向量,此即 \mathbb{C}^n 的一組基底 \{\mathbf{v}_1,\ldots,\mathbf{v}_n\}。運用這個算法,我們不僅獲得一組基底和 Frobenius 矩陣 F,並可算出特徵值和對應的特徵向量,詳細過程請見“不使用行列式的特徵值和特徵向量算法 (上)”。

 
最後還有一些細節需要釐清,包括如何選擇「好種子」,設計能夠快速檢查 A\mathbf{v}_i 是否為 \mathbf{v}_1,\ldots,\mathbf{v}_i 的線性組合的實用算法,以及探討特徵向量算法的原理及限制 (例如,不論特徵值的相重數為何,是否總能求得完整的特徵空間?)。這些問題將留待下文討論。

繼續閱讀:
Advertisements
本篇發表於 特徵分析, 線性代數專欄 並標籤為 , , , , , , , , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s