2.3 收斂速度與誤差估計#

概念說明#

知道迭代會收斂還不夠，工程上更要緊的是多快收斂。收斂速度的標準度量是收斂階（order of convergence）：若存在 \(p \ge 1\) 與常數 \(\lambda > 0\) ，使得

則稱迭代為 ** \(p\) 階收斂**，漸近誤差常數為 \(\lambda\) 。

• 線性收斂（p = 1）：每步誤差約乘上固定因子 \(\lambda < 1\) 。對數意義下，每步「固定減少同樣位數」。壓縮映像迭代、Jacobi 法多屬此類。
• 超線性（1 < p < 2）：介於兩者之間，割線法（ \(p \approx 1.618\) ，黃金比例）是代表。
• 平方收斂（p = 2）：誤差滿足 \(e_{k+1} \approx \lambda e_k^2\) 。正確位數每步翻倍：誤差 \(10^{-1} \to 10^{-2} \to 10^{-4} \to 10^{-8} \to 10^{-16}\) ，五步就用完雙精度。牛頓法與巴比倫開方法屬此類。

比較「線性但每步極便宜」與「平方但每步昂貴」的方法時，正確的指標是達到目標精度的總成本，而非迭代次數或單步成本。這是數值軟體選擇演算法的標準思考。

誤差估計的另一要務是停機準則。常見三種：

1. 絕對/相對步長： \(|x_{k+1} - x_k| < \varepsilon\) （或除以 \(|x_{k+1}|\) ）。
2. 函數值小： \(|f(x_k)| < \varepsilon\) 。
3. 混合準則：兩者皆小才停。

陷阱：線性收斂時步長與誤差成正比，準則 1 可靠；但平方收斂時 \(|x_{k+1} - x_k| \approx \lambda e_k^2\) 可能遠小於 \(e_{k+1}\) ？恰恰相反——平方收斂時步長是誤差的下界關係不明顯，實務上以 \(\lambda \,|x_{k+1}-x_k|\) 保守估計誤差，或直接看殘差 \(|f(x_k)|\) 。另一陷阱是浮點極限：雙精度下誤差降到約 \(10^{-16} |x^*|\) 後，繼續迭代只會在機器精度附近抖動，應設下限。

生活類比#

線性收斂像走樓梯下樓——每階固定高度；平方收斂像對摺紙張找目標——每摺一次可搜尋範圍平方級縮小，幾摺之內就抵達。調味做菜是線性收斂（每次嚐、每次微調固定量），而用天平二分砝碼稱重則像平方收斂。

演算法步驟#

實測一個迭代的收斂階：

1. 執行迭代，記錄誤差序列 \(e_k = |x_k - x^*|\) （ \(x^*\) 用高精度方法取得）。
2. 計算比率 \(r_k = e_{k+1} / e_k\) ：趨近常數則為線性（常數即 \(\lambda\) ）；趨近 0 且 \(e_{k+1}/e_k^2\) 趨近常數則為平方。
3. 用回歸估 \(p\) ： \(\log e_{k+1} \approx \log\lambda + p \log e_k\) ，斜率即 \(p\) 。
4. 停機時同時檢查步長與殘差。

Python 範例#

比較巴比倫法（平方收斂）與鬆弛形式（線性收斂）求 \(\sqrt{2}\) ：

def convergence_orders():
    x_true = 2 ** 0.5
    def babylon():
        x, hist = 1.0, []
        for _ in range(8):
            x = 0.5 * (x + 2 / x)
            hist.append(abs(x - x_true))
        return hist
    def linear():
        x, hist = 1.0, []
        for _ in range(30):
            x = (x + 2) / 2          # g(x) = x/2 + 1，g' = 0.5
            hist.append(abs(x - x_true))
        return hist

    for name, h in [("巴比倫", babylon()), ("線性", linear())]:
        print(name)
        for k, e in enumerate(h[:6]):
            ratio = h[k+1] / e if k + 1 < len(h) and e else float("nan")
            print(f"  e_{k} = {e:.3e}, e_next/e = {ratio:.3f}")

convergence_orders()

巴比倫法的誤差比率迅速趨近 0（且 \(e_{k+1} \approx e_k^2 / (2\sqrt2)\) ），線性法的比率恆為 0.5。

複雜度與收斂性分析#

\(p\) 階收斂下，從誤差 \(e_0\) 到精度 \(\varepsilon\) 約需 \(k = O(\log\log(1/e_0))\) 次（ \(p=2\) ）與 \(k = O(\log(1/\varepsilon))\) 次（ \(p=1\) ）——平方收斂對精度的依賴是「雙對數」的，這就是為什麼牛頓法只需 5～8 步就能榨乾雙精度。但平方收斂是漸近性質：初期誤差大時未必成立，且通常要求初始值夠靠近解。總成本 = 迭代次數 × 單步成本，選法時兩者都要算。

練習#

1. 用上例的回歸法實測割線法求 \(x^2 - 2 = 0\) 的收斂階，驗證約為 1.618。
2. 設 \(e_{k+1} = e_k^2\) 、 \(e_0 = 0.5\) 。需要幾步誤差小於 \(10^{-50}\) ？寫程式驗證。
3. 某法單步成本是牛頓法的 1/5，但僅線性收斂（ \(\lambda = 0.1\) ）。達 \(10^{-12}\) 精度時何者總成本較低？寫一個小程式比較。