Steffensen's method

The simplest form of the formula for Steffensen's method occurs when it is used to find a zero of a real function $f$; that is, to find the real value $x\_\backslash star$ that satisfies $f(x\_\backslash star)\; =\; 0$. Near the solution $x\_\backslash star$, the derivative of the function, $f\text{'}$, is supposed to approximately satisfy ; this condition ensures that $f$ is an adequate correction-function for $x$, 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 $x\_0$ must be very close to the actual solution $x\_\backslash 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$, a sequence of values $x\_0,\backslash \; x\_1,\backslash \; x\_2,\backslash \; \backslash dots,\backslash \; x\_n,\backslash \; \backslash dots$ can be generated using the formula below. When it works, each value in the sequence is much closer to the solution $x\_\backslash star$ than the prior value. The value $x\_n$ from the current step generates the value $x\_\{n+1\}$ for the next step, via the formula

:$x\_\{n+1\}\; =\; x\_n\; -\; \backslash frac\{f(x\_n)\}\{g(x\_n)\}$

for $n\; =\; 0,\; 1,\; 2,\; 3,\; ...$, where the slope function $g(x)$ is a composite of the original function $f$ given by the formula

:$g(x)\; =\; \backslash frac\{f\backslash bigl(\; x\; +\; f(x)\; \backslash bigr)\}\{f(x)\}\; -\; 1$

or perhaps more clearly,

