Content deleted Content added
minor tech edit |
m convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB) |
||
| (8 intermediate revisions by 2 users not shown) | |||
Line 1:
{{short description|Newton-like root-finding algorithm that does not use derivatives}}
In [[numerical analysis]], '''Steffensen's method''' is an [[iterative method]] named after [[Johan Frederik Steffensen]] for numerical [[root-finding method|root-finding
Steffensen's method has the drawback that it requires two function evaluations per step, whereas the secant method requires only one evaluation per step, so it is not necessarily most efficient in terms of [[computational cost]], depending on the number of iterations each requires. Newton's method also requires evaluating two functions per step – for the function and for its derivative – and its computational cost varies between being at best the same as the secant method, and at worst the same as Steffensen's method.
For rare special case functions the derivative for Newton's method can be calculated at negligible cost, by using saved parts from evaluation of the main function. If optimized in this way, Newton's method becomes only slightly more costly per step than the secant method,
}}
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]] – 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
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
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.
Line 93:
p0 = p; % update p0 for the next iteration.
end
if abs(p - p0) > tol % If we fail to meet the tolerance, we output a
% message of failure.
Line 118 ⟶ 119:
def steff(f: Func, x: float, tol: float) -> Iterator[float]:
"""
This recursive generator yields the x_{n+1} value first then, when the generator iterates,
Line 127 ⟶ 128:
x: Starting value upon first call, each level n that the function recurses x is x_n
"""
while True:
print("failed to converge in 1000 iterations")
break
else:
n = n + 1
fx = f(x)
▲ if abs(fx) <= tol:
if abs(fx) < tol:
break
else:
| |||