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

本文的閱讀等級:高級

延續前文“不使用行列式的特徵值和特徵向量算法 (上)”和“不使用行列式的特徵值和特徵向量算法 (中)”,本文將討論以下三個與實際操作相關的問題:(1) 如何選擇「好種子」?(2) 如何快速檢查 A\mathbf{v}_i 是否為 \mathbf{v}_1,\ldots,\mathbf{v}_i 的線性組合?(3) 特徵向量算法的基本原理是甚麼?不論特徵值的相重數為何,是否總能求得完整的特徵空間?往下閱讀前,請讀者先回顧前文。

 
從計算面來看,所謂的「好種子」\mathbf{v}_i 應具備的第一個性質是數值越簡單越好,譬如,標準單位向量 \mathbf{e}_j (第 j 元是 1,其餘元是 0)。見下例,

A=\left[\!\!\begin{array}{rrrr}  1&2&3&4\\  5&6&7&8\\  9&10&11&12\\  13&14&15&16  \end{array}\!\!\right]

設第一個種子 \mathbf{v}_1=\mathbf{e}_1,可得向量序:

\mathbf{v}_1=\begin{bmatrix}  1\\  0\\  0\\  0  \end{bmatrix},~~A\mathbf{v}_1=\left[\!\!\begin{array}{r}  1\\  5\\  9\\  13  \end{array}\!\!\right],~~A^2\mathbf{v}_1=\left[\!\!\begin{array}{r}  90\\  202\\  314\\  426  \end{array}\!\!\right],~~A^3\mathbf{v}_1=\left[\!\!\begin{array}{r}  3140\\  7268\\  11396\\  15524  \end{array}\!\!\right]

其中 \{\mathbf{v}_1,A\mathbf{v}_1,A^2\mathbf{v}_1\} 為一線性獨立集,但 A^3\mathbf{v}_1=80A\mathbf{v}_1+34A^2\mathbf{v}_1,故設 \mathbf{v}_2=A\mathbf{v}_1\mathbf{v}_3=A^2\mathbf{v}_1。以標準單位向量 \mathbf{e}_j 作為種子無須計算立得 A\mathbf{e}_j,即 A 的第 j 行,不過隨後生成的向量仍可能產生大數值。這個事實點出「好種子」的第二個性質:種子 \mathbf{v}_i 生成的線性獨立向量集 \{\mathbf{v}_i,A\mathbf{v}_i,\ldots,A^{k-1}\mathbf{v}_i\} 的基數 (cardinal number,即 k) 越小越好。如此一來,不僅降低大數值發生的可能性,同時也得到次數較小的特徵多項式因式,便於求解特徵值。如果種子 \mathbf{v}_i 滿足 A\mathbf{v}_i=\lambda_i\mathbf{v}_i,可知 \mathbf{v}_i 是一特徵向量,生成的線性獨立向量集基數等於 1,特徵多項式包含因式 (t-\lambda_i)。觀察發現上例矩陣 A 的第 j+1 行等於第 j 行加 (1,1,1,1)^T,即知 A 不可逆,也就是說,A 有特徵值 0。運用探索法 (“實對稱矩陣的特徵值和特徵向量探索解法”),可得特徵向量

\mathbf{x}_1=\left[\!\!\begin{array}{r}  1\\  -2\\  1\\  0  \end{array}\!\!\right],~~\mathbf{x}_2=\left[\!\!\begin{array}{r}  0\\  1\\  -2\\  1  \end{array}\!\!\right]

根據這個結果,以特徵向量作為種子,設 \mathbf{v}_1=\mathbf{x}_1\mathbf{v}_2=\mathbf{x}_2,如此一口氣就得到二個特徵向量對應特徵值 0。接著該如何選擇下一個種子 \mathbf{v}_3\notin\mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2\}?我們需要第三個性質:「好種子」 \mathbf{v}_i 產生的 A\mathbf{v}_i 向量數值應越簡單越好。譬如,\mathbf{v}_3=(-1,1,0,0)^T 生成 A\mathbf{v}_3=(1,1,1,1)^T。因為 A 的第 i+1 列等於第 i 列加上 (4,4,4,4),很容易求出向量序:

\mathbf{v}_3=\left[\!\!\begin{array}{r}  -1\\  1\\  0\\  0  \end{array}\!\!\right],~~A\mathbf{v}_3=\left[\!\!\begin{array}{r}  1\\  1\\  1\\  1  \end{array}\!\!\right],~~A^2\mathbf{v}_3=\left[\!\!\begin{array}{r}  10\\  26\\  42\\  58  \end{array}\!\!\right]

\mathbf{v}_4=A\mathbf{v}_3,計算可得 A^2\mathbf{v}_3=56\mathbf{v}_1+24\mathbf{v}_2+80\mathbf{v}_3+34\mathbf{v}_4。將以上結果整理成下表:

