Householder's method

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In numerical analysis, the class of Householder's methods are root-finding algorithms used for functions of one real variable with continuous derivatives up to some order d+1, where d will be the order of the Householder's method.

The algorithm is iterative and it has rate of convergence of d+1.


Like many root-finding methods, the Householder's method is a numerical algorithm for solving the nonlinear equation f(x) = 0. In this case, the function f has to be a function of one real variable. The method consists of a sequence of iterations

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 guess x0.[1]

If f is a (d+1) times continuously differentiable function and a is a zero of f but not of its derivative, then, in a neighborhood of a, the iterates xn satisfy:

| 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 rate (d+1).

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 d. The Ostrowski index[2] expresses the error reduction in the number of function evaluations instead of the iteration count.

  • For polynomials, the evaluation of the first d derivatives of f at xn using the Horner method has an effort of d+1 polynomial evaluations. Since n(d+1) evaluations over n iterations give an error exponent of (d+1)n, the exponent for one function evaluation is \sqrt[d+1]{d+1}, numerically 1.4142, 1.4422, 1.4142, 1.3797 for d=1,2,3,4, and falling after that.
  • For general functions the derivative evaluation using the Taylor arithmetic of automatic differentiation requires the equivalent of (d+1)(d+2)/2 function evaluations. One function evaluation thus reduces the error by an exponent of \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.


An approximate idea of the Householder's method derives from the geometric series. Let the real-valued, continuously differentiable function f(x) have a simple zero at x=a, that is a root f(a)=0 of multiplicity one, which is equivalent to f'(a)\ne0. Then 1/f(x) has a singularity at a, specifically a simple pole (also of multiplicity one), and close to a the behavior of 1/f(x) is dominated by1/(x-a). Approximatively one gets


Here f'(a)\ne0 because a is a simple zero of f(x). The coefficient of degree d has the value C\,a^{-d}. Thus, one can now reconstruct the zero a by dividing the coefficient of degree d-1 by the coefficient of degree d. Since this geometric series is an approximation to the Taylor expansion of 1/f(x), one can get estimates of the zero of f(x) − now without prior knowledge of the location of this zero − by dividing the corresponding coefficients of the Taylor expansion of 1/f(x) or, more generally, 1/f(b+x). From that one gets, for any integer d, and if the corresponding derivatives exist,

  a \approx b+\frac{(1/f)^{(d-1)}(b)}{(d-1)!}\;\frac{d!}{(1/f)^{(d)}(b)} = 

Alternative motivation[edit]

Suppose x=a is a simple root. Then near x=a, (1/f)(x) is a meromorphic function. Suppose we have the Taylor expansion:

(1/f)(x) = \sum_{d=0}^{\infty} \frac{(1/f)^{(d)}(b)}{d!} (x-b)^d.

By König's theorem, we have:

a-b = \lim_{d\rightarrow \infty} \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)}.

This suggests that the 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[edit]

The Householder's method of order 1 is just Newton's method, since:

x_{n+1} =& x_n + 1\,\frac {\left(1/f\right)(x_n)} {\left(1/f\right)^{(1)}(x_n)}\\[.7em]
=& x_n + \frac{1}{f(x_n)}\cdot\left(\frac{-f'(x_n)}{f(x_n)^2}\right)^{-1}\\[.7em]
=& x_n - \frac{f(x_n)}{f'(x_n)}.

For the Householder's method of order 2 one gets Halley's method, since the identities




result in

x_{n+1} =& x_n + 2\,\frac {\left(1/f\right)'(x_n)} {\left(1/f\right)''(x_n)}\\[1em]
=& x_n + \frac{-2f(x_n)\,f'(x_n)}{-f(x_n)f''(x_n)+2f'(x_n)^2}\\[1em]
=& x_n - \frac{f(x_n)f'(x_n)}{f'(x_n)^2-\tfrac12f(x_n)f''(x_n)}\\[1em]
=& x_n + h_n\;\frac{1}{1+\frac12(f''/f')(x_n)\,h_n}.

In the last line, h_n=-\tfrac{f(x_n)}{f'(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 1/f


and has the formula

x_{n+1} =& x_n + 3\,\frac {\left(1/f\right)''(x_n)} {\left(1/f\right)'''(x_n)}\\[1em]
=& x_n - \frac{6f(x_n)\,f'(x_n)^2-3f(x_n)^2f''(x_n)}{6f'(x)^3-6f(x_n)f'(x_n)\,f''(x)+f(x_n)^2\,f'''(x_n)}\\[1em]
=& x_n + h_n\frac{1+\frac12(f''/f')(x_n)\,h_n}{1+(f''/f')(x_n)\,h_n+\frac16(f'''/f')(x_n)\,h_n^2}

and so on...


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 y=x+2 transforms the equation into

0=f(x)=-1 + 10 x + 6 x^2 + x^3.

The Taylor series of the reciprocal function starts with

1/f(x)=& - 1 - 10\,x - 106 \,x^2 - 1121 \,x^3 - 11856 \,x^4 - 125392 \,x^5\\
       & - 1326177 \,x^6 - 14025978 \,x^7 - 148342234 \,x^8 - 1568904385 \,x^9\\
       & - 16593123232 \,x^{10} +O(x^{11})

The result of applying Householder's methods of various orders at x=0 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.10000000000000000000000000000000
2 0.094339622641509433962264150943396
3 0.094558429973238180196253345227476
4 0.094551282051282051282051282051282
5 0.094551486538216154140615031261963
6 0.094551481438752142436492263099119
7 0.094551481543746895938379484125813
8 0.094551481542336756233561913325371
9 0.094551481542324837086869382419375
10 0.094551481542326678478801765822985

As one can see, there are a little bit more than d correct decimal places for each order d.

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} + (-2ff^{\prime} ) / (2{f^{\prime}}^2 - ff^{\prime\prime})
3rd order;  x_{i+1} = x_{i} - \frac {6f {f^{\prime}}^2 - 3f^2 f^{\prime\prime} }
           {6{f^{\prime}}^3 -6 f f^{\prime}f^{\prime\prime} + f^2f^{\prime\prime\prime}}
x 1st (Newton) 2nd (Halley) 3rd order 4th order
x1 0.1 0.09433962264151 0.09455842997324 0.09455128205128
x2 0.09456812110419 0.09455148154016421472 0.094551481542326591482567
x3 0.09455148169819930297 0.09455148154232659148238654 0.09455148154232659148238654057931
x4 0.09455148154232659149606485 0.0945514815423265914823865405793 0.09455148154232659148238654057931
x5 0.09455148154232659148238654057931 0.0945514815423265914823865405793
x6 0.09455148154232659148238654057931


An exact derivation of the Householder's methods starts from the Padé approximation of order (d+1) of the function resp. its Taylor development, where the approximant with linear numerator is chosen. If 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 h=-a_0.

Just as the Taylor polynomial of degree d has d+1 coefficients that depend on the function f, also the Padé approximation always has d+1 coefficients dependent on f and its derivatives. More precisely, in any Padé approximant, the degrees of 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 f using Euclid's algorithm. However, starting from the Taylor polynomial of 1/f is shorter and leads directly to the given formula. Since

  (1/f)(x+h) = 

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


Now, solving the last equation for the zero h=-a_0 of the numerator results in


This implies the iteration formula

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

External links[edit]


  1. ^ Householder, Alston Scott (1970). The Numerical Treatment of a Single Nonlinear Equation. McGraw-Hill. p. 169. LCCN 79-103908 Check |lccn= value (help). 
  2. ^ Ostrowski, A. M. (1966), "Solution of equations and systems of equations", Pure and Applied Mathematics (Second edition), Vol. 9 (New York: Academic Press)