Steffensen's method: Difference between revisions

Revision as of 02:46, 3 August 2008

Revision as of 02:49, 3 August 2008

Line 2:

==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>x_\star</math> that satisifies <math>f(x_\star)=0</math>. Near the solution <math>x_\star</math>, the function <math>f</math> is supposed to approximately satisfy <math>-1 < f'(x_\star) < 0</math>, which makes it adequate as an itteration function to find its own solution, although not necessarilly efficiently. For some functions, Steffensen's method can work even if this condition is not met, but in such a case, the starting value <math>x_0</math> must be very close to the actual solution <math>x_\star</math>, and quadratic convergence may not be obtained.

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.&nbsp;230-231, Prentice Hall, Englewood Cliffs, NJ</ref>:

Line 8:

:<math>x_{n+1} = x_n - \frac{f(x_n)}{g(x_n)}</math>

for ''n'' &nbsp;= &nbsp;0, 1, 2, 3, ...&nbsp;, where the slope function <math>g(x_n)</math> 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>