In mathematics, and more specifically in numerical analysis, Householder's methods are a class of root-finding algorithms that are used for functions of one real variable with continuous derivatives up to some order . Each of these methods is characterized by the number , which is known as the order of the method. The algorithm is iterative and has an order of convergence of .

These methods are named after the American mathematician Alston Scott Householder. The case of corresponds to Newton's method; the case of corresponds to Halley's method.

Method

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

beginning with an initial guess , where the superscript in parentheses indicates the number of times the function is differentiated.

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

This means that the iterates converge to the zero if the initial guess is sufficiently close, and that the convergence has order or better. Furthermore, when close enough to . In particular,

• if is odd and then convergence to will be from values greater than ;

• if is odd and then convergence to will be from values less than ;

• if is even and then convergence to will be from the side where it starts; and

• if is even and then convergence to will alternate sides.

Despite their order of convergence, these methods are not widely used when because the gain in precision is not commensurate with the rise in effort. The Ostrowski index expresses the error reduction in the number of function evaluations instead of the iteration count.

• For polynomials, the evaluation of the first derivatives of at using Horner's method has an effort of polynomial evaluations. Since evaluations over iterations give an error exponent of , numerically , , , for , and falling after that. By this criterion, the case (Halley's method) is the optimal value of .

• For general functions the derivative evaluation using the Taylor arithmetic of automatic differentiation requires the equivalent of for Halley's method and falling towards 1 or linear convergence for the higher order methods.

Motivation

First approach

Suppose is analytic in a neighborhood of and . Then has a Taylor series at and its constant term is zero. Because this constant term is zero, the function will have a Taylor series at and, when , its constant term will not be zero. Because that constant term is not zero, it follows that the reciprocal has a Taylor series at and its constant term When we compute its -th derivative, we note that the terms for using big O notation. We thus get that the correction term that we add to to get a value of that is closer to is .

Second approach

Suppose is a simple root. Then near , is a meromorphic function. Suppose we have the Taylor expansion around a point that is closer to than it is to any other zero of . By König's theorem

This suggests that Householder's iteration might be a good convergent iteration. The actual proof of the convergence is also based on these ideas.

The methods of lower order

Householder's method of order 1 is just Newton's method

For Householder's method of order 2 one gets Halley's method. This line was added to demonstrate where the difference to the simple Newton's method lies.

The third order method is obtained from the identity of the third order derivative of and so on.

Example

. He observed that there should be a solution close to 2. Replacing The result of applying Householder's methods of various orders at is also obtained by dividing neighboring coefficients of the latter power series.As one can see, there are a little bit more than correct decimal places for each order d. The first one hundred digits of the correct solution are .

values for some lowest order,

And using following relations,

Derivation

An exact derivation of Householder's methods starts from the Padé approximation of order of the function, where the approximant with linear numerator is chosen. Once this has been achieved, the update for the next approximation results from computing the unique zero of the numerator.

The rational function.

Just as the Taylor polynomial of degree has coefficients that depend on the function , the Padé approximation also has coefficients dependent on has to hold.

One could determine the Padé approximant starting from the Taylor polynomial of using Euclid's algorithm. However, starting from the Taylor polynomial of .

.

.

Relation to Newton's method

Householder's method applied to the real-valued function where we are computing a -th derivative and raising to a power of . In particular, gives Newton's method unmodified and gives Halley's method.

Notes

References

External links

• Note: Use the PostScript version of this link; the website version is not compiled correctly.