Householder's method

The Householder method are a group of numerical methods for determining a zero or a scalar real function. They are named after Alston Scott Householder.

Description of the procedure

Let d be a natural number and at least ( d 1) - times continuously differentiable function which possesses a simple zero a in the interval I, ie. Be a starting value close enough to a converges by the iteration

Generated sequence of successive approximations with convergence order d 1 against a That is, there exists a constant K > 0 such that

D = 1 results in the Newton's method, for d = 2 the Halley method.

Motivation

If f has a simple zero in a, then there is a d -fold continuously differentiable function g with and. The reciprocal function ( 1 / f) has a pole of order 1 in a If x near a, the Taylor expansion of 1 / f in x dominated by this pole,

Considering g (x h ) and slowly changing to almost constant for f ( a), the Taylor coefficients are inversely proportional to the magnitude of (XA), so

For k = 1, ..., d

Example

The polynomial used by Newton to demonstrate his process was. In a first step, it was observed that there must be a zero near x = 2. By substituting x = 2 h is obtained only

And then by inverting this polynomial as a Taylor series

The result of the first step of the Householder method of a given order d is also obtained by dividing the coefficient of degree d with its left neighbor in this development. This results in the following approximations ascending order

Thus, there are in this example, slightly more than d valid digits for the first step in the process of order d

Swell

• Alston Scott Householder, Numerical Treatment of a Single Nonlinear Equation, McGraw Hill Text, New York, 1970. ISBN 0-07-030465-3

• Newton 's method and high order iterations, Pascal Zebah and Xavier Gourdon, 2001 ( On the page is linked to a PostScript version with proper representation formula. )

• Numerical Mathematics