牛顿法

牛顿法用来逼近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轴的交点，比$x_n$更接近曲线和x轴的交点。解$L(x) = 0$就得到下一个猜测值。图上的每一步，先沿淡虚线从$x_n$走到曲线上，再沿切线走到x轴。

记误差$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轴不相交，几乎水平的切线交得很远：x² − 2从0.1出发，第一步落在10.05。牛顿法失败时也不一定越跳越远。x³ − 2x + 2在0处的切线落在1，在1处的切线又落回0，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$。