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 .

    Use the Taylor polynomial of degree  n=2  for  f(x)  expanded about  :

(1)            ,  

where    lies somewhere between    and  x.  Since  f(p) = 0  and  ,  truncate this formula to the second term and obtain the approximation:

(2)            

This can be rearranged in the form:

(3)            .

Since we want to iteratively solve for the root, replace  p  with    and    with  =   in (3) and then solve for    and obtain the Newton-Raphson iteration formula:

(4)            .  

Q. E. D.

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

    The Newton-Raphson iteration function is

(5)        .

Halley's Method

    It is possible to speed up convergence significantly when the root is simple.  A popular method is known as Halley's method uses the iteration function:  
    

(6)         ,

The term in brackets in (6) shows where formula (5) is modified to yield (6).    

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.

Use the Taylor polynomial of degree  n=3  for  f(x)  expanded about  :

(7)        ,  

where    lies somewhere between    and  x.  Since  f(p) = 0  and  ,  truncate this formula to the third term and obtain the approximation:

(8)        .

This equation is non-linear in the unknown p.  Use the substitution in the bracketed term in (8).   The result is:

(9)        .

Then replace the    with  =   and  p  with    in (9) and get:

(10)        ,

Now solve for    and obtain the Halley iteration formula:

(11)        .  

Q. E. D.

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004