View source on GitHub |
Finds root(s) of a scalar function using Chandrupatla's method.
tfp.substrates.jax.math.find_root_chandrupatla(
objective_fn,
low=None,
high=None,
position_tolerance=1e-08,
value_tolerance=0.0,
max_iterations=50,
stopping_policy_fn=tf.reduce_all,
validate_args=False,
name='find_root_chandrupatla'
)
Chandrupatla's method [1, 2] is a root-finding algorithm that is guaranteed to converge if a root lies within the given bounds. It generalizes the bisection method; at each step it chooses to perform either bisection or inverse quadratic interpolation. This makes it similar in spirit to Brent's method, which also considers steps that use the secant method, but Chandrupatla's method is simpler and often converges at least as quickly [3].
Args | |
---|---|
objective_fn
|
Python callable for which roots are searched. It must be a
callable of a single variable. objective_fn must return a Tensor with
shape batch_shape and dtype matching lower_bound and upper_bound .
|
low
|
Float Tensor of shape batch_shape representing a lower
bound(s) on the value of a root(s). If either of low or high is not
provided, both are ignored and tfp.math.bracket_root is used to attempt
to infer bounds.
Default value: None .
|
high
|
Float Tensor of shape batch_shape representing an upper
bound(s) on the value of a root(s). If either of low or high is not
provided, both are ignored and tfp.math.bracket_root is used to attempt
to infer bounds.
Default value: None .
|
position_tolerance
|
Optional Tensor representing the maximum absolute
error in the positions of the estimated roots. Shape must broadcast with
batch_shape .
Default value: 1e-8 .
|
value_tolerance
|
Optional Tensor representing the absolute error allowed
in the value of the objective function. If the absolute value of
objective_fn is smaller than
value_tolerance at a given position, then that position is considered a
root for the function. Shape must broadcast with batch_shape .
Default value: 1e-8 .
|
max_iterations
|
Optional Tensor or Python integer specifying the maximum
number of steps to perform. Shape must broadcast with batch_shape .
Default value: 50 .
|
stopping_policy_fn
|
Python callable controlling the algorithm termination.
It must be a callable accepting a Tensor of booleans with the same shape
as lower_bound and upper_bound (denoting whether each search is
finished), and returning a scalar boolean Tensor indicating
whether the overall search should stop. Typical values are
tf.reduce_all (which returns only when the search is finished for all
points), and tf.reduce_any (which returns as soon as the search is
finished for any point).
Default value: tf.reduce_all (returns only when the search is finished
for all points).
|
validate_args
|
Python bool indicating whether to validate arguments.
Default value: False .
|
name
|
Python str name prefixed to ops created by this function.
Default value: 'find_root_chandrupatla'.
|
References
[1] Tirupathi R. Chandrupatla. 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, 1997. [2] Philipp OJ Scherer. Computational Physics. Springer Berlin, Heidelberg, 2010. Section 6.1.7.3 https://books.google.com/books?id=cC-8BAAAQBAJ&pg=PA95 [3] Jason Sachs. Ten Little Algorithms, Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method (2015). https://www.embeddedrelated.com/showarticle/855.php