Householder's method

Householder's method

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

Method

Like any root-finding method, 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 ight)^{(d-1)}(x_n)} {left(1/f ight)^{(d)}(x_n)}

beginning with an initial guess "x"0.

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 "x""n" satisfy:

:| x_{n+1} - a | le K cdot ^{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)".

Motivation

An approximate idea of the origin 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 "f(a)=0" while f'(a) e0. Then "1/f(x)" has a simple pole at "a", and close to "a" the behavior of "1/f(x)" is dominated by the factor "1/(x-a)". Approximatively one gets:::frac1{f(x)}=frac1{f(x)-f(a)}=frac{x-a}{f(x)-f(a)}cdotfrac{-1}{a(1-x/a)} approxfrac{-1}{af'(a)}cdotsum_{k=0}^inftyleft(frac{x}{a} ight)^k.Here f'(a) e0 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)} = b+d;frac{(1/f)^{(d-1)}(b)}{(1/f)^{(d)}(b)}.

The methods of lower order

The Householder's method of order "1" is just Newton's method, since::::egin{array}{rl}x_{n+1} =& x_n + 1,frac {left(1/f ight)(x_n)} {left(1/f ight)^{(1)}(x_n)}\ [.7em] =& x_n + frac{1}{f(x_n)}cdotleft(frac{-f'(x_n)}{f(x_n)^2} ight)^{-1}\ [.7em] =& x_n - frac{f(x_n)}{f'(x_n)}.end{array}

For the Householder's method of order "2" one gets Halley's method, since the identities::: extstyle (1/f)'(x)=-frac{f'(x)}{f(x)^2} and extstyle (1/f)"(x)=-frac{f"(x)}{f(x)^2}+2frac{f'(x)^2}{f(x)^3}result in:::egin{array}{rl}x_{n+1} =& x_n + 2,frac {left(1/f ight)'(x_n)} {left(1/f ight)"(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- frac12f(x_n)f"(x_n)}\ [1em] =& x_n + h_n;frac{1}{1+frac12(f"/f')(x_n),h_n}.end{array}In the last line, h_n=- frac{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"::: extstyle (1/f)(x)=-frac{f(x)}{f(x)^2}+6frac{f'(x),f"(x)}{f(x)^3}-6frac{f'(x)^3}{f(x)^4}and has the formula:::egin{array}{rl}x_{n+1} =& x_n + 3,frac {left(1/f ight)"(x_n)} {left(1/f ight)"'(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_nfrac{1+frac12(f"/f')(x_n),h_n}{1+(f"/f')(x_n),h_n+frac16(f"'/f')(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 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:::egin{array}{rl}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})end{array}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:As one can see, there are a little bit more than "d" correct decimal places for each order d.

Derivation

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:::f(x+h)=frac{a_0+h}{b_0+b_1h+dots+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 "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 Pade 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) = (1/f)(x)+(1/f)'(x)h+dots+(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)frac1{d!}+(1/f)^{(d-1)}(x)frac1{(d-1)!}.

Now, solving the last equation for the zero h=-a_0 of the numerator results in:::egin{array}{rl} h=&-a_0= frac{frac1{(d-1)!}(1/f)^{(d-1)}(x)}{frac1{d!}(1/f)^{(d)}(x)}\ [1em] =&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 { left(1/f ight)^{(d-1)} (x_n) } { left(1/f ight)^{(d)} (x_n) } .

External links

* " [http://numbers.computation.free.fr/Constants/Algorithms/newton.html Newton's method and high order iterations] ", Pascal Sebah and Xavier Gourdon, 2001 (the site has a link to a Postscript version for better formula display)


Wikimedia Foundation. 2010.

Нужен реферат?

Look at other dictionaries:

  • Householder transformation — In mathematics, a Householder transformation in 3 dimensional space is the reflection of a vector in a plane. In general Euclidean space it is a linear transformation that describes a reflection in a hyperplane (containing the origin).The… …   Wikipedia

  • Householder — A householder is a person who is the head of a household ; see House.Householder is also a family name: *Alston Scott Householder, American mathematician Mathematical topics named after A.S. Householder: ** Householder transformation in geometry… …   Wikipedia

  • Householder-Verfahren — Die Householder Verfahren sind eine Gruppe von numerischen Verfahren zur Bestimmung von Nullstellen einer skalaren reellen Funktion. Sie sind nach Alston Scott Householder benannt. Inhaltsverzeichnis 1 Beschreibung des Verfahrens 2 Motivation 3… …   Deutsch Wikipedia

  • Iteration de Householder — Itération de Householder En analyse numérique, l itération de Householder ou méthode de Householder désigne un algorithme de recherche d un zéro d une fonction utilisé pour les fonctions d une variable réelle dérivables deux fois et à dérivée… …   Wikipédia en Français

  • Itération De Householder — En analyse numérique, l itération de Householder ou méthode de Householder désigne un algorithme de recherche d un zéro d une fonction utilisé pour les fonctions d une variable réelle dérivables deux fois et à dérivée seconde continue (i.e. C2).… …   Wikipédia en Français

  • Itération de Householder — En analyse numérique, l itération de Householder ou méthode de Householder désigne un algorithme de recherche d un zéro d une fonction utilisé pour les fonctions d une variable réelle dérivables deux fois et à dérivée seconde continue (i.e. C2).… …   Wikipédia en Français

  • Itération de householder — En analyse numérique, l itération de Householder ou méthode de Householder désigne un algorithme de recherche d un zéro d une fonction utilisé pour les fonctions d une variable réelle dérivables deux fois et à dérivée seconde continue (i.e. C2).… …   Wikipédia en Français

  • Méthode de Householder — En analyse numérique, la méthode de Householder désigne un algorithme de recherche d un zéro d une fonction utilisé pour les fonctions d une variable réelle dérivables deux fois et à dérivée seconde continue (i.e. C2). L algorithme est itératif… …   Wikipédia en Français

  • Alston Scott Householder — (Rockford, Illinois, USA, 5 May 1904 – Malibu, California, USA, 4 July 1993) was an American mathematician who specialized in mathematical biology and numerical analysis, inventor of the Householder transformation and of Householder s method.… …   Wikipedia

  • Halley's method — In numerical analysis, Halley s method is a root finding algorithm used for functions of one real variable with a continuous second derivative, i.e. C2 functions. It is named after its inventor Edmond Halley who also discovered Halley s Comet.The …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”