Ridder 方法是介於二分法與牛頓法之間的強健求根演算法,不需要導函數、收斂速度超線性、保證收斂 (根被括住時)。本文提供純 Python 實現、參數說明與使用範例。
給定區間 [a, b] 使 f(a)*f(b) < 0 (異號),取中點 c = (a+b)/2,計算改良根:
x = c ± (c-a)*f(c)/sqrt(f(c)^2 - f(a)f(b))
符號選擇使分母絕對值最大化。新點 x 取代區間端點,重複至收斂。
import math
def ridder(f, a, b, tol=1.0e-9, max_iter=30):
"""
Ridder 方法求 f(x)=0 根
:param f: 目標函數
:param a: 區間左端
:param b: 區間右端
:param tol: 容差
:param max_iter: 最大迭代次數
:return: 根 或 None (未收斂)
"""
fa = f(a)
if abs(fa) < tol:
return a
fb = f(b)
if abs(fb) < tol:
return b
if fa * fb > 0:
raise ValueError("Root not bracketed: f(a) and f(b) must have opposite signs")
x_old = None
for i in range(max_iter):
c = 0.5 * (a + b)
fc = f(c)
if abs(fc) < tol:
return c
s = math.sqrt(fc*fc - fa*fb)
if s == 0:
return None
dx = (c - a) * fc / s
if (fa - fb) < 0:
dx = -dx
x = c + dx
fx = f(x)
# 收斂檢查
if x_old is not None and abs(x - x_old) < tol * max(abs(x), 1.0):
return x
x_old = x
# 重新括根
if fc * fx > 0:
if fa * fx < 0:
b = x
fb = fx
else:
a = x
fa = fx
else:
a = c
b = x
fa = fc
fb = fx
raise RuntimeError("Too many iterations")
# 使用範例
def f(x):
return x**3 - 2*x - 5 # 根約 2.09455
root = ridder(f, 2, 3)
print(f"Root: {root:.10f}") # 2.0945514815
| 方法 | 需導函數 | 收斂階 | 保證收斂 | 適用場景 |
|---|---|---|---|---|
| 二分法 | 否 | 線性 (1/2) | 是 | 保證收斂、函數不連續 |
| Ridder | 否 | ~1.618 (超線性) | 是 (根被括住) | 通用、無導函數、強健 |
| 牛頓法 | 是 | 二次 | 否 (需好初值) | 光滑函數、導函數易得 |
| 割線法 | 否 | ~1.618 | 否 | 無導函數、較快但可能發散 |
| Brent 方法 | 否 | 超線性 | 是 | 科學計算標準 (SciPy 預設) |
from scipy.optimize import brentq
root = brentq(f, 2, 3) # Brent 方法,更強健、經過大量測試
print(root)
Ridder 方法是無導函數、保證收斂、收斂速度快的優選演算法。教學/嵌入式無 SciPy 環境時可直接使用上述實現;生產環境優先使用 scipy.optimize.brentq。