Introduction

    Newton's method is used to locate roots of the equation  .  The Newton-Raphson iteration formula is:
(1)        

Given a starting value  ,   the sequence    is computed using:  

(2)            for    

provided that  .  

Computer Programs  Newton-Raphson Method  Newton-Raphson Method  

Mathematica Subroutine (Newton-Raphson Iteration).

    If the value    is chosen close enough to the root p, then the sequence generated in (2) will converge to the root p.  Sometimes the speed at which    converges is fast (quadratic) and at other times it is slow (linear).  To distinguish these two cases we make the following definitions.

Definition 1 (Order of Convergence)  Assume that   converges to  p,  and set  .    If two positive constants    exist, and  

    

then the sequence is said to converge to  p  with order of convergence R.  The number  A  is called the asymptotic error constant.  The cases    are given special  consideration.

(3)      If  , and      

       then the convergence of    is called quadratic.

(4)       If  , and      

       then the convergence of    is called linear.

The mathematical characteristic for determining which case occurs is the "multiplicity" of the root p.

Definition 2 (Order of a Root)  If    can be factored as

(5)            where  m  is a positive integer,

and    is continuous at    and  ,  then we say that    has a root of order  m  at  .

A root of order    is often called a simple root, and if    it is called a multiple root.  A root of order    is sometimes called a double root, and so on.  

Theorem 1 (Convergence Rate for Newton-Raphson Iteration)  Assume that Newton-Raphson iteration (2) produces a sequence   that converges to the root  p  of the function  .  

(6)        If  p  is a simple root, then convergence is quadratic and   

          for  k  sufficiently large.

(7)        If  p  is a multiple root of order  m,  then convergence is linear and  
        
          for  k  sufficiently large.

Proof  Newton-Raphson Method  Newton-Raphson Method  

    There are two common ways to use Theorem 1 and gain quadratic convergence at multiple roots. We shall call these methods A and B (see Mathews, 1987, p. 72 and Ralston & Rabinowitz, 1978, pp. 353-356).  

Method A.  Accelerated Newton-Raphson

    Suppose that  p  is a root of order   .  Then the accelerated Newton-Raphson formula is:  

(8)        .  
    
Let the starting value    be close to  p, and compute the sequence    iteratively;  

(9)            for      

Then the sequence generated by (9) will converge quadratically to  p.  

Proof  Accelerated & Modified Newton-Raphson  Accelerated & Modified Newton-Raphson  

Computer Programs  Accelerated & Modified Newton-Raphson  Accelerated & Modified Newton-Raphson  

Mathematica Subroutine (Accelerated Newton-Raphson Iteration).

    On the other hand, if    then one can show that the function    has a simple root at  .  
Derivation

    Using    in place of    in formula (1) yields Method B.

Method B.  Modified Newton-Raphson

    Suppose that  p  is a root of order   .  Then the modified Newton-Raphson formula is:  
    
(10)          

Derivation

Let the starting value    be close to  p, and compute the sequence    iteratively;  

(11)            for      

Then the sequence generated by (11) converges quadratically to  p.  

Proof  Accelerated & Modified Newton-Raphson  Accelerated & Modified Newton-Raphson  

Computer Programs  Accelerated & Modified Newton-Raphson  Accelerated & Modified Newton-Raphson  

Mathematica Subroutine (Modified Newton-Raphson Iteration).

Limitations of Methods A and B

    Method A has the disadvantage that the order  m  of the root must be known a priori.  Determining  m  is often laborious because some type of mathematical analysis must be used.  It is usually found by looking at the values of the higher derivatives of  .  That is,    has a root of order  m  at    if and only if  

(12)        .
    
