反冪法
冪法只能找到最大的特徵值。但你常常想要某個特定的——例如最靠近你心中某個數 sigma 的那個特徵值(一個共振頻率、一個已知的近似特徵值)。反冪法(inverse iteration)就是把冪法變成可瞄準的精密儀器的巧妙技巧。想法是:如果你已大致知道某特徵值在哪,就可以讓它成為某個變換後矩陣的主特徵值,再用冪法逼近它。
變換是這樣的。矩陣 (A - sigma I)^(-1) 的特徵值是 1/(lambda_i - sigma),其中 lambda_i 是 A 的特徵值。若 sigma 很接近某個特定的特徵值 lambda_j,則 lambda_j - sigma 極小,所以 1/(lambda_j - sigma) 非常巨大——它遠遠是這個「逆移位」矩陣的最大特徵值。於是在 (A - sigma I)^(-1) 上跑冪法,會快速收斂到 lambda_j 的特徵向量。實務上你絕不真去求逆:每一步是解線性系統 (A - sigma I) w = v(做一次 LU 分解,每步重複使用),再正規化。你的移位 sigma 越靠近 lambda_j,收斂越快——速率是 |(lambda_j - sigma)/(lambda_next - sigma)|。
一旦你已有不錯的特徵「值」估計(例如來自 QR 演算法),反冪法就是取得精確特徵「向量」的標準做法。看起來令人不安的是:當 sigma 逼近 lambda_j 時,(A - sigma I) 幾乎奇異——線性解不會爆掉嗎?了不起的是,它不但無害,反而正中要害:求解放大的,正是你想要的那個特徵向量方向,而向後穩定(backward-stable)的求解器即使在系統病態時,也能交出幾乎完全指向正確方向的向量。那種近奇異性正是速度的來源,不是 bug。
對列為 (2, 1) 與 (1, 2) 的 A(特徵值 3 與 1),假設你想要 sigma = 0.9 附近的特徵向量。組出 A - 0.9 I,分解一次,再反覆解 (A - 0.9 I) w = v 並正規化。因為 1/(1 - 0.9) = 10 遠大於 1/(3 - 0.9) ~= 0.48,疊代只要一兩步就鎖定 lambda = 1 的特徵向量 (1, -1)——遠快於等冪法去找那個較小的特徵值(冪法根本找不到)。
把移位 sigma 選在目標特徵值附近,就讓那個特徵值成為逆移位矩陣的主特徵值。
把 (A - sigma I) 分解一次、每次疊代重複使用——別每步重算逆矩陣,也別真的去組 (A - sigma I)^(-1)。若每步都用最新的特徵值估計來更新 sigma,就得到具三次收斂的瑞利商疊代。