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 must be very 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.

for the next step, via the formula

given by the formula

or perhaps more clearly,

is called the first-order divided difference between those two points

which is required to guarantee convergence of Steffensen's algorithm. Although slight non-conformance may not necessarily be dire, any large departure from the condition warns that Steffensen's method is liable to fail, and temporary use of some fallback algorithm is warranted (e.g. the more robust Illinois algorithm, or plain regula falsi).

to be continuous and to actually have a nearby solution. exist, such as multiplying it by or that do not quite meet the requirement.

Advantages and drawbacks

The main advantage of Steffensen's method is that it has quadratic convergence like Newton's method just as "quickly". In this case, quickly itself. This is important when the derivative is not easily or efficiently available.

is complicated. For comparison, both regula falsi and the secant method only need one function evaluation per step. The secant method increases the number of correct digits by "only" a factor of roughly 1.6per step, but one can do twice as many steps of the secant method within a given time. Since the secant method can carry out twice as many steps in the same time as Steffensen's method, in practical use the secant method actually converges faster than Steffensen's method, when both algorithms succeed: The secant method achieves a factor of about as many digits for every two steps (two function evaluations), compared to Steffensen's factor of for every one step (two function evaluations).

Similar to most other iterative root-finding algorithms may either erratically flip-flop between two (or more) extremes, or diverge to infinity, or both.

Derivation using Aitken's delta-squared process

The version of Steffensen's method implemented in the MATLAB code shown below can be found using Aitken's delta-squared process for convergence acceleration, then we can assume

so that

gives:

which results in the more rapidly convergent sequence:

Code example

In Matlab

Here is the source for an implementation of Steffensen's Method in MATLAB.

In Python

Here is the source for an implementation of Steffensen's method in Python.

Generalization to Banach space

are called fixed pointss. Many of these functions can be used to find their own solutions by repeatedly recycling the result back as input, but the rate of convergence can be slow, or the function can fail to converge at all, depending on the individual function. Steffensen's method accelerates this convergence, to make it quadratic.

Momentarily ignoring the issues of a more general Banach space vs. basic real numbers for the sake of an example: To re-orient the reader to the earlier section, a simple toy model stable under iteration, but large enough for the non-linearity to be appreciable.

This method for finding fixed points of a real-valued function that map a Banach space that map from one Banach space into another Banach space The generalized method assumes that a family of bounded linear operators can be devised that (locally) satisfies the condition

is roughly equivalent to a matrix whose entries are all functions of vector arguments Refer again back to the simple function is a divided difference is the analogue of a divided difference for use in the Banach space.

If division is possible in the Banach space can be obtained from

can be more easily seen to be an elaborate version of the divided difference discussed in the first section, above. The quotient form is shown here for orientation only; it is not required per se satisfy ().

meeting condition ( is the identity operator.

In the case that division is possible in the Banach space, the generalized iteration formula is given by

for which

to the somewhat reduced form

. However, the second form may not be as numerically stable

satisfies

Notes

References