Steffensen's method

In numerical analysis, Steffensen's method is a root-finding method. It is similar to Newton's method and it also achieves quadratic convergence, but it does not use derivatives. The method is named after Johan Frederik Steffensen.

Simple Description

The simplest form of the formula for Steffensen's method occurs when it is used to find the zeros of a function ${\displaystyle f}$ , that is, to find the input value ${\displaystyle x}$  that satisifies ${\displaystyle f(x)=0}$  . Given an adequate starting value ${\displaystyle x_{0}}$ , a sequence of values ${\displaystyle x_{0},\ x_{1},\ x_{2},\ ...,\ x_{n}...}$  can be generated. Each value in the sequence is closer to the solution than the prior value, and the value ${\displaystyle x_{n}}$  from the prior step generates the next step, ${\displaystyle x_{n+1}}$  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 auxilliary function ${\displaystyle g(x_{n})}$  is a combination of the original function ${\displaystyle f}$  given by the following formula:

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

The function ${\displaystyle g}$  is the average slope of the function ${\displaystyle f}$  between the last sequence point ${\displaystyle x=x_{n},\ y=f(x_{n})}$  and the auxilliary point ${\displaystyle x=x_{n}+f(x_{n}),\ y=f(x_{n}+f(x_{n}))}$  .

The main advantage of Steffensen's method is that it can find the roots of an equation ${\displaystyle f}$  just as "quickly" as Newton's method but the formula does not require a separate function for the derivative, so it can be programmed for any generic function. In this case quicly means that the number of correct digits in the answer doubles with each step. The cost, however is the double function evaluation: both ${\displaystyle f(x_{n})}$  and ${\displaystyle f(x_{n}+f(x_{n}))}$  must be evaluated.

Similar to Newton's method and most other quadratically convergent methods, the crucial weakness with the method is the choice of the starting value ${\displaystyle x_{0}}$  . If the value of ${\displaystyle x_{0}}$  is not "close enough" to the actual solution, the method will fail and the sequence of values ${\displaystyle x_{0},x_{1},x_{2},x_{3},...}$  will either flip flop between two extremes, or diverge to infinity (possibly both!).

Generalised definition

Steffensen's method finds fixed points of a mapping ƒ. In the original definition, ƒ was supposed to be a real function, but the method has been generalised for functions ${\displaystyle f:X\to X}$  on a Banach space ${\displaystyle X}$ .

The method assumes that a family ${\displaystyle \{F(x',x''):x',x''\in X\}}$  of bounded linear operators (called divided difference) associated with x' and x'' is known which satisfies^[2]

${\displaystyle f(x')-f(x'')=F(x',x'')(x'-x'').\,}$ 

Steffensen's method is then very similar to the Newton's method, except that it uses the divided difference${\displaystyle F(f(x),x)}$  instead of the derivative ${\displaystyle Df(x)}$ . It is thus defined by

${\displaystyle x_{k+1}=x_{k}+[I-F(f(x_{k}),x_{k})]^{-1}(f(x_{k})-x_{k}),\,}$ 

for k = 1, 2, 3, ... . If the operator F satisfies

${\displaystyle \|F(x',x'')-F(y',y'')\|\leq K{\big (}\|x'-y'\|+\|x''-y''\|{\big )}}$ 

for some constant K, then the method converges quadratically to a fixed point of ƒ if the initial approximation ${\displaystyle x_{0}}$  is sufficiently close to the desired solution ${\displaystyle \xi }$ , that satisifies ${\displaystyle \xi =f(\xi )}$ .

References

1. Germund Dahlquist, Åke Björck, tr. Ned Anderson (1974) Numerical Methods, pp. 230-231, Prentice Hall, Englewood Cliffs, NJ
2. L. W. Johnson; D. R. Scholz (1968) On Steffensen's Method, SIAM Journal on Numerical Analysis (June 1968), vol. 5, no. 2., pp. 296-302. Stable URL: [1]