Module

for

Halley's Method

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

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

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.

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004