Content deleted Content added
math notation |
inserted simplified/practical section |
||
Line 1:
In [[numerical analysis]], '''Steffensen's method''' is a [[root-finding method]]. It is similar to [[Newton's method]] and it also achieves [[order of convergence|quadratic convergence]], but it does not use [[derivative]]s. The method is named after [[Johan Frederik Steffensen]].
==Simple Description==
==Generalised definition==▼
The simplest form of the formula for Steffensen's method occurs when it is used to find the zeros of a function <math>f</math>, that is, to find the input value <math>x</math> that satisifies <math>f(x)=0</math> . Given an adequate starting value <math>x_0</math>, a sequence of values <math>x_0,\ x_1,\ x_2,\ ...,\ x_n ...</math> can be generated. Each value in the sequence is closer to the solution than the prior value, and the value <math>x_n</math> from the prior step generates the next step, <math>x_{n+1}</math> via this formula<ref>Germund Dahlquist, Åke Björck, tr. Ned Anderson (1974) ''Numerical Methods'', pp. 230-231, Prentice Hall, Englewood Cliffs, NJ</ref>:
:<math>x_{n+1} = x_n - \frac{f(x_n)}{g(x_n)}</math>
for <math>n = 0,\ 1,\ 2,\ 3,\ ...</math>, where the auxilliary function <math>g(x_n)</math> is a combination of the original function <math>f</math> given by the following formula:
:<math>g(x_n) = \frac{f(x_n + f(x_n)) - f(x_n)}{f(x_n)}</math>
The function <math>g</math> is the average slope of the function <math>f</math> between the last sequence point <math>x=x_n,\ y=f(x_n)</math> and the auxilliary point <math>x=x_n + f(x_n),\ y=f(x_n + f(x_n))</math> .
The main advantage of Steffensen's method is that it can find the roots of an equation <math>f</math> 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 ''quicly'' means that the number of correct digits in the answer doubles with each step. The cost, however is the double function evaluation: both <math>f(x_n)</math> and <math>f(x_n + f(x_n))</math> must be evaluated.
Similar to [[Newton's method]] and most other quadratically convergent methods, the crucial weakness with the method is the choice of the starting value <math>x_0</math> . If the value of <math>x_0</math> is not "close enough" to the actual solution, the method will fail and the sequence of values <math>x_0, x_1, x_2, x_3, ...</math> will either flip flop between two extremes, or diverge to infinity (possibly both!).
▲==Generalised definition==
Steffensen's method finds [[fixed point]]s of a [[Map (mathematics)|mapping]] ƒ. In the original definition, ƒ was supposed to be a real function, but the method has been generalised for functions <math>f : X \to X </math> on a [[Banach space]] <math>X</math>.
The method assumes that a [[Indexed family|family]] <math>\{F(x',x''):x', x'' \in X\}</math> of [[Bounded set|bounded]] [[linear operators]] (called ''divided difference'') associated with ''x''<nowiki>'</nowiki> and ''x''<nowiki>''</nowiki> is known which satisfies<ref>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]</ref>
:
Steffensen's method is then very similar to the Newton's method, except that it uses the divided difference<math>F(f(x),x)</math> instead of the derivative <math>Df(x)</math>. It is thus defined by
Line 21 ⟶ 37:
==References==
<references />
[[Category:Root-finding algorithms]]
| |||