rootfind.h File Reference

Deterministic scalar root finding. More...

#include <cstddef>
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for rootfind.h:

Go to the source code of this file.

Classes
struct	line::RootResult< T >
	Outcome of a scalar solve. More...

Namespaces
namespace	line

Functions
template<class T, class F>
RootResult< T >	line::root_bisect (F f, const T &a, const T &b, const T &tol, unsigned maxiter=200)
	Bisection on a bracket with a sign change.
template<class T, class F>
RootResult< T >	line::root_brent (F f, const T &a0, const T &b0, const T &tol, unsigned maxiter=200)
	Brent's method on a bracket with a sign change.
template<class T, class F, class DF>
RootResult< T >	line::root_newton (F f, DF df, const T &x0, const T &tol, unsigned maxiter=200)
	Plain Newton from a starting point.
template<class T, class F, class DF>
RootResult< T >	line::root_newton_safe (F f, DF df, const T &a0, const T &b0, const T &tol, unsigned maxiter=200)
	Newton safeguarded by a bracket with a sign change: the Newton step is used only when it stays inside the bracket and at least halves it, otherwise the step is a bisection.
template<class T, class F>
void	line::bracket_expand (F f, const T &a, T &b, unsigned maxdoubling=200)
	Expand a bracket to the right until f changes sign, doubling the upper end.

Detailed Description

Deterministic scalar root finding.

This is the replacement for MATLAB's fsolve in the scalar cases the API layer needs (the characteristic-time equations of the TTL cache approximations, matlab/src/api/cache/cache_ttl_lrua.m and cache_t_lrum_map.m, whose per-list residual is monotone in its own time). fsolve is a trust-region method seeded from a caller-supplied – in cache_ttl_lrua.m, a randomly generated – initial point, and its answer therefore depends on rng state and on Optimization Toolbox availability. Everything here is bracket based and deterministic: the same bracket and tolerance always produce the same digits, with no global state, no toolbox, and no fallback path that silently changes method.

Three methods are provided: root_bisect - bisection, one bit per iteration, cannot fail once the bracket has a sign change root_brent - Brent's method (inverse quadratic interpolation, secant and bisection), superlinear but never worse than bisection because every step is kept inside the bracket root_newton - plain Newton from a starting point, for roots of even multiplicity, which no bracketing method can see root_newton_safe - Newton safeguarded by a bracket: the Newton step is taken only when it lands inside the current bracket and reduces it, otherwise the step is a bisection

ARITHMETIC: comparisons, addition, multiplication and division only, so these instantiate at every backend including exact rationals. Note that a root is still only located to the caller's tolerance: exact arithmetic makes the iterates exact, not the answer, since an algebraic root need not be rational at all.

Definition in file rootfind.h.