User:Gauge00/Householder

Another derivation using mathematical induction

derivatives of the $D=1/f$

Let's define a new function $D=1/f(x)$. Then $1=f(x)D(x)$

By defferentiating

$0=f^{\prime }(x)D(x)+f(x)D^{\prime }(x)$, that is,

$-fD^{\prime }=Df^{\prime }$

Differentiating multiple times, we get

$-fD^{\prime \prime }=2D^{\prime }f^{\prime }+Df^{\prime \prime }$

$-fD^{\prime \prime \prime }=3D^{\prime \prime }f^{\prime }+3D^{\prime }f^{\prime \prime }+Df^{\prime \prime \prime }$

$-fD^{\prime \prime \prime \prime }=4D^{\prime \prime \prime }f^{\prime }+6D^{\prime \prime }f^{\prime \prime }+4D^{\prime }f^{\prime \prime \prime }+Df^{\prime \prime \prime \prime }$

The coefficients of the above equations are those of the Pascal's triangle. Taking $C(n,k)$ notation for the binomial coefficient, we would get

$-fD^{(n)}=C(n,1)D^{(n-1)}f^{\prime }+C(n,2)D^{(n-2)}f^{\prime \prime }+C(n,3)D^{(n-3)}f^{\prime \prime \prime }+...+C(n,n)Df^{(n)}$

Though some of followings would not be used at the derivation, let's expand some of above equations to see what forms they have,

$-fD=-1$

$-fD^{\prime }=f^{\prime }/f$

${\begin{array}{rl}-fD^{\prime \prime }=&2D^{\prime }f^{\prime }+f^{\prime \prime }D\\=&2\left(-f^{\prime }/{f^{2}}\right)f^{\prime }+f^{\prime \prime }/f\\=&\left(1/f^{2}\right)\left(-2{f^{\prime }}^{2}+ff^{\prime \prime }\right)\end{array}}$

$-fD^{\prime \prime \prime }=(1/f^{3})(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })$

$-fD^{\prime \prime \prime \prime }=(1/f^{4})(-24{f^{\prime }}^{4}+36f{f^{\prime }}^{2}f^{\prime \prime }-8f^{2}f^{\prime }f^{\prime \prime \prime }-6f^{2}{f^{\prime \prime }}^{2}+f^{3}f^{\prime \prime \prime \prime })$

...

Therefore

$D=(-1/f)(-1)$

$D^{\prime }=(-1/f^{2})f^{\prime }$

$D^{\prime \prime }=(-1/f^{3})(-2{f^{\prime }}^{2}+ff^{\prime \prime })$

$D^{\prime \prime \prime }=(-1/f^{4})(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })$

$D^{\prime \prime \prime \prime }=(-1/f^{5})(-24{f^{\prime }}^{4}+36f{f^{\prime }}^{2}f^{\prime \prime }-8f^{2}f^{\prime }f^{\prime \prime \prime }-6f^{2}{f^{\prime \prime }}^{2}+f^{3}f^{\prime \prime \prime \prime })$

Relation with $f$

By the Taylor expansion, we get (assuming $\Delta =x-x_{0}$ )

$f(x)=f(x_{0})+f^{\prime }(x_{0})\Delta +(1/2!)f^{\prime \prime }(x_{0}){\Delta }^{2}+(1/3!)f^{\prime \prime \prime }(x_{0}){\Delta }^{3}+...$

where, $x_{0}$ is the initial guess of the root of $f(x)=0$.

Let approximate f(x) by dropping higher orders of the right hand side;

$f(x)=f(x_{0})+f^{\prime }(x_{0})(x-x_{0})$

Then f(x) is approximated to a linear function, and now let's denote $x_{1}$ is the point where $f(x)=0$ met $x$ axis,

$f(x_{1})=0=f(x_{0})+f^{\prime }(x_{0})(x_{1}-x_{0})$

$x_{1}=x_{0}-f(x_{0})/f^{\prime }(x_{0})$

This is the Newton's method.

Let's define

$\Delta =x_{1}-x_{0}$

Let's call above $\Delta$ as ${\Delta }_{Newton}$ or $\Delta _{(1)}$