:$g(x)\; =\; \backslash frac\{f(x\; +\; h)\; -\; f(x)\}\{h\}\; \backslash approx\; \backslash frac\{\backslash operatorname\{d\}f(\; x\; )\}\{\; \backslash operatorname\{d\}x\; \}\; \backslash equiv\; f\text{'}(\; x\; ),$

where $h\; =\; f(x)$ is a step-size between the last iteration point, $x$, and an auxiliary point located at $x\; +\; h$.

Technically, the function $g$ is called the first-order divided difference of $f$ between those two points (it is either a forward-type or backward-type divided difference, depending on the sign {{nobr|of $h$).}} Practically, it is the averaged value of the slope $f\text{'}$ of the function $f$ between the last sequence point $\backslash left(\; x,\; y\; \backslash right)\; =\; \backslash bigl(\; x\_n,\; f\backslash left(\; x\_n\; \backslash right)\; \backslash bigr)$ and the auxiliary point at $\backslash bigl(\; x,\; y\; \backslash bigr)\; =\; \backslash bigl(\; x\_n\; +\; h,\; f\backslash left(\; x\_n\; +\; h\; \backslash right)\; \backslash bigr)$, with the size of the intermediate step (and its direction) given by $h\; =\; f(x\_n)$.

Because the value of $g$ is an approximation for $f\text{'}$, its value can optionally be checked to see if it meets the condition , 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).

It is only for the purpose of finding $h$ for this auxiliary point that the value of the function $f$ 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 $f$ to be continuous and to actually have a nearby solution. Several modest modifications of the step $h$ in the formula for the slope $g$ exist, such as multiplying it by {{sfrac| 1 |2}} or {{sfrac| 3 |4}}, to accommodate functions $f$ that do not quite meet the requirement.

The main advantage of Steffensen's method is that it has quadratic convergence like Newton's method – that is, both methods find roots to an equation $f$ 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 $f\text{'}$ as well as the function $f$, while Steffensen's method only requires $f$ 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 $f(x\_n)$ and $f(x\_n\; +\; h)$ must be calculated, which might be time-consuming if $f$ is complicated. 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,{{efn|

Because $f(\; x\_n\; +\; h\; )$ requires the prior calculation of $h\; =\; f(x\_n)$, 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.

}} 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 {{nowrap|(1.6)² ≈ 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 choosing an "adequate" starting value $x\_0$. If the value of $x\_0$ is not "close enough" to the actual solution $x\_\backslash star$, the method may fail, and the sequence of values $x\_0,\; \backslash ,\; x\_1,\; \backslash ,\; x\_2,\; \backslash ,\; x\_3,\; \backslash ,\; \backslash dots$ may either erratically flip-flop between two extremes, or diverge to infinity, or both.

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. To compare the following formulae to the formulae in the section above, notice that $x\_n\; =\; p\; -\; p\_n$. This method assumes starting with a linearly convergent sequence and increases the rate of convergence of that sequence. If the signs of $p\_n,\; \backslash ,\; p\_\{n+1\},\; \backslash ,\; p\_\{n+2\}$ agree and $p\_n$ is "sufficiently close" to the desired limit of the sequence $p$, then we can assume

:$\backslash frac\{p\_\{n+1\}\; -\; p\}\{p\_n\; -\; p\}\; \backslash approx\; \backslash frac\{p\_\{n+2\}\; -\; p\}\{p\_\{n+1\}\; -\; p\},$

so that

:$(\; p\_\{n+2\}\; -\; 2\; p\_\{n+1\}\; +\; p\_n\; )\; p\; \backslash approx\; p\_\{n+2\}\; p\_n\; -\; p\_\{n+1\}^2.$

Solving for the desired limit of the sequence $p$ gives:

:$p\; \backslash approx\; \backslash frac\{\; p\_\{n+2\}\; p\_n\; -\; p\_\{n+1\}^2\; \}\{\; p\_\{n+2\}\; -\; 2\; p\_\{n+1\}\; +\; p\_n\; \}$

:$=~\; \backslash frac\{\backslash ,\; (\backslash ,\; p\_\{n\}^2\; +\; p\_\{n\}\; \backslash ,\; p\_\{n+2\}\; -\; 2\; \backslash ,\; p\_\{n\}\; \backslash ,\; p\_\{n+1\}\; \backslash ,)\; -\; (\backslash ,\; p\_\{n\}^2\; -\; 2\; \backslash ,\; p\_\{n\}\; \backslash ,\; p\_\{n+1\}\; +\; p\_\{n+1\}^2\; \backslash ,\; )\; \backslash ,\; \}\{\backslash ,\; p\_\{n+2\}\; -\; 2\; \backslash ,\; p\_\{n+1\}\; +\; p\_n\; \backslash ,\}$

:$=\; p\_n\; -\; \backslash frac\{(\; p\_\{n+1\}\; -\; p\_n\; )^2\; \}\{\; p\_\{n+2\}\; -\; 2\; p\_\{n+1\}\; +\; p\_n\; \},$

which results in the more rapidly convergent sequence:

:$p\; \backslash approx\; p\_\{n+3\}\; =\; p\_n\; -\; \backslash frac\{\; (\; p\_\{n+1\}\; -\; p\_n\; )^2\; \}\{\; p\_\{n+2\}\; -\; 2\; p\_\{n+1\}\; +\; p\_n\; \}.$

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) + p0; % calculate the next two guesses for the fixed point.

p2 = f(p1) + p1;

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.

end

p0 = p; % update p0 for the next iteration.

end

if abs(p - p0) > tol % If we fail to meet the tolerance, we output a

% message of failure.

'failed to converge in 1000 iterations.'

end

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

from typing import Callable, Iterator

Func = Callable[[float], float, float]

def g(f: Func, x: float, fx: float) -> Func:

"""First-order divided difference function.

Arguments:

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, tol: 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.

Arguments:

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 abs(gx) <= tol:

break

else:

x = x - fx / gx # Update to x_{n+1}

yield x # Yield value

Steffensen's method can also be used to find an input $x\; =\; x\_\backslash star$ for a different kind of function $F$ that produces output the same as its input: $x\_\backslash star\; =\; F(x\_\backslash star)$ for the special value $x\_\backslash star$. Solutions like $x\_\backslash star$ 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 $f$ and the fixed-point functions are simply related by $F(x)\; =\; x\; +\; \backslash varepsilon\; f(x)$, where $\backslash varepsilon$ is some scalar constant small enough in magnitude to make $F$ stable under iteration, but large enough for the non-linearity of the function $f$ 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 generalized for functions $F\; :\; X\; \backslash to\; X$ that map a Banach space $X$ onto itself or even more generally $F\; :\; X\; \backslash to\; Y$ that map from one Banach space $X$ into another Banach space $Y$. The generalized method assumes that a family of bounded linear operators $\backslash \{\; G(u,v):\; u,\; v\; \backslash in\; X\; \backslash \}$ associated with $u$ and $v$ can be devised that (locally) satisfies the condition

{{NumBlk|:|$F\backslash left(\; u\; \backslash right)\; -\; F\backslash left(\; v\; \backslash right)\; =\; G\backslash left(\; u,\; v\; \backslash right)\; \backslash bigl[u\; -\; v\backslash bigr]$|{{EquationRef|1}}}}

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

:$G\backslash left(\; u,\; v\; \backslash right)\; =\; \backslash bigl[\; F\backslash left(\; u\; \backslash right)-\; F\backslash left(\; v\; \backslash right)\; \backslash bigr]\; \backslash bigl[\; u\; -\; v\; \backslash bigr]^\{-1\},$

which may provide some insight: Expressed in this way, the linear operator $G$ can be more easily seen to be an elaborate version of the divided difference $g$ discussed in the first section, above. The quotient form is shown here for orientation only; it is not required per se. Note also that division within the Banach space is not necessary for the elaborated Steffensen's method to be viable; the only requirement is that the operator $G$ satisfy ({{EquationNote|1}}).

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

Steffensen's method is then very similar to the Newton's method, except that it uses the divided difference $G\; \backslash bigl(\; F\backslash left(\; x\; \backslash right),\; x\; \backslash bigr)$ instead of the derivative $F\text{'}(x)$. Note that for arguments $x$ close to some fixed point $x\_\backslash star$, fixed point functions $F$ and their linear operators $G$ meeting condition ({{EquationNote|1}}), $F\text{'}(x)\; \backslash approx\; G\; \backslash bigl(\; F\backslash left(\; x\; \backslash right),\; x\; \backslash bigr)\; \backslash approx\; I$, where $I$ is the identity operator.

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

: $x\_\{n+1\}\; =\; x\_n\; +\; \backslash Bigl[\; I\; -\; G\backslash bigl(\; F\backslash left(\; x\_n\; \backslash right),\; x\_n\; \backslash bigr)\; \backslash Bigr]^\{-1\}\backslash Bigl[\; F\backslash left(\; x\_n\; \backslash right)\; -\; x\_n\; \backslash Bigr],$

for $n\; =\; 1,\backslash ,2,\backslash ,3,\backslash ,...$. In the more general case in which division may not be possible, the iteration formula requires finding a solution $x\_\{n+1\}$ close to $x\_\{n\}$ for which

: $\backslash Bigl[\; I\; -\; G\backslash bigl(\; F\backslash left(\; x\_n\; \backslash right),\; x\_n\; \backslash bigr)\; \backslash Bigr]\; \backslash Bigl[\; x\_\{n+1\}\; -\; x\_n\; \backslash Bigr]\; =\; F\backslash left(\; x\_n\; \backslash right)\; -\; x\_n.$

Equivalently, one may seek the solution $x\_\{n+1\}$ to the somewhat reduced form

: $\backslash Bigl[\; I\; -\; G\backslash bigl(\; F\backslash left(\; x\_n\; \backslash right),\; x\_n\; \backslash bigr)\; \backslash Bigr]\; x\_\{n+1\}\; =\; \backslash Bigl[\; F\backslash left(\; x\_n\; \backslash right)\; -\; G\backslash bigl(\; F\backslash left(\; x\_n\; \backslash right),\; x\_n\; \backslash bigr)\; \backslash \; x\_n\; \backslash Bigr],$

with all the values inside square brackets being independent of $x\_\{n+1\}$: the bracketed terms all only depend on $x\_\{n\}$. However, that the second form may not be as numerically stable as the first: because the first form involves finding a value for a (hopefully) small difference, it may be numerically more likely to avoid excessively large or erratic changes to the iterated value $x\_n$.

If the linear operator $G$ satisfies

: $\backslash Bigl\backslash |\; G\; \backslash left(\; u,\; v\; \backslash right)\; -\; G\; \backslash left(\; x,\; y\; \backslash right)\; \backslash Bigr\backslash |\; \backslash le\; k\; \backslash biggl(\; \backslash Bigl\backslash |u\; -\; x\; \backslash Bigr\backslash |\; +\; \backslash Bigr\backslash |\; v\; -\; y\; \backslash Bigr\backslash |\; \backslash biggr)$

for some positive real constant $k$, then the method converges quadratically to a fixed point of $F$ if the initial approximation $x\_0$ is "sufficiently close" to the desired solution $x\_\backslash star$ that satisfies $x\_\backslash star\; =\; F(x\_\backslash star)$.

{{notelist}}

{{reflist|25em|refs=

{{cite book

|first1=Germund |last1=Dahlquist |author1-link=Germund Dahlquist

|first2=Åke |last2=Björck

|translator-first=Ned |translator-last=Anderson

|year=1974

|title=Numerical Methods

|pages=[https://archive.org/details/numericalmethods00dahl/page/230 230–231]

|location=Englewood Cliffs, NJ

|publisher=Prentice Hall

|url=https://archive.org/details/numericalmethods00dahl

|url-access=registration

}}

{{cite journal

|last1=Johnson |first1=L.W.

|last2=Scholz |first2=D.R.

|date=June 1968

|title=On Steffensen's method

|journal=SIAM Journal on Numerical Analysis

|volume=5 |issue=2 |pages=296–302

|jstor=2949443 |doi=10.1137/0705026

}}

}}

{{Root-finding algorithms}}

Category:Articles with example MATLAB/Octave code

Category:Articles with example Python (programming language) code

Category:Quasi-Newton methods