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

本文的閱讀等級:中級

一百年前,行列式曾經是一個重要的數學領域。隨著數學發展方向的改變,今天行列式已漸漸遠離線性代數和矩陣理論的中心。但為甚麼絕大多數的近代線性代數教科書仍將行列式納入課程內容?美國數學教授奈林 (Evar D. Nering) 一語道破箇中緣由[1]

我們介紹行列式理論的一些主題之目的僅為了求一線性變換的特徵值。若不是因為這個用途,我們不會在本書裡討論行列式。

A 是一個 n\times n 階線性變換表示矩陣。定義 A 的特徵多項式為 p_A(t)=\det(A-tI),特徵值 \lambda 即是 p_A(t) 的根,對應的特徵向量 \mathbf{x} 滿足 (A-\lambda I)\mathbf{x}=\mathbf{0}。以上是多數教本採用的論述方式。奈林不是唯一對行列式冷感的學者,美國數學教授阿斯勒 (Sheldon Axler) 認為行列式難以理解,不具清晰直覺,且常在缺乏動機的情況下被定義出來。為擺脫行列式,他甚至寫了一本書《線性代數正確完成》(Linear Algebra Done Right) 試圖說服大眾:即便沒有行列式,線性代數照樣伸展自如 (見“拒絕行列式的特徵分析”)。不過,缺少行列式這個工具,阿斯勒並沒有告訴讀者如何計算特徵多項式 (或特徵值)。關於這個問題,他建議大家使用現成的數值計算工具,並說[2]

不幸的是,對於一典型算子的表示矩陣 (參考任意基底),不存在精確的特徵值計算方法。然而,如果我們幸運地找到一基底使得參考它的表示矩陣是上三角矩陣,那麼計算特徵值這個問題就很簡單了。

如果我們幸運地找到一基底使得線性變換參考這組基底的表示矩陣是上三角矩陣,那麼線性變換 (或表示矩陣) 的特徵值即為上三角矩陣的主對角元。或許要找到一組能夠將矩陣三角化的基底需要一點運氣,但現今確實存在可使矩陣分塊三角化的基底計算方法[3-4]。由於此法產生的分塊上三角矩陣具備特殊的型態,從主對角分塊立刻得知特徵多項式,不僅如此,一旦確定了特徵值,僅需少量的計算即可求出特徵向量。下面我就為讀者介紹這個鮮為世人所知的不使用行列式 (也不倚靠運氣或個人修為) 的特徵值和特徵向量算法。

 
我先用一個例子展示計算過程,稍後再解釋算法背後的原理。考慮下面的 4\times 4 階矩陣:

A=\left[\!\!\begin{array}{rrrr} 1&-3&5&11\\ 2&-1&3&1\\ -1&1&0&0\\ 1&-1&2&2 \end{array}\!\!\right]

挑選任意非零向量 \mathbf{v}_1 作為「種子」,依序計算 A\mathbf{v}_1, A^2\mathbf{v}_1=A(A\mathbf{v}_1),\ldots,直到第一次發生 A^k\mathbf{v}_1\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 所能生成的最大線性獨立集。為簡化計算,設 \mathbf{v}_1=(1,0,0,0)^T,則得

\mathbf{v}_1=\begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix},~~A\mathbf{v}_1=\left[\!\!\begin{array}{r} 1\\ 2\\ -1\\ 1 \end{array}\!\!\right],~~A^2\mathbf{v}_1=\left[\!\!\begin{array}{r} 1\\ -2\\ 1\\ -1 \end{array}\!\!\right]

計算到此停止,因為 A^2\mathbf{v}_1=2\mathbf{v}_1-A\mathbf{v}_1。表面上,這個式子看似平淡無奇,裡面卻暗藏我們夢寐以求的特徵方程 (A-\lambda I)\mathbf{x}=\mathbf{0}。將式子改寫成

(A^2+A-2I)\mathbf{v}_1=(A-I)(A+2I)\mathbf{v}_1=(A+2I)(A-I)\mathbf{v}_1=\mathbf{0}

上式告訴我們 A 有特徵值 \lambda_1=1,對應特徵向量 \mathbf{x}_1=(A+2I)\mathbf{v}_1,以及特徵值 \lambda_2=-2,對應特徵向量 \mathbf{x}_2=(A-I)\mathbf{v}_1。將數值代入計算,可得

\begin{aligned} \mathbf{x}_1&=(A+2I)\mathbf{v}_1=A\mathbf{v}_1+2\mathbf{v}_1=\left[\!\!\begin{array}{r} 1\\ 2\\ -1\\ 1 \end{array}\!\!\right]+2\left[\!\!\begin{array}{c} 1\\ 0\\ 0\\ 0 \end{array}\!\!\right]=\left[\!\!\begin{array}{r} 3\\ 2\\ -1\\ 1 \end{array}\!\!\right]\\ \mathbf{x}_2&=(A-I)\mathbf{v}_1=A\mathbf{v}_1-\mathbf{v}_1=\left[\!\!\begin{array}{r} 1\\ 2\\ -1\\ 1 \end{array}\!\!\right]-\left[\!\!\begin{array}{c} 1\\ 0\\ 0\\ 0 \end{array}\!\!\right]=\left[\!\!\begin{array}{r} 0\\ 2\\ -1\\ 1 \end{array}\!\!\right].\end{aligned}

輕而易舉攻克 A 的兩個特徵值和對應的特徵向量,士氣大振,繼續整裝前進。

 
\mathbf{v}_2=A\mathbf{v}_1。接下來我們要在 \{\mathbf{v}_1,\mathbf{v}_2\} 所擴張的子空間之外尋找其它的基底向量。隨意挑選一個新種子 \mathbf{v}_3\notin \mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2\},按照上述方式計算 A\mathbf{v}_3, A^2\mathbf{v}_3=A(A\mathbf{v}_3),\ldots,同樣地,直到第一次發生 A^k\mathbf{v}_3\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, A\mathbf{v}_3,\ldots,A^{k-1}\mathbf{v}_3 的線性組合。設 \mathbf{v}_3=(0,1,0,0)^T,則得

\mathbf{v}_3=\begin{bmatrix} 0\\ 1\\ 0\\ 0 \end{bmatrix},~~A\mathbf{v}_3=\left[\!\!\begin{array}{r} -3\\ -1\\ 1\\ -1 \end{array}\!\!\right]

到此停止係因 A\mathbf{v}_3=-2\mathbf{v}_1-\mathbf{v}_2+\mathbf{v}_3。從這個式子如何推導特徵值 \lambda_3?將它改寫成 (A-I)\mathbf{v}_3=-2\mathbf{v}_1-A\mathbf{v}_1,等號兩邊同時左乘 (A^2+A-2I) 可消滅等號右邊,即得

(A^2+A-2I)(A-I)\mathbf{v}_3=(A-I)(A^2+A-2I)\mathbf{v}_3=\mathbf{0}

這表明 A 有特徵值 \lambda_3=1,對應的特徵向量是

\mathbf{x}_3=(A^2+A-2I)\mathbf{v}_3=A^2\mathbf{v}_3+A\mathbf{v}_3-2\mathbf{v}_3=\left[\!\!\begin{array}{r} -6\\ -3\\ 2\\ -2 \end{array}\!\!\right]+\left[\!\!\begin{array}{r} -3\\ -1\\ 1\\ -1 \end{array}\!\!\right]-2\left[\!\!\begin{array}{r} 0\\ 1\\ 0\\ 0 \end{array}\!\!\right]=\left[\!\!\begin{array}{r} -9\\ -6\\ 3\\ -3 \end{array}\!\!\right]

上式中,除了 A^2\mathbf{v}_3=A(A\mathbf{v}_3) 需要重新計算,其他向量均為已知結果。我們發現 \mathbf{x}_3=-3\mathbf{x}_1,特徵值 1 的幾何重數小於代數重數,故知 A 是不可對角化矩陣 (見“可對角化矩陣與缺陷矩陣的判定”)。

 
至此我們已將搜尋空間擴大至 \mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\}。還剩下一個特徵值待尋 (從 \mathrm{trace}A=2,我們可以提早知道最後一個特徵值),沿用老方法,隨意選擇一個新種子 \mathbf{v}_4\notin\mathrm{span}\{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\}。設 \mathbf{v}_4=(0,0,1,0)^T,按同樣方式計算:

\mathbf{v}_4=\begin{bmatrix} 0\\ 0\\ 1\\ 0 \end{bmatrix},~~A\mathbf{v}_4=\left[\!\!\begin{array}{r} 5\\ 3\\ 0\\ 2 \end{array}\!\!\right]

不難確認 A\mathbf{v}_4=3\mathbf{v}_1+2\mathbf{v}_2-\mathbf{v}_3+2\mathbf{v}_4。將此式改為 (A-2I)\mathbf{v}_4=3\mathbf{v}_1+2A\mathbf{v}_1-\mathbf{v}_3,等號兩邊同時左乘 (A^2+A-2I)(A-I) 可消滅等號右邊,

(A^2+A-2I)(A-I)(A-2I)\mathbf{v}_4=(A-2I)(A^2+A-2I)(A-I)\mathbf{v}_4=\mathbf{0}

即知 A 有特徵值 \lambda_4=2,對應的特徵向量是

\begin{aligned} \mathbf{x}_4&=(A^2+A-2I)(A-I)\mathbf{v}_4=(A^3-3A+2I)\mathbf{v}_4=A^3\mathbf{v}_4-3A\mathbf{v}_4+2\mathbf{v}_4\\ &=\left[\!\!\begin{array}{r} 47\\ 27\\ -9\\ 17 \end{array}\!\!\right]-3\left[\!\!\begin{array}{c} 5\\ 3\\ 0\\ 2 \end{array}\!\!\right]+2\left[\!\!\begin{array}{r} 0\\ 0\\ 1\\ 0 \end{array}\!\!\right]=\left[\!\!\begin{array}{r} 32\\ 18\\ -7\\ 11 \end{array}\!\!\right].\end{aligned}

 
最後我們將矩陣分塊三角化的基底計算過程以簿記方式呈現。下表左列出矩陣 A,種子和循環衍生的向量按生成順序抄寫在 A 的右側,包含三個種子及循環。底下三列顯示 A^2\mathbf{v}_1A\mathbf{v}_3A\mathbf{v}_4 以基底 \mathfrak{B}=\{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4\} 表示的線性組合係數。

\begin{array}{rrcrcrrrcrrccc} &A&&&\vline&\mathbf{v}_1 & \mathbf{v}_2 &A^2\mathbf{v}_1&\vline&\mathbf{v}_3&A\mathbf{v}_3&\vline&\mathbf{v}_4&A\mathbf{v}_4\\ \hline 1&-3&5&11&\vline&1&1 &1&\vline & 0 & -3&\vline&0&5\\ 2&-1&3&1&\vline&0&2 &-2&\vline &1 & -1&\vline&0&3\\ -1&1&0&0&\vline&0&-1 &1 &\vline&0& 1&\vline&1&0\\ 1&-1&2&2&\vline&0&1&-1 &\vline &0 & -1&\vline&0&2\\ \hline &&&&\vline&2&-1 & & \vline && & \vline & & \\ \cline{6-8} &&&&\vline&-2&-1& & &1 & & \vline& & \\ \cline{6-11} &&&&\vline&3&2& & &-1 & & & 2 & \\ \hline \end{array}

根據上表,使用 A\mathbf{v}_1=\mathbf{v}_2A\mathbf{v}_2=A^2\mathbf{v}_1,可知 A 和基底向量 \mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4 有下列關係:

A\begin{bmatrix} \mathbf{v}_1&\mathbf{v}_2&\mathbf{v}_3&\mathbf{v}_4 \end{bmatrix}=\begin{bmatrix} \mathbf{v}_1&\mathbf{v}_2&\mathbf{v}_3&\mathbf{v}_4 \end{bmatrix}\left[\!\!\begin{array}{crrr} 0&2&-2&3\\ 1&-1&-1&2\\ 0&0&1&-1\\ 0&0&0&2 \end{array}\!\!\right]

也就是說,A 參考 \mathfrak{B} 的表示矩陣 [A]_\mathfrak{B} 即為表中組合係數構成的分塊上三角矩陣:

[A]_\mathfrak{B}=\left[\!\!\begin{array}{crcrcr} 0&2&\vline&-2&&3\\ 1&-1&\vline&-1&&2\\ \cline{1-4} 0&0&\vline&1&\vline&-1\\ \cline{4-6} 0&0&&0&\vline&2  \end{array}\!\!\right]=S^{-1}AS

上式令 S=\begin{bmatrix} \mathbf{v}_1&\mathbf{v}_2&\mathbf{v}_3&\mathbf{v}_4 \end{bmatrix}。兩相似矩陣有相同的特徵多項式,因為 A 相似於 [A]_\mathfrak{B},立得