${\begin{array}{rl}{\Delta }_{Newton}=\Delta _{(1)}=&-f(x_{0})/f^{\prime }(x_{0})=-f/f^{\prime }=(-1)/(f^{\prime }/f)=\\[0.7em]=&(-fD)/(-fD^{\prime })=D/D^{\prime }\end{array}}$

Therefore the Newton's method is the first kind of Householder's method.

Now by taking three therms of the original Taylor series,

$f(x_{1})=0=f(x_{0})+f^{\prime }(x_{0})\Delta +(1/2!)f^{\prime \prime }(x_{0}){\Delta }^{2}$

Therefore

$\Delta =-f(x_{0})/(f^{\prime }(x_{0})+(1/2!)f^{\prime \prime }(x_{0})\Delta$

and by substituting the $\Delta$ of the right hand side by ${\Delta }_{Newton}$, we get

${\begin{array}{rl}\Delta =&-f(x_{0})/\left[f^{\prime }(x_{0})+(1/2!)f^{\prime \prime }(x_{0})(-f(x_{0})/f^{\prime })\right]\\[0.7em]=&-ff^{\prime }/({f^{\prime }}^{2}-(1/2)f^{\prime \prime }f)\\[0.7em]=&2ff^{\prime }/(f^{\prime \prime }f-2{f^{\prime }}^{2})\end{array}}$

This is the Halley's method. And Let's call $\Delta$ as ${\Delta }_{Halley}$ or $\Delta _{(2)}$

${\begin{array}{rl}{\Delta }_{Halley}=\Delta _{(2)}=&2ff^{\prime }/(f^{\prime \prime }f-2{f^{\prime }}^{2})\\[0.7em]=&2(f^{\prime }/f)/\left[(1/f^{2})(f^{\prime \prime }f-2{f^{\prime }}^{2})\right]\\[0.7em]=&2(-fD^{\prime })/(-fD^{\prime \prime })=2D^{\prime }/D^{\prime \prime }\\[0.7em]\end{array}}$

Therefore the Halley's method is the second kind of Householder's method.

As we progress, we get

${\begin{array}{rl}\Delta _{(3)}=&(-f)/\left[f^{\prime }+(1/2!)f^{\prime \prime }{\Delta }_{Halley}+(1/3!)f^{\prime \prime \prime }{\Delta }_{Halley}{\Delta }_{Newton}\right]\\[0.7em]=&(-f)/\left[f^{\prime }+(1/2!)f^{\prime \prime }(2D^{\prime }/D^{\prime \prime })+(1/3!)f^{\prime \prime \prime }(2D^{\prime }/D^{\prime \prime })(D/D^{\prime })\right]\\[0.7em]=&(-3f)/\left[3f^{\prime }+3f^{\prime \prime }(D^{\prime }/D^{\prime \prime })+f^{\prime \prime \prime }(D/D^{\prime \prime })\right]\\[0.7em]=&(-3fD^{\prime \prime })/\left[3f^{\prime }D^{\prime \prime }+3f^{\prime \prime }D^{\prime }+f^{\prime \prime \prime }D\right]\\[0.7em]=&(-3fD^{\prime \prime })/(-fD^{\prime \prime \prime })\\[0.7em]=&3D^{\prime \prime }/D^{\prime \prime \prime }\\[0.7em]\end{array}}$

This is the third kind of Householder's method.

$\Delta _{(3)}=-{\frac {6f{f^{\prime }}^{2}-3f^{2}f^{\prime \prime }}{6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime }}}$

Now

