Steffensen's method: Difference between revisions

Revision as of 00:31, 12 July 2008

Revision as of 00:39, 12 July 2008

Line 2:

==Simple Description==

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>&nbsp;. 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.&nbsp;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 functionslope <math>g(x_n)\ </math> is a combinationcomposite 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>&nbsp;.

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, however is the double function evaluation: both <math>f(x_n)\ </math> and <math>f(x_n + f(x_n))\ </math> must be evaluated, which migh be costly 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>&nbsp;. 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!).

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>&nbsp;. 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==