Newton's method

Following tangents to find the solution of an equation numerically is Newton's method¹. We use it to find the positive root of $f(x) = x^2 - 2$ , that is $\sqrt{2}$ .

Following the tangents

Start from $x_0 = 2$ . Since $f(2) = 2$ and $f'(2) = 4$ , the tangent at $(2, 2)$ is $y = 4x - 6$ . It meets the $x$ -axis at $x = 1.5$ , and that becomes the next value $x_1$ .

Repeat. Since $f(1.5) = 0.25$ and $f'(1.5) = 3$ , the tangent is $y = 3x - \dfrac{17}{4}$ , meeting the $x$ -axis at $x_2 = \dfrac{17}{12} = 1.41667$ .

The general formula

Find where the tangent $y = f(x_n) + f'(x_n)(x - x_n)$ meets the $x$ -axis.

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

For $f(x) = x^2 - 2$ this tidies up as follows.

\begin{align*} x_{n+1} &= x_n - \frac{x_n^2 - 2}{2x_n} \\ &= \frac{1}{2}\left(x_n + \frac{2}{x_n}\right) \end{align*}

It takes the average of the current value and $\dfrac{2}{x_n}$ . If $x_n$ is larger than $\sqrt{2}$ then $\dfrac{2}{x_n}$ is smaller, so the average always lands between them.

How fast it converges

$n$	$x_n$	Error
$0$	$2$	$0.586$
$1$	$1.5$	$0.086$
$2$	$1.416667$	$0.0025$
$3$	$1.414216$	$0.000002$

Against $\sqrt{2} = 1.414214$ , the number of correct digits roughly doubles at each step.

When it fails

If $f'(x_n) = 0$ the tangent is horizontal and the next value is undefined
If the starting value is far from a root, the iteration may jump to a different one
The values may also oscillate and never settle

What the method really is

That a tangent is the linear approximation of a curve is the substance of the method. The curve is replaced by a line and solved, and at the answer obtained the replacement is made again. That is all it repeats.

The parabola on the graph is $y = x^2 - 2$ , the two lines are the tangents at $x_0 = 2$ and $x_1 = 1.5$ , and the large dots are the points of tangency together with the points where the tangents cut the $x$ -axis.

Newton's method, Wikipedia