Dodes (1978, pp. 81-82) has observed that in practical problems it is unlikely that we will know the multiplicity.  However, a constant  m  should be used in (8) to speed up convergence, and it should be chosen small enough so that     does not shoot to the wrong side of  p.  Rice (1983, pp. 232-233) has suggested a way to empirically find  m.  If    is a good approximation to  p  and , and somewhat distant from    then  m  can be determined by the calculation:

        .  

    Method B has a disadvantage, it involves three functions  .  Again, the laborious task of finding the formula for    could detract from using Method B.  Furthermore, Ralston and Rabinowitz (1978, pp. 353-356) have observed that    will have poles at points where the zeros of    are not roots of .  Hence,    may not be a continuous function.

The New Method C.  Adaptive Newton-Raphson

    The adaptive Newton-Raphson method incorporates a linear search method with formula (8).  Starting with  ,  the following values are computed:  

(13)            for    .  

Our task is to determine the value  m  to use in formula (13), because it is not known a priori.  First, we take the derivative of    in formula (5), and obtain:  

(14)          

When (5) and (14) are substituted into formula (1) we have    which can be simplified to get  

        .

This enables us to rewrite (13) as  

(15)        .  

    We shall assume that the starting value    is close enough to  p  so that  

(16)        ,    where    .  

The iterates    in (15) satisfy the following:  

(17)            for         

If we subtract  p  from both sides of (17) then  

        

and the result after simplification is:  

(18)        .  

Since  ,  the iterates    get closer to  p  as  j  goes from  ,  which is manifest by the inequalities:

(19)        .  

The values    are shown in Figure 1.  

    Notice that if the iteration (15) was continued for    then    could be larger than  .  This is proven by using the derivatives in (12) and the Taylor polynomial approximation of degree  m  for     expanded about  :  

(20)        .  

Figure 1.     The values    for the "linear search" obtained by using formula (15)  
                   near a "double root"  p  (of order  ).   Notice that  .  

If    is closer to  p  than    then (19) and (20) imply that  ,   hence we have:  

(21)        .  

Therefore, the way to computationally determine  m  is to successively compute the values    using formula (13) for    until we arrive at  .

The New Adaptive Newton-Raphson Algorithm

Start with  ,  then we determine the next approximation as follows:  

            

    Observe that the above iteration involves a linear search in either the interval    when    or in the interval     when  .   In the algorithm, the value    is stored so that unnecessary computations are avoided.  After the point    has been found, it should replace    and the process is repeated.  

Mathematica Subroutine (Adaptive Newton-Raphson Iteration).

Example 1.  Use the value    and compare Methods A,B and C for finding the double root    of the equation  .
Solution 1.

Behavior at a Triple Root

    When the function has a triple root, then one more iteration for the linear search in (13) is necessary.  The situation is shown in Figure 2.

Figure 2.  The values    for the "linear search" obtained by using formula (15)  
                   near a "triple root"  p  (of order  ).   Notice that  .  

Example 2.  Use the value    and compare Methods A,B and C for finding the triple root    of the equation  .
Solution 2.

Example 3.  Use the value    and compare Methods A,B and C for finding the quadruple root    of the equation  .
Solution 3.

Acknowledgement

    This module uses Mathematica instead of Pascal, and the content is that of the article:

John Mathews, An Improved Newton's Method, The AMATYC Review, Vol. 10, No. 2, Spring, 1989, pp. 9-14.

References

1.  Dodes, 1. A.,  Numerical analysis for computer science, 1978, New York: North-Holland.
2.  Mathews, J. H.,  Numerical methods for computer science, engineering and mathematics, 1987, Englewood Cliffs, NJ: Prentice-Hall.
3.  Ralston, A. & Rabinowitz, P.,  A first course in numerical analysis, second ed., 1978, New York: McGraw-Hill.
4.  Rice, J. R.,  Numerical methods, software and analysis: IMSL reference edition, 1983, New York: McGraw-Hill.

Related Material

Animations ( Newton's Method  Newton's Method ).  

Research Experience for Undergraduates

Newton-Raphson Method  Newton-Raphson Method  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook The Improved Newton Method

(c) John H. Mathews 2004