### The Newton-Raphson iterative method

The Newton-Raphson method is suitable for implementation on a computer; cf. its pseudo-code). It is a process for the determination of a real root of an equation f (x) = 0, given just one point close to the desired root. It can be viewed as a limiting case of the secant method (Step 8) or as a special case of the method of simple iteration ( Step 9).

1. ### Procedure

Let x0 denote the known approximate value of the root of f(x) = 0 and h the difference between the true value and the approximate value, i.e.,

The second degree terminated Taylor expansion (cf. STEP 5) about x0 is

where lies between

Ignoring the remainder term and writing

whence

and, consequently,

should be a better estimate of the root than x0. Even better approximations may be obtained by repetition (iteration) of the process, which then becomes

Note that if f is a polynomial, we can use the recursive procedure of STEP 5 to compute

The geometrical interpretation is that each iteration provides the point at which the tangent at the original point cuts the x-axis (see Figure 9). Thus the equation of the tangent at (xn, f (xn)) is

so that (xn+1, 0) corresponds to

whence

Figure 9. Newton-Raphson method

2. ### Example

We will use the Newton-Raphson method to find the positive root of the equation sinx = x2, correct to 3D.

It will be convenient to use the method of false position to obtain an initial approximation. Tabulating, one finds

With numbers displayed to 4D, we see that there is a root in the interval 0.75 < x < 1 at approximately

Next, we will use the Newton-Raphson method; we have

and

yielding

Consequently, a better approximation is

Repeating this step, we obtain

and

so that

Since f(x2) = 0.0000, we conclude that the root is 0.877 to 3D.

3. ### Convergence

If we write

the Newton-Raphson iteration expression

may be written

We observed (see STEP 9) that, in general, the iteration method converges when near the root. In the case of Newton-Raphson, we have

so that the criterion for convergence is

,

i.e., convergence is not as assured as for the bisection method (say).

4. ### Rate of convergence

The second degree terminated Taylor expansion about xn is

where is the error at the n-th iteration and .

Since , we find

But, by the Newton-Raphson formula,

whence the error at the (n + 1)-th iteration is

provided en is sufficiently small. This result states that the error at the n + 1-th iteration is proportional to the square of the error at the nth iteration; hence, if , an answer correct to one decimal place at one iteration should be accurate to two places at the next iteration, four at the next, eight at the next, etc. This quadratic (second-order) convergence outstrips the rate of convergence of the methods of bisection and false position!

In relatively little used computer programs, it may be wise to prefer the methods of bisection or false position, since convergence is virtually assured. However, for hand calculations or for computer routines in constant use, the Newton-Raphson method is usually preferred.

5. ### The square root

One application of the Newton-Raphson method is in the computation of square roots. Since is equivalent to finding the positive root of x2 = a. i.e.,

Since , we have the Newton-Raphson iteration formula:

,

a formula known to the ancient Greeks. Thus, if a = 16 and x0 = 5, we find to 4D x1 = (5 + 3.2)/2 = 4.1, x2 = (4.1 + 3.9022)/2 = 4.0012, and x3 = (4.0012 + 3.9988)/2 = 4.0000.

### Checkpoint

1. What is the geometrical interpretation of the Newton-Raphson iter- ative procedure?
2. What is the convergence criterion for the Newton-Raphson method?
3. What major advantage has the Newton-Raphson method over some other methods?

### EXERCISES

1. Use the Newton-Raphson method to find to 4S the (positive) root of
2. Derive the Newton-Raphson iteration formula

for finding the k-th root of a.

3. Use the formula

to compute to 5S the square root of 10, using the initial guess 1.

4. Use the Newton-Raphson method to find to 4D the root of the equation

.

5. Use the Newton-Raphson method to find to 4D the root of each equation in the exercises 2.1 - 2.3.