Another derivation using mathematical induction
derivatives of the
D
=
1
/
f
{\displaystyle D=1/f}
edit
Let's define a new function
D
=
1
/
f
(
x
)
{\displaystyle D=1/f(x)}
. Then
1
=
f
(
x
)
D
(
x
)
{\displaystyle 1=f(x)D(x)}
By defferentiating
0
=
f
′
(
x
)
D
(
x
)
+
f
(
x
)
D
′
(
x
)
{\displaystyle 0=f^{\prime }(x)D(x)+f(x)D^{\prime }(x)}
, that is,
−
f
D
′
=
D
f
′
{\displaystyle -fD^{\prime }=Df^{\prime }}
Differentiating multiple times, we get
−
f
D
′
′
=
2
D
′
f
′
+
D
f
′
′
{\displaystyle -fD^{\prime \prime }=2D^{\prime }f^{\prime }+Df^{\prime \prime }}
−
f
D
′
′
′
=
3
D
′
′
f
′
+
3
D
′
f
′
′
+
D
f
′
′
′
{\displaystyle -fD^{\prime \prime \prime }=3D^{\prime \prime }f^{\prime }+3D^{\prime }f^{\prime \prime }+Df^{\prime \prime \prime }}
−
f
D
′
′
′
′
=
4
D
′
′
′
f
′
+
6
D
′
′
f
′
′
+
4
D
′
f
′
′
′
+
D
f
′
′
′
′
{\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 }}
The coefficients of the above equations are those of the Pascal's triangle . Taking
C
(
n
,
k
)
{\displaystyle C(n,k)}
notation for the binomial coefficient , we would get
−
f
D
(
n
)
=
C
(
n
,
1
)
D
(
n
−
1
)
f
′
+
C
(
n
,
2
)
D
(
n
−
2
)
f
′
′
+
C
(
n
,
3
)
D
(
n
−
3
)
f
′
′
′
+
.
.
.
+
C
(
n
,
n
)
D
f
(
n
)
{\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)}}
Though some of followings would not be used at the derivation,
let's expand some of above equations to see what forms they have,
−
f
D
=
−
1
{\displaystyle -fD=-1}
−
f
D
′
=
f
′
/
f
{\displaystyle -fD^{\prime }=f^{\prime }/f}
−
f
D
′
′
=
2
D
′
f
′
+
f
′
′
D
=
2
(
−
f
′
/
f
2
)
f
′
+
f
′
′
/
f
=
(
1
/
f
2
)
(
−
2
f
′
2
+
f
f
′
′
)
{\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}}}
−
f
D
′
′
′
=
(
1
/
f
3
)
(
6
f
′
3
−
6
f
f
′
f
′
′
+
f
2
f
′
′
′
)
{\displaystyle -fD^{\prime \prime \prime }=(1/f^{3})(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })}
−
f
D
′
′
′
′
=
(
1
/
f
4
)
(
−
24
f
′
4
+
36
f
f
′
2
f
′
′
−
8
f
2
f
′
f
′
′
′
−
6
f
2
f
′
′
2
+
f
3
f
′
′
′
′
)
{\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 })}
...
Therefore
D
=
(
−
1
/
f
)
(
−
1
)
{\displaystyle D=(-1/f)(-1)}
D
′
=
(
−
1
/
f
2
)
f
′
{\displaystyle D^{\prime }=(-1/f^{2})f^{\prime }}
D
′
′
=
(
−
1
/
f
3
)
(
−
2
f
′
2
+
f
f
′
′
)
{\displaystyle D^{\prime \prime }=(-1/f^{3})(-2{f^{\prime }}^{2}+ff^{\prime \prime })}
D
′
′
′
=
(
−
1
/
f
4
)
(
6
f
′
3
−
6
f
f
′
f
′
′
+
f
2
f
′
′
′
)
{\displaystyle D^{\prime \prime \prime }=(-1/f^{4})(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })}
D
′
′
′
′
=
(
−
1
/
f
5
)
(
−
24
f
′
4
+
36
f
f
′
2
f
′
′
−
8
f
2
f
′
f
′
′
′
−
6
f
2
f
′
′
2
+
f
3
f
′
′
′
′
)
{\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 })}
Relation with
f
{\displaystyle f}
edit
By the Taylor expansion , we get (assuming
Δ
=
x
−
x
0
{\displaystyle \Delta =x-x_{0}}
)
f
(
x
)
=
f
(
x
0
)
+
f
′
(
x
0
)
Δ
+
(
1
/
2
!
)
f
′
′
(
x
0
)
Δ
2
+
(
1
/
3
!
)
f
′
′
′
(
x
0
)
Δ
3
+
.
.
.
{\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}+...}
where,
x
0
{\displaystyle x_{0}}
is the initial guess of the root of
f
(
x
)
=
0
{\displaystyle f(x)=0}
.
Let approximate f(x) by dropping higher orders of the right hand side;
f
(
x
)
=
f
(
x
0
)
+
f
′
(
x
0
)
(
x
−
x
0
)
{\displaystyle 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
{\displaystyle x_{1}}
is the point where
f
(
x
)
=
0
{\displaystyle f(x)=0}
met
x
{\displaystyle x}
axis,
f
(
x
1
)
=
0
=
f
(
x
0
)
+
f
′
(
x
0
)
(
x
1
−
x
0
)
{\displaystyle f(x_{1})=0=f(x_{0})+f^{\prime }(x_{0})(x_{1}-x_{0})}
x
1
=
x
0
−
f
(
x
0
)
/
f
′
(
x
0
)
{\displaystyle x_{1}=x_{0}-f(x_{0})/f^{\prime }(x_{0})}
This is the Newton's method .
Let's define
Δ
=
x
1
−
x
0
{\displaystyle \Delta =x_{1}-x_{0}}
Let's call above
Δ
{\displaystyle \Delta }
as
Δ
N
e
w
t
o
n
{\displaystyle {\Delta }_{Newton}}
or
Δ
(
1
)
{\displaystyle \Delta _{(1)}}
Δ
N
e
w
t
o
n
=
Δ
(
1
)
=
−
f
(
x
0
)
/
f
′
(
x
0
)
=
−
f
/
f
′
=
(
−
1
)
/
(
f
′
/
f
)
=
=
(
−
f
D
)
/
(
−
f
D
′
)
=
D
/
D
′
{\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}}}
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
′
(
x
0
)
Δ
+
(
1
/
2
!
)
f
′
′
(
x
0
)
Δ
2
{\displaystyle f(x_{1})=0=f(x_{0})+f^{\prime }(x_{0})\Delta +(1/2!)f^{\prime \prime }(x_{0}){\Delta }^{2}}
Therefore
Δ
=
−
f
(
x
0
)
/
(
f
′
(
x
0
)
+
(
1
/
2
!
)
f
′
′
(
x
0
)
Δ
{\displaystyle \Delta =-f(x_{0})/(f^{\prime }(x_{0})+(1/2!)f^{\prime \prime }(x_{0})\Delta }
and by substituting the
Δ
{\displaystyle \Delta }
of the right hand side by
Δ
N
e
w
t
o
n
{\displaystyle {\Delta }_{Newton}}
, we get
Δ
=
−
f
(
x
0
)
/
[
f
′
(
x
0
)
+
(
1
/
2
!
)
f
′
′
(
x
0
)
(
−
f
(
x
0
)
/
f
′
)
]
=
−
f
f
′
/
(
f
′
2
−
(
1
/
2
)
f
′
′
f
)
=
2
f
f
′
/
(
f
′
′
f
−
2
f
′
2
)
{\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}}}
This is the Halley's method . And Let's call
Δ
{\displaystyle \Delta }
as
Δ
H
a
l
l
e
y
{\displaystyle {\Delta }_{Halley}}
or
Δ
(
2
)
{\displaystyle \Delta _{(2)}}
Δ
H
a
l
l
e
y
=
Δ
(
2
)
=
2
f
f
′
/
(
f
′
′
f
−
2
f
′
2
)
=
2
(
f
′
/
f
)
/
[
(
1
/
f
2
)
(
f
′
′
f
−
2
f
′
2
)
]
=
2
(
−
f
D
′
)
/
(
−
f
D
′
′
)
=
2
D
′
/
D
′
′
{\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}}}
Therefore the Halley's method is the second kind of Householder's method.
As we progress, we get
Δ
(
3
)
=
(
−
f
)
/
[
f
′
+
(
1
/
2
!
)
f
′
′
Δ
H
a
l
l
e
y
+
(
1
/
3
!
)
f
′
′
′
Δ
H
a
l
l
e
y
Δ
N
e
w
t
o
n
]
=
(
−
f
)
/
[
f
′
+
(
1
/
2
!
)
f
′
′
(
2
D
′
/
D
′
′
)
+
(
1
/
3
!
)
f
′
′
′
(
2
D
′
/
D
′
′
)
(
D
/
D
′
)
]
=
(
−
3
f
)
/
[
3
f
′
+
3
f
′
′
(
D
′
/
D
′
′
)
+
f
′
′
′
(
D
/
D
′
′
)
]
=
(
−
3
f
D
′
′
)
/
[
3
f
′
D
′
′
+
3
f
′
′
D
′
+
f
′
′
′
D
]
=
(
−
3
f
D
′
′
)
/
(
−
f
D
′
′
′
)
=
3
D
′
′
/
D
′
′
′
{\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}}}
This is the third kind of Householder's method.
Δ
(
3
)
=
−
6
f
f
′
2
−
3
f
2
f
′
′
6
f
′
3
−
6
f
f
′
f
′
′
+
f
2
f
′
′
′
{\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 }}}}
Now
Δ
(
n
)
=
(
−
f
)
/
[
f
′
+
(
1
/
2
!
)
f
′
′
Δ
(
n
−
1
)
+
(
1
/
3
!
)
f
′
′
′
Δ
(
n
−
1
)
Δ
(
n
−
2
)
+
.
.
.
]
=
(
−
f
)
/
[
f
′
+
(
1
/
2
!
)
f
′
′
(
(
n
−
1
)
D
(
n
−
2
)
/
D
(
n
−
1
)
)
+
(
1
/
3
!
)
f
′
′
′
(
(
n
−
1
)
D
(
n
−
2
)
/
D
(
n
−
1
)
)
(
(
n
−
2
)
D
(
n
−
3
)
/
D
(
n
−
2
)
)
+
(
1
/
4
!
)
f
′
′
′
′
(
(
n
−
1
)
D
(
n
−
2
)
/
D
(
n
−
1
)
)
(
(
n
−
2
)
D
(
n
−
3
)
/
D
(
n
−
2
)
)
(
(
n
−
3
)
D
(
n
−
4
)
/
D
(
n
−
3
)
)
+
.
.
.
]
=
(
−
f
)
/
[
f
′
+
(
1
/
2
!
)
f
′
′
(
(
n
−
1
)
D
(
n
−
2
)
/
D
(
n
−
1
)
)
+
(
1
/
3
!
)
f
′
′
′
(
(
n
−
1
)
(
n
−
2
)
D
(
n
−
3
)
/
D
(
n
−
1
)
)
+
(
1
/
4
!
)
f
′
′
′
′
(
(
n
−
1
)
(
n
−
2
)
(
n
−
3
)
D
(
n
−
4
)
/
D
(
n
−
1
)
)
+
.
.
.
+
(
(
n
−
1
)
!
/
n
!
)
f
(
n
)
(
D
/
D
(
n
−
1
)
)
]
=
(
−
n
f
D
(
n
−
1
)
)
/
[
C
(
n
,
1
)
f
′
D
(
n
−
1
)
+
C
(
n
,
2
)
f
′
′
D
(
n
−
2
)
+
C
(
n
,
3
)
f
′
′
′
D
(
n
−
3
)
+
C
(
n
,
4
)
f
′
′
′
′
D
(
n
−
4
)
+
.
.
.
+
C
(
n
,
n
)
f
(
n
)
D
]
=
(
−
n
f
D
(
n
−
1
)
/
(
−
f
D
(
n
)
)
=
n
D
(
n
−
1
)
/
D
(
n
)
{\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}}}
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
{\displaystyle x-x_{1}}
is chosen.
The Padé approximation has the form
f
(
x
)
=
x
−
x
1
b
0
+
b
1
(
x
−
x
0
)
+
.
.
.
+
b
d
−
1
(
x
−
x
0
)
d
−
1
+
O
(
(
x
−
x
0
)
d
+
1
)
.
{\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}).}
where
x
0
{\displaystyle x_{0}}
is the initial guess, and
b
i
{\displaystyle b_{i}}
's and
x
1
{\displaystyle x_{1}}
are constants that are dependent on
x
0
{\displaystyle x_{0}}
and
f
(
x
)
{\displaystyle f(x)}
.
Since
f
(
x
1
)
=
0
{\displaystyle f(x_{1})=0}
,
x
1
{\displaystyle 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
{\displaystyle d}
order,
b
d
=
0
{\displaystyle 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
)
+
…
{\displaystyle (1/f)(x)=(1/f)(x_{0})+(1/f)'(x_{0})(x-x_{0})+\dots }
+
1
(
d
−
1
)
!
(
1
/
f
)
(
d
−
1
)
(
x
0
)
(
x
−
x
0
)
d
−
1
+
1
d
!
(
1
/
f
)
(
d
)
(
x
0
)
(
x
−
x
0
)
d
+
O
(
(
x
−
x
0
)
d
+
1
)
{\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})}
And
x
−
x
0
=
(
x
−
x
0
)
−
(
x
1
−
x
0
)
{\displaystyle x-x_{0}={(x-x_{0})-(x_{1}-x_{0})}}
, let's calculate
(
1
/
f
)
(
x
)
∗
(
(
x
−
x
0
)
−
(
x
1
−
x
0
)
)
=
−
(
1
/
f
)
(
x
0
)
∗
(
x
1
−
x
0
)
+
(
x
−
x
0
)
∗
[
(
1
/
f
)
(
x
0
)
−
(
1
/
f
)
′
(
x
0
)
(
x
1
−
x
0
)
]
+
(
x
−
x
0
)
2
∗
[
(
1
/
f
)
′
(
x
0
)
−
(
1
/
f
)
″
(
x
0
)
(
x
1
−
x
0
)
/
2
]
+
.
.
.
+
(
x
−
x
0
)
d
∗
[
(
1
/
f
)
(
d
−
1
)
(
x
0
)
/
(
d
−
1
)
!
−
(
1
/
f
)
(
d
)
(
x
0
)
(
x
1
−
x
0
)
/
(
d
!
)
]
+
O
(
(
x
−
x
0
)
d
+
1
)
{\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}}}
This has to be the denominator of the Pade approximant of f(x) of d th order
of
f
(
x
)
{\displaystyle f(x)}
, and
b
d
=
0
{\displaystyle b_{d}=0}
has to hold
0
=
b
d
=
(
1
/
f
)
(
d
−
1
)
(
x
0
)
1
(
d
−
1
)
!
−
(
1
/
f
)
(
d
)
(
x
0
)
1
d
!
∗
(
x
1
−
x
0
)
{\displaystyle 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
{\displaystyle x_{1}-x_{0}}
,
x
1
−
x
0
=
(
1
/
f
)
(
d
−
1
)
(
x
0
)
/
(
d
−
1
)
!
(
1
/
f
)
(
d
)
(
x
0
)
/
d
!
=
d
∗
(
1
/
f
)
(
d
−
1
)
(
x
0
)
(
1
/
f
)
(
d
)
(
x
0
)
{\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})}}}
This implies the iteration formula
x
n
+
1
=
x
n
+
d
(
1
/
f
)
(
d
−
1
)
(
x
n
)
(
1
/
f
)
(
d
)
(
x
n
)
{\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}
.