二分法：慢，但保證找得到

我們究竟為什麼要獵根

大量的計算工作最終都歸結成同一個形狀：找一個 x 使得 f(x) = 0。拋射物何時落地？解 height(t) = 0。什麼利率能讓一筆貸款的還款與本金相抵？解一個關於利率、等於零的多項式。供給在哪裡遇上需求，化學反應在哪裡達到平衡？每一個都是某個函數穿過零的地方。最佳化也加入了這個行列，因為一個光滑函數的極小值，恰好坐落在它導數消失之處，所以把 g 最小化往往就意味著解 g'(x) = 0。求根，是支撐著極廣泛問題的那匹主力馬。

麻煩在於，這裡頭幾乎沒有一個能用公式解。二次式有它工整的公式，連三次與四次也有（駭人的）公式，但一個著名的結果說：對於一般的五次或更高次多項式，並不存在以根式表達的公式。再摻進一個正弦、一個指數、或一個對數——就像 x = cos(x)，或者那些混雜了次方與加總的利率方程——就完全沒有封閉形式了。於是我們做這整個學習階梯所要做的事：放棄精確的符號答案，改為計算根的一個數值近似，要多準就把它做到多準。這一級裡每一個答案都會是近似的，而我們真正的問題永遠是：一個方法把那個近似驅趕向真值的速度有多快。

我們唯一能倚靠的承諾：一次變號

二分法立基於一個直覺到連小孩都信的想法。想像一個連續函數 f，是不抬筆一筆畫出來的。若在某點 a 處 f(a) 為負、在另一點 b 處 f(b) 為正，那麼在 a 與 b 之間的某處，筆勢必曾穿過那條水平軸——在 (a, b) 裡必定有一個 x 使得 f(x) = 0。如果你從不抬筆，就不可能從線的下方走到線的上方而不碰到它。這正是把中間值定理拿來幹活：在 f 連續的一個區間上出現變號 f(a)*f(b) < 0，就是一個保證——有一個根被困住、被「括住」在裡頭。

注意這個要求有多麼樸素。我們不需要 f 的公式，不需要它的導數，甚至不需要知道根在哪裡、或有幾個——我們只需要能在某點求出 f 的值並讀出它的符號，外加一個兩端符號相反的起始括住區間。這份樸素，正是二分法的超能力。在那些更花俏的方法要求導數、要求光滑、要求一個好的起始猜測之處，二分法幾乎什麼都不要，卻以一個鐵打的承諾回報你。

演算法：對半切、檢查符號、重複

給定一個有變號的括住區間 [a, b]，這一步簡單到幾乎令人不好意思。取中點 c = (a + b) / 2 並求出 f(c)。如今那個原本在 [a, b] 某處的根，必定落在兩半之一，而 f(c) 的符號告訴你是哪一半：哪一半仍然顯示變號，哪一半就仍然括住那個根。留下那一半，丟掉另一半，你就得到一個寬度恰好減半、仍然保證含有一個根的新括住區間。重複。每一步只花一次新的 f 求值，外加一次符號比較。

從滿足 f(a) 與 f(b) 異號（即 f(a)*f(b) < 0）的 a、b 出發，並挑一個容忍度 tol，決定括住區間最終要縮到多小。
計算中點 c = (a + b) / 2，並求一次 f(c)。
若 f(c) 為零（或夠接近零），c 就是根——停止。否則檢查 f(c) 的符號。
若 f(a) 與 f(c) 異號，根在左半邊：令 b = c。否則根在右半邊：令 a = c。
若括住區間的寬度 b - a 低於 tol，回報中點作為答案；否則回到步驟 2。

bisection(f, a, b, tol):
    assert f(a) * f(b) < 0          # bracket must show a sign change
    while (b - a) / 2 > tol:
        c = a + (b - a) / 2         # midpoint (this form avoids overflow)
        fc = f(c)
        if fc == 0: return c        # exact hit (rare with floats)
        if f(a) * fc < 0:           # sign change is in the LEFT half
            b = c
        else:                       # sign change is in the RIGHT half
            a = c
    return a + (b - a) / 2          # midpoint of final tiny bracket

