3.1 二分法#

概念說明#

二分法（bisection method）是求根法中最簡單也最可靠的一種。前提： \(f\) 在閉區間 \([a, b]\) 上連續，且 \(f(a) f(b) < 0\) （兩端異號）。由中間值定理， \(f\) 必在 \((a, b)\) 內有根。

迭代過程：取中點 \(m = (a+b)/2\) ，檢查 \(f(m)\) 的符號：

若 \(f(a) f(m) < 0\) ，根在 \([a, m]\) ，令 \(b \leftarrow m\) ；
否則根在 \([m, b]\) ，令 \(a \leftarrow m\) 。

每輪區間長度恰好減半，含根區間始終被夾住。 \(n\) 輪後區間長度為 \((b-a)/2^n\) ，故達到精度 \(\varepsilon\) 需要 \(n \ge \log_2\!\big(\tfrac{b-a}{\varepsilon}\big)\) 次——線性收斂，收斂速率 \(L = 1/2\) ，是二分法可事先精確預測迭代次數的罕見美德。例如把 1 單位長的區間縮到 \(10^{-12}\) ，只需約 40 次迭代。

優點：保證收斂、只需函數連續（不必可微）、程式極簡、對浮點誤差魯棒。缺點：線性收斂偏慢；只能求一個根；無法處理根是偶數重（函數不變號）的問題，如 \(f(x) = (x-1)^2\) 在根兩側同號，二分法會錯過它。實務上二分法常作為「保底」：與快但偶爾發散的方法（牛頓法）混合使用。

生活類比#

猜 1 到 100 的數字，對方只說「高了/低了」：每次砍一半，七次必中——這正是二分法。查字典也一樣：翻中間比對，決定往前或往後，範圍對半縮小。

演算法步驟#

確認 \(f(a) f(b) < 0\) ，否則回報「無法保證夾根」。
迭代： \(m = (a+b)/2\) ；若 \(f(m) = 0\) （或夠小）直接回傳。
依符號更新 \(a\) 或 \(b\) ，保持 \(f(a)f(b) < 0\) 。
當 \(b - a < \varepsilon\) （或 \(|f(m)| < \delta\) ）時停止，回傳中點。
為避免區間過小時 \((a+b)/2\) 因浮點捨入而不再變動，可檢查 \(m \in \{a, b\}\) 提前停止。

Python 範例#

求 \(f(x) = x^3 - x - 2\) 的根：

def bisection(f, a, b, eps=1e-12, max_iter=200):
    fa, fb = f(a), f(b)
    if fa == 0:
        return a
    if fb == 0:
        return b
    if fa * fb > 0:
        raise ValueError("f(a) 與 f(b) 未夾根")
    for k in range(1, max_iter + 1):
        m = a + (b - a) / 2      # 避免溢位的寫法
        fm = f(m)
        if fm == 0 or (b - a) / 2 < eps:
            return m, k
        if fa * fm < 0:
            b, fb = m, fm
        else:
            a, fa = m, fm
    return a + (b - a) / 2, max_iter

f = lambda x: x**3 - x - 2
root, n = bisection(f, 1, 2)
import math
print(f"根 ≈ {root:.12f}，迭代 {n} 次，f(根) = {f(root):.2e}")
print("理論次數 ≈", math.ceil(math.log2((2 - 1) / 1e-12)))

實測迭代次數與理論值 \(\lceil \log_2(1/10^{-12}) \rceil = 40\) 吻合。

複雜度與收斂性分析#

每次迭代一次函數求值，總成本 \(O(\log_2((b-a)/\varepsilon))\) 次求值，誤差上界 \(|m - x^*| \le (b-a)/2^{k+1}\) 嚴格成立。線性收斂、速率恰 \(1/2\) 。與牛頓法比較：二分法每步只縮一位精度的一半（對數意義），牛頓法位數翻倍，故高精度時牛頓法快得多；但二分法不需要導數、永不發散。經驗法則：有可靠夾根區間就用二分法打底，要快就上牛頓或割線，生產程式碼用混合法。

練習#

用二分法求 \(\sqrt{2}\) （即 \(f(x) = x^2 - 2\) ），迭代到區間小於 \(10^{-15}\) ，與 math.sqrt 比較。
偶數重根問題：對 \(f(x) = (x-1)^2\) 用二分法會發生什麼？設計一個對偶數重根也有效的策略（提示：對 \(|f'|\) 或 \(f\) 的小值做搜尋）。
寫一個自動掃描 \([x_{\min}, x_{\max}]\) 找出所有夾根區間、再逐一用二分法求根的函數，對 \(f(x) = \sin(x) - x/2\) 在 \([-10, 10]\) 測試。