Newton’s method

Newton’s method approximates a root of f, a number r with $f(r) = 0$, by repeating one step. At the current guess $x_n$, take the tangent line to the graph at $(x_n, f(x_n))$, which is $L(x) = f(x_n) + f'(x_n)(x - x_n)$. Near $x_n$ the tangent stays close to the curve, so where it crosses the x-axis is a better guess for where the curve does. Solving $L(x) = 0$ gives the next guess. On the graph each step goes along the faint dashed line from $x_n$ to the curve, then along the tangent to the axis.

Write $e_n = x_n - r$ for the error. If r is a simple root ($f'(r) \ne 0$) and f has a continuous second derivative, a Taylor expansion of the step gives $e_{n+1} \approx \frac{f''(r)}{2f'(r)}\,e_n^2$ once $x_n$ is close to r. Squaring the error roughly doubles the number of correct digits. For x² − 2 from x₀ = 1 the errors are 0.086, 0.0025, 2.1 × 10⁻⁶ and 1.6 × 10⁻¹², and the readout shows $e_n/e_{n-1}^2$ settling near $1/(2\sqrt2) \approx 0.354$. Far from the root there is no such guarantee. Where $f''(r) = 0$ the squared term drops out and it is faster still: for arctan x the error is about $-\tfrac23 e_n^3$, cubed each step.

The step needs $f'(x_n) \ne 0$. A flat tangent never meets the axis, and a nearly flat one meets it far away: for x² − 2 from 0.1 the first step lands at 10.05. The method can also fail without running away. For x³ − 2x + 2 the tangent at 0 lands on 1 and the tangent at 1 lands back on 0, and starts near 0 are pulled into this loop: the sequence stays bounded but has no limit. For arctan x there is a boundary α ≈ 1.3917, the number with $2\alpha = (1 + \alpha^2)\arctan\alpha$. Starts with |x₀| < α converge, and starts beyond it land farther out on the other side each time. Every start colours the x-axis by where each start ends. For x³ − 2x + 2 about a fifth of [−3, 3] ends in the loop, including narrow bands that crowd toward the flat points $\pm\sqrt{2/3}$. Starting from complex numbers turns those bands into the Newton fractal.

At a multiple root $f'(r) = 0$ too, and the squaring is lost. For $(x - 1)^2$ the step is exactly $x_{n+1} = (x_n + 1)/2$, so the error halves every step. That is linear convergence, about 3.3 steps for each new decimal digit. Near a root of multiplicity m the ratio $e_{n+1}/e_n$ tends to $(m - 1)/m$.