9.3 迭代方法設計要訣與陷阱#

概念說明#

全書九種迭代方法走完，最後沉澱出一套可攜帶的設計紀律。每個迭代法都可拆成五個決策點，設計即是在每個點上做對選擇：

表述：把問題寫成 \(x = g(x)\) （不動點）、 \(f(x) = 0\) （求根）、 \(\min f\) （最佳化）或不動點格（離散）。表述決定了可用方法的集合。
更新規則：用多少歷史資訊？（一階 GD、二階牛頓、Krylov 子空間）用不用隨機性？（蒙地卡羅、SGD）
收斂條件：壓縮性（連續）、單調性＋有限格（離散）、譜半徑（線性）、Lyapunov（動態）。不滿足時有無退路（混合法、阻尼、鬆弛）。
停機準則：步長、殘差、兩者並用；加上最大迭代數的硬保險。永遠要有最大迭代數。
誤差管理：理論誤差界（先驗/後驗）、浮點沉積誤差、混沌放大、統計誤差。

十大陷阱（每一條都有真實程式碼翻車）：

步長過大發散：GD 的 \(\alpha > 2/L\) 、SOR 的 \(\omega \ge 2\) 、牛頓在遠離解處跨過山頭。解法：線搜尋、信賴域、回退二分。
停機過早：線性收斂時 |Δx| < ε 尚可，但初值太近解時 Δx 天生就小；應加殘差判據。
停機過晚/永不停止：浮點下 \(|x_{k+1} - x_k|\) 降到機器精度後震盪，無最大迭代數就無限迴圈。
初值敏感：牛頓法跳到別的根（或發散）、局部最佳化陷入局部極小。解法：多起點、全域掃描打底、退火。
病態條件： \(\kappa\) 大→GD 蛇行、CG 龜速、直接法精度崩壞。解法：預處理、尺度歸一化、改參數化。
浮點沉積誤差：千萬次迭代的捨入累積（如長期積分、混沌軌道）讓理論收斂名存實亡。解法：更高精度、誤差補償（Kahan 求和）、定期重置。
多重根與不變號區間：二分法漏偶數重根；牛頓法在重根退化線性。解法：重數修正、改對 \(f'\) 求根。
隨機性的誤用：蒙地卡羅不報信賴區間＝不合格；MCMC 不丟燒入期、不檢查混合＝樣本無效。
離散迭代的非單調更新：資料流分析若轉移函數不單調，可能震盪不停。解法：確認半格操作、加寬匯合（widening）。
驗證錯誤的標準答案：與更高精度版本、解析解、或對偶方法比對。收斂曲線不對勁就是 bug——這是數值除錯的第一直覺。

最後一個要訣是方法混合：牛頓＋二分（Brent）、Krylov＋多重網格、局部搜尋＋全域掃描——工程上最穩的組合幾乎都是「快的＋穩的」配對。

生活類比#

迭代法像開車導航：表述是「目的地在哪」，更新規則是「怎麼轉向」，收斂條件是「這條路通不通」，停機準則是「到了嗎」，誤差管理是「油夠不夠、輪胎準不準」。新手翻車常不在方向盤，而在沒看油表（最大迭代數）與沒校準地圖（驗證基準）。

演算法步驟#

拿到新問題的迭代設計檢查清單：

能否表述為不動點/求根/最佳化？哪種表述導數最好求？
有無可靠初值或夾根區間？沒有就先掃描或全域法打底。
選主方法（快）與保底方法（穩），定義切換條件。
停機：殘差＋步長雙準則＋最大迭代數；報告實際迭代次數與最終殘差。
收斂實驗：跑三組精度（ \(\varepsilon, \varepsilon/10, \varepsilon/100\) ），驗證誤差按理論階數下降；不對勁即查 bug。
壓力測試：病態參數、極端初值、隨機種子掃描。

Python 範例#

一個整合了雙準則停機、混合保底與收斂階自檢的求根器：

import numpy as np

def robust_root(f, a, b, eps=1e-12, max_iter=200):
    """牛頓為主、二分保底的混合求根（含收斂階回報）"""
    fa, fb = f(a), f(b)
    if fa * fb > 0:
        raise ValueError("無夾根區間")
    x, fx, hist = (a + b) / 2, f((a + b) / 2), []
    lo, hi = a, b
    for k in range(1, max_iter + 1):
        try:                                   # 牛頓步（數值導數）
            h = max(1e-8, 1e-7 * abs(x))
            d = (f(x + h) - f(x - h)) / (2 * h)
            s = x - fx / d if d != 0 else None
        except OverflowError:
            s = None
        if s is None or not (lo < s < hi):     # 牛頓不可靠 → 二分
            s = (lo + hi) / 2
        fs = f(s)
        hist.append(abs(fs))
        if fs * fx < 0: hi = s
        else: lo, fx = s, fs
        if abs(fs) < eps or hi - lo < eps:
            # 收斂階自檢：比較最後兩誤差比
            if len(hist) >= 3 and hist[-3] > 0:
                ratio = hist[-1] / hist[-2]
                print(f"最後誤差比 {ratio:.2e}（牛頓應趨 0）")
            return s, k
        x, fx = s, fs
    raise RuntimeError("超過最大迭代數")

f = lambda x: np.cos(x) - x
root, n = robust_root(f, 0.0, 1.0)
print(f"根 ≈ {root:.13f}，迭代 {n} 次，f = {f(root):.1e}")

# 收斂實驗：驗證精度改進符合預期
for eps in (1e-6, 1e-9, 1e-12):
    r, k = robust_root(f, 0.0, 1.0, eps=eps)
    print(f"eps={eps:.0e}: {k} 次迭代")

複雜度與收斂性分析#

混合法的最壞情形由保底法決定（此處二分 \(O(\log_2((b-a)/\varepsilon))\) ），典型情形由快法決定（牛頓平方收斂，數步完成）——魯棒性買了保險，速度幾乎不打折。收斂實驗是唯一的品質關卡：若方法宣稱 \(p\) 階收斂，誤差比 \(e_{k+1}/e_k^p\) 應趨於常數；實測不符時，先懷疑實作（導數錯、停機太早、浮點下限），再懷理論。設計迭代的元能力不是記住公式，而是對每一步都問：它為什麼會收斂、收斂到哪、多快、錯了怎麼知道。

練習#

把 robust_root 用於 \(f(x) = \tan(x) - x\) 的多重根情境，觀察牛頓步跨根時混合機制如何救回。
為 4.1 的 Gauss-Seidel 加上「殘差＋步長雙準則＋最大迭代數＋發散偵測（殘差暴增即中止）」的工業級外殼。
選一個你寫過的迴圈，用本章清單逐項審查：表述、收斂條件、停機準則、誤差管理——找出至少一個潛在陷阱並修復。