求根與非線性方程

二分法(bisection method)

想像你知道一筆寶藏埋在田裡兩根木樁之間的某處,而你手上的儀器在任何一點只會告訴你寶藏在你的左邊還是右邊。你走到中點問儀器,把不可能藏寶藏的那一半丟掉,再重複下去,未搜尋的範圍每次都減半。二分法解 f(x) = 0 也是同樣的道理:不斷對半切割一個保證困住根的區間。

具體來說,你從兩個點 a 與 b 開始,要求 f(a) 與 f(b) 正負號相反(一正一負)。若 f 連續,介值定理保證它們之間必有一個根。你算中點 m = (a + b) / 2,看 f(m) 的正負號;[a, m] 與 [m, b] 之中仍然兩端異號的那一半成為新區間,另一半捨棄。n 步之後區間長度為 (b - a) / 2^n,於是根被鎖定在這個容差之內。要把誤差壓到 epsilon 以下,大約需要 log2((b - a) / epsilon) 步——例如把寬度 1 縮到 10^-6,約需 20 次函數計算。

二分法是求根界的烏龜:它保證收斂(不會發散也不會循環),只需要 f 的正負號,連導數都不必。代價是速度——它只線性收斂,每步固定縮小一半,大致每次迭代多得到一個正確的二進位位數(約三步換一個十進位有效位)。一旦靠近根,牛頓法或割線法等快速方法會把它遠遠甩開,這也正是為何 Brent 法等穩健求解器把二分法當安全網,在安全時切換到快速方法。

在 [1, 2] 上解 x^2 - 2 = 0。f(1) = -1、f(2) = 2,正負相反。中點 1.5 給出 f = 0.25 > 0,保留 [1, 1.5]。下個中點 1.25 給出 f = -0.4375 < 0,保留 [1.25, 1.5]。區間持續對半逼近 sqrt(2) = 1.41421...;每步約增加一個二進位位數。

每步把括住的區間減半——慢,但極其可靠。

二分法需要真正的變號才能起步:若 f 只觸碰零而不穿越(如重根 (x-1)^2),兩端正負號相同,二分法根本無法開始。它也只找到括住區間內的一個根,而非全部。

又稱
binary search for a rootinterval halving對分法