STEP 10

NONLINEAR EQUATIONS 5

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.