find_root#
- scipy.optimize.elementwise.find_root(f, init, /, *, args=(), tolerances=None, maxiter=None, callback=None)[source]#
Find the root of a monotonic, real-valued function of a real variable.
For each element of the output of f,
find_root
seeks the scalar root that makes the element 0. This function currently uses Chandrupatla’s bracketing algorithm [1] and therefore requires argument init to provide a bracket around the root: the function values at the two endpoints must have opposite signs.Provided a valid bracket,
find_root
is guaranteed to converge to a solution that satisfies the provided tolerances if the function is continuous within the bracket.This function works elementwise when init and args contain (broadcastable) arrays.
- Parameters:
- fcallable
The function whose root is desired. The signature must be:
f(x: array, *args) -> array
where each element of
x
is a finite real andargs
is a tuple, which may contain an arbitrary number of arrays that are broadcastable withx
.f must be an elementwise function: each element
f(x)[i]
must equalf(x[i])
for all indicesi
. It must not mutate the arrayx
or the arrays inargs
.find_root
seeks an arrayx
such thatf(x)
is an array of zeros.- init2-tuple of float array_like
The lower and upper endpoints of a bracket surrounding the desired root. A bracket is valid if arrays
xl, xr = init
satisfyxl < xr
andsign(f(xl)) == -sign(f(xr))
elementwise. Arrays be broadcastable with one another and args.- argstuple of array_like, optional
Additional positional array arguments to be passed to f. Arrays must be broadcastable with one another and the arrays of init. If the callable for which the root is desired requires arguments that are not broadcastable with x, wrap that callable with f such that f accepts only x and broadcastable
*args
.- tolerancesdictionary of floats, optional
Absolute and relative tolerances on the root and function value. Valid keys of the dictionary are:
xatol
- absolute tolerance on the rootxrtol
- relative tolerance on the rootfatol
- absolute tolerance on the function valuefrtol
- relative tolerance on the function value
See Notes for default values and explicit termination conditions.
- maxiterint, optional
The maximum number of iterations of the algorithm to perform. The default is the maximum possible number of bisections within the (normal) floating point numbers of the relevant dtype.
- callbackcallable, optional
An optional user-supplied function to be called before the first iteration and after each iteration. Called as
callback(res)
, whereres
is a_RichResult
similar to that returned byfind_root
(but containing the current iterate’s values of all variables). If callback raises aStopIteration
, the algorithm will terminate immediately andfind_root
will return a result. callback must not mutate res or its attributes.
- Returns:
- res_RichResult
An object similar to an instance of
scipy.optimize.OptimizeResult
with the following attributes. The descriptions are written as though the values will be scalars; however, if f returns an array, the outputs will be arrays of the same shape.- successbool array
True
where the algorithm terminated successfully (status0
);False
otherwise.- statusint array
An integer representing the exit status of the algorithm.
0
: The algorithm converged to the specified tolerances.-1
: The initial bracket was invalid.-2
: The maximum number of iterations was reached.-3
: A non-finite value was encountered.-4
: Iteration was terminated by callback.1
: The algorithm is proceeding normally (in callback only).
- xfloat array
The root of the function, if the algorithm terminated successfully.
- f_xfloat array
The value of f evaluated at x.
- nfevint array
The number of abscissae at which f was evaluated to find the root. This is distinct from the number of times f is called because the the function may evaluated at multiple points in a single call.
- nitint array
The number of iterations of the algorithm that were performed.
- brackettuple of float arrays
The lower and upper endpoints of the final bracket.
- f_brackettuple of float arrays
The value of f evaluated at the lower and upper endpoints of the bracket.
See also
Notes
Implemented based on Chandrupatla’s original paper [1].
Let:
a, b = init
be the left and right endpoints of the initial bracket,xl
andxr
be the left and right endpoints of the final bracket,xmin = xl if abs(f(xl)) <= abs(f(xr)) else xr
be the final bracket endpoint with the smaller function value, andfmin0 = min(f(a), f(b))
be the minimum of the two values of the function evaluated at the initial bracket endpoints.
Then the algorithm is considered to have converged when
abs(xr - xl) < xatol + abs(xmin) * xrtol
orfun(xmin) <= fatol + abs(fmin0) * frtol
.
This is equivalent to the termination condition described in [1] with
xrtol = 4e-10
,xatol = 1e-5
, andfatol = frtol = 0
. However, the default values of the tolerances dictionary arexatol = 4*tiny
,xrtol = 4*eps
,frtol = 0
, andfatol = tiny
, whereeps
andtiny
are the precision and smallest normal number of the resultdtype
of function inputs and outputs.References
[1] (1,2,3)Chandrupatla, Tirupathi R. “A new hybrid quadratic/bisection algorithm for finding the zero of a nonlinear function without using derivatives”. Advances in Engineering Software, 28(3), 145-149. https://doi.org/10.1016/s0965-9978(96)00051-8
Examples
Suppose we wish to find the root of the following function.
>>> def f(x, c=5): ... return x**3 - 2*x - c
First, we must find a valid bracket. The function is not monotonic, but
bracket_root
may be able to provide a bracket.>>> from scipy.optimize import elementwise >>> res_bracket = elementwise.bracket_root(f, 0) >>> res_bracket.success True >>> res_bracket.bracket (2.0, 4.0)
Indeed, the values of the function at the bracket endpoints have opposite signs.
>>> res_bracket.f_bracket (-1.0, 51.0)
Once we have a valid bracket,
find_root
can be used to provide a precise root.>>> res_root = elementwise.find_root(f, res_bracket.bracket) >>> res_root.x 2.0945514815423265
The final bracket is only a few ULPs wide, so the error between this value and the true root cannot be much smaller within values that are representable in double precision arithmetic.
>>> import numpy as np >>> xl, xr = res_root.bracket >>> (xr - xl) / np.spacing(xl) 2.0 >>> res_root.f_bracket (-8.881784197001252e-16, 9.769962616701378e-15)
bracket_root
andfind_root
accept arrays for most arguments. For instance, to find the root for a few values of the parameterc
at once:>>> c = np.asarray([3, 4, 5]) >>> res_bracket = elementwise.bracket_root(f, 0, args=(c,)) >>> res_bracket.bracket (array([1., 1., 2.]), array([2., 2., 4.])) >>> res_root = elementwise.find_root(f, res_bracket.bracket, args=(c,)) >>> res_root.x array([1.8932892 , 2. , 2.09455148])