1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Bracket and Solve Root</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="bisect.html" title="Bisection"> 10<link rel="next" href="TOMS748.html" title="Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions"> 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="bisect.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="TOMS748.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.bracket_solve"></a><a class="link" href="bracket_solve.html" title="Bracket and Solve Root">Bracket and 28 Solve Root</a> 29</h3></div></div></div> 30<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> 31<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> 32 <span class="identifier">bracket_and_solve_root</span><span class="special">(</span> 33 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 34 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">guess</span><span class="special">,</span> 35 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">factor</span><span class="special">,</span> 36 <span class="keyword">bool</span> <span class="identifier">rising</span><span class="special">,</span> 37 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 38 <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> 39 40<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> 41<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> 42 <span class="identifier">bracket_and_solve_root</span><span class="special">(</span> 43 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 44 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">guess</span><span class="special">,</span> 45 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">factor</span><span class="special">,</span> 46 <span class="keyword">bool</span> <span class="identifier">rising</span><span class="special">,</span> 47 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 48 <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> 49 <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> 50</pre> 51<p> 52 <code class="computeroutput"><span class="identifier">bracket_and_solve_root</span></code> is 53 a convenience function that calls <a class="link" href="TOMS748.html" title="Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions">TOMS 54 748 algorithm</a> internally to find the root of <span class="emphasis"><em>f(x)</em></span>. 55 It is generally much easier to use this function rather than <a class="link" href="TOMS748.html" title="Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions">TOMS 56 748 algorithm</a>, since it does the hard work of bracketing the root 57 for you. It's bracketing routines are quite robust and will usually be more 58 foolproof than home-grown routines, unless the function can be analysed to 59 yield tight brackets. 60 </p> 61<p> 62 Note that this routine can only be used when: 63 </p> 64<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 65<li class="listitem"> 66 <span class="emphasis"><em>f(x)</em></span> is monotonic in the half of the real axis containing 67 <span class="emphasis"><em>guess</em></span>. 68 </li> 69<li class="listitem"> 70 The value of the initial guess must have the same sign as the root: the 71 function will <span class="emphasis"><em>never cross the origin</em></span> when searching 72 for the root. 73 </li> 74<li class="listitem"> 75 The location of the root should be known at least approximately, if the 76 location of the root differs by many orders of magnitude from <span class="emphasis"><em>guess</em></span> 77 then many iterations will be needed to bracket the root in spite of the 78 special heuristics used to guard against this very situation. A typical 79 example would be setting the initial guess to 0.1, when the root is at 80 1e-300. 81 </li> 82</ul></div> 83<p> 84 The <code class="computeroutput"><span class="identifier">bracket_and_solve_root</span></code> 85 parameters are: 86 </p> 87<div class="variablelist"> 88<p class="title"><b></b></p> 89<dl class="variablelist"> 90<dt><span class="term">f</span></dt> 91<dd><p> 92 A unary functor (or C++ lambda) that is the function whose root is 93 to be solved. <span class="emphasis"><em>f(x)</em></span> must be uniformly increasing 94 or decreasing on <span class="emphasis"><em>x</em></span>. 95 </p></dd> 96<dt><span class="term">guess</span></dt> 97<dd><p> 98 An initial approximation to the root. 99 </p></dd> 100<dt><span class="term">factor</span></dt> 101<dd><p> 102 A scaling factor that is used to bracket the root: the value <span class="emphasis"><em>guess</em></span> 103 is multiplied (or divided as appropriate) by <span class="emphasis"><em>factor</em></span> 104 until two values are found that bracket the root. A value such as 2 105 is a typical choice for <span class="emphasis"><em>factor</em></span>. In addition <span class="emphasis"><em>factor</em></span> 106 will be multiplied by 2 every 32 iterations: this is to guard against 107 a really very bad initial guess, typically these occur when it's known 108 the result is very large or small, but not the exact order of magnitude. 109 </p></dd> 110<dt><span class="term">rising</span></dt> 111<dd><p> 112 Set to <span class="emphasis"><em>true</em></span> if <span class="emphasis"><em>f(x)</em></span> is rising 113 on <span class="emphasis"><em>x</em></span> and <span class="emphasis"><em>false</em></span> if <span class="emphasis"><em>f(x)</em></span> 114 is falling on <span class="emphasis"><em>x</em></span>. This value is used along with 115 the result of <span class="emphasis"><em>f(guess)</em></span> to determine if <span class="emphasis"><em>guess</em></span> 116 is above or below the root. 117 </p></dd> 118<dt><span class="term">tol</span></dt> 119<dd><p> 120 A binary functor (or C++ lambda) that determines the termination condition 121 for the search for the root. <span class="emphasis"><em>tol</em></span> is passed the 122 current brackets at each step, when it returns true then the current 123 brackets are returned as the pair result. See also <a class="link" href="root_termination.html" title="Termination Condition Functors">predefined 124 termination functors</a>. 125 </p></dd> 126<dt><span class="term">max_iter</span></dt> 127<dd><p> 128 The maximum number of function invocations to perform in the search 129 for the root. On exit is set to the actual number of invocations performed. 130 </p></dd> 131</dl> 132</div> 133<p> 134 The final <a class="link" href="../../policy.html" title="Chapter 21. Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and can 135 be used to control the behaviour of the function: how it handles errors, 136 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 137 documentation for more details</a>. 138 </p> 139<p> 140 <span class="bold"><strong>Returns</strong></span>: a pair of values <span class="emphasis"><em>r</em></span> 141 that bracket the root so that: 142 </p> 143<div class="blockquote"><blockquote class="blockquote"><p> 144 f(r.first) * f(r.second) <= 0 145 </p></blockquote></div> 146<p> 147 and either 148 </p> 149<div class="blockquote"><blockquote class="blockquote"><p> 150 tol(r.first, r.second) == true 151 </p></blockquote></div> 152<p> 153 or 154 </p> 155<div class="blockquote"><blockquote class="blockquote"><p> 156 max_iter >= m 157 </p></blockquote></div> 158<p> 159 where <span class="emphasis"><em>m</em></span> is the initial value of <span class="emphasis"><em>max_iter</em></span> 160 passed to the function. 161 </p> 162<p> 163 In other words, it's up to the caller to verify whether termination occurred 164 as a result of exceeding <span class="emphasis"><em>max_iter</em></span> function invocations 165 (easily done by checking the value of <span class="emphasis"><em>max_iter</em></span> when 166 the function returns), rather than because the termination condition <span class="emphasis"><em>tol</em></span> 167 was satisfied. 168 </p> 169</div> 170<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 171<td align="left"></td> 172<td align="right"><div class="copyright-footer">Copyright © 2006-2019 Nikhar 173 Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, 174 Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan 175 Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, 176 Daryle Walker and Xiaogang Zhang<p> 177 Distributed under the Boost Software License, Version 1.0. (See accompanying 178 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>) 179 </p> 180</div></td> 181</tr></table> 182<hr> 183<div class="spirit-nav"> 184<a accesskey="p" href="bisect.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="TOMS748.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 185</div> 186</body> 187</html> 188
