Householder's method

Template:Short description Template:Refimprove Template:No footnotes 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 Template:Math. Each of these methods is characterized by the number Template:Mvar, which is known as the order of the method. The algorithm is iterative and has a rate of convergence of Template:Math.

These methods are named after the American mathematician Alston Scott Householder.

Method

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

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

beginning with an initial guess Template:Math.

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

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

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

• if Template:Math is even and Template:Math then convergence to Template:Mvar will be from values greater than Template:Mvar;
• if Template:Math is even and Template:Math then convergence to Template:Mvar will be from values less than Template:Mvar;
• if Template:Math is odd and Template:Math then convergence to Template:Mvar will be from the side where it starts; and
• if Template:Math is odd and Template:Math then convergence to Template:Mvar 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 Template:Mvar. 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 Template:Mvar derivatives of Template:Mvar at Template:Math using Horner's method has an effort of Template:Math polynomial evaluations. Since Template:Math evaluations over Template:Mvar iterations give an error exponent of Template:Math, the exponent for one function evaluation is $\sqrt[d+1]{d+1}$, numerically Template:Math, Template:Math, Template:Math, Template:Math for Template:Math, and falling after that. By this criterion, the Template:Math case (Halley's method) is the optimal value of Template:Mvar.
• For general functions the derivative evaluation using the Taylor arithmetic of automatic differentiation requires the equivalent of Template:Math function evaluations. One function evaluation thus reduces the error by an exponent of $\sqrt[\frac{(d+1)(d+2)}{2}]{d+1}$, which is $\sqrt[3]{2}\approx 1.2599$ for Newton's method, $\sqrt[6]{3}\approx 1.2009$ for Halley's method and falling towards 1 or linear convergence for the higher order methods.

Motivation

First approach

Suppose Template:Mvar is analytic in a neighborhood of Template:Mvar and Template:Math. Then Template:Mvar has a Taylor series at Template:Mvar and its constant term is zero. Because this constant term is zero, the function Template:Math will have a Taylor series at Template:Mvar and, when Template:Math, its constant term will not be zero. Because that constant term is not zero, it follows that the reciprocal Template:Math has a Taylor series at Template:Mvar, which we will write as $\sum _{k=0}^{\mathrm{\infty }}\frac{c_k(x-a{)}^k}{k!}$ and its constant term Template:Math will not be zero. Using that Taylor series we can write $$\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 its Template:Mvar-th derivative, we note that the terms for Template:Math conveniently vanish: $${\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)!}$$ $$=\frac{(-1{)}^{d}d!c_0}{(x-a{)}^{d+1}}(1+\frac{1}{(-1{)}^{d}d!c_0}\sum _{k=d+1}^{\mathrm{\infty }}\frac{c_k(x-a{)}^k}{k(k-d-1)!})$$ $$=\frac{(-1{)}^{d}d!c_0}{(x-a{)}^{d+1}}(1+𝒪((x-a{)}^{d+1})),$$ using big O notation. We thus get that the correction term that we add to Template:Math to get a value of Template:Math that is closer to Template:Mvar is: $$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+𝒪((x-a{)}^d)}{1+𝒪((x-a{)}^{d+1})}\right)$$ $$=-(x-a)(1+𝒪((x-a{)}^d)).$$ If Template:Mvar is the zero of Template:Mvar that is closest to Template:Mvar then the second factor goes to 1 as Template:Mvar goes to infinity and $x+d\frac{(1/f{)}^{(d-1)}}{(1/f{)}^{(d)}}$ goes to Template:Mvar.

Second approach

Suppose Template:Math is a simple root. Then near Template:Math, Template:Math is a meromorphic function. Suppose we have the Taylor expansion: $$(1/f)(x)=\sum _{d=0}^{\mathrm{\infty }}\frac{(1/f{)}^{(d)}(b)}{d!}(x-b{)}^d$$ around a point Template:Mvar that is closer to Template:Mvar than it is to any other zero of Template:Mvar. By König's theorem, we have: $$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.

The methods of lower order

Householder's method of order 1 is just Newton's method, since: $$\begin{array}{cc}{x}_{n+1}=& x_n+1\frac{(1/f)(x_n)}{{(1/f)}^{(1)}(x_n)}\\ =& x_n+\frac{1}{f(x_n)}\cdot {\left(\frac{-f^{\prime }(x_n)}{f(x_n{)}^2}\right)}^{-1}\\ =& x_n-\frac{f(x_n)}{f^{\prime }(x_n)}.\end{array}$$