\begin{array}{rrrrcrcrcrcc}   &A&&&\vline&\mathbf{v}_1 & \vline&\mathbf{v}_2 &\vline&\mathbf{v}_3&\mathbf{v}_4&A^2\mathbf{v}_3\\ \hline     1&2&3&4&\vline&1&\vline &0&\vline & -1 &1&10\\     5&6&7&8&\vline&-2&\vline& 1 &\vline &1 &1&26\\     9&10&11&12&\vline&1&\vline&-2 &\vline&0&1&42\\     13&14&15&16&\vline&0&\vline&1&\vline &0 &1&58\\ \hline     &&&&\vline&56&&24& &80 & 34 & \\ \hline \end{array}

所以,A 相似於 Frobenius 矩陣

F=\left[\!\!\begin{array}{rcrcrr}  0&\vline&0&&0&56\\ \cline{1-3}  0&\vline&0&\vline&0&24\\ \cline{3-6}  0&&0&\vline&0&80\\  0&&0&\vline&1&34  \end{array}\!\!\right]

即知特徵多項式 p_A(t)=p_F(t)=t^2(t^2-34t-80)

 
選擇適當的「好種子」可以減低計算的複雜度,但要如何快速檢查 A\mathbf{v}_i 是否為 \mathbf{v}_1,\mathbf{v}_2,\ldots,\mathbf{v}_i 的線性組合?如果是,組合權重又為何?我們知道基本列運算不改變行向量之間的線性組合關係 (見“左乘還是右乘,這就是問題所在”),利用此性質可設計一個簡明的簿記方法。以上例 A 說明,我們用一個 4\times 4 矩陣 E 記錄所有執行過的基本列運算,初始值設為單位矩陣 I_4。以下提及的 E 指的是最新的計算結果。設 \mathbf{v}_1=(1,-2,1,0)^T,寫出增廣矩陣 \begin{bmatrix}  E\,\vert\, E\mathbf{v}_1  \end{bmatrix}。以基本列運算將分塊 E\mathbf{v}_1 化簡成簡約列梯形式,即單位向量 \mathbf{e}_1,如下:

\begin{array}{cccccr}  &&E&&&E\mathbf{v}_1\\ \hline  1&0&0&0&\vline&1\\  0&1&0&0&\vline&-2\\  0&0&1&0&\vline&1\\  0&0&0&1&\vline&0 \\ \hline  \end{array}\to  \begin{array}{rccccc}  &&E&&&E\mathbf{v}_1\\ \hline  1&0&0&0&\vline&1\\  2&1&0&0&\vline&0\\  -1&0&1&0&\vline&0\\  0&0&0&1&\vline&0 \\ \hline  \end{array}

設新種子 \mathbf{v}_2=(0,1,-2,1)^T,計算可得 E\mathbf{v}_2=(0,1,-2,1)^T。將此結果併入增廣矩陣,並繼續以基本列運算將分塊 \begin{bmatrix}  E\mathbf{v}_1&E\mathbf{v}_2  \end{bmatrix} 化簡至簡約列梯形式,如下:

\to\begin{array}{rcccccr}  &&E&&&E\mathbf{v}_1&E\mathbf{v}_2\\ \hline  1&0&0&0&\vline&1&0\\  2&1&0&0&\vline&0&1\\  -1&0&1&0&\vline&0&-2\\  0&0&0&1&\vline&0&1 \\ \hline  \end{array}\to  \begin{array}{rrccccc}  &&E&&&E\mathbf{v}_1&E\mathbf{v}_2\\ \hline  1&0&0&0&\vline&1&0\\  2&1&0&0&\vline&0&1\\  3&2&1&0&\vline&0&0\\  -2&-1&0&1&\vline&0&0\\ \hline  \end{array}

設新種子 \mathbf{v}_3=(-1,1,0,0)^T,算出 E\mathbf{v}_3=(-1,-1,-1,1)^T,併入增廣矩陣,化簡得

\to\begin{array}{rrcccccr}  &&E&&&E\mathbf{v}_1&E\mathbf{v}_2&E\mathbf{v}_3\\ \hline  1&0&0&0&\vline&1&0&-1\\  2&1&0&0&\vline&0&1 &-1\\   3&2&1&0&\vline&0&0&-1\\  -2&-1&0&1&\vline&0&0&1\\ \hline  \end{array}\to  \begin{array}{rrrccccc}  &&E&&&E\mathbf{v}_1&E\mathbf{v}_2&E\mathbf{v}_3\\ \hline  -2&-2&-1&0&\vline&1&0&0\\  -1&-1&-1&0&\vline&0&1 &0\\   -3&-2&-1&0&\vline&0&0&1\\  1&1&1&1&\vline&0&0&0\\ \hline  \end{array}

