Steffensen's method

Steffensen's method

In numerical analysis, Steffensen's method is a root-finding method. It is similar to Newton's method and it also achieves quadratic convergence, but it does not use derivatives. The method is named after Johan Frederik Steffensen.

imple 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 f, that is, to find the input value x_star that satisifies f(x_star)=0. Near the solution x_star, the function f is supposed to approximately satisfy -1 < f'(x_star) < 0, which makes it adequate as an correction function for finding its own solution, although it is not required to be efficient. 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_star, and convergence to the solution may be slow.

Given an adequate starting value x_0 , a sequence of values x_0, x_1, x_2,dots, x_n,dots can be generated. When it works, each value in the sequence is much closer to the solution x_star than the prior value. The value x_n from the current step generates the value x_{n+1} for the next step, via this formula [Germund Dahlquist, Åke Björck, tr. Ned Anderson (1974) "Numerical Methods", pp. 230-231, Prentice Hall, Englewood Cliffs, NJ] :

:x_{n+1} = x_n - frac{f(x_n)}{g(x_n)}

for "n" = 0, 1, 2, 3, ... , where the slope function g(x_n) is a composite of the original function f given by the following formula:

:g(x_n) = frac{f(x_n + f(x_n)) - f(x_n)}{f(x_n)}

The function g is the average slope of the function &fnof; between the last sequence point (x,y)=( x_n, f(x_n) ) and the auxiliary point (x,y)=( x_n + h, f(x_n + h) ), with the step h=f(x_n) . It is only for the purpose of finding this auxiliary point that the value of the function f must be an adequate correction to get closer to its own solution. 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 slope calculation g exist to accommodate functions f that do not quite meet this requirement.

The main advantage of Steffensen's method is that it can find the roots of an equation f just as "quickly" as Newton's method but the formula does not require a separate function for the derivative, so it can be programmed for any generic function. In this case "quickly" means that the number of correct digits in the answer doubles with each step. The cost for the quick convergence is the double function evaluation: both f(x_n) and f(x_n + f(x_n)) must be calculated, which might be time-consuming if f is a complicated function. For comparison, the secant method needs only one function evaluation per step, so allowing for 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 2.6 while one step of Steffensen's (or Newton's) method increases it by a factor 2.

Similar to Newton's method and most other quadratically convergent methods, the crucial weakness with the method is the choice of the starting value x_0 . If the value of x_0 is not "close enough" to the actual solution, the method will fail and the sequence of values x_0, x_1, x_2, x_3,dots will either flip flop between two extremes, or diverge to infinity (possibly both!).

Generalisation

Steffensen's method can also be used to find an input x = x_star of the function f that produces the same output: x_star = f(x_star). Such solutions are called "fixed points". Many of 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 convergence.

This method for finding fixed points of a real-valued function has been generalised for functions f : X o X on a Banach space X. The generalised method assumes that a family of bounded linear operators {L(u,v): u, v in X} associated with u and v are can be found to satisfy the condition [L. W. Johnson; D. R. Scholz (1968) On Steffensen's Method, "SIAM Journal on Numerical Analysis" (June 1968), vol. 5, no. 2., pp. 296-302. Stable URL: [http://links.jstor.org/sici?sici=0036-1429%28196806%295%3A2%3C296%3AOSM%3E2.0.CO%3B2-H] ]

:f(u)- f(v)=L(u,v) (u-v) .

In the original form (given in the section above), where the function f simply takes in and produces real numbers, the operators are "divided differences". In the general form, the operators L are the analogue of divided differences in the Banach space.

Steffensen's method is then very similar to the Newton's method, except that it uses the divided differenceL(f(x),x) instead of the derivative Df(x) . It is thus defined by

: x_{n+1} = x_n + [I - L(f(x_n), x_n)] ^{-1}(f(x_n) - x_n) ,

for n=1, 2, 3, ..., and where I is the identity operator. If the operator L satisfies

: |L(u,v)-L(x,y)| le K ig( |u-x| + |v-y| ig)

for some constant K , then the method converges quadratically to a fixed point of &fnof; if the initial approximation x_0 is sufficiently close to the desired solution x_star, that satisfies x_star = f(x_star) .

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Método de Steffensen — El método de Steffensen (por Johan Frederik Steffensen) es un algoritmo para obtener los ceros de una función. El método de Steffensen se puede considerar como una combinación del método de punto fijo y del método de Aitken. Como el método de… …   Wikipedia Español

  • Johan Frederik Steffensen — (1873 ndash;1961) was a Danish mathematician, statistician, and actuary who did research in the fields of calculus of finite differences and interpolation. Steffensen s inequality and Steffensen s method (an iterative numerical method) are named… …   Wikipedia

  • Newton's method — In numerical analysis, Newton s method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real valued function. The… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Fixed point iteration — In numerical analysis, fixed point iteration is a method of computing fixed points of iterated functions.More specifically, given a function f defined on the real numbers with real values and given a point x 0 in the domain of f, the fixed point… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Aitken's delta-squared process — 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 [Alexander Aitken, On… …   Wikipedia

  • Iterated function — In mathematics, iterated functions are the objects of deep study in computer science, fractals and dynamical systems. An iterated function is a function which is composed with itself, repeatedly, a process called iteration.DefinitionThe formal… …   Wikipedia

  • Darcy friction factor formulae — In fluid dynamics, the Darcy friction factor formulae are equations based on experimental data and theory for the Darcy friction factor. The Darcy friction factor is a dimensionless quantity used in the Darcy–Weisbach equation, for the… …   Wikipedia

  • Andreas Grassl — (born October 25, 1984) is a German man found in England in April 2005, who remained unidentified for a long time due to his refusal to speak, communicating instead through drawing and playing the piano. During the more than four months that… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”