Derive Newton-Raphson formula

The Newton-Raphson method finds a root of f(x) = 0 by repeatedly replacing the curve by its tangent line.

Derivation (Taylor series)

Let x0 be an approximation to the root and let the exact root be x0 + h, where h is a small correction. Then f(x0 + h) = 0. Expand by Taylor's series:

f(x0 + h) = f(x0) + h f'(x0) + (h²/2!) f''(x0) + ... = 0

Since h is small, neglect h² and higher powers:

f(x0) + h f'(x0) ≈ 0
h = − f(x0) / f'(x0)

The improved approximation is x1 = x0 + h, so

x1 = x0 − f(x0) / f'(x0)

Repeating the process gives the general formula:

x(n+1) = x(n) − f(x(n)) / f'(x(n)),     n = 0, 1, 2, ...

with f′(x(n)) ≠ 0. Iteration stops when |x(n+1) − x(n)| is less than the required tolerance.

Geometrical meaning

The tangent to y = f(x) at the point (x(n), f(x(n))) cuts the x-axis at x(n+1). The slope of the tangent is f′(x(n)) = f(x(n)) / (x(n) − x(n+1)), which gives the same formula.

The method has quadratic convergence: the error in each step is roughly the square of the error in the previous step.