跳轉到

1950 — 冪迭代法#

案件摘要#

1950 年前後，矩陣特徵值的數值計算出現了第一件「以最笨的方法辦成最聰明的事」的案子：不分解、不消去，只是反覆把矩陣 \(A\) 乘在一個向量上—— \(v_{k+1} = Av_k / \|Av_k\|\) ——向量竟自己「漂」向主特徵向量。配合 Rayleigh 商 \(\lambda = \frac{v^TAv}{v^Tv}\) ，主特徵值也自動浮出水面。冪迭代法是特徵值理論第一次被壓縮成三行程式碼，也是此後所有 Krylov 子空間方法、乃至 PageRank 的共同祖先。

前因 -- 為什麼會有這個案子#

  • 19 世紀 Cayley–Hamilton（1858）確立特徵值概念，Jordan 標準形說明矩陣行為由特徵結構決定。
  • 1907 年 Perron 證明正矩陣必有唯一的「主特徵值」（模最大且單根）；1912 年 Frobenius 推廣到非負不可約矩陣——這正是冪迭代會收斂的數學保證。
  • 1930 年代，Richard von Mises 在德國傳播「迭代法」（Iterationsverfahren）：對動力系統 \(\sigma_{k+1} = A\sigma_k\) ，觀察其漸近行為即得主特徵值。這是本案最早的案發紀錄。
  • 1950 年代，美國 Los Alamos 與英國 NPL 的計算需求（中子擴散、飛機振動）迫使特徵值計算規模化，Wilkinson 等人把冪迭代整理成標準教材方法。
  • 案發動機：實際問題（振動模態、量子基態、穩定性分析）往往只要求最大或最小特徵值，何必算出全部？只需「定向放大」主特徵方向的成分。

線索與推理 -- 數學式、程式、理論#

線索一：為什麼反覆乘 \(A\) 就會收斂#

設 \(A\) 可對角化， \(A = X\Lambda X^{-1}\) ，特徵值 \(|\lambda_1| > |\lambda_2| \ge \cdots\) 。把任意向量按特徵基展開：

\[ v_0 = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \]

每次乘 \(A\) ，各成分被放大自己的特徵值倍：

\[ A^k v_0 = \lambda_1^k\left[c_1 x_1 + c_2 \left(\frac{\lambda_2}{\lambda_1}\right)^k x_2 + \cdots\right] \]

因為 \(|\lambda_2/\lambda_1| < 1\) ，第二項以幾何速度消失， \(v_k\) 的方向收斂到 \(x_1\) 。收斂速率由譜隙比 \(\left|\lambda_2/\lambda_1\right|\) 決定——每迭代一次，誤差乘上 \(\left|\lambda_2/\lambda_1\right|\) 倍。這就是本案的「指紋」：譜隙越大收得越快，譜隙小（如 \(0.99\) ）則慢得令人絕望。

線索二：Rayleigh 商 —— 特徵值的自動指認器#

歸一化避免溢位後， \(v_k \to x_1/\|x_1\|\) ，但特徵值從哪來？對每個近似向量定義：

\[ \rho(v) = \frac{v^T A v}{v^T v} \]

這是 Rayleigh 商（Rayleigh, 1877《聲學理論》已用於振動問題）。它有三個關鍵性質： 1. 若 \(v = x_i\) 恰為特徵向量， \(\rho(v) = \lambda_i\) 。 2. \(\rho(v)\) 是所有 \(v\) 方向上「最優的特徵值估計」： \(\min_{v\neq 0}\rho(v) = \lambda_{\min}\) ， \(\max = \lambda_{\max}\) （變分原理）。 3. 誤差是二階的：若 \(\|v - x_1\| = O(\epsilon)\) 且 \(\lambda_1\) 單根，則 \(|\rho(v) - \lambda_1| = O(\epsilon^2)\) 。

性質 3 意味著：向量方向每進步一位數，特徵值估計自動進步兩位數——Rayleigh 商是「免費的二次加速」。

線索三：缺陷與補救#

