demuller
- sherpa.utils.demuller(fcn, xa, xb, xc, fa=None, fb=None, fc=None, args=(), maxfev=32, tol=1e-06)[source] [edit on github]
A root-finding algorithm using Muller’s method.
The algorithm is described at https://en.wikipedia.org/wiki/Muller%27s_method.
p( x ) = f( xc ) + A ( x - xc ) + B ( x - xc ) ( x - xb )
Notes
The general case:
2 f( x ) n x = x - ---------------------------------------- n+1 n C + sgn( C ) sqrt( C^2 - 4 f( x ) B ) n n n n n 1 ( f( x ) - f( x ) f( x ) - f( x ) ) ( n n-1 n-1 n-2 ) B = ------- ( ------------------ - ------------------- ) n x - x ( x - x x - x ) n n-2 ( n n-1 n-1 n-2 ) f( x ) - f( x ) n n-1 A = ----------------- n x - x n n-1 C = A + B ( x - x ) n n n n n-1
The convergence rate for Muller’s method can be shown to be the real root of the cubic x - x^3, that is:
p = (a + 4 / a + 1) / 3 a = (19 + 3 sqrt(33))^1/3
In other words: O(h^p) where p is approximately 1.839286755.
- Parameters:
fcn (callable) – The function with a root. The function signature is
fcn(x, *args)
.xa (float) – Muller’s method requires three initial values.
xb (float) – Muller’s method requires three initial values.
xc (float) – Muller’s method requires three initial values.
fa (float or None) – Function values at
xa
,xb
, andxc
. These parameters are optional and can be passed to save time in cases wherefcn(xa, *args)
is already known and function evaluation takes a long time. IfNone
, they will be calculated.fb (float or None) – Function values at
xa
,xb
, andxc
. These parameters are optional and can be passed to save time in cases wherefcn(xa, *args)
is already known and function evaluation takes a long time. IfNone
, they will be calculated.fc (float or None) – Function values at
xa
,xb
, andxc
. These parameters are optional and can be passed to save time in cases wherefcn(xa, *args)
is already known and function evaluation takes a long time. IfNone
, they will be calculated.args (tuple) – Additional parameters that will be passed through to
fcn
.maxfev (int) – Maximal number of function evaluations
tol (float) – The root finding algorthm stops if the function value a value x with
abs(fcn(x)) < tol
is found.
- Returns:
out – The output has the form of a list:
[[x, fcn(x)], [x1, fcn(x1)], [x2, fcn(x2)], nfev]
wherex
is the location of the root, andx1
andx2
are the previous steps. The function value for those steps is returned as well.nfev
is the total number of function evaluations. If any of those values is not available,None
will be returned instead.- Return type: