...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
#include <boost/math/tools/roots.hpp>
namespace boost { namespace math { namespace tools { // Note namespace boost::math::tools. // Bisection template <class F, class T, class Tol> std::pair<T, T> bisect( F f, T min, T max, Tol tol, std::uintmax_t& max_iter); template <class F, class T, class Tol> std::pair<T, T> bisect( F f, T min, T max, Tol tol); template <class F, class T, class Tol, class Policy> std::pair<T, T> bisect( F f, T min, T max, Tol tol, std::uintmax_t& max_iter, const Policy&); // Bracket and Solve Root 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&); // TOMS 748 algorithm template <class F, class T, class Tol> std::pair<T, T> toms748_solve( F f, const T& a, const T& b, Tol tol, std::uintmax_t& max_iter); template <class F, class T, class Tol, class Policy> std::pair<T, T> toms748_solve( F f, const T& a, const T& b, Tol tol, std::uintmax_t& max_iter, const Policy&); template <class F, class T, class Tol> std::pair<T, T> toms748_solve( F f, const T& a, const T& b, const T& fa, const T& fb, Tol tol, std::uintmax_t& max_iter); template <class F, class T, class Tol, class Policy> std::pair<T, T> toms748_solve( F f, const T& a, const T& b, const T& fa, const T& fb, Tol tol, std::uintmax_t& max_iter, const Policy&); // Termination conditions: template <class T> struct eps_tolerance; struct equal_floor; struct equal_ceil; struct equal_nearest_integer; }}} // boost::math::tools namespaces
These functions solve the root of some function f(x) - without the need for any derivatives of f(x).
The bracket_and_solve_root
functions use TOMS 748 algorithm
by Alefeld, Potra and Shi that is asymptotically the most efficient known,
and has been shown to be optimal for a certain classes of smooth functions.
Variants with and without Policies are provided.
Alternatively, bisect is a simple bisection routine which can be useful in its own right in some situations, or alternatively for narrowing down the range containing the root, prior to calling a more advanced algorithm.
All the algorithms in this section reduce the diameter of the enclosing interval
with the same asymptotic efficiency with which they locate the root. This is
in contrast to the derivative based methods which may never
significantly reduce the enclosing interval, even though they rapidly approach
the root. This is also in contrast to some other derivative-free methods (for
example, Brent's method described at Brent-Dekker)
which only reduces the enclosing interval on the final step. Therefore these
methods return a std::pair
containing the enclosing interval found,
and accept a function object specifying the termination condition.
Three function objects are provided for ready-made termination conditions: