一堵你願望落空也搬不走的牆
在線性代數裡，你認識的特徵值是那些讓 A x = lambda x 有非零解 x 的數 lambda——也就是 A 只把它拉伸、不旋轉的那些方向。而你也學過它們從哪來：lambda 是特徵值，恰好等價於 det(A - lambda I) = 0。把那個行列式展開，就得到一個關於 lambda 的多項式，也就是特徵多項式 p(lambda)，而特徵值正是它的根。乍看之下這像是個已經解決的問題：算出多項式、求出它的根，收工。本級之所以存在，正因為這幅乾淨的圖像，若照字面當成演算法，到了電腦上就會散架。
其實有兩堵互不相同的牆，把它們分開看會清楚得多。第一堵純屬數學，而且是絕對的：對一般 5×5 或更大的矩陣，不存在任何根式的有限公式——沒有任何加、乘、開 n 次方的巧妙組合——能從矩陣元素算出特徵值。這其實就是換了裝的阿貝爾–魯菲尼定理：一個 5×5 矩陣的特徵多項式可以是五次的，而一般五次方程沒有根式解。所以不像 2×2 的情形，二次公式一步就把答案交給你；對特徵值，根本不可能有一個直接的封閉形式公式。
那個顯然的替代做法是個陷阱
「好啊，」你說，「沒有封閉形式——但我本來就會用數值方法求多項式的根。從求根那級我學了牛頓法之類的工具。那就先把特徵多項式 p(lambda) 組出來，再迭代地去獵它的根。」這就是第二堵牆，而且是更微妙、更危險的一堵，因為這套計畫「聽起來」很合理，甚至真的跑得動——它只是回給你垃圾。先組出多項式再求根，是已知用來算特徵值的最糟做法之一，而看清楚為什麼，正是讓你領會那些好演算法的入口。
毛病出在條件性。一個多項式的根，對係數的微小變動可以極度敏感，即使這個矩陣的特徵值本身規規矩矩、彼此分得很開也一樣。威爾金森那則著名的警告，就是根剛好是整數 1、2、3、…、20 的多項式。把 lambda^19 的係數推動約 2^(-23)——大約第七位小數的一點抖動——某些根會整整跳動好幾個單位，甚至分裂成複數對。矩陣 -> 係數 -> 根 這條路，把問題穿過了一個極度病態的中間步驟：你儲存那些係數時無可避免的捨入，會被求根器災難性地放大。
這是本級在主方程「準確度 = 條件性 x 穩定性」上的第一課。你原本的問題——求 A 的特徵值——可能本身就非常良態：A 變動一點點，特徵值也只動一點點。但你選擇把它繞道一個中間物件，也就是多項式的係數，而它的「係數到根」映射卻病態得可怕。於是即便是一個完美無瑕、在精確算術下運作、只吃進稍微捨入過的係數的求根器，也必定回給你錯得離譜的根。再聰明、再穩定的求根演算法都救不了你，因為傷害早在你組出係數的那一瞬間就已造成。誠實的教訓是：別為了方便，把一個良態問題改造成一個病態問題。
反過來走，一樣糟
這裡有一個誘人的對稱性值得點名，因為函式庫真的會利用它——只是方向相反。給定一個多項式，你可以造出一個特殊矩陣，它的伴隨矩陣，其特徵多項式恰好就是那個多項式；於是它的特徵值就是多項式的根。穩健的軟體實際上正是這樣求多項式的根：它組出伴隨矩陣，再呼叫一個好的特徵值求解器。求根被化約成了求特徵值，而不是反過來。這支箭之所以從多項式指向矩陣，正是因為矩陣世界裡有一件穩定、可信賴的工具，而係數世界裡沒有。
TWO ROUTES, ONE GOOD
A --> p(lambda) --> roots (the trap: ill-conditioned middle)
----------------------------
form find roots
char. poly of polynomial
p(lambda) --> companion C --> eigenvalues (what libraries do)
--------------------------------
build C run the
from coeffs QR algorithm
rule of thumb: stay in matrix-land; never round-trip through
polynomial coefficients.所以兩條天真的路都被封死了：你沒辦法用公式解出特徵值（阿貝爾–魯菲尼），也不該繞道特徵多項式（病態性）。剩下的辦法，是直接在矩陣上動手，用一種迭代，產生一串 lambda_0、lambda_1、lambda_2、… 慢慢爬向某個真正的特徵值，並配上一串向量慢慢爬向某個特徵向量。接下來四篇指南的工夫，就在於讓這些序列收斂得「快」，而且至關重要地，以一種後向穩定的方式——回給你「某個與你的 A 只差一個捨入誤差的矩陣」的精確特徵值，而那正是一個誠實的方法所能承諾的極限。
一個特徵值求解器的樣貌
在看那些精修過的方法之前，先看一個最簡單的誠實迭代會很有幫助。隨便取一個起始向量，然後就一直拿 A 去乘它：v、A v、A^2 v、A^3 v，依此類推（每一步都重新正規化成單位長度，免得它爆掉或消失）。如果 A 有一個特徵值的絕對值比其餘全部都大，這串方向就會穩穩地朝那個主特徵向量傾斜，而每一步的拉伸倍率會收斂到那個主特徵值。這就是冪法的全部想法，也是那些正經演算法從中長出來的「晶種」。
- 挑一個隨機的非零起始向量 v_0，把它縮放到長度 1。
- 相乘：w = A v_n。這是唯一不可少的運算——你永遠只需要把 A 作用在一個向量上，從不需要對它求逆、甚至不必把它完整存下來。
- 重新正規化：v_{n+1} = w / ||w||。那個長度因子 ||w|| 就是你目前對主特徵值大小的估計。
- 檢查一個停止測試——v 是否不再移動了？殘差 ||A v - lambda v|| 是否已經夠小？——若否就繞回去重來。你停在「夠接近」，永遠停不在「精確」。
那個迴圈有兩個特點，是整個本級的 DNA。第一，它對 A 唯一的要求就是「拿一個向量來乘我」。對真實應用裡那些龐大的稀疏矩陣而言，這是黃金——A 可能有數十億個元素卻大半是零，一次矩陣乘向量很便宜，而你從不需要組出任何稠密的東西。本級稍後的 Krylov 方法，例如蘭索斯與阿諾迪，整個就建在這一項特權上。第二，收斂速度取決於特徵值之間的「間隙」：當最大的兩個大小很接近時，冪法就爬得很慢；而前方一個重要主題，就是刻意地用「移位」製造更大的間隙，好讓迭代衝刺起來。
本級要打造什麼
這是前方的路線，好讓各個零件能扣在一起。下一篇我們把冪法磨利，成為冪法與反冪法：一對孿生技巧，藉由對選定的移位 mu 操作 (A - mu I)^{-1}，能去追你所指向的「任何一個」特徵值，而不只是最大的那個——而且收斂得飛快。接著登場的是 QR 演算法，也就是藏在每個數值函式庫 eig() 程序裡那台真正的主力：把它想成是同時對一整組基底跑的冪法，經過巧妙重組，讓矩陣一步步邁向三角形，並把它所有特徵值一起揭示出來。
一個反覆出現的紓解，是對稱性。當 A 對稱（A = A^T）時，特徵值是實的，特徵向量彼此正交，整個問題就變得乖巧太多了——對稱特徵值問題有它自己更快、更準確的機制。而對於大到根本寫不成稠密形式的矩陣，Krylov 求解器（對稱用蘭索斯、一般用阿諾迪）只憑你上面看到的那些「矩陣乘向量」乘積，就能萃取出少數幾個極端的特徵值，整個過程都活在一個Krylov 子空間裡。