TOPICS
Search

Halley's Method


A root-finding algorithm also known as the tangent hyperbolas method or Halley's rational formula. As in Halley's irrational formula, take the second-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)

Now write

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

giving

 x_(n+1)=x_n-(f(x_n))/(f^'(x_n)+1/2f^('')(x_n)(x_(n+1)-x_n)).
(4)

Using the result from Newton's method,

 x_(n+1)-x_n=-(f(x_n))/(f^'(x_n)),
(5)

gives

 x_(n+1)=x_n-(2f(x_n)f^'(x_n))/(2[f^'(x_n)]^2-f(x_n)f^('')(x_n)),
(6)

so the iteration function is

 H_f(x)=x-(2f(x)f^'(x))/(2[f^'(x)]^2-f(x)f^('')(x)).
(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)=-{(f^(''')(alpha))/(f^'(alpha))-3/2[(f^('')(alpha))/(f^'(alpha))]^2}
(8)

is the Schwarzian derivative. Halley's method may also be derived by applying Newton's method to ff^('-1/2). It may also be derived by using an osculating curve of the form

 y(x)=((x-x_n)+c)/(a(x-x_n)+b).
(9)

Taking derivatives,

f(x_n)=c/b
(10)
f^'(x_n)=(b-ac)/(b^2)
(11)
f^('')(x_n)=(2a(ac-b))/(b^3),
(12)

which has solutions

a=-(f^('')(x_n))/(2[f^'(x_n)]^2-f(x_n)f^('')(x_n))
(13)
b=(2f^'(x_n))/(2[f^'(x_n)]^2-f(x_n)f^('')(x_n))
(14)
c=(2f(x_n)f^'(x_n))/(2[f^'(x_n)]^2-f(x_n)f^('')(x_n)),
(15)

so at a root, y(x_(n+1))=0 and

 x_(n+1)=x_n-c,
(16)

which is Halley's method.


See also

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

Explore with Wolfram|Alpha

References

Ortega, J. M. and Rheinboldt, W. C. Iterative Solution of Nonlinear Equations in Several Variables. Philadelphia, PA: SIAM, 2000.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 Method

Cite this as:

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

Subject classifications