4.1 二分法與假位法#

概念說明#

假設 f 在區間 [a, b] 上連續，且 f(a) 與 f(b) 異號。由中間值定理（Intermediate Value Theorem），必存在某個 c ∈ (a, b) 使 f(c) = 0。求根演算法最穩健的家族就建立在這個定理上：我們不斷「縮小那個保證含根的區間」，直到區間小於容許誤差。

二分法（Bisection）：每次取中點 m = (a+b)/2，檢驗 f(m) 的符號，把區間砍半。無論函數形狀如何，保證收斂，這是它最大的優點。
假位法（False Position / Regula Falsi）：不用中點，改用連接 (a, f(a)) 與 (b, f(b)) 的割線與 x 軸的交點作為新測試點。當函數接近線性時，收斂得比二分法快；但最壞情況下可能一端不動，退化成線性收斂。

兩者的共同哲學是：只用函數值的符號資訊，不碰導數。這使它們適用於 f 不可微、甚至只有黑箱存取的場合。

演算法步驟#

以二分法為例：

確認 f(a)·f(b) < 0（否則報錯：此區間不保證含根）。
計算中點 m = (a+b)/2。
若 f(m) = 0，直接輸出 m。
若 f(a)·f(m) < 0，根在 [a, m]，令 b = m；否則令 a = m。
重複 2~4 直到 b − a < ε（誤差容許值）或達最大迭代次數。

假位法僅將第 2 步改為：m = (a·f(b) − b·f(a)) / (f(b) − f(a))，這是割線的 x 截距。

Python 程式碼範例#

def bisection(f, a, b, tol=1e-10, max_iter=200):
    fa, fb = f(a), f(b)
    if fa * fb > 0:
        raise ValueError("f(a) 與 f(b) 必須異號")
    for i in range(max_iter):
        m = (a + b) / 2
        fm = f(m)
        if fm == 0 or (b - a) / 2 < tol:
            return m, i + 1
        if fa * fm < 0:
            b, fb = m, fm
        else:
            a, fa = m, fm
    return (a + b) / 2, max_iter

def false_position(f, a, b, tol=1e-10, max_iter=200):
    fa, fb = f(a), f(b)
    for i in range(max_iter):
        m = (a * fb - b * fa) / (fb - fa)
        fm = f(m)
        if abs(fm) < tol:
            return m, i + 1
        if fa * fm < 0:
            b, fb = m, fm
        else:
            a, fa = m, fm
    return m, max_iter

# 例：解 x^3 - x - 2 = 0
f = lambda x: x**3 - x - 2
root, n = bisection(f, 1, 2)
print(f"二分法:   根 ≈ {root:.12f}，迭代 {n} 次")
root2, n2 = false_position(f, 1, 2)
print(f"假位法:   根 ≈ {root2:.12f}，迭代 {n2} 次")

執行結果中，二分法約需 33 次迭代達到 1e-10 精度；假位法在這個例子上更快，但你可以嘗試 f(x) = x^10 − 1 在 [0, 2] 上，會發現假位法的一端長期不動，反而更慢。

複雜度與誤差分析#

二分法每次迭代把區間長度減半，n 次迭代後誤差 ≤ (b−a)/2^n。要達到誤差 ε，需要 n ≈ log₂((b−a)/ε) 次——這是線性收斂（每次迭代誤差乘上一個固定常數 1/2），而且這個界對任何連續函數都成立，是「最壞情況保證」的典範。假位法的收斂階通常優於線性，但不保證；改良版 Illinois 演算法透過在停滯端加倍函數值權重，可恢復超線性收斂。實務上， scipy.optimize.brentq 採用的 Brent 法混合二分、割線與反插值，兼顧穩健與速度，是工程首選。

練習#

把 bisection 改成回傳完整迭代紀錄（每步的區間與中點），並對 f(x) = cos(x) − x 在 [0, 1] 上驗證誤差確實每次減半。
實作 Illinois 修正的假位法：當某一端連續兩次不變時，將該端 f 值乘上 0.5 再做插值。比較它與原始假位法在 x^10 − 1 上的迭代次數。
用二分法寫一個函數 find_all_roots(f, lo, hi, n=1000)：先把 [lo, hi] 切成 n 個小段，對每段檢查變號再套二分法。用它找出 sin(x) 在 [0, 10] 上的所有根。