...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
template <class F, class T, class Tol> std::pair<T, T> bracket_and_solve_root( F f, const T& guess, const T& factor, bool rising, Tol tol, std::uintmax_t& max_iter); template <class F, class T, class Tol, class Policy> std::pair<T, T> bracket_and_solve_root( F f, const T& guess, const T& factor, bool rising, Tol tol, std::uintmax_t& max_iter, const Policy&);
bracket_and_solve_root
is
a convenience function that calls TOMS
748 algorithm internally to find the root of f(x).
It is generally much easier to use this function rather than TOMS
748 algorithm, since it does the hard work of bracketing the root
for you. It's bracketing routines are quite robust and will usually be more
foolproof than home-grown routines, unless the function can be analysed to
yield tight brackets.
Note that this routine can only be used when:
The bracket_and_solve_root
parameters are:
A unary functor (or C++ lambda) that is the function whose root is to be solved. f(x) must be uniformly increasing or decreasing on x.
An initial approximation to the root.
A scaling factor that is used to bracket the root: the value guess is multiplied (or divided as appropriate) by factor until two values are found that bracket the root. A value such as 2 is a typical choice for factor. In addition factor will be multiplied by 2 every 32 iterations: this is to guard against a really very bad initial guess, typically these occur when it's known the result is very large or small, but not the exact order of magnitude.
Set to true if f(x) is rising on x and false if f(x) is falling on x. This value is used along with the result of f(guess) to determine if guess is above or below the root.
A binary functor (or C++ lambda) that determines the termination condition for the search for the root. tol is passed the current brackets at each step, when it returns true then the current brackets are returned as the pair result. See also predefined termination functors.
The maximum number of function invocations to perform in the search for the root. On exit is set to the actual number of invocations performed.
The final Policy argument is optional and can be used to control the behaviour of the function: how it handles errors, what level of precision to use etc. Refer to the policy documentation for more details.
Returns: a pair of values r that bracket the root so that:
f(r.first) * f(r.second) <= 0
and either
tol(r.first, r.second) == true
or
max_iter >= m
where m is the initial value of max_iter passed to the function.
In other words, it's up to the caller to verify whether termination occurred as a result of exceeding max_iter function invocations (easily done by checking the value of max_iter when the function returns), rather than because the termination condition tol was satisfied.