|
==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 <math>f\ </math>, that is, to find the input value <math>xx_\ star</math> that satisifies <math>f(xx_\star)=0\ </math>. GivenNear anthe adequate starting valuesolution <math>x_0x_\ star</math>, athe sequencefunction of<math>f</math> valuesis supposed to approximately satisfy <math>x_0,\-1 x_1,\< x_2,\dots,f'(x_\star) x_n,\dots< 0</math>, can be generated.which Whenmakes it works,adequate eachas valuean initteration thefunction sequenceto isfind muchits closer to theown solution, thanalthough thenot priornecessarilly valueefficiently. TheFor valuesome <math>x_n\functions, </math>Steffensen's frommethod thecan currentwork stepeven generatesif thethis valuecondition <math>x_{n+1}\is </math>not formet, thebut nextin step,such viaa this formula<ref>Germund Dahlquistcase, Åkethe Björck,starting tr.value Ned<math>x_0</math> Andersonmust (1974)be ''Numericalvery Methods'',close pp. 230-231,to Prenticethe Hall,actual Englewood Cliffs,solution NJ<math>x_\star</refmath>:.
Given an adequate starting value <math>x_0\ </math>, a sequence of values <math>x_0,\ x_1,\ x_2,\dots,\ x_n,\dots</math> can be generated. When it works, each value in the sequence is much closer to the solution <math>x_\star</math> than the prior value. The value <math>x_n\ </math> from the current step generates the value <math>x_{n+1}\ </math> for the next step, 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 ''n'' = 0, 1, 2, 3, ..., where the slope ''function <math>g''(''x''<sub>''n''x_n)</submath>) is a composite 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 ƒ between the last sequence point <math>(x=x_n,\ y)=(x_n,f(x_n))\ </math> and the auxilliary point <math>(x,y)=(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 "[[quadratic convergence|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 ''[[quadratic convergence|quicly]]'' 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 <math>f(x_n)\ </math> and <math>f(x_n + f(x_n))\ </math> must be calculated, which might be time-consuming if ƒ<math>f</math> is a complicated function.
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,\dots</math> will either flip flop between two extremes, or diverge to infinity (possibly both!).
==Generalised definition==
|
