info prev up next book cdrom email home

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

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 $f(x)$ satisfies $f(x)=0$, so
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
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)

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,
x_{n+1}-x_n=-{f(x_n)\over f'(x_n)},
\end{displaymath} (5)

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
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
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
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
\end{displaymath} (16)

which is Halley's method.

See also Halley's Irrational Formula, Laguerre's Method, Newton's Method


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

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein