bundles / scipy 1.17.1 / scipy / optimize / _zeros_py / toms748
function
scipy.optimize._zeros_py:toms748
Signature
def toms748 ( f , a , b , args = () , k = 1 , xtol = 2e-12 , rtol = 8.881784197001252e-16 , maxiter = 100 , full_output = False , disp = True ) Summary
Find a root using TOMS Algorithm 748 method.
Extended Summary
Implements the Algorithm 748 method of Alefeld, Potro and Shi to find a root 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: functionPython function returning a scalar. The function must be continuous, and and have opposite signs.
a: scalar,lower boundary of the search interval
b: scalar,upper boundary of the search interval
args: tuple, optionalcontaining extra arguments for the function
f.fis called byf(x, *args).k: int, optionalThe number of Newton quadratic steps to perform each iteration.
k>=1.xtol: scalar, optionalThe computed root
x0will satisfynp.isclose(x, x0, atol=xtol, rtol=rtol), wherexis the exact root. The parameter must be positive.rtol: scalar, optionalThe computed root
x0will satisfynp.isclose(x, x0, atol=xtol, rtol=rtol), wherexis the exact root.maxiter: int, optionalIf convergence is not achieved in
maxiteriterations, an error is raised. Must be >= 0.full_output: bool, optionalIf
full_outputis False, the root is returned. Iffull_outputis True, the return value is(x, r), wherexis the root, and r is a RootResults object.disp: bool, optionalIf True, raise RuntimeError if the algorithm didn't converge. Otherwise, the convergence status is recorded in the RootResults return object.
Returns
root: floatApproximate root of
fr: `RootResults` (present if ``full_output = True``)Object containing information about the convergence. In particular,
r.convergedis True if the routine converged.
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 continuous 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 kth root of (3k-2), hence k=1 or k=2 are usually appropriate.
As mentioned in the parameter documentation, the computed root x0 will satisfy np.isclose(x, x0, atol=xtol, rtol=rtol), where x is the exact root. In equation form, this terminating condition is abs(x - x0) <= xtol + rtol * abs(x0).
The default value xtol=2e-12 may lead to surprising behavior if one expects toms748 to always compute roots with relative error near machine precision. Care should be taken to select xtol for the use case at hand. Setting xtol=5e-324, the smallest subnormal number, will ensure the highest level of accuracy. Larger values of xtol may be useful for saving function evaluations when a root is at or near zero in applications where the tiny absolute differences available between floating point numbers near zero are not meaningful.
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
✗results
✓See also
Aliases
-
scipy.optimize.toms748