\begin{aligned} p_A(t)&=p_{[A]_\mathfrak{B}}(t)\\ &=\left|\!\!\begin{array}{cccc} 0-t&2&-2&3\\ 1&-1-t&-1&2\\ 0&0&1-t&-1\\ 0&0&0&2-t \end{array}\!\!\right|\\ &=\left|\!\!\begin{array}{cc} 0-t&2\\ 1&-1-t \end{array}\!\!\right|(1-t)(2-t)\\ &=(t^2+t-2)(t-1)(t-2)=(t-1)^2(t+2)(t-2).\end{aligned}

這裡行列式的作用僅在輔助說明 p_A(t)[A]_\mathfrak{B} 主對角分塊特徵多項式的積,與特徵值計算無關。事實上,上述算法已經求得 A 的特徵值 1, -2, 1, 2,即知特徵多項式是 p_A(t)=(t-1)^2(t+2)(t-2)

 
下文將解說這套不使用行列式的特徵值和特徵向量算法背後的原理,並討論一些實際操作時可能發生的情況。在此之前,建議讀者自行演練本文介紹的算法,並與傳統採用行列式的運算方法比較,如耗費時間、運算量和簿記抄寫等。為何基於行列式的特徵值算法始終屹立不墜?透過大量的實證,或許我們能窺見部分答案。

 
參考來源:
[1] Evar D. Nering, Linear Algebra and Matrix Theory, 2nd edition, 1970, pp 85. 原文是 “We introduce some topics from the theory of determinants solely for the purpose of finding the eigenvalues of a linear transformation. Were it not for this use of determinants we would not discuss them in this book.”
[2] Sheldon Axler, Linear Algebra Done Right, 2nd edition, 1997, pp 86. 原文是 “Unfortunately no method exists for exact computing the eigenvalue of a typical operator from its matrix (with respect to an arbitrary basis). However, if we fortunate enough to find a basis with respect to which the matrix of the operator is upper triangular, then the problem of computing the eigenvalues becomes trivial.”
[3] William A. McWorter, Jr., An algorithm for the characteristic polynomial, Mathematics Magazine, Vol. 56, No. 3, 1983, pp 168-175.
[4] William A. McWorter, Jr. and Leroy F. Meyers, Computing eigenvalues and eigenvectors without determinants, Mathematics Magazine, Vol. 71, No. 1, 1998, pp 24-33.

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

