Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

Bisection

template <class F, class T, class Tol>
std::pair<T, T>
   bisect(  // Unlimited iterations.
      F f,
      T min,
      T max,
      Tol tol);

template <class F, class T, class Tol>
std::pair<T, T>
   bisect(  // Limited iterations.
      F f,
      T min,
      T max,
      Tol tol,
      std::uintmax_t& max_iter);

template <class F, class T, class Tol, class Policy>
std::pair<T, T>
   bisect( // Specified policy.
      F f,
      T min,
      T max,
      Tol tol,
      std::uintmax_t& max_iter,
      const Policy&);

These functions locate the root using bisection.

bisect function arguments are:

f

A unary functor (or C++ lambda) which is the function f(x) whose root is to be found.

min

The left bracket of the interval known to contain the root.

max

The right bracket of the interval known to contain the root.
It is a precondition that min < max and f(min)*f(max) <= 0, the function raises an evaluation_error if these preconditions are violated. The action taken on error is controlled by the Policy template argument: the default behavior is to throw a boost::math::evaluation_error. If the Policy is changed to not throw then it returns std::pair<T>(min, min).

tol

A binary functor (or C++ lambda) that specifies the termination condition: the function will return the current brackets enclosing the root when tol(min, max) becomes true. See also predefined termination functors.

max_iter

The maximum number of invocations of f(x) to make while searching for the root. On exit, this is updated 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 updated value of max_iter when the function returns), rather than because the termination condition tol was satisfied.


PrevUpHomeNext