3 <meta http-equiv=
"Content-Type" content=
"text/html; charset=US-ASCII">
4 <title>Bisection
</title>
5 <link rel=
"stylesheet" href=
"../../../math.css" type=
"text/css">
6 <meta name=
"generator" content=
"DocBook XSL Stylesheets V1.77.1">
7 <link rel=
"home" href=
"../../../index.html" title=
"Math Toolkit 2.5.1">
8 <link rel=
"up" href=
"../roots_noderiv.html" title=
"Root Finding Without Derivatives">
9 <link rel=
"prev" href=
"../roots_noderiv.html" title=
"Root Finding Without Derivatives">
10 <link rel=
"next" href=
"bracket_solve.html" title=
"Bracket and Solve Root">
12 <body bgcolor=
"white" text=
"black" link=
"#0000FF" vlink=
"#840084" alink=
"#0000FF">
13 <table cellpadding=
"2" width=
"100%"><tr>
14 <td valign=
"top"><img alt=
"Boost C++ Libraries" width=
"277" height=
"86" src=
"../../../../../../../boost.png"></td>
15 <td align=
"center"><a href=
"../../../../../../../index.html">Home
</a></td>
16 <td align=
"center"><a href=
"../../../../../../../libs/libraries.htm">Libraries
</a></td>
17 <td align=
"center"><a href=
"http://www.boost.org/users/people.html">People
</a></td>
18 <td align=
"center"><a href=
"http://www.boost.org/users/faq.html">FAQ
</a></td>
19 <td align=
"center"><a href=
"../../../../../../../more/index.htm">More
</a></td>
22 <div class=
"spirit-nav">
23 <a accesskey=
"p" href=
"../roots_noderiv.html"><img src=
"../../../../../../../doc/src/images/prev.png" alt=
"Prev"></a><a accesskey=
"u" href=
"../roots_noderiv.html"><img src=
"../../../../../../../doc/src/images/up.png" alt=
"Up"></a><a accesskey=
"h" href=
"../../../index.html"><img src=
"../../../../../../../doc/src/images/home.png" alt=
"Home"></a><a accesskey=
"n" href=
"bracket_solve.html"><img src=
"../../../../../../../doc/src/images/next.png" alt=
"Next"></a>
26 <div class=
"titlepage"><div><div><h4 class=
"title">
27 <a name=
"math_toolkit.roots.roots_noderiv.bisect"></a><a class=
"link" href=
"bisect.html" title=
"Bisection">Bisection
</a>
28 </h4></div></div></div>
29 <pre class=
"programlisting"><span class=
"keyword">template
</span> <span class=
"special"><</span><span class=
"keyword">class
</span> <span class=
"identifier">F
</span><span class=
"special">,
</span> <span class=
"keyword">class
</span> <span class=
"identifier">T
</span><span class=
"special">,
</span> <span class=
"keyword">class
</span> <span class=
"identifier">Tol
</span><span class=
"special">></span>
30 <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">pair
</span><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">,
</span> <span class=
"identifier">T
</span><span class=
"special">></span>
31 <span class=
"identifier">bisect
</span><span class=
"special">(
</span> <span class=
"comment">// Unlimited iterations.
</span>
32 <span class=
"identifier">F
</span> <span class=
"identifier">f
</span><span class=
"special">,
</span>
33 <span class=
"identifier">T
</span> <span class=
"identifier">min
</span><span class=
"special">,
</span>
34 <span class=
"identifier">T
</span> <span class=
"identifier">max
</span><span class=
"special">,
</span>
35 <span class=
"identifier">Tol
</span> <span class=
"identifier">tol
</span><span class=
"special">);
</span>
37 <span class=
"keyword">template
</span> <span class=
"special"><</span><span class=
"keyword">class
</span> <span class=
"identifier">F
</span><span class=
"special">,
</span> <span class=
"keyword">class
</span> <span class=
"identifier">T
</span><span class=
"special">,
</span> <span class=
"keyword">class
</span> <span class=
"identifier">Tol
</span><span class=
"special">></span>
38 <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">pair
</span><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">,
</span> <span class=
"identifier">T
</span><span class=
"special">></span>
39 <span class=
"identifier">bisect
</span><span class=
"special">(
</span> <span class=
"comment">// Limited iterations.
</span>
40 <span class=
"identifier">F
</span> <span class=
"identifier">f
</span><span class=
"special">,
</span>
41 <span class=
"identifier">T
</span> <span class=
"identifier">min
</span><span class=
"special">,
</span>
42 <span class=
"identifier">T
</span> <span class=
"identifier">max
</span><span class=
"special">,
</span>
43 <span class=
"identifier">Tol
</span> <span class=
"identifier">tol
</span><span class=
"special">,
</span>
44 <span class=
"identifier">boost
</span><span class=
"special">::
</span><span class=
"identifier">uintmax_t
</span><span class=
"special">&</span> <span class=
"identifier">max_iter
</span><span class=
"special">);
</span>
46 <span class=
"keyword">template
</span> <span class=
"special"><</span><span class=
"keyword">class
</span> <span class=
"identifier">F
</span><span class=
"special">,
</span> <span class=
"keyword">class
</span> <span class=
"identifier">T
</span><span class=
"special">,
</span> <span class=
"keyword">class
</span> <span class=
"identifier">Tol
</span><span class=
"special">,
</span> <span class=
"keyword">class
</span> <a class=
"link" href=
"../../../policy.html" title=
"Chapter 15. Policies: Controlling Precision, Error Handling etc">Policy
</a><span class=
"special">></span>
47 <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">pair
</span><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">,
</span> <span class=
"identifier">T
</span><span class=
"special">></span>
48 <span class=
"identifier">bisect
</span><span class=
"special">(
</span> <span class=
"comment">// Specified policy.
</span>
49 <span class=
"identifier">F
</span> <span class=
"identifier">f
</span><span class=
"special">,
</span>
50 <span class=
"identifier">T
</span> <span class=
"identifier">min
</span><span class=
"special">,
</span>
51 <span class=
"identifier">T
</span> <span class=
"identifier">max
</span><span class=
"special">,
</span>
52 <span class=
"identifier">Tol
</span> <span class=
"identifier">tol
</span><span class=
"special">,
</span>
53 <span class=
"identifier">boost
</span><span class=
"special">::
</span><span class=
"identifier">uintmax_t
</span><span class=
"special">&</span> <span class=
"identifier">max_iter
</span><span class=
"special">,
</span>
54 <span class=
"keyword">const
</span> <a class=
"link" href=
"../../../policy.html" title=
"Chapter 15. Policies: Controlling Precision, Error Handling etc">Policy
</a><span class=
"special">&);
</span>
57 These functions locate the root using
<a href=
"https://en.wikipedia.org/wiki/Bisection" target=
"_top">bisection
</a>.
60 <code class=
"computeroutput"><span class=
"identifier">bisect
</span></code> function arguments
63 <div class=
"variablelist">
64 <p class=
"title"><b></b></p>
65 <dl class=
"variablelist">
66 <dt><span class=
"term">f
</span></dt>
68 A unary functor which is the function
<span class=
"emphasis"><em>f(x)
</em></span> whose
71 <dt><span class=
"term">min
</span></dt>
73 The left bracket of the interval known to contain the root.
75 <dt><span class=
"term">max
</span></dt>
77 The right bracket of the interval known to contain the root.
<br>
78 It is a precondition that
<span class=
"emphasis"><em>min
< max
</em></span> and
79 <span class=
"emphasis"><em>f(min)*f(max)
<=
0</em></span>, the function raises an
80 <a class=
"link" href=
"../../error_handling.html#math_toolkit.error_handling.evaluation_error">evaluation_error
</a>
81 if these preconditions are violated. The action taken on error is
82 controlled by the
<a class=
"link" href=
"../../../policy.html" title=
"Chapter 15. Policies: Controlling Precision, Error Handling etc">Policy
</a> template argument:
83 the default behavior is to throw a
<span class=
"emphasis"><em>boost::math::evaluation_error
</em></span>.
84 If the
<a class=
"link" href=
"../../../policy.html" title=
"Chapter 15. Policies: Controlling Precision, Error Handling etc">Policy
</a> is changed to not throw
85 then it returns
<span class=
"emphasis"><em>std::pair
<T
>(min, min)
</em></span>.
87 <dt><span class=
"term">tol
</span></dt>
89 A binary functor that specifies the termination condition: the function
90 will return the current brackets enclosing the root when
<span class=
"emphasis"><em>tol(min,
91 max)
</em></span> becomes true. See also
<a class=
"link" href=
"root_termination.html" title=
"Termination Condition Functors">predefined
92 termination functors
</a>.
94 <dt><span class=
"term">max_iter
</span></dt>
96 The maximum number of invocations of
<span class=
"emphasis"><em>f(x)
</em></span> to
97 make while searching for the root. On exit, this is updated to the
98 actual number of invocations performed.
103 The final
<a class=
"link" href=
"../../../policy.html" title=
"Chapter 15. Policies: Controlling Precision, Error Handling etc">Policy
</a> argument is optional and
104 can be used to control the behaviour of the function: how it handles errors,
105 what level of precision to use etc. Refer to the
<a class=
"link" href=
"../../../policy.html" title=
"Chapter 15. Policies: Controlling Precision, Error Handling etc">policy
106 documentation for more details
</a>.
109 <span class=
"bold"><strong>Returns
</strong></span>: a pair of values
<span class=
"emphasis"><em>r
</em></span>
110 that bracket the root so that:
112 <pre class=
"programlisting"><span class=
"identifier">f
</span><span class=
"special">(
</span><span class=
"identifier">r
</span><span class=
"special">.
</span><span class=
"identifier">first
</span><span class=
"special">)
</span> <span class=
"special">*
</span> <span class=
"identifier">f
</span><span class=
"special">(
</span><span class=
"identifier">r
</span><span class=
"special">.
</span><span class=
"identifier">second
</span><span class=
"special">)
</span> <span class=
"special"><=
</span> <span class=
"number">0</span>
117 <pre class=
"programlisting"><span class=
"identifier">tol
</span><span class=
"special">(
</span><span class=
"identifier">r
</span><span class=
"special">.
</span><span class=
"identifier">first
</span><span class=
"special">,
</span> <span class=
"identifier">r
</span><span class=
"special">.
</span><span class=
"identifier">second
</span><span class=
"special">)
</span> <span class=
"special">==
</span> <span class=
"keyword">true
</span>
122 <pre class=
"programlisting"><span class=
"identifier">max_iter
</span> <span class=
"special">>=
</span> <span class=
"identifier">m
</span>
125 where
<span class=
"emphasis"><em>m
</em></span> is the initial value of
<span class=
"emphasis"><em>max_iter
</em></span>
126 passed to the function.
129 In other words, it's up to the caller to verify whether termination occurred
130 as a result of exceeding
<span class=
"emphasis"><em>max_iter
</em></span> function invocations
131 (easily done by checking the updated value of
<span class=
"emphasis"><em>max_iter
</em></span>
132 when the function returns), rather than because the termination condition
133 <span class=
"emphasis"><em>tol
</em></span> was satisfied.
136 <table xmlns:
rev=
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width=
"100%"><tr>
137 <td align=
"left"></td>
138 <td align=
"right"><div class=
"copyright-footer">Copyright
© 2006-
2010,
2012-
2014 Nikhar Agrawal,
139 Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert
140 Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Johan R
åde, Gautam Sewani,
141 Benjamin Sobotta, Thijs van den Berg, Daryle Walker and Xiaogang Zhang
<p>
142 Distributed under the Boost Software License, Version
1.0. (See accompanying
143 file LICENSE_1_0.txt or copy at
<a href=
"http://www.boost.org/LICENSE_1_0.txt" target=
"_top">http://www.boost.org/LICENSE_1_0.txt
</a>)
148 <div class=
"spirit-nav">
149 <a accesskey=
"p" href=
"../roots_noderiv.html"><img src=
"../../../../../../../doc/src/images/prev.png" alt=
"Prev"></a><a accesskey=
"u" href=
"../roots_noderiv.html"><img src=
"../../../../../../../doc/src/images/up.png" alt=
"Up"></a><a accesskey=
"h" href=
"../../../index.html"><img src=
"../../../../../../../doc/src/images/home.png" alt=
"Home"></a><a accesskey=
"n" href=
"bracket_solve.html"><img src=
"../../../../../../../doc/src/images/next.png" alt=
"Next"></a>