兩種「愈來愈好」
我們已經見過兩種非常不同型態的計算。一種是固定步驟、跑一次就停：高斯消去法做固定份量的工作，然後交給你一個答案。另一種是迭代法：它產生一連串的猜測 x_0、x_1、x_2、……，你希望它們會朝真正的答案 x* 前進。迭代無所不在——求根、解巨大的稀疏系統、訓練模型都是。自然要問的是：這趟前進真的會抵達嗎？而且抵達得多快？
收斂是個是非題：當 n 變大時，誤差 e_n = x_n - x* 會不會縮小到零？對你的問題會收斂的方法，意味著它後面的猜測你可以信任。但光是「會收斂」其實門檻很低。一個方法可能會收斂，卻要一百萬步才得到四個正確位數；另一個方法卻能在五步內得到十六個位數。要選得好，我們得衡量它的速度——這正是收斂速率要刻畫的東西。
線性收斂：一點一點削
衡量速度最乾淨的方式，是把每一步的誤差和前一步比較。假設誤差大致滿足 |e_{n+1}| ≈ C·|e_n|，其中常數 C 介於 0 與 1 之間。那麼每一步都把誤差乘上 C——誤差像等比數列一樣衰減。這叫線性收斂，C 稱為速率或收縮因子。若 C = 0.1，你大約每步多賺一個十進位數；若 C = 0.5，誤差每次只是減半，那就只能慢慢爬。
「線性」這個詞其實很容易誤導——誤差曲線不是一條直線，而是一條衰減的指數。這名字指的是右邊 e_n 的次方：它是一次方。二分法每步把根所在的區間對半切，是教科書範例：C 恰好等於 1/2，完全可靠但很慢。許多解線性系統的定常迭代（雅可比、高斯–賽德爾）也是線性收斂，其 C 由迭代矩陣的譜半徑決定——只有當這個半徑小於 1 時才會收斂。
比線性更快：階數 p
有些方法表現得好太多了。一般的定義是拿 e_{n+1} 去和 e_n 的某個次方比較：|e_{n+1}| ≈ C·|e_n|^p。這個指數 p 就是收斂階。當 p = 1 時回到線性（而且那時還額外需要 C < 1）。當 p = 2 時就是二次收斂，最令人嚮往：大致來說，正確位數每步翻倍。兩個正確位數變四個、再變八個、再變十六個——你會在寥寥幾步內就撞上雙精度的天花板。
牛頓法就是那個著名的二次收斂者。它的更新式如下：從一個猜測 x_n 出發，沿著 f 的切線滑到它與零相交之處。在單根附近、起點又夠好時，誤差每步平方一次——正是這個「翻倍」讓牛頓法在它管用的時候感覺幾乎像魔法。
x_{n+1} = x_n - f(x_n)/f'(x_n)
n x_n |error|
0 1.0 ~5e-1 (good start)
1 1.5 ~8e-2
2 1.4167 ~2e-3
3 1.41422 ~6e-6
4 1.4142136 ~4e-11 digits roughly double each step介於線性與二次之間的是超線性收斂，此時誤差比 |e_{n+1}|/|e_n| 本身趨近於零，但階數不是完整的 2。割線法是經典例子，階數約 1.618（黃金比例）——每步比牛頓法慢，但它不需要導數，所以每步更便宜。「階數最快」和「實際耗時最快」並不是同一回事。
細則：收斂是有條件的
階數描述的是在答案附近的行為——它是漸近的。它完全沒有說你到底會不會足夠靠近、好讓那個「快速階段」啟動。牛頓法的二次速率是一個局部承諾：從遠處出發，它可能猛烈衝過頭、卡在兩點之間來回循環、或飛向無窮大。這些是它的失效模式，而且很真實、並不罕見。一旦假設破裂，階數也會掉：在重根處（此時 f'(x*) = 0），牛頓法會從二次一路退化成只有線性。
就連最普通的線性方法都需要一個條件才會收斂。不動點迭代 x_{n+1} = g(x_n) 只有當 g 在不動點附近是一個收縮映射時才會收斂——具體來說，當 |g'(x*)| < 1，也就是收縮映射條件。若 |g'(x*)| > 1，迭代會遠離答案。蛛網圖就是把這件事畫出來的小圖：在曲線 y = g(x) 和直線 y = x 之間彈跳，看那個階梯是往內螺旋還是往外發散。
知道何時該停——以及自己量出速率
這一切裡藏著一個陷阱：誤差 e_n = x_n - x* 用到了 x*，也就是你還不知道的那個答案。所以實務上你沒辦法直接盯著真正的誤差看。取而代之，你盯著你看得到的量，把它們當作停止準則——通常是步長 |x_{n+1} - x_n|，以及求根時的殘差 |f(x_n)|。當兩者都低於容許值時就停。這是後驗的判斷進度方式：從你已經算出來的數字去估計，而不是靠一個事先就知道的公式。
你也可以從連續三個迭代值用實驗估計階數 p，完全不必知道 x*。取連續差的比值再取對數即可；下面的步驟把它寫清楚。這和對離散化做準確度階研究是同樣的精神：別只是相信理論上的O(h^p)宣稱——從你自己的執行結果量出指數，檢查數字是否真的照理論承諾的那樣做。
- 執行迭代，保留連續三個猜測 x_{n-1}、x_n、x_{n+1}（外加再前一個 x_{n-2}）。
- 計算連續差 d_n = x_{n+1} - x_n，同樣地算出 d_{n-1} 和 d_{n-2}。
- 把階數估計為 p ≈ log(|d_n| / |d_{n-1}|) / log(|d_{n-1}| / |d_{n-2}|)；這些差值就替代了未知的誤差。
- 解讀結果：p 接近 1 是線性、接近 2 是二次、約 1.6 暗示割線式的超線性方法。若你本來期待 2 卻量到接近 1，就該懷疑遇到重根或程式有錯。