Steffensen's method: Difference between revisions

Revision as of 18:15, 11 July 2025

Latest revision as of 18:14, 24 July 2025

Line 38:

The main advantage of Steffensen's method is that it has [[quadratic convergence]]<ref name=Dahlquist-Björck-1974/> like [[Newton's method]] &ndash; that is, both methods find roots to an equation <math>\ f\ </math> just as "quickly". In this case, ''quickly'' means that for both methods, the number of correct digits in the answer doubles with each step. But the formula for Newton's method requires evaluation of the function's derivative <math>\ f'\ </math> as well as the function <math>\ f\ ,</math> while Steffensen's method only requires <math>\ f\ </math> itself. This is important when the derivative is not easily or efficiently available.

The price for the quick convergence is the double function evaluation: Both <math>\ f(x_n)\ </math> and <math>\ f(x_n + h)\ </math> must be calculated, which might be time-consuming if <math>\ f\ </math> is complicated. For comparison, both [[regula falsi]] and the [[secant method]] only need one function evaluation per step. The secant method increases the number of correct digits by "only" a factor of roughly &thinsp; 1.6&nbsp;per step,&thinsp; but one can do twice as many steps of the secant method within a given time. Since the secant method can carry out twice as many steps in the same time as Steffensen's method,{{efn|

Because <math>\ f( x_n + h )\ </math> requires the prior calculation of <math>\ h \equiv f(x_n)\ ,</math> the two evaluations must be done sequentially – the algorithm ''per se'' cannot be made faster by running the function evaluations in parallel. This is yet another disadvantage of Steffensen's method.

}} in practical use the secant method actually converges faster than Steffensen's method, when both algorithms succeed: The secant method achieves a factor of about &thinsp; {{nobr|{{math|(1.6){{sup|2}} &hairsp; ≈ &hairsp; 2.6}} times}} &thinsp; as many digits for every two steps (two function evaluations), compared to Steffensen's factor of &thinsp; {{math|2}} &thinsp; for every one step (two function evaluations).

Similar to most other [[Root-finding algorithm#Iterative methods|iterative root-finding algorithms]], the crucial weakness in Steffensen's method is choosing a "sufficiently close" starting value <math>\ x_0 ~.</math> If the value of <math>\ x_0\ </math> is not "close enough" to the actual solution <math>\ x_\star\ ,</math> the method may fail, and the sequence of values <math>\ x_0, \, x_1, \, x_2, \, x_3, \, \dots\ </math> may either erratically flip-flop between two (or more) extremes, or diverge to infinity, or both.