For Householder's method of order 2 one gets Halley's method, since the identities $$(1/f{)}^{\prime }(x)=-\frac{f^{\prime }(x)}{f(x{)}^2}$$ and $$(1/f{)}^{″}(x)=-\frac{f^{″}(x)}{f(x{)}^2}+2\frac{f^{\prime }(x{)}^2}{f(x{)}^3}$$ result in $$\begin{array}{cc}{x}_{n+1}=& x_n+2\frac{(1/f)(x_n)}{(1/f)(x_n)}\\ =& x_n+\frac{-2f(x_n)f^{\prime }(x_n)}{-f(x_n)f^{″}(x_n)+2f^{\prime }(x_n{)}^2}\\ =& x_n-\frac{f(x_n)f^{\prime }(x_n)}{f^{\prime }(x_n{)}^2-\frac{1}{2}f(x_n)f^{″}(x_n)}\\ =& x_n+h_n\frac{1}{1+\frac{1}{2}(f^{″}/f^{\prime })(x_n)h_n}.\end{array}$$ In the last line, $h_n=-\frac{f(x_n)}{f^{\prime }(x_n)}$ is the update of the Newton iteration at the point $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 of Template:Math $$(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 $$\begin{array}{cc}{x}_{n+1}=& x_n+3\frac{(1/f)(x_n)}{(1/f)(x_n)}\\ =& x_n-\frac{6f(x_n)f^{\prime }(x_n{)}^2-3f(x_n{)}^2{f}^{″}(x_n)}{6f^{\prime }(x_n{)}^3-6f(x_n)f^{\prime }(x_n)f^{″}(x_n)+f(x_n{)}^2{f}^{‴}(x_n)}\\ =& x_n+h_n\frac{1+\frac{1}{2}(f^{″}/f^{\prime })(x_n)h_n}{1+(f^{″}/f^{\prime })(x_n)h_n+\frac{1}{6}(f^{‴}/f^{\prime })(x_n)h_n^2}\end{array}$$ and so on.

Example

The first problem solved by Newton with the Newton-Raphson-Simpson method was the polynomial equation $y^3-2y-5=0$. He observed that there should be a solution close to 2. Replacing Template:Math transforms the equation into $$0=f(x)=-1+10x+6x^2+x^3$$. The Taylor series of the reciprocal function starts with $$\begin{array}{cc}1/f(x)=& -1-10x-106x^2-1121x^3-11856x^4-125392x^5\\ & -1326177x^6-14025978x^7-148342234x^8-1568904385x^9\\ & -16593123232x^{10}+O(x^{11})\end{array}$$ The result of applying Householder's methods of various orders at Template:Math 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, $x_1=0.0+106/1121=0.09455842997324$.

d	x1
1	0.100000000000000000000000000000000
2	0.094339622641509433962264150943396
3	0.094558429973238180196253345227475
4	0.094551282051282051282051282051282
5	0.094551486538216154140615031261962
6	0.094551481438752142436492263099118
7	0.094551481543746895938379484125812
8	0.094551481542336756233561913325371
9	0.094551481542324837086869382419375
10	0.094551481542326678478801765822985

As one can see, there are a little bit more than Template:Mvar correct decimal places for each order d. The first one hundred digits of the correct solution are Template:Gaps.

Let's calculate the $x_2,x_3,x_4$ values for some lowest order,

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

And using following relations,

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

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

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

x	1st (Newton)	2nd (Halley)	3rd order	4th order
x1	0.100000000000000000000000000000000	0.094339622641509433962264150943395	0.094558429973238180196253345227475	0.09455128205128
x2	0.094568121104185218165627782724844	0.094551481540164214717107966227500	0.094551481542326591482567319958483
x3	0.094551481698199302883823703544266	0.094551481542326591482386540579303	0.094551481542326591482386540579303
x4	0.094551481542326591496064847153714	0.094551481542326591482386540579303	0.094551481542326591482386540579303
x5	0.094551481542326591482386540579303
x6	0.094551481542326591482386540579303

Derivation

An exact derivation of Householder's methods starts from the Padé approximation of order Template:Math 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 $$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 $h=-a_0$.

Just as the Taylor polynomial of degree Template:Mvar has Template:Math coefficients that depend on the function Template:Mvar, the Padé approximation also has Template:Math coefficients dependent on Template:Mvar 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, $b_d=0$ has to hold.

One could determine the Padé approximant starting from the Taylor polynomial of Template:Mvar using Euclid's algorithm. However, starting from the Taylor polynomial of Template:Math is shorter and leads directly to the given formula. Since $$(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 $a_0+h$ in the power $h^d$ the equation $$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 $h=-a_0$ of the numerator results in $$\begin{array}{cc}h& =-a_0=\frac{\frac{1}{(d-1)!}(1/f{)}^{(d-1)}(x)}{\frac{1}{d!}(1/f{)}^{(d)}(x)}\\ & =d\frac{(1/f{)}^{(d-1)}(x)}{(1/f{)}^{(d)}(x)}\end{array}$$.

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

Relation to Newton's method

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

External links

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