Householder's method


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 a rate of convergence of.
These methods are named after the American mathematician Alston Scott Householder.

Method

Householder'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
beginning with an initial guess.
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.
Despite their order of convergence, these methods are not widely used because the gain in precision is not commensurate with the rise in effort for large. The Ostrowski index expresses the error reduction in the number of function evaluations instead of the iteration count.

First approach

An approximate idea of Householder's method derives from the geometric series. Let the real-valued, continuously differentiable function have a simple zero at, that is a root of multiplicity one, which is equivalent to. Then has a singularity at, specifically a simple pole, and close to the behavior of is dominated by. Approximately, one gets
Here because is a simple zero of. The coefficient of degree has the value. Thus, one can now reconstruct the zero by dividing the coefficient of degree by the coefficient of degree. Since this geometric series is an approximation to the Taylor expansion of, one can get estimates of the zero of – now without prior knowledge of the location of this zero – by dividing the corresponding coefficients of the Taylor expansion of or, more generally,. From that one gets, for any integer, and if the corresponding derivatives exist,

Second approach

Suppose is a simple root. Then near, is a meromorphic function. Suppose we have the Taylor expansion:
By König's theorem, we have:
This suggests that Householder's iteration might be a good convergent iteration. The actual proof of the convergence is also based on this idea.

The methods of lower order

Householder's method of order 1 is just Newton's method, since:
For Householder's method of order 2 one gets Halley's method, since the identities
and
result in
In the last line, is the update of the Newton iteration at the point. 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 has the formula
and so on.

Example

The first problem solved by Newton with the Newton-Raphson-Simpson method was the polynomial equation. He observed that there should be a solution close to 2. Replacing transforms the equation into
The Taylor series of the reciprocal function starts with
The result of applying Householder's methods of various orders at is also obtained by dividing neighboring coefficients of the latter power series. For the first orders one gets the following values after just one iteration step: For an example, in the case of the 3rd order,
dx1
10.100000000000000000000000000000000
20.094339622641509433962264150943396
30.094558429973238180196253345227475
40.094551282051282051282051282051281
50.094551486538216154140615031261961
60.094551481438752142436492263099118
70.094551481543746895938379484125813
80.094551481542336756233561913325371
90.094551481542324837086869382419375
100.094551481542326678478801765822984

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.
Let's calculate the values for some lowest order,
And using following relations,
x1st 2nd 3rd order4th order
x10.1000000000000000000000000000000000.0943396226415094339622641509433950.0945584299732381801962533452274750.09455128205128
x20.0945681211041852181656277827248440.0945514815401642147171079662275000.094551481542326591482567319958483
x30.0945514816981993028838237035442660.0945514815423265914823865405793030.094551481542326591482386540579303
x40.0945514815423265914960648471537140.0945514815423265914823865405793030.094551481542326591482386540579303
x50.094551481542326591482386540579303
x60.094551481542326591482386540579303

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 Padé approximation has the form
The rational function has a zero at.
Just as the Taylor polynomial of degree has coefficients that depend on the function, the Padé approximation also has coefficients dependent on and its derivatives. More precisely, in any Padé approximant, the degrees of the numerator and denominator polynomials have to add to the order of the approximant. Therefore, 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 is shorter and leads directly to the given formula. Since
has to be equal to the inverse of the desired rational function, we get after multiplying with in the power the equation
Now, solving the last equation for the zero of the numerator results in
This implies the iteration formula

Relation to Newton's method

Householder's method applied to the real-valued function is the same as Newton's method applied to the function :
with
In particular, gives Newton's method unmodified and gives Halley's method.