Inmathematics, and more specifically innumerical analysis,Householder's methods are a class ofroot-finding algorithms that are used for functions of one real variable with continuous derivatives up to some orderd + 1. Each of these methods is characterized by the numberd, which is known as theorder of the method. The algorithm is iterative and has anorder of convergence ofd + 1.

These methods are named after the American mathematicianAlston Scott Householder. The case ofd = 1 corresponds toNewton's method; the case ofd = 2 corresponds toHalley's method.

Householder's method is a numerical algorithm for solving the equationf(x) = 0. In this case, the functionf has to be a function of one real variable. The method consists of a sequence of iterations

$${\displaystyle x_{n+1}=x_n+d\frac{{\left(1/f\right)}^{(d-1)}(x_n)}{{\left(1/f\right)}^{(d)}(x_n)}}$$ 

beginning with an initial guessx₀.^[1]

Iff is ad + 1 times continuously differentiable function anda is a zero off but not of its derivative, then, in a neighborhood ofa, the iteratesx_n satisfy:^{[citation needed]}

$${\displaystyle |x_{n+1}-a|\le K\cdot {|x_n-a|}^{d+1}}$$ , for some${\displaystyle K>0.}$ 

This means that the iterates converge to the zero if the initial guess is sufficiently close, and that the convergence has orderd + 1 or better. Furthermore, when close enough toa, it commonly is the case that${\displaystyle x_{n+1}-a\approx C(x_n-a{)}^{d+1}}$  for some${\displaystyle C\ne 0}$ . In particular,

• ifd + 1 is even andC > 0 then convergence toa will be from values greater thana;
• ifd + 1 is even andC < 0 then convergence toa will be from values less thana;
• ifd + 1 is odd andC > 0 then convergence toa will be from the side where it starts; and
• ifd + 1 is odd andC < 0 then convergence toa 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 larged. TheOstrowski index expresses the error reduction in the number of function evaluations instead of the iteration count.^[2]

• For polynomials, the evaluation of the firstd derivatives off atx_n usingHorner's method has an effort ofd + 1 polynomial evaluations. Sincen(d + 1) evaluations overn iterations give an error exponent of(d + 1)ⁿ, the exponent for one function evaluation is${\displaystyle \sqrt[d+1]{d+1}}$ , numerically1.4142,1.4422,1.4142,1.3797 ford = 1, 2, 3, 4, and falling after that. By this criterion, thed=2 case (Halley's method) is the optimal value ofd.
• For general functions the derivative evaluation using the Taylor arithmetic ofautomatic differentiation requires the equivalent of(d + 1)(d + 2)/2 function evaluations. One function evaluation thus reduces the error by an exponent of${\displaystyle \sqrt[\frac{(d+1)(d+2)}{2}]{d+1}}$ , which is${\displaystyle \sqrt[3]{2}\approx 1.2599}$  for Newton's method,${\displaystyle \sqrt[6]{3}\approx 1.2009}$  for Halley's method and falling towards 1 or linear convergence for the higher order methods.

