1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Bisection</title> 5<link rel="stylesheet" href="../../math.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../index.html" title="Math Toolkit 2.12.0"> 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"> 11</head> 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> 20</tr></table> 21<hr> 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> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h3 class="title"> 27<a name="math_toolkit.roots_noderiv.bisect"></a><a class="link" href="bisect.html" title="Bisection">Bisection</a> 28</h3></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> 36 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> 45 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 21. 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 21. Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&);</span> 55</pre> 56<p> 57 These functions locate the root using <a href="https://en.wikipedia.org/wiki/Bisection" target="_top">bisection</a>. 58 </p> 59<p> 60 <code class="computeroutput"><span class="identifier">bisect</span></code> function arguments 61 are: 62 </p> 63<div class="variablelist"> 64<p class="title"><b></b></p> 65<dl class="variablelist"> 66<dt><span class="term">f</span></dt> 67<dd><p> 68 A unary functor (or C++ lambda) which is the function <span class="emphasis"><em>f(x)</em></span> 69 whose root is to be found. 70 </p></dd> 71<dt><span class="term">min</span></dt> 72<dd><p> 73 The left bracket of the interval known to contain the root. 74 </p></dd> 75<dt><span class="term">max</span></dt> 76<dd><p> 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 <span class="emphasis"><em>f(min)*f(max) 79 <= 0</em></span>, the function raises an <a class="link" href="../error_handling.html#math_toolkit.error_handling.evaluation_error">evaluation_error</a> 80 if these preconditions are violated. The action taken on error is controlled 81 by the <a class="link" href="../../policy.html" title="Chapter 21. Policies: Controlling Precision, Error Handling etc">Policy</a> template argument: the 82 default behavior is to throw a <span class="emphasis"><em>boost::math::evaluation_error</em></span>. 83 If the <a class="link" href="../../policy.html" title="Chapter 21. Policies: Controlling Precision, Error Handling etc">Policy</a> is changed to not throw 84 then it returns <span class="emphasis"><em>std::pair<T>(min, min)</em></span>. 85 </p></dd> 86<dt><span class="term">tol</span></dt> 87<dd><p> 88 A binary functor (or C++ lambda) that specifies the termination condition: 89 the function will return the current brackets enclosing the root when 90 <span class="emphasis"><em>tol(min, max)</em></span> becomes true. See also <a class="link" href="root_termination.html" title="Termination Condition Functors">predefined 91 termination functors</a>. 92 </p></dd> 93<dt><span class="term">max_iter</span></dt> 94<dd><p> 95 The maximum number of invocations of <span class="emphasis"><em>f(x)</em></span> to make 96 while searching for the root. On exit, this is updated to the actual 97 number of invocations performed. 98 </p></dd> 99</dl> 100</div> 101<p> 102 The final <a class="link" href="../../policy.html" title="Chapter 21. Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and can 103 be used to control the behaviour of the function: how it handles errors, 104 what level of precision to use etc. Refer to the <a class="link" href="../../policy.html" title="Chapter 21. Policies: Controlling Precision, Error Handling etc">policy 105 documentation for more details</a>. 106 </p> 107<p> 108 <span class="bold"><strong>Returns</strong></span>: a pair of values <span class="emphasis"><em>r</em></span> 109 that bracket the root so that: 110 </p> 111<div class="blockquote"><blockquote class="blockquote"><p> 112 f(r.first) * f(r.second) <= 0 113 </p></blockquote></div> 114<p> 115 and either 116 </p> 117<div class="blockquote"><blockquote class="blockquote"><p> 118 tol(r.first, r.second) == true 119 </p></blockquote></div> 120<p> 121 or 122 </p> 123<div class="blockquote"><blockquote class="blockquote"><p> 124 max_iter >= m 125 </p></blockquote></div> 126<p> 127 where <span class="emphasis"><em>m</em></span> is the initial value of <span class="emphasis"><em>max_iter</em></span> 128 passed to the function. 129 </p> 130<p> 131 In other words, it's up to the caller to verify whether termination occurred 132 as a result of exceeding <span class="emphasis"><em>max_iter</em></span> function invocations 133 (easily done by checking the updated value of <span class="emphasis"><em>max_iter</em></span> 134 when the function returns), rather than because the termination condition 135 <span class="emphasis"><em>tol</em></span> was satisfied. 136 </p> 137</div> 138<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 139<td align="left"></td> 140<td align="right"><div class="copyright-footer">Copyright © 2006-2019 Nikhar 141 Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, 142 Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan 143 Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, 144 Daryle Walker and Xiaogang Zhang<p> 145 Distributed under the Boost Software License, Version 1.0. (See accompanying 146 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>) 147 </p> 148</div></td> 149</tr></table> 150<hr> 151<div class="spirit-nav"> 152<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> 153</div> 154</body> 155</html> 156
