Householder process

The Householder methods are a group of numerical methods for determining the zeros of a scalar real function. They are named after Alston Scott Householder .

Description of the procedure

Let be a natural number and an at least -fold continuously differentiable function that has a single zero in the interval , i.e. H. . Be a starting value close enough to . Then the converges through the iteration ${\displaystyle d}$ ${\displaystyle f\colon I\subset \mathbb {R} \to \mathbb {R} }$ ${\displaystyle (d+1)}$ ${\displaystyle I}$ ${\displaystyle a}$ ${\displaystyle f'(a)\neq 0}$ ${\displaystyle x_{0}}$ ${\displaystyle a}$

${\displaystyle x_{k+1}=x_{k}+d{\frac {(1/f)^{(d-1)}(x_{k})}{(1/f)^{(d)}(x_{k})}}\quad {\text{mit }}k=0,1,2,\dots }$

generated sequence of successive approximations with order of convergence against . That is, there is a constant with ${\displaystyle (x_{k})_{k\in \mathbb {N} }}$ ${\displaystyle d+1}$ ${\displaystyle a}$ ${\displaystyle K>0}$

${\displaystyle |x_{k+1}-a|\leq K\cdot |x_{k}-a|^{d+1}}$.

For the Newton method results , for the Halley method . ${\displaystyle d=1}$ ${\displaystyle d=2}$

motivation

If there is a simple zero in , there is a -fold continuously differentiable function with and . The reciprocal function has a pole of order in . It is obvious that the Taylor expansion of in is dominated by this pole, ${\displaystyle f}$ ${\displaystyle a}$ ${\displaystyle d}$ ${\displaystyle g}$ ${\displaystyle g(a)=f'(a)\neq 0}$ ${\displaystyle f(x)=g(x)(x-a)}$ ${\displaystyle {\frac {1}{f}}}$ ${\displaystyle 1}$ ${\displaystyle a}$ ${\displaystyle x}$ ${\displaystyle a}$ ${\displaystyle {\frac {1}{f}}}$ ${\displaystyle x}$

${\displaystyle {\begin{aligned}(1/f)(x+h)&=\sum _{k=0}^{d}(1/f)^{(k)}(x){\frac {h^{k}}{k!}}+{\mathcal {O}}(h^{d+1})\\[1em]={\frac {1}{g(x+h)(x+h-a)}}&={\frac {1}{g(x+h)(a-x)}}\sum _{k=0}^{d}\left({\frac {h}{a-x}}\right)^{k}+{\mathcal {O}}(h^{d+1})\end{aligned}}}$

If one considers it to be slowly changing to almost constant , then the Taylor coefficients are inversely proportional to the powers of , that is ${\displaystyle g(x+h)}$ ${\displaystyle f^{\prime }(a)}$ ${\displaystyle x-a}$

${\displaystyle {\begin{aligned}&(1/f)^{(k)}(x)\approx {\frac {k!}{f'(a)\,(a-x)^{k+1}}}\\\implies &{\frac {(1/f)^{(k-1)}(x)}{(1/f)^{(k)}(x)}}\approx {\frac {a-x}{k}}\\\implies &a\approx x+k{\frac {(1/f)^{(k-1)}(x)}{(1/f)^{(k)}(x)}}\end{aligned}}}$

For ${\displaystyle k=1,\ldots ,d.}$

example

The polynomial equation used by Newton to demonstrate his method was . In a first step it was observed that there must be a zero point close by. By inserting you only get ${\displaystyle x^{3}-2x-5=0}$ ${\displaystyle x=2}$ ${\displaystyle x=2+h}$

${\displaystyle f(2+h)=-1+10h+6h^{2}+h^{3}}$

and then by inverting this polynomial as a Taylor series

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

The result of the first step of the Householder method of a given order is also obtained by dividing the coefficient of the degree by its left neighbor in this expansion. This gives the following approximations of increasing order ${\displaystyle d}$ ${\displaystyle d}$

d	x 1 = 2 +
1	0.1 00000000000000000000000000000000
2	0.094 339622641509433962264150943396
3	0.09455 8429973238180196253345227476
4th	0.094551 282051282051282051282051282
5	0.09455148 6538216154140615031261963
6th	0.094551481 438752142436492263099119
7th	0.09455148154 3746895938379484125813
8th	0.0945514815423 36756233561913325371
9	0.09455148154232 4837086869382419375
10	0.094551481542326 678478801765822985

In this example, there are slightly more than valid decimal places for the first step in the order procedure ${\displaystyle d}$ ${\displaystyle d.}$

swell

• Alston Scott Householder, Numerical Treatment of a Single Nonlinear Equation , McGraw Hill Text, New York , 1970. ISBN 0-07-030465-3
• Newton's method and high order iterations , Pascal Sebah and Xavier Gourdon, 2001 (A Postscript version with the correct formula is linked on the page.)