3.2 牛頓法#

概念說明#

牛頓法（Newton-Raphson method）是求根迭代的速度之王。想法：在目前的猜測點 \(x_k\) ，用曲線 \(y = f(x)\) 的切線近似曲線，切線與 x 軸的交點作為下一個猜測。切線方程為 \(y = f(x_k) + f'(x_k)(x - x_k)\) ，令 \(y = 0\) 解出：

這正是 2.1 節不動點形式 \(x_{k+1} = g(x_k)\) ，其中 \(g(x) = x - f(x)/f'(x)\) 。計算 \(g'(x^*) = 1 - \frac{f'(x^*)^2 - f(x^*)f''(x^*)}{f'(x^*)^2} = \frac{f(x^*) f''(x^*)}{f'(x^*)^2} = 0\) （因 \(f(x^*) = 0\) ）——導數在不動點為零，正是不動點迭代達到平方收斂的訊號：誤差滿足

正確位數每步翻倍，5～8 步即達雙精度極限。

牛頓法也是化根為不動點的設計學：求 \(c\) 的平方根即解 \(x^2 - c = 0\) ，代入得 \(x_{k+1} = \frac{1}{2}(x_k + c/x_k)\) ——巴比倫法原來就是牛頓法！同樣手法可導出倒數（ \(f(x) = 1/x - c\) ，得 \(x_{k+1} = x_k(2 - c x_k)\) ，不需除法，GPU 求倒數的經典技巧）、立方根等。

風險面：若 \(f'(x_k)\) 接近 0，修正量爆炸；若初始值不當，可能發散、震盪，或收斂到「錯的根」；對多重根（ \(f(x) = (x-1)^2\) ）收斂退化為線性（ \(\lambda = 1/2\) ）。因此生產級程式碼幾乎都把牛頓法與二分法混合。

生活類比#

在濃霧中下山找谷底：站在原地感受坡度，沿最陡方向跨一步，再感受、再跨——這是牛頓法在最佳化中的化身（5.1 節）。跨步大小由當地坡度決定，坡平時跨大步、坡陡時跨小步。

演算法步驟#

1. 選初始值 \(x_0\) （若可能，靠近預期根；可用掃描或二分法先打底）。
2. 迭代 \(x_{k+1} = x_k - f(x_k)/f'(x_k)\) 。
3. 停機： \(|x_{k+1} - x_k| < \varepsilon_1\) 且 \(|f(x_{k+1})| < \varepsilon_2\) （混合準則）。
4. 防護：限制最大迭代次數；若 \(|f'|\) 過小，中止或改用二分法保護。

Python 範例#

def newton(f, df, x0, eps=1e-12, max_iter=50):
    x = x0
    for k in range(1, max_iter + 1):
        fx, dx = f(x), df(x)
        if abs(dx) < 1e-300:
            raise ZeroDivisionError("導數趨近於零")
        x_new = x - fx / dx
        if abs(x_new - x) < eps and abs(f(x_new)) < eps:
            return x_new, k
        x = x_new
    return x, max_iter

# 例 1：求 x^3 - x - 2 = 0
f  = lambda x: x**3 - x - 2
df = lambda x: 3*x**2 - 1
root, n = newton(f, df, 2.0)
print(f"牛頓法根 ≈ {root:.12f}，迭代 {n} 次")

# 例 2：巴比倫法即牛頓法
sqrt2, n = newton(lambda x: x*x - 2, lambda x: 2*x, 1.0)
print(f"sqrt(2) ≈ {sqrt2:.15f}，迭代 {n} 次")

# 例 3：發散反例 f(x) = x^(1/3)（導數在 0 處無界/發散行為）
try:
    newton(lambda x: x**(1/3) if x else 0.0,
           lambda x: (1/3) * x**(-2/3) if x else float("inf"), 1.0, max_iter=20)
except OverflowError:
    print("例 3 發散：牛頓法不是萬能的")

複雜度與收斂性分析#

每步需一次 \(f\) 與一次 \(f'\) 的求值。達精度 \(\varepsilon\) 約需 \(\log_2 \log_2(1/\varepsilon) + O(1)\) 次迭代——從 \(10^0\) 到 \(10^{-16}\) 只要約 5 步。單重根平方收斂；多重根線性收斂（可用修正式 \(x_{k+1} = x_k - m\, f(x_k)/f'(x_k)\) ， \(m\) 為重數，恢復平方收斂）。缺點：需要導數（可用數值微分或自動微分補）、全域收斂無保證。與二分法的混合策略見 3.3 節。

練習#

1. 用牛頓法解 \(x = \cos x\) ，並解釋為何收斂階仍是平方（雖然 2.1 的形式不顯含導數）。
2. 推導「用牛頓法求 \(1/c\) 」的迭代式，寫程式驗證（過程中不得使用 /）。
3. 對 \(f(x) = (x-1)^2\) 執行牛頓法，實測收斂階；再實作重數修正版，比較迭代次數。