Halley's Method

Theorem (Convergence Rate for Newton-Raphson Iteration)

Assume that Newton-Raphson iteration produces a sequence that converges to the rootpof the function.

Ifpis a simple root, then convergence is quadratic andforksufficiently large.

Ifpis a multiple root of orderm,then convergence is linear andforksufficiently 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, thenwill have order of convergence,i.e..

Square Roots

The function wherecan 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.