Newton's method

To solve $f(x) = 0$, replace $f$ by its tangent line at the current guess and jump to where the tangent hits zero: $x_{k+1} = x_k - f(x_k)/f'(x_k)$. Near a simple root the number of correct digits doubles every step.

Equations like $\cos x = x$ or $x e^x = 3$ have no formula for their solution, and nonlinear systems in engineering have thousands of unknowns. Newton's insight: we cannot solve $f = 0$, but we can solve its linear approximation exactly — and repeat.

Stand on the curve at $(x_k, f(x_k))$, slide down the tangent until you hit the $x$-axis, step up to the curve again. If the curve is close to straight near the root, each tangent lands very close. The step $-f/f'$ is "how far, at the current slope, until I reach zero". It fails when the slope is nearly flat (huge jumps) or when the start is in the wrong basin.

Theorem (local quadratic convergence). Let $f \in C^2$ near a root $x^\ast$ with $f'(x^\ast) \ne 0$. Then there is $\delta > 0$ such that for every $x_0$ with $|x_0 - x^\ast| < \delta$ the iterates converge to $x^\ast$ and

Taylor at $x_k$: $0 = f(x^\ast) = f(x_k) + f'(x_k)(x^\ast - x_k) + \tfrac12 f''(\xi)(x^\ast - x_k)^2$. Divide by $f'(x_k)$ and use the definition of $x_{k+1}$: $x_{k+1} - x^\ast = \frac{f''(\xi)}{2f'(x_k)}(x_k - x^\ast)^2$.

x = x0
repeat:
    step = f(x) / df(x)
    x = x - step
until |step| < tol·|x|  or  too many iterations

In practice add safeguards: fall back to bisection if the step leaves a bracketing interval, and damp the step ($x - \alpha\,f/f'$) far from the root.

$\sqrt 2$ as the root of $x^2 - 2$: $x_{k+1} = \frac12\left(x_k + \frac{2}{x_k}\right)$ — the Babylonian method, 4000 years old. From $x_0 = 1$: $1.5$, $1.41667$, $1.4142157$, $1.41421356237469$, … The correct digits go 1, 3, 6, 12: doubling each step.

Newton's method is inside your CPU (division and square roots refine an initial approximation by Newton steps), inside every nonlinear solver of engineering software, inside implicit physics integrators and inverse kinematics, and — applied to $\nabla f = 0$ — it is the prototype of all second-order optimization methods.