Steffensen's method

Newton-like root-finding algorithm that does not use derivatives

In numerical analysis, Steffensen's method is an iterative method for root-finding named after Johan Frederik Steffensen which is similar to Newton's method, but with certain situational advantages. In particular, Steffensen's method achieves similar quadratic convergence, but without using derivatives, as required for Newton's method.

Simple description

The simplest form of the formula for Steffensen's method occurs when it is used to find a zero of a real function ${\displaystyle \ f\,;}$ that is, to find the real value ${\displaystyle x_{\star }}$ that satisfies ${\displaystyle \ f(x_{\star })=0~.}$ Near the solution ${\displaystyle \ x_{\star }\,,}$ the function ${\displaystyle \ f\ }$ is supposed to approximately satisfy ${\displaystyle \ -1<f'(x_{\star })<0\,;}$ this condition makes ${\displaystyle \ f\ }$ adequate as a correction-function for ${\displaystyle ~x~}$ for finding its own solution, although it is not required to work efficiently. For some functions, Steffensen's method can work even if this condition is not met, but in such a case, the starting value ${\displaystyle \ x_{0}\ }$ must be very close to the actual solution ${\displaystyle \ x_{\star }\,,}$ and convergence to the solution may be slow. Adjustment of the size of the method's intermediate step, mentioned later, can improve convergence in some of these cases.

Given an adequate starting value ${\displaystyle \ x_{0}\,,}$ a sequence of values ${\displaystyle \ x_{0},\ x_{1},\ x_{2},\dots ,\ x_{n},\ \dots \ }$ can be generated using the formula below. When it works, each value in the sequence is much closer to the solution ${\displaystyle \ x_{\star }\ }$ than the prior value. The value ${\displaystyle \ x_{n}\ }$ from the current step generates the value ${\displaystyle \ x_{n+1}\ }$ for the next step, via this formula:^[1]

${\displaystyle \ x_{n+1}=x_{n}-{\frac {\,f(x_{n})\,}{g(x_{n})}}\ }$

for ${\displaystyle \ n=0,1,2,3,...\,;}$ where the slope function ${\displaystyle \ g(x)\ }$ is a composite of the original function ${\displaystyle \ f\ }$ given by the following formula:

${\displaystyle \ g(x)={\frac {\,f{\bigl (}x+f(x){\bigr )}\,}{f(x)}}-1\ }$

or perhaps more clearly,

${\displaystyle \ g(x)~=~{\frac {\ f(x+h)-f(x)\ }{h}}\ ~~\approx ~~{\frac {\ \operatorname {d} f(x)\ }{\operatorname {d} x}}~\equiv ~f'(x)\ ,}$

where ${\displaystyle \ h=f(x)\ }$ is a step-size between the last iteration point, ${\displaystyle \ x\ ,}$ and an auxiliary point located at ${\displaystyle \ x+h~.}$

Technically, the function ${\displaystyle \ g\ }$ is called the first-order divided difference of ${\displaystyle \ f\ }$ between those two points ( it is either a forward-type or backward-type divided difference, depending on the sign of ${\displaystyle \ h\ }$). Practically, it is the averaged value of the slope ${\displaystyle \ f'\ }$ of the function ${\displaystyle \ f\ }$ between the last sequence point ${\displaystyle \ \left(x,y\right)={\bigl (}x_{n},\ f\left(x_{n}\right){\bigr )}\ }$ and the auxiliary point at ${\displaystyle \ {\bigl (}x,y{\bigr )}={\bigl (}\ x_{n}+h,\ f\left(x_{n}+h\right)\ {\bigr )}\ ,}$ with step size (and direction) ${\displaystyle \ h=f(x_{n})~.}$

Because the value of ${\displaystyle \ g\ }$ is an approximation for ${\displaystyle \ f'\ ,}$ its value can optionally be checked to see if it meets the condition