Background

    Newton's method is commonly used to find the root of an equation.  If the root is simple then the extension to Halley's method will increase the order of convergence from quadratic to cubic.  At a multiple root it can be speed up with the accelerated Newton-Raphson and modified Newton-Raphson methods.  
    
Theorem (Newton-Raphson Theorem).  Assume that and there exists a number , where .  If   , then there exists a such that the sequence defined by the iteration  

        for      

will converge to for any initial approximation  .  

Proof  Newton-Raphson Method  Newton-Raphson Method  

Definition (Order of a Root)  Assume that  f(x)  and its derivatives    are defined and continuous on an interval about  x = p.  We say that  f(x) = 0  has a root of order  m  at   x = p  if and only if  

    .  

A root of order  m = 1  is often called a simple root, and if  m > 1  it is called a multiple root.  A root of order  m = 2  is sometimes called a double root, and so on.  The next result will illuminate these concepts.

Definition (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.

(i)   If  , the convergence of    is called linear.

(ii)  If  , the convergence of    is called quadratic.

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

If  p  is a simple root, then convergence is quadratic and    for  k  sufficiently large.

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  

Algorithm (Newton-Raphson Iteration).  To find a root of    given an initial approximation    using the iteration  

       for    .

Computer Programs  Newton-Raphson Method  Newton-Raphson Method  

Mathematica Subroutine (Newton-Raphson Iteration).

Example 1.  Use Newton's method to find the roots of the cubic polynomial  .  
1 (a) Fast Convergence.  Investigate quadratic convergence at the simple root  ,  using the starting value  
1 (b) Slow Convergence.  Investigate linear convergence at the double root  ,  using the starting value  
Solution 1 (a).
Solution 1 (b).

Theorem (Acceleration of Newton-Raphson Iteration)  Given that the Newton-Raphson algorithm produces a sequence that converges linearly to the root    of order   .  Then the accelerated Newton-Raphson formula

        for      

will produce a sequence that 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 (Accelerated Newton-Raphson Iteration).

Example 2.  Use the accelerated Newton's method to find the double root  ,  of the cubic polynomial  .  Use the starting value  
Solution 2.

Example 3.  Use the accelerated Newton's method to find the double root  ,  and triple root   ,  of the cubic polynomial  .  
Solution 3.

More Background

    If  f(x)  has a root of multiplicity   m   at  x=p  , then  f(x)  can be expressed in the form
     
         

where  .  In this situation, the function  h(x)  is defined by

        

and it is easy to prove that  h(x)  has a simple root at  x=p.  When Newton's method is applied for finding the root  x=p  of  h(x)  we obtain the following result.

Theorem (Modified Newton-Raphson Iteration)  Given that the Newton-Raphson algorithm produces a sequence that converges linearly to the root    of multiplicity   .  Then the modified Newton-Raphson formula

         
    
which can be simplified as

        for      

will produce a sequence that 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).

Example 4.  Use the modified Newton's method to find the double root  ,  of the cubic polynomial  .  Use the starting value  
Solution 4.

Example 5.  Use the modified Newton's method to find the double root  ,  and triple root   ,  of the cubic polynomial  .  
Solution 5.

Example 6.  Consider the function  .  
6 (a).  Use Newton's method to find the multiple root  .  
6 (b).  Use the accelerated Newton's method to find the multiple root  .  
6 (c).  Use the modified Newton's method to find the multiple root  .  
Solution 6 (a).
Solution 6 (b).
Solution 6 (c).

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

Old Lab Project ( 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 Accelerated and Modified Newton Methods  

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004