In numerical analysis, Steffensen's method is an iterative method named after Johan Frederik Steffensen for numerical root-finding that is similar to the secant method and to Newton's method. Steffensen's method achieves a quadratic order of convergence without using derivatives, whereas the more familiar Newton's method also converges quadratically, but requires derivatives and the secant method does not require derivatives but also converges less quickly than quadratically. Steffensen's method has the drawback that it requires two function evaluations per step, whereas the secant method requires only one evaluation per step, so it is not necessarily most efficient in terms of computational cost, depending on the number of iterations each requires. Newton's method also requires evaluating two functions per step – for the function and for its derivative – and its computational cost varies between being at best the same as the secant method, and at worst the same as Steffensen's method. For most functions, calculation of the derivative is just as computationally costly as calculating the original function, and so the normal case is that Newton's method is equally costly as Steffensen's. Steffensen's method can be derived as an adaptation of Aitken's delta-squared process applied to fixed-point iteration. Viewed in this way, Steffensen's method naturally generalizes to efficient fixed-point calculation in general Banach spaces, whenever fixed points are guaranteed to exist and fixed-point iteration is guaranteed to converge, although possibly slowly, by the Banach fixed-point theorem.
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 f {\displaystyle f} ; that is, to find the real value x ⋆ {\displaystyle \ x_{\star }\ } that satisfies f ( x ⋆ ) = 0 . {\displaystyle \ f(x_{\star })=0~.} Near the solution x ⋆ , {\displaystyle \ x_{\star }\ ,} the derivative of the function, f ′ , {\displaystyle \ f'\ ,} needs to either exactly or very nearly satisfy − 1 < f ′ ( x ⋆ ) < 0 . {\displaystyle -1<f'(x_{\star })<0~.}
For some functions, Steffensen's method can work even if this condition is not met, but in such a case, the starting value x 0 {\displaystyle \ x_{0}\ } must be very close to the actual solution x ⋆ , {\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 x 0 , {\displaystyle \ x_{0}\ ,} a sequence of values x 0 , x 1 , x 2 , … , x n , … {\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 x ⋆ {\displaystyle \ x_{\star }\ } than the prior value. The value x n {\displaystyle \ x_{n}\ } from the current step generates the value x n + 1 {\displaystyle \ x_{n+1}\ } for the next step, via the formula
x n + 1 = x n − f ( x n ) g ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{g(x_{n})}}}
for n = 0 , 1 , 2 , 3 , . . . , {\displaystyle \ n=0,1,2,3,...\ ,} where the slope function g ( x ) {\displaystyle \ g(x)\ } is a composite of the original function f {\displaystyle \ f\ } given by the formula
… excerpt ends here. Continue reading the full article.
