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 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:

, for some 

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 , it commonly is the case that  for some . In particular,
 if  is even and  then convergence to  will be from the right;
 if  is even and  then convergence to  will be from the left;
 if  is odd and  then convergence to  will be from the side where it starts; and
 if  is odd and  then convergence to  will alternate sides. 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. For polynomials, the evaluation of the first  derivatives of  at  using the Horner method has an effort of  polynomial evaluations. Since  evaluations over  iterations give an error exponent of , the exponent for one function evaluation is , 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  function evaluations. One function evaluation thus reduces the error by an exponent of , which is  for Newton's method,  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 , which we will write as  and its constant term  will not be zero. Using that Taylor series we can write

When we compute its -th derivative, we note that the terms for  conveniently vanish:

using big O notation. We thus get that the ratio

If  is the zero of  that is closest to  then the second factor goes to 1 as  goes to infinity and 
 goes to . 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, we have:

These suggest 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, 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,
. 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,

 1st order; 
 2nd order; 
 3rd order;

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. References

External links 
  Note: Use the PostScript version of this link; the website version is not compiled correctly. Root-finding algorithms