Halley's method

In numerical analysis, Halley's method is a root-finding algorithm used for functions of one real variable with a continuous second derivative. Edmond Halley was an English mathematician and astronomer who introduced the method now called by his name.

The algorithm is second in the class of Householder's methods, after Newton's method. Like the latter, it iteratively produces a sequence of approximations to the root; their rate of convergence to the root is cubic. Multidimensional versions of this method exist.

Halley's method exactly finds the roots of a linear-over-linear Padé approximation to the function, in contrast to Newton's method or the Secant method which approximate the function linearly, or Muller's method which approximates the function quadratically.

There is also Halley's irrational method, described below.

Method

Halley's method is a numerical algorithm for solving the nonlinear equation In this case, the function has to be a function of one real variable. The method consists of a sequence of iterations:

:$x_ = x_n - \frac$

beginning with an initial guess .

If is a three times continuously differentiable function and is a zero of but not of its derivative, then, in a neighborhood of , the iterates satisfy:

:$, x_ - a , \le K \cdot ^3, \quad \text\quad K > 0 ~.$

This means that the iterates converge to the zero if the initial guess is sufficiently close, and that the convergence is cubic.

The following alternative formulation shows the similarity between Halley's method and Newton's method. The ratio $\ f(x_n)/f'(x_n)\$ only needs to be computed once, and this form is particularly useful when the other ratio, $\ f''(x_n)/f'(x_n)\ ,$ can be reduced to a simpler form:

:x_\ =\ x_n -\frac\ =\ x_n - \frac \left 1\ -\ \frac \cdot \frac \cdot \frac\ \right ~.

When the second derivative, $\ f''(x_n)\ ,$ is very close to zero, the Halley's method iteration is almost the same as the Newton's method iteration.

Motivation

When deriving Newton's method, a proof starts with the approximation
$0 = f(x_) \approx f(x_n) + f'(x_n) (x_ - x_n)$
to compute
$x_-x_n = -\frac\,.$
Similarly for Halley's method, a proof starts with
$0 = f(x_) \approx f(x_n) + f'(x_n) (x_ - x_n) + \frac2 (x_ - x_n)^2\,.$
For Halley's rational method, this is rearranged to give
$x_-x_n = -\frac\,$
where appears on both sides of the equation. Substituting in the Newton's method value for into the right-hand side of this last formula gives the formula for Halley's method,
$x_ = x_n - \frac\,.$

Also see the motivation and proofs for the more general class of Householder's methods.

Cubic convergence

Suppose ''a'' is a root of ''f'' but not of its derivative. And suppose that the third derivative of ''f'' exists and is continuous in a neighborhood of ''a'' and is in that neighborhood. Then Taylor's theorem implies:

:$0 = f(a) = f(x_n) + f'(x_n) (a - x_n) + \frac (a - x_n)^2 + \frac (a - x_n)^3$

and also

:$0 = f(a) = f(x_n) + f'(x_n) (a - x_n) + \frac (a - x_n)^2,$

where ξ and η are numbers lying between ''a'' and . Multiply the first equation by $2f'(x_n)$ and subtract from it the second equation times $f''(x_n)(a - x_n)$ to give:

:\begin
0 &= 2 f(x_n) f'(x_n) + 2 '(x_n)2 (a - x_n) + f'(x_n) f''(x_n) (a - x_n)^2 + \frac (a - x_n)^3 \\
&\qquad- f(x_n) f''(x_n) (a - x_n) - f'(x_n) f''(x_n) (a - x_n)^2 - \frac (a - x_n)^3.
\end

Canceling $f'(x_n) f''(x_n) (a - x_n)^2$ and re-organizing terms yields:

:0 = 2 f(x_n) f'(x_n) + \left(2 '(x_n)2 - f(x_n) f''(x_n) \right) (a - x_n) + \left(\frac - \frac \right) (a - x_n)^3.

Put the second term on the left side and divide through by

: 2 '(x_n)2 - f(x_n) f''(x_n)

to get:

:$a - x_n = \frac - \frac (a - x_n)^3.$

Thus:

:$a - x_ = - \frac (a - x_n)^3.$

The limit of the coefficient on the right side as is:

:$-\frac.$

If we take ''K'' to be a little larger than the absolute value of this, we can take absolute values of both sides of the formula and replace the absolute value of coefficient by its upper bound near ''a'' to get:

:$, a - x_, \leq K , a - x_n, ^3$

which is what was to be proved.

To summarize,

:$\Delta x_ =\frac (\Delta x_i)^3 + O$Delta x_i4, \qquad \Delta x_i \triangleq x_i - a.

Halley's irrational method

Halley actually developed ''two'' third-order root-finding methods. The above, using only a division, is referred to as ''Halley's rational method''. A second, "irrational" method uses a square root as well. An English translation was published as
It starts with
:$f(x_) \approx f(x_n) + f'(x_n)(x_ - x_) + \frac(x_ - x_)^2$
and solves $f(x_) \approx 0$ for the value $(x_ - x_)$ using one of two forms of the quadratic formula. The quadratic formula solution either has the radical in the numerator:
:$x_ = x_n - \frac = x_n - \frac$
or it has the radical in the denominator, yielding an update step that often gives better results:
:$x_ = x_n - \frac = x_n - \frac$
This iteration was "deservedly preferred" to the rational method by Halley on the grounds that the denominator is smaller, making the division easier. A second advantage is that it tends to have about half of the error of the rational method, a benefit which multiplies as it is iterated. On a computer, it would appear to be slower as it has two slow operations (division and square root) instead of one, but on modern computers the reciprocal of the denominator can be computed at the same time as the square root via instruction pipelining, so the latency of each iteration differs very little.

The formulation with the radical in the denominator reduces to Halley's rational method under the approximation that .

Muller's method could be considered as modification of this method. So, this method can be used to find the complex roots.

References

External links

*
*
Newton's method and high order iterations
', Pascal Sebah and Xavier Gourdon, 2001 (the site has a link to a Postscript version for better formula display)

{{DEFAULTSORT:Halley's Method
Root-finding algorithms