冪迭代有三個已知的破綻，各自催生了後續案件： 1. ** \(|\lambda_1| = |\lambda_2|\) 時不收斂**（如實對稱矩陣的正負成對特徵值 \(\pm\lambda\) ，向量會在兩方向間震盪）。補救：位移反冪法 \(v_{k+1} = (A - \sigma I)^{-1}v_k\) ，收斂到最靠近 \(\sigma\) 的特徵值——這需要解線性系統，正好接上 LU 分解。 2. 收斂慢。補救：不是迭代一個向量，而是迭代整個子空間——1951 年 Lanczos（對稱矩陣）與 Arnoldi（一般矩陣，1951 年後）建立 Krylov 子空間方法 \(\mathcal{K}_m = \text{span}\{v_0, Av_0, \dots, A^{m-1}v_0\}\) ，本質上「同時」做了多次冪迭代並在子空間內做 Rayleigh–Ritz 提取。 3. 只抓一個特徵對。補救：deflation（收縮），找到 \(\lambda_1\) 後在 \(A - \lambda_1 x_1 x_1^T\) 上繼續跑，或直接對多列投影。

程式碼範例：冪迭代收斂到主特徵值，Rayleigh 商驗證#

import numpy as np

rng = np.random.default_rng(42)

# 構造已知譜的對稱矩陣：特徵值 10, 3, 5, 1, 2
Q, _ = np.linalg.qr(rng.normal(size=(5, 5)))
lam = np.array([10.0, 3.0, 5.0, 1.0, 2.0])
A = Q @ np.diag(lam) @ Q.T

v = rng.normal(size=5)
v /= np.linalg.norm(v)
for k in range(1, 31):
    w = A @ v
    v_new = w / np.linalg.norm(w)
    rayleigh = v_new @ A @ v_new          # Rayleigh 商
    if k % 5 == 0 or k == 1:
        err = abs(rayleigh - lam.max())
        ratio = np.abs(err) ** 0.5        # 看二階收斂的跡象
        print(f"k={k:2d}  Rayleigh 商={rayleigh:.8f}  |誤差|={err:.2e}")
    v = v_new

# 對照 numpy
print("numpy 主特徵值 =", np.linalg.eigvalsh(A).max())
print("收斂速率預測 |λ2/λ1| =", abs(lam[1] / lam[0]))

輸出顯示 Rayleigh 商快速逼近 10，且誤差以每步約平方的速度縮小——向量方向的一階誤差在 Rayleigh 商上變成二階收斂，正符合線索二的理論預測。

結案 -- 後果與影響#

  • 冪迭代成為主特徵值計算的入門標準，所有數值線性代數教科書的第一個迭代法。
  • 1951 年 Lanczos 演算法（對稱）與 Arnoldi 演算法推廣，發展成今日大規模特徵值計算的主力：ARPACK（scipy.sparse.linalg.eigs/eigsh 的核心）本質上就是「聰明版的冪迭代」。
  • Rayleigh 商成為量子力學變分原理、有限元模態分析、模型降階的通用工具。
  • 1998 年 Page 與 Brin 的 PageRank：整個 Web 超連結矩陣的 PageRank 向量就是冪迭代的極限—— \(10^{10}\) 規模的矩陣也只有冪迭代（配合稀疏乘法）跑得動。PageRank 成為本案最轟動的「現代重審」。
  • 影響至今：譜聚類、譜嵌入、Google 搜尋、量子化學基態計算，全是冪迭代思想的直系後裔。

關鍵人物與文獻#

人物 角色
Richard von Mises 1930 年代傳播冪迭代法
Oskar Perron / Georg Frobenius 正矩陣主特徵值定理（收斂保證）
John William Rayleigh Rayleigh 商（1877《聲學理論》）
Cornelius Lanczos 1951 年 Krylov 子空間方法
Walter Edwin Arnoldi 1951 年 Arnoldi 演算法
Larry Page / Sergey Brin 1998 年 PageRank = 冪迭代的 Web 規模應用
  • R. von Mises & H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung, ZAMM 9 (1929)。
  • C. Lanczos, An iteration method for the solution of the eigenvalue problem..., J. Res. NBS 45, 255 (1950)。
  • G. H. Golub & C. F. Van Loan, Matrix Computations, 4th ed., Ch. 8 (2013)。
  • L. Page et al., The PageRank Citation Ranking, Stanford InfoLab (1999)。