papyri
{ } Raw JSON

bundles / scipy 1.18.0 / scipy / optimize / _elementwise / find_root

function

scipy.optimize._elementwise:find_root

source: /scipy/optimize/_elementwise.py:7

Signature

def find_root(f, init, /, args = (), kwargs = None, tolerances = None, maxiter = None, callback = None)

Summary

Find the root of a monotonic, real-valued function of a real variable.

Extended Summary

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

f : callable

The function whose root is desired. The signature must be 

f(x: array, *args) -> array

where each element of x is a finite real and args is a tuple, which may contain an arbitrary number of arrays that are broadcastable with x.

f must be an elementwise function: each element f(x)[i] must equal f(x[i]) for all indices i. It must not mutate the array x or the arrays in args.

find_root seeks an array x such that f(x) is an array of zeros.

init : 2-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 satisfy xl < xr and sign(f(xl)) == -sign(f(xr)) elementwise. Arrays be broadcastable with one another and args.

args : tuple 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.

kwargs : dict of str:array_like, optional

Additional keyword arguments to be passed to f. See args.

tolerances : dictionary of floats, optional

Absolute and relative tolerances on the root and function value. Valid keys of the dictionary are:

  • xatol - absolute tolerance on the root

  • xrtol - relative tolerance on the root

  • fatol - absolute tolerance on the function value

  • frtol - relative tolerance on the function value

See Notes for default values and explicit termination conditions.

maxiter : int, 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.

callback : callable, optional

An optional user-supplied function to be called before the first iteration and after each iteration. Called as callback(res), where res is a _RichResult similar to that returned by find_root (but containing the current iterate's values of all variables). If callback raises a StopIteration, the algorithm will terminate immediately and find_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.

success

True where the algorithm terminated successfully (status 0); False otherwise.

status

An integer representing the exit status of the algorithm.

  • 0The algorithm converged to the specified tolerances.

  • -1The initial bracket was invalid.

  • -2The maximum number of iterations was reached.

  • -3A non-finite value was encountered.

  • -4Iteration was terminated by callback.

  • 1The algorithm is proceeding normally (in callback only).

x

The root of the function, if the algorithm terminated successfully.

f_x

The value of f evaluated at x.

nfev

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.

nit

The number of iterations of the algorithm that were performed.

bracket

The lower and upper endpoints of the final bracket.

f_bracket

The value of f evaluated at the lower and upper endpoints of the bracket.

Notes

Implemented based on Chandrupatla's original paper [1].

Let:

  • a, b = init be the left and right endpoints of the initial bracket,

  • xl and xr 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, and

  • fmin0 = 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 or

  • fun(xmin) <= fatol + abs(fmin0) * frtol.

This is equivalent to the termination condition described in [1] with xrtol = 4e-10, xatol = 1e-5, and fatol = frtol = 0. However, the default values of the tolerances dictionary are xatol = 4*tiny, xrtol = 4*eps, frtol = 0, and fatol = tiny, where eps and tiny are the precision and smallest normal number of the result dtype of function inputs and outputs.

Array API Standard Support

find_root has experimental support for Python Array API Standard compatible backends in addition to NumPy. Please consider testing these features by setting an environment variable SCIPY_ARRAY_API=1 and providing CuPy, PyTorch, JAX, or Dask arrays as array arguments. The following combinations of backend and device (or other capability) are supported.

====================  ====================  ====================
Library               CPU                   GPU
====================  ====================  ====================
NumPy                 ✅                     n/a                 
CuPy                  n/a                   ✅                   
PyTorch               ✅                     ✅                   
JAX                   ⛔                     ⛔                   
Dask                  ⛔                     n/a                 
====================  ====================  ====================

See dev-arrayapi for more information.

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
res_bracket.bracket
✗
(np.float64(2.0), np.float64(4.0))
Indeed, the values of the function at the bracket endpoints have opposite signs. 
res_bracket.f_bracket
✗
(np.float64(-1.0), np.float64(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
✗
np.float64(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)
res_root.f_bracket
✗
(np.float64(-8.881784197001252e-16), np.float64(9.769962616701378e-15))
`bracket_root` and `find_root` accept arrays for most arguments. For instance, to find the root for a few values of the parameter ``c`` at once: 
c = np.asarray([3, 4, 5])
res_bracket = elementwise.bracket_root(f, 0, args=(c,))
res_bracket.bracket
res_root = elementwise.find_root(f, res_bracket.bracket, args=(c,))
✓
res_root.x
✗
array([1.89329, 2.     , 2.09455])

See also

bracket_root

Aliases

  • scipy.optimize._elementwise.find_root

Referenced by

This package