Background

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

    .  

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

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

Theorem (Newton-Raphson Iteration).  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  .  

Furthermore, if   is a simple root, then    will have order of convergence  ,  i.e.  .

Proof  Newton-Raphson Method  Newton-Raphson Method  

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.

Halley's Method


    The Newton-Raphson iteration function is

(1)        .
        
    It is possible to speed up convergence significantly when the root is simple.  A popular method is attributed to Edmond Halley (1656-1742) and uses the iteration function:  
    
(2)         ,

The term in brackets shows where Newton-Raphson iteration function is changed.

Theorem (Halley's Iteration).  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  .  

Furthermore, if   is a simple root, then    will have order of convergence  ,  i.e.  .

Proof  Halley's Method  Halley's Method  

Square Roots

    The function   where    can be used with (1) and (2) to produce iteration formulas for finding  .  If it is used in (1), the result is the familiar Newton-Raphson formula for finding square roots:

(3)            .

When it is used in (2) the resulting Halley formula is:

              
(4)            or
              

This latter formula is a third-order method for computing  .  Because of the rapid convergence of the sequences generated by (3) and (4), the iteration usually converges to machine accuracy in a few iterations.  Multiple precision arithmetic is needed to demonstrate the distinction between second and third order convergence.  The software Mathematica has extended precision arithmetic which is useful for exploring these ideas.

Computer Programs  Halley's Method  Halley's Method  

Example 1.  Consider the function  , which has a root at  .   
1 (a).  Use the Newton-Raphson formula to find the root.      Use the starting value  
1 (b).  Use Halley's formula to find the root.      Use the starting value  
Solution 1 (a).
Solution 1 (b).

Example 2.  Consider the function  , which has a root at  .   
2 (a).  Use the Newton-Raphson formula to find the root.    Use the starting value  
2 (b).  Use Halley's formula to find the root.    Use the starting value  
Solution 2 (a).
Solution 2 (b).

Research Experience for Undergraduates

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

Halley's Method  Halley's Method  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Halley's Method

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004