The Newton-Raphson method

Summary

Bolzano’s theorem guarantees that a continuous function that changes sign has a root, and bisection locates it, gaining one binary digit per halving. This lesson studies a much faster procedure, when it works: the Newton-Raphson method, which replaces the graph by its tangent line and takes as the new approximation the point where the tangent crosses the axis. The approximations so obtained are defined one after another for the integers $n \geq 0$ , and their limit is understood through the definition of the limit as the variable tends to infinity, without the theory of sequences. The lesson proves, by means of convexity, that if the derivative does not vanish and the function is convex or concave, the iterates that start on the right side approach the root without passing it and converge to it; and, by means of the mean value theorem, that the value of the function, which is computed, bounds the distance to the root, which is not known. It then shows, with numerical examples, that the number of correct digits doubles at each iteration, and the ways in which the method fails: a zero derivative, a cycle, a divergence. The problems compute cube roots and reciprocals without division, break a cycle, study a double root and find the exact boundary between convergence and divergence for the arctangent.

Learning objectives

Compute the Newton-Raphson iterates of a differentiable function and recognize in them the point where the tangent line crosses the axis.
Prove the monotone convergence of the iterates when the derivative does not vanish and the function is convex or concave, and choose a starting point on the right side.
Bound the distance from an approximation to the root by means of the value of the function and a lower bound of its derivative.
Recognize the ways in which the method fails and compare it with bisection, in speed and in reliability.

The iteration

Let $f$ be a differentiable function whose root $r$ is sought, and let $x_0$ be a first approximation. Near $x_0$ , the graph of $f$ resembles its tangent line, $y = f(x_0) + f'(x_0)(x - x_0)$ , according to the definition of the tangent line in the lesson on the derivative as a limit; put in terms of the differential from the lesson on higher-order derivatives and the differential, the increment $f(x_0 + \Delta x) - f(x_0)$ resembles $f'(x_0) \Delta x$ . The tangent crosses the axis at a single point if $f'(x_0) \neq 0$ , and it is natural to take that point as the new approximation: it is obtained by setting the equation of the tangent equal to zero. Repeating the procedure from the point obtained is the Newton-Raphson method.

DefinitionNewton-Raphson iterates

Let $f$ be a function differentiable on an interval $I$ and $x_0$ a point of $I$ . The Newton-Raphson iterates starting from $x_0$ are the numbers defined, one after another, by

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

as long as $x_n$ is in $I$ and $f'(x_n) \neq 0$ . If these conditions hold for every integer $n \geq 0$ , the iterates form a function $n \mapsto x_n$ defined on the set of nonnegative integers, which is not bounded above, and the definition of the limit as the variable tends to infinity, from the lesson on limits as the variable tends to infinity, applies to it. The iterates are said to converge to $r$ if $\lim_{n \to \infty} x_n = r$ , that is, if

(\forall \varepsilon > 0)(\exists M)(\forall n \geq 0)\left(n > M \rightarrow \abs{x_n - r} < \varepsilon\right)

Each iterate is the point where the tangent at $(x_n, f(x_n))$ crosses the axis: setting $y = 0$ and $x = x_{n+1}$ in the equation $y = f(x_n) + f'(x_n)(x - x_n)$ and solving yields the formula of the definition. The method does not require the function to change sign on a given interval, as bisection does, but to be differentiable and to have a derivative that does not vanish at the points it passes through; in exchange, nothing guarantees in advance that the iterates approach a root. Conditions that guarantee it are given below.

ExampleThe square root of 2

Apply the Newton-Raphson method to $f(x) = x^2 - 2$ from $x_0 = 2$ . The calculation below shows the first three tangents and the points where they cross the axis.

Proof

$x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right), \qquad \resaltar{x_1 = \frac{3}{2}}$
The derivative is $f'(x) = 2x$ , which does not vanish if $x > 0$ . The iteration takes the following form: each approximation is the average of the one before it and of $2$ divided by it. From $x_0 = 2$ , the tangent $y = 2 + 4(x - 2)$ crosses the axis at $\frac{3}{2}$ .
$x_2 = \frac{1}{2}\left(\frac{3}{2} + \frac{4}{3}\right) = \resaltar{\frac{17}{12}} \approx 1.416667$
The tangent at $\left(\frac{3}{2}, \frac{1}{4}\right)$ crosses the axis much closer to the root.
$x_3 = \frac{1}{2}\left(\frac{17}{12} + \frac{24}{17}\right) = \resaltar{\frac{577}{408}} \approx 1.4142157, \qquad \sqrt{2} \approx 1.4142136$
The third iterate already has five correct decimal places. The errors, $x_n - \sqrt{2}$ , are about $0.59$ , $0.086$ , $0.0025$ and $0.0000021$ : each is of the order of the square of the one before.

The error in this example is squared exactly. From the formula of the iteration one obtains, for every $x_n > 0$ , the following identity:

x_{n+1} - \sqrt{2} = \frac{x_n^2 - 2\sqrt{2}\,x_n + 2}{2x_n} = \frac{\left(x_n - \sqrt{2}\right)^2}{2x_n}

Therefore, all the iterates from the first on are greater than or equal to $\sqrt{2}$ , and if $x_n \geq 1$ , the new error is at most half the square of the current error: the fourth iterate, $x_4 = \frac{665\,857}{470\,832}$ , has eleven correct decimal places. With $2$ replaced by any positive number, the same procedure computes square roots; it already appears in the Metrica of Heron of Alexandria, in the 1st century, and for this reason it is also called Heron’s method.

Isaac Newton described his method for polynomial equations in 1669, in a paper that circulated in manuscript and was published in 1711; Joseph Raphson published a simpler exposition in 1690, and Thomas Simpson presented it in 1740 as an iterative method for general equations.