Halley's Method

Also known as the Tangent Hyperbolas Method or Halley's Rational Formula. As in Halley's Irrational Formula, take the second-order Taylor Polynomial

$\begin{displaymath} f(x)=f(x_n)+f'(x_n)(x-x_n)+{\textstyle{1\over 2}}f''(x_n)(x-x_n)^2+\ldots. \end{displaymath}$

(1)

A Root of

satisfies

, so

$\begin{displaymath} 0\approx f(x_n)+f'(x_n)(x_{n+1}-x_n)+{\textstyle{1\over 2}}f''(x_n)(x_{n+1}-x_n)^2. \end{displaymath}$

(2)

Now write

$\begin{displaymath} 0=f(x_n)+(x_{n+1}-x_n)[f'(x_n)+{\textstyle{1\over 2}}f''(x_n)(x_{n+1}-x_n)], \end{displaymath}$

(3)

giving

$\begin{displaymath} x_{n+1}=x_n-{f(x_n)\over f'(x_n)+{\textstyle{1\over 2}}f''(x_n)(x_{n+1}-x_n)}. \end{displaymath}$

(4)

Using the result from Newton's Method,

$\begin{displaymath} x_{n+1}-x_n=-{f(x_n)\over f'(x_n)}, \end{displaymath}$

(5)

gives

$\begin{displaymath} x_{n+1}=x_n-{2f(x_n)f'(x_n)\over 2[f'(x_n)]^2-f(x_n)f''(x_n)}, \end{displaymath}$

(6)

so the iteration function is

$\begin{displaymath} H_f(x)=x-{2f(x)f'(x)\over 2[f'(x)]^2-f(x)f''(x)}. \end{displaymath}$

(7)

This satisfies $H_f'(\alpha)=H_f''(\alpha)=0$ where $\alpha$ is a Root, so it is third order for simple zeros. Curiously, the third derivative

$\begin{displaymath} H_f'''(\alpha)=-\left\{{{f'''(\alpha)\over f'(\alpha)}-{3\over 2}\left[{f''(\alpha)\over f'(\alpha)}\right]^2}\right\} \end{displaymath}$

(8)

is the Schwarzian Derivative. Halley's method may also be derived by applying Newton's Method to $f f'^{-1/2}$ . It may also be derived by using an Osculating Curve of the form

$\begin{displaymath} y(x)={(x-x_n)+c\over a(x-x_n)+b}. \end{displaymath}$

(9)

Taking derivatives,

$\displaystyle f(x_n)$	$\textstyle =$	$\displaystyle {c\over b}$	(10)
$\displaystyle f'(x_n)$	$\textstyle =$	$\displaystyle {b-ac\over b^2}$	(11)
$\displaystyle f''(x_n)$	$\textstyle =$	$\displaystyle {2a(ac-b)\over b^3},$	(12)

which has solutions

$\displaystyle a$	$\textstyle =$	$\displaystyle -{f''(x_n)\over 2[f'(x_n)]^2-f(x_n)f''(x_n)}$	(13)
$\displaystyle b$	$\textstyle =$	$\displaystyle {2f'(x_n)\over 2[f'(x_n)]^2-f(x_n)f''(x_n)}$	(14)
$\displaystyle c$	$\textstyle =$	$\displaystyle {2f(x_n)f'(x_n)\over 2[f'(x_n)]^2-f(x_n)f''(x_n)},$	(15)

so at a Root, $y(x_{n+1})=0$ and

$\begin{displaymath} x_{n+1}=x_n-c, \end{displaymath}$

(16)

which is Halley's method.

References

Scavo, T. R. and Thoo, J. B. ``On the Geometry of Halley's Method.'' Amer. Math. Monthly 102, 417-426, 1995.