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 1.

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.

References

1

http://en.wikipedia.org/wiki/Muller%27s_method