12 則回應給 不使用行列式的特徵值和特徵向量算法 (上)

  1. EMK 說:

    有一處不太明白。

    第二次計算得出1是特徵值的時候,如何知道是另一個特徵值,而不是重複了呢?
    即是,當計算出兩個1的時候,怎知道1的代數重數是二呢?

    • ccjou 說:

      好問題!前兩個特徵向量 x_1,x_2v_1,v_2 的線性組合,為了避免重複尋找,我們刻意在子空間 \mathrm{span}\{v_1,v_2\} 外挑選新種子 v_3\{v_1,v_2,v_3\} 線性獨立,搜尋範圍因此擴大,這保證新得到的1和舊的1無關。或者這麼說,第三個特徵方程形如 Av_3=c_1v_1+c_2v_2+c_3v_3,改為 (A-c_3I)v_3=c_1v_1+c_2v_2,這和先前的特徵方程不同。別忘了,幾何重數不大於代數重數,v_3v_1,v_2 獨立,所以特徵值1有相重數2(到目前為止)。另一個觀點是我們的任務其實在尋找一基底 v_1,\ldots,v_4 可將 A 分塊上三角形化,只要達成這個目標,A 就相似於分塊上三角形矩陣,兩者有相同的特徵值。任一矩陣必可分塊三角化,但未必可對角化。

      當計算出兩個特徵值1的時候,我們並不知道1的代數重數是2,因為後面還有一個特徵值未定,但我們確知特徵值1的獨立特徵向量僅有1個。所以到目前為止,特徵值1的代數重數是2,幾何重數是1。

  2. levinc417 說:

    換個角度想,當初首提出「行列式」這個概念的創始者之貢獻與影響很大啊~~

    • ccjou 說:

      是的,美國數學教授Morris Kline說:矩陣理論在被創造前就已發展完善。這是指行列式為矩陣理論的發展提供了堅實的基礎。

      我認為行列式不太可能從線性代數分離開來,兩者之間有一條很難剪斷的臍帶:\det (AB)=(\det A)(\det B)

  3. EMK 說:

    我認為這跟微積分學有點類似。

    微分學和積分學可以發展成獨立的理論,但由微積分基本定理把兩個理論合而為一。

    同樣,矩陣論和行列式論也可以亦曾經發展成獨立的理論,但由線性代數把它們之關係突顯了出來。

    • ccjou 說:

      矩陣最早是隨著行列式的腳步發展的,矩陣乘法發明人Cayley也說:矩陣記號是直接來自行列式或為了表示
      x'=ax+by
      y'=cx+dy
      分道揚鑣是後來的事。雖然如此,兩者至今依然密不可分,縱使Axler不怎麼喜愛行列式,他仍在書中最後一章介紹了det和trace,因為特徵值的積等於det,特徵值的和等於trace。這個事實任誰也不能否認。

  4. Moonlove 說:

    老師您好:
    最近我在練習使用這個方法來找出矩陣的特徵值和特徵向量,希望至少找出特徵值,特徵向量頂多再用Gauss Jordan消去法來找也沒關係,但第一個種子總是取不好,我有看老師的另外一篇「從不變子空間切入特徵值問題」,但仍然不太會取。

    例如以下這一題:

    A=[a1,a2,a3,a4,a5]、a1=[1,2,3,4,5]^T、a2=[6,7,8,9,10]^T、a3=[11,12,13,14,15]^T、a4=[16,17,18,19,20]^T、a5=[21,22,23,24,25]^T,欲求這個矩陣的特徵值。

    例如我取v1=[1,0,0,0,0]^T、Av1=[1,6,11,16,21],接下去就很痛苦了..

    但若我取v1=[1,1,1,1,1]^T,會很快的收斂到兩個向量所生成的不變子空間,至少就找到兩個了。

    請問老師,我究竟該如何尋找第一個種子呢?

    • Moonlove 說:

      我似乎題目寫錯了,以上矩陣應當再取轉置才是原題目。

    • ccjou 說:

      是這個矩陣吧?
      A=\begin{bmatrix} 1&2&3&4&5\\ 6&7&8&9&10\\ 11&12&13&14&15\\ 16&17&18&19&20\\ 21&22&23&24&25 \end{bmatrix}
      該怎麼挑選“好種子”呢?你提的問題正是我遲遲沒有貼出(下篇)的原因之一,我也在想這個問題。甚麼才是好種子?它應該不要生成太長的序列,一方面我們可以得到次數較小的因式,這樣容易解出特徵值,另一方面屢乘 A 容易產生數值很大的向量,像你說的接下去就很痛苦了。挑選好種子必須透過觀察矩陣的型態,此例矩陣不可逆,各行皆等於左行加 (1,1,1,1,1)^T,因此我們可以設種子為 (-1,1,0,0,0)^T,這樣得到 (1,1,1,1,1)^T。如果你一眼能看出對應特徵值0的特徵向量,那就千萬不要客氣,直接設 (1,-2,1,0,0)^T(0,1,-2,1,0)^T(0,0,1,-2,1)^T。這樣一口氣就得到三個特徵向量對應特徵值0。接下來只要再計算一兩回即可。

      • ccjou 說:

        上面的種子次序沒說清楚。先設 v_1=(1,-2,1,0,0)^T,v_2=(0,1,-2,1,0)^T,v_3=(0,0,1,-2,1)^T (它們對應特徵值0),然後設 v_4=(-1,1,0,0,0)^T (這麼做是因數字簡單),可得 v_5=Av_4=(1,1,1,1,1),則 Av_5=(15,40,65,90,115)^T=200v_1+125v_2+50v_3+250v_4+65v_5 (線性組合係數由解方程式得到)。最後,相似矩陣是
        F=\begin{bmatrix} 0&0&0&\vline&0&200\\ 0&0&0&\vline&0&125\\ 0&0&0&\vline&0&50\\  \hline 0&0&0&\vline&0&250\\ 0&0&0&\vline&1&65 \end{bmatrix}
        因此 p(t)=t^3(t^2-65t-250)。最後二個特徵向量應該也不難求,在此省略。

        • Moonlove 說:

          感謝老師的回覆,這確實是很好的方法。

          以這題來看,經過幾個簡單的獵運算後,一般學生應當都算出此矩陣不可逆且特徵值有三個0,接下來問題會留在最後兩個特徵值上,所以不該把求特徵值和求特徵向量分開做(以前我的習慣都是算出全部的特徵值再算全部的特徵向量),如果在找到三個0後馬上找三個特徵向量,接下來的路應該會好走很多。

          但我仍舊有個疑問,因為幾何重數不一定會等於代數重數,假設我對應特徵值0的特徵向量不滿三個時,餘下的一個找不到的向量該當如何呢?

發表迴響

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

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s