試位法(regula falsi)
/ REG-yoo-lah FAL-see /
Regula falsi(拉丁文「試位之法」)是最古老的求根想法之一,曾用於古巴比倫、埃及與中國。把它想成繫上安全帶的割線法:它在兩點之間畫同樣的直線,但讓那兩個點「永遠」跨越根——一個 f 為負、一個為正——使根無從脫離掌握。它把割線的直線速度與二分法的保證結合起來。
你像二分法一樣,從 f(a) 與 f(b) 異號的夾根區間 [a, b] 開始。但不取中點,而取連接 (a, f(a)) 與 (b, f(b)) 的直線(割線)穿越零的點:c = b - f(b) * (b - a) / (f(b) - f(a))。你計算 f(c),並替換掉與 f(c)「同號」的那個端點,使新的一對仍夾住根。因為你始終保有真正的夾根區間,regula falsi 不會發散——不像普通割線法——且通常勝過二分法,因為割線瞄準根而非盲目對半。
有一個著名的陷阱值得誠實面對。對在夾根區間上強烈彎曲(凸或凹)的函數,「一個」端點可能卡住永不更新,而另一個每次只爬一小步向根靠近。方法仍收斂,但只線性——有時比二分法還慢——背離了它的初衷。標準補救是 Illinois 演算法及其變體,把停滯端點的函數值減半以逼它移動,在保有夾根區間的同時恢復快速的超線性收斂。Brent 法把這些加保護的想法揉合在一起,成為現代的預設選擇。
對 f(x) = x^3 - x - 1 取夾根區間 [1, 2](f(1) = -1、f(2) = 5):割線給出 c = 2 - 5*(2-1)/(5-(-1)) = 1.167,且 f(1.167) < 0,故替換 a:新夾根區間 [1.167, 2]。每步直線瞄得更靠近根 1.3247——比對半快,卻從不失去夾根區間。
保持在夾根區間內的割線:像二分法一樣安全,通常更快。
對強烈彎曲的函數,當一個端點卡住時,普通的 regula falsi 會停滯到線性速度(甚至比二分法還慢);務必使用穩定化的變體(Illinois),或直接用自動處理此問題的 Brent 法。