4.2 牛頓法#

概念說明#

二分法只會「看符號」，牛頓法（Newton-Raphson Method）則會「看斜率」。想法很直覺：想解 f(x) = 0，先猜一個點 x₀，在該點畫出 f 的切線，切線與 x 軸的交點通常比 x₀ 更接近真正的根，於是把它當成新的猜測 x₁，如此反覆。切線在 x₀ 的方程為 y = f(x₀) + f′(x₀)(x − x₀)，令 y = 0 解出：

x_{n+1} = x_n − f(x_n) / f′(x_n)

這一行迭代公式是數值分析中最著名的公式之一。它有優雅的幾何解釋（沿切線滑到 x 軸），也有深刻的理論性質：在根附近且 f′ 不為零時，誤差滿足 e_{n+1} ≈ C·e_n²，即二次收斂——每迭代一次，正確位數大約翻倍。第 1 章的巴比倫開方法正是牛頓法用在 f(x) = x² − a 上的特例。

牛頓法的代價有三：(1) 需要導數 f′，有時只能用差分近似或改用割線法；(2) 初始猜測太遠時可能發散或震盪（例如 f(x) = x^(1/3) 會永遠在兩個點之間跳）；(3) 在 f′ ≈ 0 的平坦區域，步長會爆掉。因此實作上必須加入步長上限與最大迭代次數等保護措施。

演算法步驟#

選定初始猜測 x₀ 與容許誤差 ε、最大迭代次數 N。
計算 f(x_n) 與 f′(x_n)。
若 |f(x_n)| < ε 或 |Δx| < ε，回傳 x_n。
令 x_{n+1} = x_n − f(x_n)/f′(x_n)（若 |f′| 過小，報「平坦區」錯誤）。
重複 2~4 直到收斂或達 N 次。

Python 程式碼範例#

def newton(f, df, x0, tol=1e-12, max_iter=50):
    x = x0
    for i in range(max_iter):
        fx = f(x)
        if abs(fx) < tol:
            return x, i
        d = df(x)
        if abs(d) < 1e-14:
            raise ZeroDivisionError("導數趨近零，牛頓法失效")
        step = fx / d
        x -= step
        if abs(step) < tol:
            return x, i + 1
    raise RuntimeError("牛頓法未收斂")

# 例 1：解 x = cos(x)
f  = lambda x: x - __import__("math").cos(x)
df = lambda x: 1 + __import__("math").sin(x)
root, n = newton(f, df, 0.5)
print(f"x = cos(x) 的根 ≈ {root:.15f}，迭代 {n} 次")

# 例 2：搭配 sympy 自動求導
import sympy as sp
X = sp.symbols("x")
g = sp.exp(-X) - X          # 解 e^(-x) = x
dg = sp.diff(g, X)
gfun, dgfun = sp.lambdify(X, g), sp.lambdify(X, dg)
root2, n2 = newton(gfun, dgfun, 1.0)
print(f"e^(-x) = x 的根（Omega 常數）≈ {root2:.15f}，迭代 {n2} 次")

你可以觀察到：兩個例子都在 4~6 次迭代內達到機器精度，這正是二次收斂的威力。同時試試把初始值改成 10 或 −5，體會「初始猜測很重要」這件事。

複雜度與誤差分析#

設 r 是 f 的單根，且 f 在 r 附近二階連續可微、f′(r) ≠ 0。泰勒展開可證誤差滿足

e_{n+1} = |f″(r) / (2f′(r))| · e_n² + O(e_n³)

因此牛頓法的收斂階 p = 2。達到精度 ε 所需迭代次數約為 log₂(log₂(1/ε) − log₂ e₀)，與 ε 只有雙重對數關係——從 10⁻¹ 到 10⁻¹⁵ 精度往往只多花三四次迭代。若 r 是 m 重根，收斂退化為線性，修正方法是改解 u(x) = f(x)/f′(x) 或用 x_{n+1} = x_n − m·f/f′。每次迭代的計算成本是「一次 f 求值 + 一次 f′ 求值」；割線法省去導數，但收斂階降為 1.618。多維版本（牛頓法解聯立方程組）將除法換成解線性系統，是第 5 章高斯消去的直接應用。

練習#

用牛頓法計算 √a（f(x) = x² − a），並與第 1 章的巴比倫法比對，說明兩者的迭代式完全相同的原因。
對 f(x) = x³ − 2x + 2（有多個臨界點的經典發散案例），測試不同的 x₀，找出會發散或落入循環的初始值，並解釋幾何原因。
實作割線法（用前兩點的割線斜率取代導數），與牛頓法在同一問題上比較迭代次數與函數求值總次數。