SciPy

scipy.optimize.toms748

scipy.optimize.toms748(f, a, b, args=(), k=1, xtol=2e-12, rtol=8.881784197001252e-16, maxiter=100, full_output=False, disp=True)[source]

Find a zero using TOMS Algorithm 748 method.

Implements the Algorithm 748 method of Alefeld, Potro and Shi to find a zero of the function f on the interval [a , b], where f(a) and f(b) must have opposite signs.

It uses a mixture of inverse cubic interpolation and “Newton-quadratic” steps. [APS1995].

Parameters:
f : function

Python function returning a scalar. The function \(f\) must be continuous, and \(f(a)\) and \(f(b)\) have opposite signs.

a : scalar,

lower boundary of the search interval

b : scalar,

upper boundary of the search interval

args : tuple, optional

containing extra arguments for the function f. f is called by f(x, *args).

k : int, optional

The number of Newton quadratic steps to perform each iteration. k>=1.

xtol : scalar, optional

The computed root x0 will satisfy np.allclose(x, x0, atol=xtol, rtol=rtol), where x is the exact root. The parameter must be nonnegative.

rtol : scalar, optional

The computed root x0 will satisfy np.allclose(x, x0, atol=xtol, rtol=rtol), where x is the exact root.

maxiter : int, optional

if convergence is not achieved in maxiter iterations, an error is raised. Must be >= 0.

full_output : bool, optional

If full_output is False, the root is returned. If full_output is True, the return value is (x, r), where x is the root, and r is a RootResults object.

disp : bool, optional

If True, raise RuntimeError if the algorithm didn’t converge. Otherwise the convergence status is recorded in the RootResults return object.

Returns:
x0 : float

Approximate Zero of f

r : RootResults (present if full_output = True)

Object containing information about the convergence. In particular, r.converged is True if the routine converged.

See also

brentq, brenth, ridder, bisect, newton

fsolve
find zeroes in n dimensions.

Notes

f must be continuous. Algorithm 748 with k=2 is asymptotically the most efficient algorithm known for finding roots of a four times continuously differentiable function. In contrast with Brent’s algorithm, which may only decrease the length of the enclosing bracket on the last step, Algorithm 748 decreases it each iteration with the same asymptotic efficiency as it finds the root.

For easy statement of efficiency indices, assume that f has 4 continuouous deriviatives. For k=1, the convergence order is at least 2.7, and with about asymptotically 2 function evaluations per iteration, the efficiency index is approximately 1.65. For k=2, the order is about 4.6 with asymptotically 3 function evaluations per iteration, and the efficiency index 1.66. For higher values of k, the efficiency index approaches the k-th root of (3k-2), hence k=1 or k=2 are usually appropriate.

References

[APS1995]Alefeld, G. E. and Potra, F. A. and Shi, Yixun, Algorithm 748: Enclosing Zeros of Continuous Functions, ACM Trans. Math. Softw. Volume 221(1995) doi = {10.1145/210089.210111}

Examples

>>> def f(x):
...     return (x**3 - 1)  # only one real root at x = 1
>>> from scipy import optimize
>>> root, results = optimize.toms748(f, 0, 2, full_output=True)
>>> root
1.0
>>> results
      converged: True
           flag: 'converged'
 function_calls: 11
     iterations: 5
           root: 1.0

Previous topic

scipy.optimize.newton

Next topic

scipy.optimize.RootResults