TOPICS
Search

Halley's Irrational Formula


A root-finding algorithm which makes use of a third-order Taylor series

 f(x)=f(x_n)+f^'(x_n)(x-x_n)+1/2f^('')(x_n)(x-x_n)^2+....
(1)

A root of f(x) satisfies f(x)=0, so

 0 approx f(x_n)+f^'(x_n)(x_(n+1)-x_n)+1/2f^('')(x_n)(x_(n+1)-x_n)^2.
(2)

Using the quadratic equation then gives

 x_(n+1)=x_n+(-f^'(x_n)+/-sqrt([f^'(x_n)]^2-2f(x_n)f^('')(x_n)))/(f^('')(x_n)).
(3)

Picking the plus sign gives the iteration function

 C_f(x)=x-(1-sqrt(1-(2f(x)f^('')(x))/([f^'(x)]^2)))/((f^('')(x))/(f^'(x))).
(4)

This equation can be used as a starting point for deriving Halley's method.

If the alternate form of the quadratic equation is used instead in solving (◇), the iteration function becomes instead

 C_f(x)=x-(2f(x))/(f^'(x)+/-sqrt([f^'(x)]^2-2f(x)f^('')(x))).
(5)

This form can also be derived by setting n=2 in Laguerre's method. Numerically, the sign in the denominator is chosen to maximize its absolute value. Note that in the above equation, if f^('')(x)=0, then Newton's method is recovered. This form of Halley's irrational formula has cubic convergence, and is usually found to be substantially more stable than Newton's method. However, it does run into difficulty when both f(x) and f^'(x) or f^'(x) and f^('')(x) are simultaneously near zero.


See also

Halley's Method, Householder's Method, Laguerre's Method, Newton's Method

Explore with Wolfram|Alpha

References

Gourdon, X. and Sebah, P. "Newton's Iteration." http://numbers.computation.free.fr/Constants/Algorithms/newton.html.Ortega, J. M. and Rheinboldt, W. C. Iterative Solution of Nonlinear Equations in Several Variables. Philadelphia, PA: SIAM, 2000.Qiu, H. "A Robust Examination of the Newton-Raphson Method with Strong Global Convergence Properties." Master's Thesis. University of Central Florida, 1993.Scavo, T. R. and Thoo, J. B. "On the Geometry of Halley's Method." Amer. Math. Monthly 102, 417-426, 1995.

Referenced on Wolfram|Alpha

Halley's Irrational Formula

Cite this as:

Weisstein, Eric W. "Halley's Irrational Formula." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HalleysIrrationalFormula.html

Subject classifications