牛頓法

牛頓法反覆執行一個步驟，逼近f的根，也就是滿足$f(r) = 0$的數r。在目前的猜測值$x_n$處，取曲線上$(x_n, f(x_n))$這一點的切線，其方程式為$L(x) = f(x_n) + f'(x_n)(x - x_n)$。在$x_n$附近，切線貼近曲線，因此切線與x軸的交點，是曲線交點的更好猜測。解$L(x) = 0$就得到下一個猜測值。圖上的每一步先沿淡虛線，從$x_n$走到曲線，再沿切線走向軸。

將誤差寫成$e_n = x_n - r$。若r是單根（$f'(r) \ne 0$），而且f有連續的二階導函數，對步驟做泰勒展開可知，當$x_n$接近r時有$e_{n+1} \approx \frac{f''(r)}{2f'(r)}\,e_n^2$。誤差平方大致會讓正確位數加倍。對x² − 2，從x₀ = 1開始，誤差為0.086、0.0025、2.1 × 10⁻⁶和1.6 × 10⁻¹²；讀數顯示$e_n/e_{n-1}^2$逐漸接近$1/(2\sqrt2) \approx 0.354$。遠離根時就沒有這項保證。若$f''(r) = 0$，平方項消失，收斂更快：對arctan x，下一個誤差約為$-\tfrac23 e_n^3$，每一步變成立方。

這個步驟需要$f'(x_n) \ne 0$。水平切線不與軸相交，幾乎水平的切線則在遠處相交：x² − 2從0.1出發，第一步落在10.05。方法也可能不往遠處逃，卻仍然失敗。對x³ − 2x + 2，0處的切線落在1，1處的切線又落回0，附近的起點也被拉進此循環：數列有界，卻沒有極限。對arctan x，有一道界線α ≈ 1.3917，它滿足$2\alpha = (1 + \alpha^2)\arctan\alpha$。|x₀| < α的起點收斂，超過界線的則每次落到另一側更遠處。「所有起點」依各起點的去向為x軸上色。對x³ − 2x + 2，[−3, 3]約五分之一落入循環，包括聚集在切線水平點$\pm\sqrt{2/3}$附近的細帶。起點改用複數時，這些帶就形成牛頓分形。

重根處也有$f'(r) = 0$，誤差平方的效果便消失了。對$(x - 1)^2$，步驟恰好是$x_{n+1} = (x_n + 1)/2$，所以誤差每一步減半。這是一次收斂，每多一位正確小數約需3.3步。接近m重根時，比值$e_{n+1}/e_n$趨近$(m - 1)/m$。