Steffensen's method

From Wikipedia, the free encyclopedia

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.

[edit] 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 f : X \to X on a Banach space X.

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

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 this operator instead of the derivative Df(x). It is thus defined by

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

If F satisfies

\|F(x,x')-F(y,y')\| \le 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 x0 is sufficiently good.

[edit] References

  • "On Steffensen's Method", L. W. Johnson; D. R. Scholz, SIAM Journal on Numerical Analysis, Vol. 5, No. 2. (Jun., 1968), pp. 296-302. Stable URL: [1]