萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 數值求根:Ridder 尋根法實現 f(x)=0 解析

Ridder 方法是介於二分法與牛頓法之間的強健求根演算法,不需要導函數、收斂速度超線性、保證收斂 (根被括住時)。本文提供純 Python 實現、參數說明與使用範例。

Ridder 方法原理

給定區間 [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 取代區間端點,重複至收斂。

純 Python 實現

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 預設)

生產環境建議:使用 SciPy

from scipy.optimize import brentq
root = brentq(f, 2, 3)  # Brent 方法,更強健、經過大量測試
print(root)

總結

Ridder 方法是無導函數、保證收斂、收斂速度快的優選演算法。教學/嵌入式無 SciPy 環境時可直接使用上述實現;生產環境優先使用 scipy.optimize.brentq。

copyright © 萬盛學電腦網 all rights reserved