整個方法九行寫完。注意是 c = a + (b - a)/2 而非 (a + b)/2：兩者在實數算術裡相同，但前者即使逼近浮點極限時也安穩地待在 [a, b] 之內，而 (a + b) 在那裡可能溢位、或捨入到括住區間之外。

它到底有多快——又有多慢

美妙、完全可預測的部分來了。每一步都把括住區間的寬度減半，而根在裡頭某處，所以誤差——中點到真正的根的距離——最多是括住區間寬度的一半，並且每一次迭代都被砍半。經過 n 步，起始寬度便縮小了 2^n 倍。想從寬度為 W 的括住區間出發、算到某個容忍度？你大約需要 log2(W / tol) 步。把一個寬度為 1 的括住區間擠到 10^-6，大約要 20 步；擠到 10^-15、逼近雙精度浮點數的極限，大約要 50 步。每多一個正確的十進位數字，固定要再花大約 3.3 步，永遠如此——沒有驚喜，沒有加速。

那個固定的兌換率，正是我們所說的線性收斂：下一步的誤差是當前誤差的一個固定比例（這裡是二分之一），所以 e_{n+1} 大約是 (1/2) * e_n。用收斂那一級的語言來說，二分法的收斂階為 1，漸近常數為 1/2。拿它跟這一級後面會登場的牛頓法比一比，後者的誤差每一步是平方——一旦靠近，每次迭代大致讓正確數字的位數加倍。二分法一次只擠出一個數字、慢慢滴；牛頓法在一個好的根附近，則是傾盆而下地添加。以快速求解器的標準看，二分法確實慢，而我們應當直白地說出來。

但慢不等於弱。二分法的收斂速率是無條件的：它不依賴一個好的起始猜測、不依賴函數光滑、不依賴導數乖巧、也不依賴除了「那一個連續的變號」之外的任何東西。牛頓法可能從壞的起點發散、循環、或衝向無窮；二分法則根本不可能停止前進，因為把一個含有根的區間對半切，永遠都在朝那個根收縮。它是那個你可以信賴、每一次都會交貨、而且步調能事先預測的求根器。慢，但保證——這不是個安慰獎；對許多工作而言，它恰恰就是你想要的那個性質。

懂得何時該停——以及二分法做不到的事

因為括住區間的寬度是誤差的一個誠實上界，二分法擁有所有求根器中最乾淨的停止準則：當 (b - a)/2 低於你的容忍度時停下，你就能保證誤差不大於它。多數方法給不了這樣的保證；它們只能盯著相鄰猜測之間的變化，期望它能反映真正的誤差。但有兩點要留意。第一，容忍度要相對於根的大小來選，而不只是絕對值：想把一個接近 10^6 的根釘到絕對的 10^-15 是辦不到的，因為那比那裡可表示的雙精度數之間的間距還細。第二，每個數值答案都是活在浮點數網格上的近似；把 tol 壓到單位捨入誤差以下，只是白白浪費迭代，去追逐硬體根本表示不出的數字。

二分法能找到什麼，也有它誠實的限制。它需要一次變號，所以它對「碰到軸卻不穿越」的根視而不見——像 (x - 2)^2 這樣的重根，它在 x = 2 觸零後又彈回來，從不變號，二分法便無法把它括住。在給定的括住區間裡，即使藏著好幾個根，它也只找得到一個；而對複數根，它什麼也告訴不了你。並且在更高維度裡，當你必須同時解好幾個未知數的好幾條方程時，「跨區間變號」這個概念本身就瓦解了；並不存在乾淨的多維二分法，這正是後面關於方程組那一篇改而伸手去拿牛頓法的原因之一。