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 )

Parameters:

fcncallable(): The function with a root. The function signature is fcn(x, *args).
xa, xb, xcfloat: Muller’s method requires three initial values.
fa, fb, fcfloat or None: Function values at xa, xb, and xc. These parameters are optional and can be passed to save time in cases where fcn(xa, *args) is already known and function evaluation takes a long time. If None, they will be calculated.
argstuple: Additional parameters that will be passed through to fcn.
maxfevint: Maximal number of function evaluations
tolfloat: The root finding algorithm stops if the function value a value x with abs(fcn(x)) < tol is found.

Returns:

outlist: The output has the form of a list: [[x, fcn(x)], [x1, fcn(x1)], [x2, fcn(x2)], nfev] where x is the location of the root, and x1 and x2 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.

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.