3.3 割線法與其他變形#

概念說明#

牛頓法快，但要導數；二分法穩，但慢。割線法（secant method）走中間路線：不計算 \(f'\) ，而是用最近兩點 \((x_{k-1}, f(x_{k-1}))\) 、 \((x_k, f(x_k))\) 的連線（割線）斜率近似導數：

\[ x_{k+1} = x_k - f(x_k)\,\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})} \]

幾何上是用割線取代切線；代數上是用差商 \(\frac{f(x_k)-f(x_{k-1})}{x_k - x_{k-1}}\) 近似 \(f'(x_k)\) 。因兩點距離隨迭代縮小，近似越來越準，收斂階達 \(p = \frac{1+\sqrt5}{2} \approx 1.618\) （黃金比例）——比線性快、比平方慢。有趣的是：以「每步一個新函數值」計算，割線法每步 1 次求值，牛頓法每步 2 次；按效率指數 \(p^{1/\text{每步求值次數}}\) 比較，割線法 \(1.618\) 高於牛頓法的 \(\sqrt2 \approx 1.414\) ——少算一個導數反而總體更省。

其他重要變形：

假位法（regula falsi）：用割線公式，但像二分法一樣維持夾根區間。保證收斂，但一端常「卡住」，收斂可能比二分法還慢。
Steffensen 法：用 \(f(x_k + f(x_k))\) 取代差商，平方收斂、免導數，但要求初始值極近。
Dekker/Brent 混合法：每步在「割線」「反二次插值」「二分」三者中選擇，能快則快、該穩則穩，並始終保持夾根區間。Brent 證明其收斂性至少不遜於二分法，實務上通常以超線性速度收斂——這是 scipy.optimize.brentq 與 MATLAB fzero 的核心。

生活類比#

估計自行車速度：不用儀表（導數），而是記住「3 秒前與現在的位置」，用平均速度外推瞬時速度——這是差商。天氣預報混用快而野的模型與慢而穩的經驗法則，遇到不靠譜就退回保守估計——這是混合法的精神。

演算法步驟#

割線法：

給 \(x_0, x_1\) （兩點靠近根、且 \(f(x_0) \ne f(x_1)\) ）。
迭代割線公式得 \(x_{k+1}\) 。
停機： \(|x_{k+1} - x_k| < \varepsilon\) 且 \(|f(x_{k+1})| < \delta\) 。
防護：若 \(f(x_k) = f(x_{k-1})\) （割線水平）或迭代過多，中止。

Brent 混合法（概念版）：

維持夾根區間 \([a, b]\) 。
每步嘗試割線/反二次插值求候選點 \(s\) 。
若 \(s\) 落在區間內且收斂條件健康，接受；否則退回二分中點。
區間更新保持符號異號，直到區間小於 \(\varepsilon\) 。

Python 範例#

def secant(f, x0, x1, eps=1e-12, max_iter=50):
    f0, f1 = f(x0), f(x1)
    for k in range(1, max_iter + 1):
        if f1 == f0:
            raise ZeroDivisionError("割線水平")
        x2 = x1 - f1 * (x1 - x0) / (f1 - f0)
        if abs(x2 - x1) < eps and abs(f(x2)) < eps:
            return x2, k
        x0, f0, x1, f1 = x1, f1, x2, f(x2)
    return x1, max_iter

f = lambda x: x**3 - x - 2
root, n = secant(f, 1.0, 2.0)
print(f"割線法根 ≈ {root:.12f}，迭代 {n} 次")

# 混合法：牛頓失足時退回二分
def hybrid(f, a, b, eps=1e-12, max_iter=100):
    fa, fb = f(a), f(b)
    if fa * fb > 0:
        raise ValueError("未夾根")
    x, fx = a, fa
    for k in range(max_iter):
        s = x - fx / 1e-9 if False else None
        try:  # 割線候選
            s = x - fx * (x - b) / (fx - fb) if fx != fb else None
        except ZeroDivisionError:
            s = None
        if s is None or not (a < s < b):
            s = (a + b) / 2
        fs = f(s)
        if abs(fs) < eps or (b - a) / 2 < eps:
            return s, k + 1
        if fa * fs < 0:
            b, fb = s, fs
        else:
            a, fa = s, fs
        x, fx = s, fs
    return (a + b) / 2, max_iter

print("混合法根 ≈", f"{hybrid(f, 1, 2)[0]:.12f}")

複雜度與收斂性分析#

割線法收斂階 1.618，兩個初始值靠近根時極快；缺點是無全域保證、可能發散或循環。假位法保證收斂但可能緩慢。Brent 法最壞情形為線性（ \(L \le 1/2\) ，與二分法同）、典型為超線性，且不需導數——生產環境求根的預設選擇。選法總結：有夾根區間→Brent；導數便宜且起點可靠→牛頓；兩點歷史資料現成、無導數→割線。

練習#

實測割線法解 \(x^3 - x - 2 = 0\) 的收斂階，與 1.618 比對。
實作假位法，觀察「一端卡住」現象（印出每輪區間），並用 Illinois 修正（假位法加速版：卡住端函數值減半）改善。
用 scipy.optimize.brentq 解同一方程，比較其迭代次數與你手寫混合法的差異，並閱讀文件確認它基於 Brent 法。