Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, Steffensen's method is a root-finding method, similar to Newton's method
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
Johan Frederik Steffensen was a Danish mathematician, statistician, and actuary who did research in the fields of calculus of finite differences and interpolation. He was professor of actuarial science at the University of Copenhagen from 1923 to 1943. Steffensen's inequality and Steffensen's...
. Steffensen's method also achieves quadratic convergence, but without using derivative
Derivative
In calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
does.
Simple description
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 input value that satisfies . Near the solution , the function is supposed to approximately satisfy ; this condition makes the function adequate as a correction 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 :
for n = 0, 1, 2, 3, ... , where the slope function is a composite of the original function given by the following formula:
The function is the average slope of the function between the last sequence point and the auxiliary point , with the step . 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. Several modest modifications of the step in the slope calculation exist to accommodate functions 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
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
– that is, both methods find roots to an equation just as 'quickly'. In this case quickly means that the number of correct digits in the answer doubles with each step for both. But the formula for Newton's method requires a separate function for the derivative; Steffensen's method does not. So Steffensen's method can be programmed for a generic function, as long as that function meets the constraints mentioned above.
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
Secant method
In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f. The secant method can be thought of as a finite difference approximation of Newton's method. However, the method was developed...
needs only one function evaluation per step, so with two function evaluations the secant method can do two steps, and two steps of the secant method increase the number of correct digits by a factor of 1.6 . The equally time-consuming single step of Steffensen's (or Newton's) method increases the correct digits by a factor of 2 : only slightly better.
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
and most other quadratically convergent 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 (possibly both!).
Derivation using Aitken's delta-squared process
The version of Steffensen's method implemented in the MATLAB
MATLAB
MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...
In numerical analysis, Aitken's delta-squared process is a series acceleration method, used for accelerating the rate of convergence of a sequence. It is named after Alexander Aitken, who introduced this method in 1926. Its early form was known to Seki Kōwa and was found for rectification of the...
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:
then
so
and hence .
Solving for the desired limit of the sequence gives:
Which results in the more rapidly convergent sequence:
Implementation in Matlab
Here is the source for an implementation of Steffensen's Method in MATLAB
MATLAB
MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...
.
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.
p2=f(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)
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
Generalization
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 point
Fixed point (mathematics)
In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
s. Many such 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.
This method for finding fixed points of a real-valued function has been generalised for functions on a Banach space
Banach space
In mathematics, Banach spaces is the name for complete normed vector spaces, one of the central objects of study in functional analysis. A complete normed vector space is a vector space V with a norm ||·|| such that every Cauchy sequence in V has a limit in V In mathematics, Banach spaces is the...
In mathematics, an indexed family is a collection of values that are associated with indexes. For example, a family of real numbers, indexed by the integers is a collection of real numbers, where each integer is associated with one of the real numbers....
In mathematical analysis and related areas of mathematics, a set is called bounded, if it is, in a certain sense, of finite size. Conversely, a set which is not bounded is called unbounded...
linear operators associated with and are can be found to satisfy the condition .
In the simple form given in the section above, the function simply takes in and produces 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
Banach space
In mathematics, Banach spaces is the name for complete normed vector spaces, one of the central objects of study in functional analysis. A complete normed vector space is a vector space V with a norm ||·|| such that every Cauchy sequence in V has a limit in V In mathematics, Banach spaces is the...
.
Steffensen's method is then very similar to the Newton's method, except that it uses the divided difference instead of the derivative . It is thus defined by
,
for , and where is the identity operator.
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 .
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
; that is: to find the input value 
that satisfies 
. Near the solution 
, the function 
is supposed to approximately satisfy 
; this condition makes the function 
adequate as a correction 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.
, 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 :
is a composite of the original function 
given by the following formula:
is the average slope of the function 
between the last sequence point 
and the auxiliary point 
, with the step 
. 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. Several modest modifications of the step 
in the slope calculation 
exist to accommodate functions 
that do not quite meet the requirement.
just as 'quickly'. In this case quickly means that the number of correct digits in the answer doubles with each step for both. But the formula for Newton's method requires a separate function for the derivative; Steffensen's method does not. So Steffensen's method can be programmed for a generic function, as long as that function meets the constraints mentioned above.
and 
must be calculated, which might be time-consuming if 
is a complicated function. For comparison, the secant method
. 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 (possibly both!).
. 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:
.
gives:
for a different kind of function 
that produces output the same as its input: 
for the special value 
. Solutions like 
are called fixed point
on a Banach space
. The generalised method assumes that a family
associated with 
and 
are can be found to satisfy the condition
.
simply takes in and produces 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
instead of the derivative 
. It is thus defined by
, and where 
is the identity operator.
satisfies
, then the method converges quadratically to a fixed point of 
if the initial approximation 
is "sufficiently close" to the desired solution 
, that satisfies 
.
,