Supposef is analytic in a neighborhood ofa andf(a) = 0. Thenf has aTaylor series ata and its constant term is zero. Because this constant term is zero, the functionf(x) / (x −a) will have a Taylor series ata and, whenf ′ (a) ≠ 0, its constant term will not be zero. Because that constant term is not zero, it follows that the reciprocal(x −a) /f(x) has a Taylor series ata, which we will write as${\displaystyle \sum _{k=0}^{\mathrm{\infty }}\frac{c_k(x-a{)}^k}{k!}}$  and its constant termc₀ will not be zero. Using that Taylor series we can write$${\displaystyle \frac{1}{f}=\frac{c_0}{x-a}+\sum _{k=1}^{\mathrm{\infty }}\frac{c_k(x-a{)}^{k-1}}{k(k-1)!}.}$$ When we compute itsd-th derivative, we note that the terms fork = 1, ...,d conveniently vanish:$${\displaystyle {\left(\frac{1}{f}\right)}^{(d)}=\frac{(-1{)}^{d}d!c_0}{(x-a{)}^{d+1}}+\sum _{k=d+1}^{\mathrm{\infty }}\frac{c_k(x-a{)}^{k-d-1}}{k(k-d-1)!}}$$ $${\displaystyle =\frac{(-1{)}^{d}d!c_0}{(x-a{)}^{d+1}}\left(1+\frac{1}{(-1{)}^{d}d!c_0}\sum _{k=d+1}^{\mathrm{\infty }}\frac{c_k(x-a{)}^k}{k(k-d-1)!}\right)}$$ $${\displaystyle =\frac{(-1{)}^{d}d!c_0}{(x-a{)}^{d+1}}\left(1+\mathcal{O}\left((x-a{)}^{d+1}\right)\right),}$$ usingbig O notation. We thus get that the correction term that we add tox =x_n to get a value ofx_n+1 that is closer toa is:$${\displaystyle d\frac{(1/f{)}^{(d-1)}}{(1/f{)}^{(d)}}=d\frac{(-1{)}^{d-1}(d-1)!c_0}{(-1{)}^{d}d!c_0}(x-a)\left(\frac{1+\mathcal{O}\left((x-a{)}^d\right)}{1+\mathcal{O}\left((x-a{)}^{d+1}\right)}\right)}$$ $${\displaystyle =-\left((x-a)+\mathcal{O}\left((x-a{)}^{d+1}\right)\right).}$$ Thus,${\displaystyle x+d\frac{(1/f{)}^{(d-1)}}{(1/f{)}^{(d)}}}$  goes to⁠${\displaystyle a+\mathcal{O}\left((x-a{)}^d\right)}$ ⁠.

Supposex =a is a simple root. Then nearx =a,(1/f)(x) is ameromorphic function. Suppose we have theTaylor expansion:$${\displaystyle (1/f)(x)=\sum _{d=0}^{\mathrm{\infty }}\frac{(1/f{)}^{(d)}(b)}{d!}(x-b{)}^d}$$ around a pointb that is closer toa than it is to any other zero off. ByKönig's theorem, we have:$${\displaystyle a-b=\underset{d\to \mathrm{\infty }}{lim}\frac{\frac{(1/f{)}^{(d-1)}(b)}{(d-1)!}}{\frac{(1/f{)}^{(d)}(b)}{d!}}=d\frac{(1/f{)}^{(d-1)}(b)}{(1/f{)}^{(d)}(b)}.}$$ 

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

Householder's method of order 1 is justNewton's method, since: 

For Householder's method of order 2 one getsHalley's method, since the identities$${\displaystyle (1/f{)}^{\prime }(x)=-\frac{f^{\prime }(x)}{f(x{)}^2}}$$ and$${\displaystyle (1/f{)}^{″}(x)=-\frac{f^{″}(x)}{f(x{)}^2}+2\frac{f^{\prime }(x{)}^2}{f(x{)}^3}}$$ result in In the last line,${\displaystyle h_n=-\frac{f(x_n)}{f^{\prime }(x_n)}}$  is the update of the Newton iteration at the point${\displaystyle x_n}$ . 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 of1/f$${\displaystyle (1/f{)}^{‴}(x)=-\frac{f^{‴}(x)}{f(x{)}^2}+6\frac{f^{\prime }(x)f^{″}(x)}{f(x{)}^3}-6\frac{f^{\prime }(x{)}^3}{f(x{)}^4}}$$ and has the formula and so on.

The first problem solved by Newton with the Newton-Raphson-Simpson method was the polynomial equation${\displaystyle y^3-2y-5=0}$ . He observed that there should be a solution close to 2. Replacingy =x + 2 transforms the equation into$${\displaystyle 0=f(x)=-1+10x+6x^2+x^3}$$ .The Taylor series of the reciprocal function starts with The result of applying Householder's methods of various orders atx = 0 is also obtained by dividing neighboring coefficients of the latterpower 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,${\displaystyle x_1=0.0+106/1121=0.09455842997324}$ .

