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

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,
      boost::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,
      boost::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:

f

A unary functor that is the function whose root is to be solved. f(x) must be uniformly increasing or decreasing on x.

guess

An initial approximation to the root.

factor

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.

rising

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.

tol

A binary functor 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.

max_iter

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.


PrevUpHomeNext