${\begin{array}{rl}\Delta _{(n)}=&(-f)/\left[f^{\prime }+(1/2!)f^{\prime \prime }{\Delta }_{(n-1)}+(1/3!)f^{\prime \prime \prime }{\Delta }_{(n-1)}{\Delta }_{(n-2)}+...\right]\\[0.7em]=&(-f)/\left[f^{\prime }+(1/2!)f^{\prime \prime }((n-1)D^{(n-2)}/D^{(n-1)})+(1/3!)f^{\prime \prime \prime }((n-1)D^{(n-2)}/D^{(n-1)})((n-2)D^{(n-3)}/D^{(n-2)})+(1/4!)f^{\prime \prime \prime \prime }((n-1)D^{(n-2)}/D^{(n-1)})((n-2)D^{(n-3)}/D^{(n-2)})((n-3)D^{(n-4)}/D^{(n-3)})+...\right]\\[0.7em]=&(-f)/\left[f^{\prime }+(1/2!)f^{\prime \prime }((n-1)D^{(n-2)}/D^{(n-1)})+(1/3!)f^{\prime \prime \prime }((n-1)(n-2)D^{(n-3)}/D^{(n-1)})+(1/4!)f^{\prime \prime \prime \prime }((n-1)(n-2)(n-3)D^{(n-4)}/D^{(n-1)})+...+((n-1)!/n!)f^{(n)}(D/D^{(n-1)})\right]\\[0.7em]=&(-nfD^{(n-1)})/\left[C(n,1)f^{\prime }D^{(n-1)}+C(n,2)f^{\prime \prime }D^{(n-2)}+C(n,3)f^{\prime \prime \prime }D^{(n-3)}+C(n,4)f^{\prime \prime \prime \prime }D^{(n-4)}+...+C(n,n)f^{(n)}D\right]\\[0.7em]=&(-nfD^{(n-1)}/(-fD^{(n)})\\[0.7em]=&nD^{(n-1)}/D^{(n)}\\[0.7em]\end{array}}$

Derivation

Following is not Gauge00's derivation, it is from the original derivation Householder's method.

An exact derivation of the Householder's methods starts from the Padé approximation of order (d+1), where the approximant with linear numerator of the form $x-x_{1}$ is chosen.

The Padé approximation has the form

$f(x)={\frac {x-x_{1}}{b_{0}+b_{1}(x-x_{0})+...+b_{d-1}(x-x_{0})^{d-1}}}+O((x-x_{0})^{d+1}).$

where $x_{0}$ is the initial guess, and $b_{i}$'s and $x_{1}$ are constants that are dependent on $x_{0}$ and $f(x)$ .

Since $f(x_{1})=0$, $x_{1}$ will be used as the second guess,

In Pade approximant, the degrees of numerator and denominator polynomials have to add to the order of the approximant. Therefore, in our approximation of $d$ order, $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.

$(1/f)(x)=(1/f)(x_{0})+(1/f)'(x_{0})(x-x_{0})+\dots$

$+{\frac {1}{(d-1)!}}(1/f)^{(d-1)}(x_{0}){(x-x_{0})}^{d-1}+{\frac {1}{d!}}(1/f)^{(d)}(x_{0}){(x-x_{0})}^{d}+O((x-x_{0})^{d+1})$

And $x-x_{0}={(x-x_{0})-(x_{1}-x_{0})}$, let's calculate

${\begin{array}{rl}(1/f)(x)*&((x-x_{0})-(x_{1}-x_{0}))\\[0.5em]=&-(1/f)(x_{0})*(x_{1}-x_{0})\\[0.5em]+&(x-x_{0})*\left[(1/f)(x_{0})-(1/f)'(x_{0})(x_{1}-x_{0})\right]\\[0.5em]+&(x-x_{0})^{2}*[(1/f)'(x_{0})-(1/f)''(x_{0})(x_{1}-x_{0})/2]\\[0.5em]+&...\\[0.5em]+&(x-x_{0})^{d}*[(1/f)^{(d-1)}(x_{0})/(d-1)!-(1/f)^{(d)}(x_{0})(x_{1}-x_{0})/(d!)]\\[0.5em]+&O((x-x_{0})^{d+1})\end{array}}$

This has to be the denominator of the Pade approximant of f(x) of d th order of $f(x)$, and $b_{d}=0$ has to hold

$0=b_{d}=(1/f)^{(d-1)}(x_{0}){\frac {1}{(d-1)!}}-(1/f)^{(d)}(x_{0}){\frac {1}{d!}}*(x_{1}-x_{0})$.

Now, solving the last equation $x_{1}-x_{0}$,

$x_{1}-x_{0}={\frac {(1/f)^{(d-1)}(x_{0})/(d-1)!}{(1/f)^{(d)}(x_{0})/d!}}=d*{\frac {(1/f)^{(d-1)}(x_{0})}{(1/f)^{(d)}(x_{0})}}$

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})}}$.