Halley's method

Halley, the method ( process also contacting the hyperbolas ) is similar to the Newton's method, a method of the numerical analysis for the determination of the zeros f ( x) = 0 of real features. In contrast to Newton's method, it has the convergence order 3, but needed to addition to the first and the second derivative. It is named after the astronomer Edmond Halley, who also determined the recurrence of the law named after Halley 's Comet. A similar method is the Euler - Chebyshev method.

Description of the procedure

Let f be a real function with a continuous second derivative, and let a be a simple zero of f, ie. Then converges for starting points near a by the iteration

Generated sequence of successive approximations with cubic order of convergence towards a

Variants of this method are the irrational or parabolic Halley method originally used by Halley with the iteration

And generalization in which the Laguerre method

For polynomials where n is equal to the degree is set. Since the term under the square root can be negative, these two variants can also converge for purely real polynomials and real starting values ​​to complex zeros. When necessary in subsequent iterations, determination of the square root of complex numbers here, the solution is always to choose with positive real part, so that the denominator is the maximum amount.

Motivation

Let f be a real function with a continuous second derivative, and let a be a simple zero of f, ie. Then the function curve of f is " straightened " in the vicinity of a second-order, rather than by the function f is considered. This construction is independent of the zero point. Now, the Newton method is applied to g. It is

And therefore

The same provision is derived from the general Householder method in the second order

Example

The iteration for the square root of, for example a = 5 results with the iteration

And thus the calculation table

The result is a sequence of 0, 1, 5, 21, > 60 significant digits, ie a tripling in each step. The Newton method has the procedural rule:

In direct comparison, the Halley method shows faster convergence. However, it requires more arithmetic operations per step.

Cubic convergence

Let f be three times continuously differentiable. Since a was assumed to be zero of f, to a first approximation. More precisely, on an interval I containing a, by the mean value theorem of differential calculus, the two-sided estimate

I.e. both. Thus, it is sufficient to determine the ratio of the function values ​​from one iteration to the next.

Irrational or parabolic Halley method

The Taylor expansion of the second degree of f is

This initially creates an approximation by a parabola, the x touches the graph of f at the point of second order. F ( x ) is small enough, this parabola has a zero point which is significantly close to x, namely

The corresponding iteration is

Since the denominator of H in the vicinity of a root of f is not zero, is considered. By this construction of h disappear the first three terms of the Taylor expansion, therefore applies.

This form of the method was originally proposed by E. Halley. Expanding the root after, we get that, now common, rational or hyperbolic Halley method.

Hyperbolic Halley method

If one uses the Taylor expansion of the identity, we can transform this into a fraction of linear functions in h, ie, f is approximated in the vicinity of x by a hyperbolic function, and determines from this the below zero:

The function f is thus approximated by a hyperbola that touches f at x to also second order. The numerator of the hyperbolic function vanishes, hence the Halley - iteration (see above) results. Again, and is thus

It follows then for the Halley - iteration

I.e., the cubic convergence.

Multidimensional extension

An extension of the method to functions of several variables is possible. It can be the same used to produce a trick binomial hyperbolic. It is however to be noted

These are not obstacles, these features make the bill just a little more confusing. Denote the usual Newton step is the appropriately modified second-order term. Then for the Taylor expansion in x

The linear in t part of the counter will be set to zero and further reshaped. (. ., ) The symmetry of C is used:

If now the short notations replaced by the original expressions, we obtain

It is easy, that this formula reduces to the one-dimensional case to the Halley - iteration. The resulting iteration of the multidimensional Halley method can be determined in 3 simple steps:

If the 2.Ableitung Lipschitz continuous, then the method converges locally cubically.

Since F (x) was assumed to be small, it is not necessary to determine the inverse of the large bracket. It can be re-used the binomial trick (or the Taylor formula 1 degree ) to the simpler, but up to terms of third order ( now in F ( x)) identical expression

To obtain. The derived iteration is the Euler - Chebyshev method.