因為 E 是可逆矩陣,\mathrm{rank}\begin{bmatrix}  E\mathbf{v}_1&E\mathbf{v}_2&E\mathbf{v}_3  \end{bmatrix}=\mathrm{rank}\begin{bmatrix}  \mathbf{v}_1&\mathbf{v}_2&\mathbf{v}_3\end{bmatrix}=3,可知 \{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\} 是線性獨立集。接著考慮 A\mathbf{v}_3=(1,1,1,1)^T,算出 EA\mathbf{v}_3=(-5,-3,-6,4)^T,併入增廣矩陣,化簡得

\to\begin{array}{rrrcccccr}  &&E&&&E\mathbf{v}_1&E\mathbf{v}_2&E\mathbf{v}_3&EA\mathbf{v}_3\\ \hline  -2&-2&-1&0&\vline&1&0&0&-5\\  -1&-1&-1&0&\vline&0&1 &0&-3\\   -3&-2&-1&0&\vline&0&0&1&-6\\  1&1&1&1&\vline&0&0&0&4\\ \hline  \end{array}

\to  \begin{array}{rrrrccccc}  &&E&&&E\mathbf{v}_1&E\mathbf{v}_2&E\mathbf{v}_3&EA\mathbf{v}_3\\ \hline  -\frac{3}{4}&-\frac{3}{4}&\frac{1}{4}&\frac{5}{4}&\vline&1&0&0&0\\[0.3em]  -\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}&\frac{3}{4}&\vline&0&1 &0&0\\[0.3em]   -\frac{3}{2}&-\frac{1}{2}&\frac{1}{2}&\frac{3}{2}&\vline&0&0&1&0\\[0.3em]  \frac{1}{4}&\frac{1}{4}&\frac{1}{4}&\frac{1}{4}&\vline&0&0&0&1\\ \hline  \end{array}

因為 \mathrm{rank}\begin{bmatrix}  E\mathbf{v}_1&E\mathbf{v}_2&E\mathbf{v}_3&EA\mathbf{v}_3  \end{bmatrix}=4,確定 A\mathbf{v}_3 不破壞線性獨立性,設 \mathbf{v}_4=A\mathbf{v}_3。最後考慮 A^2\mathbf{v}_3=(10,26,42,58)^T,算出 EA^2\mathbf{v}_3=(56,24,80,34)^T,併入增廣矩陣:

\to  \begin{array}{rrrrcccccc}  &&E&&&E\mathbf{v}_1&E\mathbf{v}_2&E\mathbf{v}_3&E\mathbf{v}_4 &EA^2\mathbf{v}_3\\ \hline  -\frac{3}{4}&-\frac{3}{4}&\frac{1}{4}&\frac{5}{4}&\vline&1&0&0&0&56\\[0.3em]  -\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}&\frac{3}{4}&\vline&0&1 &0&0&24\\[0.3em]   -\frac{3}{2}&-\frac{1}{2}&\frac{1}{2}&\frac{3}{2}&\vline&0&0&1&0&80\\[0.3em]  \frac{1}{4}&\frac{1}{4}&\frac{1}{4}&\frac{1}{4}&\vline&0&0&0&1&34\\ \hline  \end{array}

最末一行說明 A^2\mathbf{v}_3 可表示為 \mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4 的線性組合,EA^2\mathbf{v}_3 的元即為對應的組合權重。

 
最後我們討論特徵向量的算法。考慮 n\times n 階矩陣 A。為方便說明,令 \mathbf{v}_1,\ldots,\mathbf{v}_n 是種子 \mathbf{w}_1,\ldots,\mathbf{w}_m 生成的 \mathbb{C}^n 基底,p_i(t) 表示種子 \mathbf{w}_i 生成的向量序所對應的特徵多項式因式,\mathcal{X}_i 表示 \mathbf{v}_1,\ldots,\mathbf{v}_j 擴張出的子空間,其中 \mathbf{v}_{j+1}=\mathbf{w}_{i+1}。上例中,n=4m=3,種子 \mathbf{w}_1=\mathbf{v}_1\mathbf{w}_2=\mathbf{v}_2\mathbf{w}_3=\mathbf{v}_3,對應因式 p_1(t)=tp_2(t)=tp_3(t)=t^2-34t-80,子空間則為 \mathcal{X}_1=\mathrm{span}\{\mathbf{v}_1\}\mathcal{X}_2=\mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2\}\mathcal{X}_3=\mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4\}=\mathbb{C}^4。對於 i=1,\ldots,m,不難確認演算法採用的基底向量的生成方式使得每一 \mathbf{x}\in\mathcal{X}_i,皆有 A\mathbf{x}\in\mathcal{X}_i,換句話說,\mathcal{X}_i 是一不變子空間。若將 A 限定於不變子空間 \mathcal{X}_i,則 A_{/\mathcal{X}_i} 稱為限定算子 (見“限定算子的特徵值與特徵向量 (上)”),其特徵多項式是 p_{A_{/\mathcal{X}_i}}(t)=p_1(t)\ldots p_i(t)。限定算子 A_{/\mathcal{X}_i} 的特徵多項式消滅子空間 \mathcal{X}_i (見“限定算子的特徵值與特徵向量 (下)”),也就是說,對於每一 \mathbf{x}\in\mathcal{X}_ii=1,\ldots,m

