# 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`, 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.

• fb (float 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.

• fc (float 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.

• 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]` 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.

Return type:

list