5.3 特徵值與冪法#

概念說明#

特徵值問題是線性代數的深水區：給定方陣 A，找非零向量 v 與純量 λ 使 Av = λv。λ 是特徵值，v 是對應的特徵向量。特徵值決定了線性系統的一切動態行為——振動頻率、穩定性、主成分方向、收斂速率。

n ≤ 4 時可以展開特徵多項式 det(A − λI) = 0 用代數方法求解（這呼應第 4 章的多項式求根），但 n ≥ 5 時 Abel 已證明沒有根式解，數值方法因此成為唯一的路。現代程式庫用 QR 演算法把所有特徵值一次算出（O(n³)），但當矩陣巨大、而我們只需要最大的那一兩個特徵值時，有一個美到近乎奢侈的方法：冪法（Power Iteration）。

冪法的洞察是：把任意向量反覆乘上 A，即 v, Av, A²v, …，用特徵基底展開後，對應最大特徵值 |λ₁| 的分量會以 (λ₁/λⱼ)ⁿ 的速度壓倒其他所有分量。於是 vₖ = Aᵏv⁰ 的方向自然轉向主特徵向量，而相鄰兩次迭代的比值收斂到 λ₁。整個演算法只需要矩陣—向量乘法——這代表 A 甚至不必真的存起來，只要能算「A 作用在向量上」就行（例如 PageRank 中的隨機漫遊矩陣，它是 10¹⁰ 階的，但每列只有少數非零）。

演算法步驟#

選一個不與特徵向量正交的起始向量 v₀（隨機向量即可，機率 1 成功）。
反覆：w = A·vₖ；λ̂ = vₖᵀw（Rayleigh 商，用於估特徵值）；vₖ₊₁ = w / ‖w‖（正規化避免溢位/下溢）。
當 ‖vₖ₊₁ − vₖ‖ < ε 或 |λ̂ₖ₊₁ − λ̂ₖ| < ε 時停止。
若需要次大特徵值，對 A 做降階：A ← A − λ₁v₁v₁ᵀ，再跑一次（稱為 deflation）。

Python 程式碼範例#

import numpy as np

def power_iteration(A, tol=1e-12, max_iter=10000):
    n = A.shape[0]
    v = np.random.default_rng(0).standard_normal(n)
    v /= np.linalg.norm(v)
    lam = 0.0
    for i in range(max_iter):
        w = A @ v
        lam_new = v @ w               # Rayleigh 商估最大特徵值
        v_new = w / np.linalg.norm(w)
        if abs(lam_new - lam) < tol:
            return lam_new, v_new, i + 1
        lam, v = lam_new, v_new
    return lam, v, max_iter

np.random.seed(42)
Q, _ = np.linalg.qr(np.random.randn(5, 5))     # 隨機正交基底
A = Q @ np.diag([9.0, 4.0, 2.0, 1.0, 0.5]) @ Q.T

lam, v, n = power_iteration(A)
print(f"冪法: λ₁ ≈ {lam:.10f}，迭代 {n} 次")
print(f"numpy: λ₁ = {np.linalg.eigvals(A).max():.10f}")
print("特徵向量核對 A@v ≈ λv:", np.abs(A @ v - lam * v).max())

# --- 應用：PageRank 的迷你版 ---
def pagerank(links, d=0.85, iters=1000):
    n = len(links)
    M = np.zeros((n, n))
    for i, outs in enumerate(links):
        for j in outs:
            M[j, i] = 1 / len(outs)            # 連結矩陣（行隨機）
    v = np.ones(n) / n
    for _ in range(iters):
        v = d * (M @ v) + (1 - d) / n          # Google 矩陣作用
    return v

links = [[1, 2], [2], [0, 1], [0]]             # 4 個網頁的連結結構
pr = pagerank(links)
print("PageRank 分數:", np.round(pr / pr.sum(), 4))

PageRank 本質上就是冪法：反覆把「隨機上網者的分布向量」乘上轉移矩陣，收斂到的向量就是各網頁的重要性。

複雜度與誤差分析#

冪法每次迭代成本是一次矩陣—向量乘：稠密矩陣 O(n²)，稀疏矩陣 O(nnz)（非零元素個數）。收斂率由比值 |λ₂/λ₁| 決定：每迭代一次，非主分量的振幅乘上這個比值，誤差因此呈指數下降，迭代次數約 O(log(1/ε) / |log|λ₂/λ₁||)。當 λ₂ 接近 λ₁ 時收斂極慢，此時應改用反冪法（對 A − σI 求反，配合解線性系統，收斂到離 σ 最近的特徵值，即「位移反冪法」）或 Lanczos/Arnoldi 等 Krylov 子空間法。兩個限制要牢記：冪法只找 |λ| 最大的特徵值，且若 |λ₁| = −|λ₂|（如 A = diag(1, −1)）迭代會在兩個向量間振盪不收斂，修正方法是以 A² 或隨機重新起始處理。特徵值的數值條件由特徵向量的正交性決定：對稱矩陣特徵值條件數為 1（非常穩定），非對稱矩陣則可能病態，非正規矩陣建議一律用 SVD 思維處理。

練習#

對 A = [[0, 1], [1, 0]]（λ = ±1）跑冪法，觀察振盪；再對 A² 跑，解釋為何收斂到 1。
實作位移反冪法：解 (A − σI)w = v 用 np.linalg.solve，取 σ = 2.5，找出上例 A 中第二大的特徵值 4。
把 PageRank 函式改成迭代到 ‖v_new − v‖∞ < 1e-10 為止，並記錄需要幾次迭代；把 d 從 0.85 改成 0.5 與 0.99，比較收斂速度並解釋原因。