6.2 冪法求特徵值#

概念說明#

特徵值問題 \(A\mathbf{v} = \lambda \mathbf{v}\) 遍布科學與工程：振動模態、穩態機率、主成分分析、PageRank。對大型稀疏矩陣，求全部特徵值（QR 演算法， \(O(n^3)\) ）既慢又毀稀疏性；但往往只需要最大的一個——這正是冪法（power method）的舞台。

想法極簡：反覆乘上 \(A\) ， \(\mathbf{v}_{k+1} = A\mathbf{v}_k / \|A\mathbf{v}_k\|\) 。把初始向量按特徵向量展開 \(\mathbf{v}_0 = \sum_i c_i \mathbf{q}_i\) ，則 \(A^k \mathbf{v}_0 = \sum_i c_i \lambda_i^k \mathbf{q}_i\) 。若 \(|\lambda_1| > |\lambda_2| \ge \cdots\) ，則 \(\lambda_1^k\) 的相對優勢以 \((|\lambda_2|/|\lambda_1|)^k\) 的速度碾壓其餘，方向收斂到 \(\mathbf{q}_1\) ，特徵值由 Rayleigh 商 \(\mathbf{v}^T A \mathbf{v} / \mathbf{v}^T \mathbf{v}\) 讀出。

收斂率由特徵值間隙決定： \(\mathbf{v}_k\) 與 \(\mathbf{q}_1\) 的夾角每步縮小 \((|\lambda_2|/|\lambda_1|)\) 倍——又一個線性收斂、速率由「比值」控制的迭代（與 2.2 節壓縮映像同構）。三個實務要點：

正規化：每步除以範數，避免溢位/下溢。
失效條件： \(|\lambda_1| = |\lambda_2|\) （如旋轉矩陣、共軛複數對）時不收斂； \(\lambda_1 < 0\) 時方向震盪但可取 \(\lambda_1^2\) 的平方根處理。
收斂加速：反冪法（乘 \(A - \sigma I\) ，收斂到最靠近 \(\sigma\) 的特徵值，配 LU 分解極快）、Rayleigh 商迭代（自動更新 \(\sigma\) ，平方收斂）、Lanczos（對稱矩陣，Krylov 子空間法，4.3 節精神的重現）。

PageRank 是史上最大的冪法應用： \(\mathbf{p}_{k+1} = (d\,M + (1-d)\mathbf{1}\mathbf{1}^T/n)\,\mathbf{p}_k\) ，隨機瀏覽矩陣是隨機矩陣，譜半徑 \(\le d = 0.85 < 1\) ，保證收斂——2.2 節的壓縮映像原理在億維空間的應用。

生活類比#

向一池靜水丟石子：水波的多種頻率同時存在，但最慢衰減的頻率最後留下來——反覆「施加作用」（乘 \(A\) ）會把系統的主模態（最大特徵值）篩出來。選秀節目的多輪淘汰也是冪法：每輪放大最受歡迎者的相對優勢，最後冠軍脫穎而出。

演算法步驟#

取初始向量 \(\mathbf{v}_0\) （隨機，且不與 \(\mathbf{q}_1\) 正交；隨機選取幾乎必然滿足）。
迭代： \(\mathbf{w} = A\mathbf{v}_k\) ； \(\lambda_k = \mathbf{v}_k^T \mathbf{w}\) （Rayleigh 商）； \(\mathbf{v}_{k+1} = \mathbf{w}/\|\mathbf{w}\|\) 。
當 \(\|\mathbf{v}_{k+1} - \mathbf{v}_k\| < \varepsilon\) 或 Rayleigh 商變化小於 \(\varepsilon\) 時停止。
回傳 \(\lambda \approx \lambda_k\) 、 \(\mathbf{q}_1 \approx \mathbf{v}_{k+1}\) 。

Python 範例#

import numpy as np

def power_method(A, tol=1e-12, max_iter=5000):
    n = A.shape[0]
    v = np.random.default_rng(0).standard_normal(n)
    v /= np.linalg.norm(v)
    lam_old = 0.0
    for k in range(1, max_iter + 1):
        w = A @ v
        lam = v @ w                     # Rayleigh 商
        v_new = w / np.linalg.norm(w)
        if abs(lam - lam_old) < tol * max(1.0, abs(lam)):
            return lam, v_new, k
        v, lam_old = v_new, lam
    return lam, v, max_iter

rng = np.random.default_rng(1)
Q, _ = np.linalg.qr(rng.standard_normal((6, 6)))
A = Q @ np.diag([9.0, 5.0, 3.0, 2.0, 1.0, 0.5]) @ Q.T
lam, v, it = power_method(A)
print(f"冪法: λ₁ ≈ {lam:.10f}，迭代 {it} 次")
print(f"numpy: λ₁ = {np.linalg.eigvalsh(A)[-1]:.10f}")
print(f"殘差 ‖Av - λv‖ = {np.linalg.norm(A @ v - lam * v):.2e}")

# PageRank 小例子
M = np.array([[0., 0, 1], [0.5, 0, 0], [0.5, 1, 0]])  # 連結機率
d = 0.85; n = 3
G = d * M + (1 - d) / n
p = np.full(n, 1/n)
for _ in range(100):
    p = G @ p
print("PageRank:", p.round(4), "（總和 =", p.sum(), "）")

複雜度與收斂性分析#

每步一次矩陣-向量乘 \(O(\text{nnz})\) 加 \(O(n)\) 正規化，記憶體 \(O(n)\) ——可在裝不下一個稠密矩陣的機器上處理十億維稀疏矩陣。迭代次數 \(\sim \frac{\ln(1/\varepsilon)}{\ln(|\lambda_1|/|\lambda_2|)}\) ：間隙越小越慢， \(\lambda_1 = 9, \lambda_2 = 5\) 時每步約縮 0.56，數十步收斂；若 \(\lambda_1 = 1.01, \lambda_2 = 1.00\) 則需數千步。改進譜：反冪法＋位移把目標對準特定特徵值；Lanczos 對對稱矩陣在 Krylov 子空間中做 Rayleigh-Ritz，收斂遠快於冪法。記憶口訣：冪法找最大、反冪法找最近、Lanczos 找前幾大。

練習#

實驗 \(\lambda_2/\lambda_1 = 0.9\) 與 \(0.99\) 的矩陣，驗證收斂迭代次數與理論公式的關係。
對 6.2 例的矩陣實作反冪法（ \(\sigma = 4.5\) ），驗證收斂到 5.0（提示：解線性系統可用 numpy.linalg.solve）。
把 PageRank 的 \(d\) 調成 0.99 與 0.5，觀察冪法迭代次數與排名穩定性的變化，並解釋。