Steffensen's method

In numerical analysis, Steffensen's method is a root-finding technique named after Johan Frederik Steffensen which is similar to Newton's method. Steffensen's method also achieves quadratic convergence, but without using derivatives as Newton's method does.

Simple descriptionEdit

The simplest form of the formula for Steffensen's method occurs when it is used to find the zeros, or roots, of a function   that is: To find the value   that satisfies   Near the solution   the function   is supposed to approximately satisfy   this condition makes   adequate as a correction-function for   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   must be very close to the actual solution   and convergence to the solution may be slow.

Given an adequate starting value   a sequence of values   can be generated using the formula below. When it works, each value in the sequence is much closer to the solution   than the prior value. The value   from the current step generates the value   for the next step, via this formula:[1]


for   where the slope function   is a composite of the original function   given by the following formula:


or perhaps more clearly,


where   is a step-size between the last iteration point, x, and an auxiliary point located at  

The function   is the average value for the slope of the function   between the last sequence point   and the auxiliary point   with the step   It is also called the first-order divided difference of   between those two points.

It is only for the purpose of finding   for this auxiliary point that the value of the function   must be an adequate correction to get closer to its own solution, and for that reason fulfill the requirement that   For all other parts of the calculation, Steffensen's method only requires the function   to be continuous and to actually have a nearby solution.[1] Several modest modifications of the step   in the slope calculation   exist to accommodate functions   that do not quite meet the requirement.

Advantages and drawbacksEdit

The main advantage of Steffensen's method is that it has quadratic convergence[1] like Newton's method – that is, both methods find roots to an equation   just as 'quickly'. In this case quickly means that for both methods, the number of correct digits in the answer doubles with each step. But the formula for Newton's method requires evaluation of the function's derivative   as well as the function   while Steffensen's method only requires   itself. This is important when the derivative is not easily or efficiently available.

The price for the quick convergence is the double function evaluation: Both   and   must be calculated, which might be time-consuming if   is a complicated function. For comparison, the secant method needs only one function evaluation per step. The secant method increases the number of correct digits by "only" a factor of roughly 1.6 per 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,[a] when both algorithms succeed, the secant method actually converges faster than Steffensen's method in practical use: The secant method achieves a factor of about (1.6)2 ≈ 2.6 times as many digits for every two steps (two function evaluations), compared to Steffensen's factor of 2 for every one step (two function evaluations).

Similar to most other iterative root-finding algorithms, the crucial weakness in Steffensen's method is the choice of the starting value   If the value of   is not 'close enough' to the actual solution   the method may fail and the sequence of values   may either flip-flop between two extremes, or diverge to infinity, or both.

Derivation using Aitken's delta-squared processEdit

The version of Steffensen's method implemented in the MATLAB code shown below can be found using the Aitken's delta-squared process for accelerating convergence of a sequence. To compare the following formulae to the formulae in the section above, notice that   This method assumes starting with a linearly convergent sequence and increases the rate of convergence of that sequence. If the signs of   agree and   is 'sufficiently close' to the desired limit of the sequence   we can assume the following:






and hence


Solving for the desired limit of the sequence   gives:


which results in the more rapidly convergent sequence:


Code exampleEdit

In MatlabEdit

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

function Steffensen(f,p0,tol)
% This function takes as inputs: a fixed point iteration function, f, 
% and initial guess to the fixed point, p0, and a tolerance, tol.
% The fixed point iteration function is assumed to be input as an
% inline function. 
% This function will calculate and return the fixed point, p, 
% that makes the expression f(x) = p true to within the desired 
% tolerance, tol.

format compact % This shortens the output.
format long    % This prints more decimal places.

for i=1:1000   % get ready to do a large, but finite, number of iterations.
               % This is so that if the method fails to converge, we won't
               % be stuck in an infinite loop.
    p1=f(p0);  % calculate the next two guesses for the fixed point.
    p=p0-(p1-p0)^2/(p2-2*p1+p0) % use Aitken's delta squared method to
                                % find a better approximation to p0.
    if abs(p-p0)<tol  % test to see if we are within tolerance.
        break         % if we are, stop the iterations, we have our answer.
    p0=p;              % update p0 for the next iteration.
if abs(p-p0)>tol       % If we fail to meet the tolerance, we output a
                       % message of failure.
    'failed to converge in 1000 iterations.'

In PythonEdit

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

from typing import Callable, Iterator
Func = Callable[[float], float]

def g(f: Func, x: float, fx: float) -> Func:
    """First-order divided difference function.

        f: Function input to g
        x: Point at which to evaluate g
        fx: Function f evaluated at x 
    return lambda x: f(x + fx) / fx - 1

def steff(f: Func, x: float) -> Iterator[float]:
    """Steffenson algorithm for finding roots.

    This recursive generator yields the x_{n+1} value first then, when the generator iterates,
    it yields x_{n+2} from the next level of recursion.

        f: Function whose root we are searching for
        x: Starting value upon first call, each level n that the function recurses x is x_n
    while True:    
        fx = f(x)
        gx = g(f, x, fx)(x)
        if gx == 0:
            x = x - fx / gx    # Update to x_{n+1}
            yield x            # Yield value


Steffensen's method can also be used to find an input   for a different kind of function   that produces output the same as its input:   for the special value   Solutions like   are called fixed points. 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.

For orientation, the root function   and the fixed-point functions are simply related by   where   is some scalar constant small enough in magnitude to make   stable under iteration, but large enough for the non-linearity of the function   to be appreciable. All issues of a more general Banach space vs. basic real numbers being momentarily ignored for the sake of the comparison.

This method for finding fixed points of a real-valued function has been generalised for functions   that map a Banach space   onto itself or even more generally   that map from one Banach space   into another Banach space   The generalized method assumes that a family of bounded linear operators   associated with   and   can be devised that (locally) satisfies that condition.[2]

 eqn. (𝄋)

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


Which may provide some insight. (The quotient form is shown for orientation; it is not required per se.) Expressed in this way, the linear operator   can be more easily seen to be an elaborate version of the divided difference   discussed in the first section, above. Note that the division is not necessary; the only requirement is that the operator   satisfy the equation marked with the segno, (𝄋).

For the basic real number function  , given in the first section, the function simply takes in and puts out real numbers. There, the function   is a divided difference. In the generalized form here, the operator   is the analogue of a divided difference for use in the Banach space. The operator   is roughly equivalent to a matrix whose entries are all functions of vector arguments   and  .

Steffensen's method is then very similar to the Newton's method, except that it uses the divided difference   instead of the derivative   Note that for fixed point functions,   and for linear operators   meeting the marked (𝄋) condition,   where   is the identity operator.

The generalized iteration formula is given by



If the operator   satisfies


for some constant   then the method converges quadratically to a fixed point of   if the initial approximation   is 'sufficiently close' to the desired solution   that satisfies  


  1. ^ Because   requires the prior calculation of   the two evaluations must be done sequentially – the algorithm per se cannot be made faster by running the function evaluations in parallel. This is yet another disadvantage of Steffensen's method.


  1. ^ a b c Dahlquist, Germund; Björck, Åke (1974). Numerical Methods. Translated by Anderson, Ned. Englewood Cliffs, NJ: Prentice Hall. pp. 230–231.
  2. ^ Johnson, L.W.; Scholz, D.R. (June 1968). "On Steffensen's method". SIAM Journal on Numerical Analysis. 5 (2): 296–302. doi:10.1137/0705026. JSTOR 2949443.