As one can see, there are a little bit more thand correct decimal places for each order d. The first one hundred digits of the correct solution are0.0945514815423265914823865405793029638573061056282391803041285290453121899834836671462672817771577578.

Let's calculate the${\displaystyle x_2,x_3,x_4}$  values for some lowest order,

$${\displaystyle f=-1+10x+6x^2+x^3}$$ $${\displaystyle f^{\mathrm{\prime }}=10+12x+3x^2}$$ $${\displaystyle f^{\mathrm{\prime }\mathrm{\prime }}=12+6x}$$ $${\displaystyle f^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}=6}$$ 

And using following relations,

1st order;${\displaystyle x_{i+1}=x_i-f(x_i)/f^{\mathrm{\prime }}(x_i)}$ 

2nd order;${\displaystyle x_{i+1}=x_i-2f{f}^{\mathrm{\prime }}/(2{f^{\mathrm{\prime }}}^2-f{f}^{\mathrm{\prime }\mathrm{\prime }})}$ 

3rd order;${\displaystyle x_{i+1}=x_i-(6f{f^{\mathrm{\prime }}}^2-3f^2{f}^{\mathrm{\prime }\mathrm{\prime }})/(6{f^{\mathrm{\prime }}}^3-6f{f}^{\mathrm{\prime }}{f}^{\mathrm{\prime }\mathrm{\prime }}+f^2{f}^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }})}$ 

An exact derivation of Householder's methods starts from thePadé approximation of orderd + 1 of the function, where the approximant with linearnumerator 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$${\displaystyle f(x+h)=\frac{a_0+h}{b_0+b_{1}h+\cdots +b_{d-1}{h}^{d-1}}+O(h^{d+1}).}$$ The rational function has a zero at${\displaystyle h=-a_0}$ .

Just as the Taylor polynomial of degreed hasd + 1 coefficients that depend on the functionf, the Padé approximation also hasd + 1 coefficients dependent onf 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,${\displaystyle b_d=0}$  has to hold.

One could determine the Padé approximant starting from the Taylor polynomial off usingEuclid's algorithm. However, starting from the Taylor polynomial of1/f is shorter and leads directly to the given formula. Since$${\displaystyle (1/f)(x+h)=(1/f)(x)+(1/f{)}^{\prime }(x)h+\cdots +(1/f{)}^{(d-1)}(x)\frac{h^{d-1}}{(d-1)!}+(1/f{)}^{(d)}(x)\frac{h^d}{d!}+O(h^{d+1})}$$ has to be equal to the inverse of the desired rational function, we get after multiplying with${\displaystyle a_0+h}$  in the power${\displaystyle h^d}$  the equation$${\displaystyle 0=b_d=a_0(1/f{)}^{(d)}(x)\frac{1}{d!}+(1/f{)}^{(d-1)}(x)\frac{1}{(d-1)!}}$$ .

Now, solving the last equation for the zero${\displaystyle h=-a_0}$  of the numerator results in .

This implies the iteration formula$${\displaystyle x_{n+1}=x_n+d\frac{{\left(1/f\right)}^{(d-1)}(x_n)}{{\left(1/f\right)}^{(d)}(x_n)}}$$ .

Householder's method applied to the real-valued functionf(x) is the same as applying Newton's method$${\displaystyle x_{n+1}=x_n-\frac{g(x_n)}{g^{\prime }(x_n)}}$$ to find the zeros of the function:$${\displaystyle g(x)={\left|(1/f{)}^{(d-1)}\right|}^{-1/d}.}$$ In particular,d = 1 gives Newton's method unmodified andd = 2 gives Halley's method.

• Pascal Sebah and Xavier Gourdon (2001)."Newton's method and high order iteration".Note: Use thePostScript version of this link; the website version is not compiled correctly.