p_{A_{/\mathcal{X}_i}}(A)\mathbf{x}=p_1(A)\cdots p_i(A)\mathbf{x}=\mathbf{0}

對於特徵值 \lambda_j,特徵向量 \mathbf{x}_j 滿足特徵方程 (A-\lambda_jI)\mathbf{x}_j=\mathbf{0}。上式提供了求解特徵向量 \mathbf{x}_j 所需的特徵方程。若 p_i(t) 包含因式 (t-\lambda_j),令 p_{A_{/\mathcal{X}_i}}(t)=(t-\lambda_j)q(t),則 p_{A_{/\mathcal{X}_i}}(A)\mathbf{w}_i=(A-\lambda_jI)q(A)\mathbf{w}_i=\mathbf{0},也就有 \mathbf{x}_j=q(A)\mathbf{w}_i。我們用前例解說特徵向量的計算過程。若 \mathbf{x}\in\mathcal{X}_1=\mathrm{span}\{\mathbf{v}_1\}

p_1(A)\mathbf{x}=A\mathbf{x}=\mathbf{0}

對應特徵值 \lambda_1=0 的特徵向量是 \mathbf{x}_1=\mathbf{v}_1。若 \mathbf{x}\in\mathcal{X}_2=\mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2\}

p_1(A)p_2(A)\mathbf{x}=A^2\mathbf{x}=A(A\mathbf{x})=\mathbf{0}

新增特徵值 \lambda_2=0。設 \mathbf{x}=\mathbf{v}_2,則特徵向量是 \mathbf{x}_2=A\mathbf{v}_2,但 A\mathbf{v}_2=\mathbf{0},因此改設 \mathbf{x}_2=\mathbf{v}_2。這個結果顯示特徵向量算法可能失效,稍後再詳細說明。若 \mathbf{x}\in\mathcal{X}_3=\mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4\}

p_1(A)p_2(A)p_3(A)\mathbf{x}=A^2(A^2-34A-80)\mathbf{x}  =(A-\lambda_3I)(A-\lambda_4I)A^2\mathbf{x}=\mathbf{0}

其中 \lambda_3=17+3\sqrt{41}\lambda_4=17-3\sqrt{41}。設 \mathbf{x}=\mathbf{v}_3,對應的特徵向量分別是 \mathbf{x}_3=(A-\lambda_4I)A^2\mathbf{v}_3\mathbf{x}_4=(A-\lambda_3I)A^2\mathbf{v}_3。在此省略數值計算結果,請讀者自行驗證。

 
請特別注意,我們介紹的特徵向量計算法未必能夠找齊所有的線性獨立特徵向量。例如 (取自[1]),

A=\left[\!\!\begin{array}{cccc}  0&0&\vline&0\\  1&0&\vline&1\\ \hline  0&0&\vline&0  \end{array}\!\!\right]

有重複3次的特徵值 0,並有2個線性獨立的特徵向量 (0,1,0)^T(-1,0,1)^T。算法給出 \mathbf{v}_1=(1,0,0)^T\mathbf{v}_2=A\mathbf{v}_1=(0,1,0)^T\mathbf{v}_3=(0,0,1)^T。若 \mathbf{x}\in\mathcal{X}_1=\mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2\},則 p_1(A)\mathbf{x}=A^2\mathbf{x}=\mathbf{0},得到 \mathbf{x}_1=A\mathbf{v}_1=(0,1,0)^T。若 \mathbf{x}\in\mathcal{X}_2=\mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\},則 p_1(A)p_2(A)\mathbf{x}=A^3\mathbf{x}=A(A^2\mathbf{x})=\mathbf{0},得到 \mathbf{x}_2=A^2\mathbf{v}_3=\mathbf{0},不符要求。這個例子說明若矩陣 A 包含重複特徵值 \lambda_j,上述特徵向量算法可能失效,此時為了保險起見,我們可以使用標準的線性方程解法 (如高斯消去法) 求得完整的零空間 N(A-\lambda_jI)

 
參考來源:
[1] William A. McWorter, Jr., An algorithm for the characteristic polynomial, Mathematics Magazine, Vol. 56, No. 3, 1983, pp 168-175.

This entry was posted in 特徵分析, 線性代數專欄 and tagged , , , , , . Bookmark the permalink.

發表迴響

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

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s