Another derivation using mathematical induction
derivatives of the ![{\displaystyle D=1/f}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30791b82a097279a9c5c8d83d66c4ede3c0185a1)
Let's define a new function
. Then
By defferentiating
, that is,
![{\displaystyle -fD^{\prime }=Df^{\prime }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a391c6f54f4199f7149d3a046a642071035e3f1)
Differentiating multiple times, we get
![{\displaystyle -fD^{\prime \prime }=2D^{\prime }f^{\prime }+Df^{\prime \prime }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/574c7848ee8edbd80f5788af0d3e4c3e7cf4bf84)
![{\displaystyle -fD^{\prime \prime \prime }=3D^{\prime \prime }f^{\prime }+3D^{\prime }f^{\prime \prime }+Df^{\prime \prime \prime }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b51ecc8a97dac624b8818388b0546be22ee4639e)
![{\displaystyle -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 }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83e687758f294633047bff96696568a6703e8567)
The coefficients of the above equations are those of the Pascal's triangle. Taking
notation for the binomial coefficient, we would get
![{\displaystyle -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)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f93c60cdefd02db9e006ff96d09230906cbe9a18)
Though some of followings would not be used at the derivation,
let's expand some of above equations to see what forms they have,
![{\displaystyle -fD=-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65349da2664764c4805f2fa3de34af941eabb821)
![{\displaystyle -fD^{\prime }=f^{\prime }/f}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a477e1a6920ed799e8a9cb931bf643a988ac66d3)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11f6ce4367d198db0a73a63332713ff46d93516f)
![{\displaystyle -fD^{\prime \prime \prime }=(1/f^{3})(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90e2d5490c646ddbdac97a7df08b1f7b258e7e56)
![{\displaystyle -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 })}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb6e78958f77e1ae902d59888d1dd132242ff3e7)
...
Therefore
![{\displaystyle D=(-1/f)(-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30dcc371ff19a5262f62c3f9458acb08002aa43)
![{\displaystyle D^{\prime }=(-1/f^{2})f^{\prime }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/773f94d096556064e7986b00db89d1f08bc1bac4)
![{\displaystyle D^{\prime \prime }=(-1/f^{3})(-2{f^{\prime }}^{2}+ff^{\prime \prime })}](https://wikimedia.org/api/rest_v1/media/math/render/svg/094ab22015fcbd4d94ba1ccc01e36a5088da4ef9)
![{\displaystyle D^{\prime \prime \prime }=(-1/f^{4})(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7373a6c066dbd2a75ab5d715ef0bdf5b463bdd35)
![{\displaystyle 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 })}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d336ecf78a42088d36d0e704544d9ff728835473)
Relation with ![{\displaystyle f}](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
By the Taylor expansion, we get (assuming
)
![{\displaystyle 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}+...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1f936ce1a76adfd62479e25649506bd8169b51b)
where,
is the initial guess of the root of
.
Let approximate f(x) by dropping higher orders of the right hand side;
![{\displaystyle f(x)=f(x_{0})+f^{\prime }(x_{0})(x-x_{0})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b99eb44719aee3850514f31f9e03273dbe0ce2c0)
Then f(x) is approximated to a linear function, and now let's denote
is the point where
met
axis,
![{\displaystyle f(x_{1})=0=f(x_{0})+f^{\prime }(x_{0})(x_{1}-x_{0})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36d2b1b8e4652d1d46f76c6b24577e7f889681b7)
![{\displaystyle x_{1}=x_{0}-f(x_{0})/f^{\prime }(x_{0})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4679a3e478e334ca21f8c129d65ede2051b973e2)
This is the Newton's method.
Let's define
![{\displaystyle \Delta =x_{1}-x_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b38554b3835a280b14ff3eb4f0ff6f410019942)
Let's call above
as
or
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c899a9107ae0850b30b7967a8b974837d70e2ef)
Therefore the Newton's method is the first kind of Householder's method.
Now by taking three therms of the original Taylor series,
![{\displaystyle f(x_{1})=0=f(x_{0})+f^{\prime }(x_{0})\Delta +(1/2!)f^{\prime \prime }(x_{0}){\Delta }^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e0258aaa8d3973136352afb4a338f28d965b14f)
Therefore
![{\displaystyle \Delta =-f(x_{0})/(f^{\prime }(x_{0})+(1/2!)f^{\prime \prime }(x_{0})\Delta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb54cce2f2e5d3a8c8f9c5b18f5684471f1431b5)
and by substituting the
of the right hand side by
, we get
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0dcb2cf97e7cf4a7e8270a5dea9d13081f172b9)
This is the Halley's method. And Let's call
as
or
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/befa9963043d1e74494141661e9ccdf7324de330)
Therefore the Halley's method is the second kind of Householder's method.
As we progress, we get
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4756ed5e6b9db30c7a5ac436aaa5d9e7d1bb17b5)
This is the third kind of Householder's method.
![{\displaystyle \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 }}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7338a33509ddba29915291b45ee045c13af04162)
Now
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e451a3f725d2b812178bc774d84e8e17ea89604e)
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
is chosen.
The Padé approximation has the form
![{\displaystyle 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}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87b22ee71d563cb53ed370d226b855dd02cdef61)
where
is the initial guess, and
's and
are constants that are dependent on
and
.
Since
,
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
order,
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.
![{\displaystyle +{\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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f112b7450ef01dcb6d25e5f32505de2d82512fa5)
And
, let's calculate
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fac42a8e9034e0cac78b6fabd0d90c81ec511440)
This has to be the denominator of the Pade approximant of f(x) of d th order
of
, and
has to hold
.
Now, solving the last equation
,
![{\displaystyle 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})}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0fbdb02fbbde06ff533bed20ea0931c3d1edee9)
This implies the iteration formula
.