從 f(x) = 0 到 x = g(x)
上一篇指南給了我們二分法：安全、有保證，但慢——它每一步把區間對半砍，每次迭代只換來大約一個位元。我們想要更快的東西，而最便宜的點子就是這個。拿你的方程式 f(x) = 0，用代數把它挪成 x = g(x) 的形式，這樣一個解就是被 g 映成自己的那個點。這樣的點叫做 g 的不動點（fixed point），因為把它餵過 g 什麼都不會變：g 讓它不動。於是解 f(x) = 0 和找出對的 g 的不動點，就是同一件事穿著兩套不同的戲服。
一旦你有了 x = g(x)，方法就自動寫好了：挑一個起始猜測 x_0，然後迭代 x_{n+1} = g(x_n)，每一次讀出一個新猜測。這就是不動點迭代，它簡單到不能再簡單——每步算一次函數，不用導數、不用區間。想像一條數線：你站在 x_0，函數 g 把你拎起來、放到 x_1 = g(x_0)，再從那裡把你拎起來、放到 x_2，以此類推。如果你不斷落得離某一點越來越近，那一點就是不動點，你也就拿到了答案。
讓這門主題變得有趣的關鍵就在這裡：那個改寫並不唯一。同一個方程式 f(x) = 0 可以被揉成許多不同的 g，而它們的行為並不一致。拿 x^2 - x - 2 = 0，它的根是 -1 與 2。你可以寫成 x = x^2 - 2，或 x = sqrt(x + 2)，或 x = 2/(x - 1)，或 x = 1 + 2/x——它們全都以 x = 2 為不動點，然而有些迴圈飛奔向 2，有些用爬的，有些則爆掉、根本到不了。同一個根、同一個起始猜測，命運卻天差地遠。所以真正的問題不是「x = 2 是不是不動點」，而是「『這個』迴圈會找到它嗎？」
在蛛網圖上看迴圈跑
有一幅美麗的圖能讓你「看見」一個迴圈是否收斂，叫做蛛網圖（cobweb diagram）。在同一組座標軸上畫出曲線 y = g(x) 與對角線 y = x。它們的交點就是不動點，那裡 g(x) 等於 x。現在追蹤一步：從橫軸上的 x_0 出發，直直往上到曲線，讀出 g(x_0)——那個高度就是你的下一個猜測 x_1——再直直橫越到對角線，把那個值帶回到 x 軸上當作新的輸入。上到曲線、橫到直線、上到曲線、橫到直線：這條路徑會走成樓梯或盤成螺旋，而蛛網圖讓整個迭代一眼可見。
蛛網究竟是「捲進」交點還是「甩離」它，完全取決於曲線 g 在它與對角線相遇之處有多陡。如果曲線在那裡很平緩——比 45 度對角線還平——每一步就落得離不動點更近，蛛網會收緊進那個角落。如果曲線比對角線還陡，每一步就比前一步多衝過頭一點，蛛網會向外炸開，遠離你正在追的那一點。捕捉「比對角線更陡還是更平」的那個單一數字，就是 g 在不動點處的斜率 g'(x_star)。那個斜率，就是整場遊戲的關鍵。
壓縮條件
讓我們把這幅圖變成一個保證。假設在根附近的某個區間上，g 把距離拉伸的倍數從不超過某個固定、且小於 1 的因子 L——形式上講，對區間裡所有的 a、b 都有 |g(a) - g(b)| <= L |a - b|，其中 L < 1。一個像這樣把每段距離都縮小的映射，叫做壓縮映射（contraction），而 L 是它的壓縮因子。於是壓縮映射條件一口氣保證三件事：區間裡恰好有一個不動點、迭代從區間內任何起點都收斂到它、而且收斂是幾何式的。
理由直接到幾乎令人不好意思。設 x_star 是不動點，e_n = x_n - x_star 是第 n 步的誤差。因為 g(x_star) = x_star，一步之後的誤差是 e_{n+1} = g(x_n) - g(x_star)，而壓縮上界說這頂多是 L 乘上 |x_n - x_star| = |e_n|。所以每一步把誤差至多乘上 L：n 步之後，|e_n| <= L^n |e_0|。因為 L < 1，因子 L^n 一路走向零，把誤差一起拖下去。不管你在區間裡哪裡起步，這個迴圈都非收斂不可。
L 和我們在蛛網上看到的斜率有什麼關係？由均值定理，如果 g 可微，那麼在一個區間上行得通的最小 L，就是該處 |g'(x)| 的最大值。所以在不動點附近，局部的壓縮因子就是 |g'(x_star)|，而條件 |g'(x_star)| < 1 正是蛛網方才向我們展示的東西。這就把兩種觀點綁在一起：你在圖上目測的斜率，「就是」那個掌控誤差的壓縮因子。這是收斂階最乾淨的例子——這裡是一階，我們接下來就探討它。
線性收斂——以及一個小小的算例
因為每一步把誤差大致乘上常數因子 L = |g'(x_star)|，不動點迭代是線性收斂：誤差每步以一個穩定的比例縮小，正確位數每步增加固定的量。收斂速率就是那個因子 L。如果 L = 0.1，你每步換來一位小數——很快。如果 L = 0.9，你大約每 22 步才換來一位，因為要掉一個數量級得靠約 0.9^22——慢得讓人難受，儘管它最終確實會收斂。線性收斂誠實卻謙遜；它是這一級裡那些更快的方法將要設法超越的底線。
Solve x = cos(x) (i.e. find the root of x - cos(x) = 0) Here g(x) = cos(x), and g'(x) = -sin(x), so near the root |g'| is about 0.67 < 1 -> a contraction, alternating-sign errors. x_0 = 1.000000 x_1 = cos(1.000000) = 0.540302 x_2 = cos(0.540302) = 0.857553 x_3 = cos(0.857553) = 0.654290 x_4 = cos(0.654290) = 0.793480 ... x_20 ~ 0.739085 (true fixed point 0.7390851...) Errors flip sign each step (spiral) and shrink by ~0.67 per step: linear convergence, about one new digit every ~6 steps.
拿它對照先前那些糟糕的改寫。對於 x^2 - x - 2 = 0 在根 x = 2 處，形式 x = x^2 - 2 有 g'(x) = 2x，所以 g'(2) = 4：斜率遠比對角線陡，蛛網向外炸開，迭代不管你起步多近都發散。形式 x = sqrt(x + 2) 有 g'(x) = 1/(2 sqrt(x+2))，所以 g'(2) = 0.25 < 1：一個壓縮，它漂亮地收斂。同樣的方程式、同樣的根——「唯一」的差別就是 g 在不動點處的斜率。這就是為什麼挑選改寫方式才是這個方法真正的功夫。
停手、誠實的極限，與這通往何處
你什麼時候停手？你沒辦法盯著真正的誤差 e_n，因為你沒有 x_star。實用的停止準則改盯步長：當相鄰的迭代值幾乎不動時就停手，也就是 |x_{n+1} - x_n| 低於某個容忍度，可以再搭配檢查 |f(x_n)| 是否夠小。不過這裡有個細節。當 L 接近 1 時，步長 |x_{n+1} - x_n| 看起來可能很小，但剩餘的誤差 |x_n - x_star| 仍約是那個步長的 1/(1 - L) 倍——所以一個近乎停滯的迴圈可能騙得你太早收手。L 越接近 1，步長就越會低估真正的誤差。
那為什麼要費心於一個只是線性、甚至沒保證的方法？因為這個想法是後面一切的種子。我們夢想的是工程出一個 g，使它在根處的斜率不只小於 1，而是恰好為「零」——那時線性收斂就崩塌，一個更快的局面接手。那正是下一篇指南裡牛頓法背後的把戲：它是一個帶有精心建造的 g 的不動點迭代，使得 g'(x_star) = 0，從而買到二次收斂，每一步大致把正確位數翻倍。而遠遠超出求根之外，壓縮與不動點的故事還會以迭代線性求解器背後的引擎之姿重現，那裡迭代矩陣扮演 g' 的角色、它的譜半徑扮演 L 的角色。把這個小迴圈學透，你就見到了迭代計算的心跳。