1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Root Finding Without Derivatives</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="../root_finding.html" title="Chapter 10. Root Finding & Minimization Algorithms"> 9<link rel="prev" href="../root_finding.html" title="Chapter 10. Root Finding & Minimization Algorithms"> 10<link rel="next" href="roots_noderiv/bisect.html" title="Bisection"> 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="../root_finding.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_finding.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="roots_noderiv/bisect.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 27<a name="math_toolkit.roots_noderiv"></a><a class="link" href="roots_noderiv.html" title="Root Finding Without Derivatives">Root Finding Without Derivatives</a> 28</h2></div></div></div> 29<div class="toc"><dl class="toc"> 30<dt><span class="section"><a href="roots_noderiv/bisect.html">Bisection</a></span></dt> 31<dt><span class="section"><a href="roots_noderiv/bracket_solve.html">Bracket and 32 Solve Root</a></span></dt> 33<dt><span class="section"><a href="roots_noderiv/TOMS748.html">Algorithm TOMS 748: 34 Alefeld, Potra and Shi: Enclosing zeros of continuous functions</a></span></dt> 35<dt><span class="section"><a href="roots_noderiv/brent.html">Brent-Decker Algorithm</a></span></dt> 36<dt><span class="section"><a href="roots_noderiv/root_termination.html">Termination 37 Condition Functors</a></span></dt> 38<dt><span class="section"><a href="roots_noderiv/implementation.html">Implementation</a></span></dt> 39</dl></div> 40<h5> 41<a name="math_toolkit.roots_noderiv.h0"></a> 42 <span class="phrase"><a name="math_toolkit.roots_noderiv.synopsis"></a></span><a class="link" href="roots_noderiv.html#math_toolkit.roots_noderiv.synopsis">Synopsis</a> 43 </h5> 44<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">tools</span><span class="special">/</span><span class="identifier">roots</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 45</pre> 46<pre class="programlisting"> <span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span> <span class="special">{</span> 47 <span class="keyword">namespace</span> <span class="identifier">tools</span> <span class="special">{</span> <span class="comment">// Note namespace boost::math::tools.</span> 48 <span class="comment">// Bisection</span> 49 <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> 50 <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> 51 <span class="identifier">bisect</span><span class="special">(</span> 52 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 53 <span class="identifier">T</span> <span class="identifier">min</span><span class="special">,</span> 54 <span class="identifier">T</span> <span class="identifier">max</span><span class="special">,</span> 55 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 56 <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> 57 58 <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> 59 <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> 60 <span class="identifier">bisect</span><span class="special">(</span> 61 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 62 <span class="identifier">T</span> <span class="identifier">min</span><span class="special">,</span> 63 <span class="identifier">T</span> <span class="identifier">max</span><span class="special">,</span> 64 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">);</span> 65 66 <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> 67 <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> 68 <span class="identifier">bisect</span><span class="special">(</span> 69 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 70 <span class="identifier">T</span> <span class="identifier">min</span><span class="special">,</span> 71 <span class="identifier">T</span> <span class="identifier">max</span><span class="special">,</span> 72 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 73 <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> 74 <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> 75 76 <span class="comment">// Bracket and Solve Root</span> 77 <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> 78 <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> 79 <span class="identifier">bracket_and_solve_root</span><span class="special">(</span> 80 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 81 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">guess</span><span class="special">,</span> 82 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">factor</span><span class="special">,</span> 83 <span class="keyword">bool</span> <span class="identifier">rising</span><span class="special">,</span> 84 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 85 <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> 86 87 <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> 88 <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> 89 <span class="identifier">bracket_and_solve_root</span><span class="special">(</span> 90 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 91 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">guess</span><span class="special">,</span> 92 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">factor</span><span class="special">,</span> 93 <span class="keyword">bool</span> <span class="identifier">rising</span><span class="special">,</span> 94 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 95 <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> 96 <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> 97 98<span class="comment">// TOMS 748 algorithm</span> 99 <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> 100 <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> 101 <span class="identifier">toms748_solve</span><span class="special">(</span> 102 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 103 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">a</span><span class="special">,</span> 104 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">b</span><span class="special">,</span> 105 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 106 <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> 107 108 <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> 109 <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> 110 <span class="identifier">toms748_solve</span><span class="special">(</span> 111 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 112 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">a</span><span class="special">,</span> 113 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">b</span><span class="special">,</span> 114 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 115 <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> 116 <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> 117 118 <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> 119 <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> 120 <span class="identifier">toms748_solve</span><span class="special">(</span> 121 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 122 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">a</span><span class="special">,</span> 123 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">b</span><span class="special">,</span> 124 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">fa</span><span class="special">,</span> 125 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">fb</span><span class="special">,</span> 126 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 127 <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> 128 129 <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> 130 <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> 131 <span class="identifier">toms748_solve</span><span class="special">(</span> 132 <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span> 133 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">a</span><span class="special">,</span> 134 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">b</span><span class="special">,</span> 135 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">fa</span><span class="special">,</span> 136 <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">fb</span><span class="special">,</span> 137 <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span> 138 <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> 139 <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> 140 141 <span class="comment">// Termination conditions:</span> 142 <span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">></span> 143 <span class="keyword">struct</span> <span class="identifier">eps_tolerance</span><span class="special">;</span> 144 145 <span class="keyword">struct</span> <span class="identifier">equal_floor</span><span class="special">;</span> 146 <span class="keyword">struct</span> <span class="identifier">equal_ceil</span><span class="special">;</span> 147 <span class="keyword">struct</span> <span class="identifier">equal_nearest_integer</span><span class="special">;</span> 148 149 <span class="special">}}}</span> <span class="comment">// boost::math::tools namespaces</span> 150</pre> 151<h5> 152<a name="math_toolkit.roots_noderiv.h1"></a> 153 <span class="phrase"><a name="math_toolkit.roots_noderiv.description"></a></span><a class="link" href="roots_noderiv.html#math_toolkit.roots_noderiv.description">Description</a> 154 </h5> 155<p> 156 These functions solve the root of some function <span class="emphasis"><em>f(x)</em></span> - 157 <span class="emphasis"><em>without the need for any derivatives of <span class="emphasis"><em>f(x)</em></span></em></span>. 158 </p> 159<p> 160 The <code class="computeroutput"><span class="identifier">bracket_and_solve_root</span></code> 161 functions use <a class="link" href="roots_noderiv/TOMS748.html" title="Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions">TOMS 748 algorithm</a> 162 by Alefeld, Potra and Shi that is asymptotically the most efficient known, 163 and has been shown to be optimal for a certain classes of smooth functions. 164 Variants with and without <a class="link" href="../policy.html" title="Chapter 21. Policies: Controlling Precision, Error Handling etc">Policies</a> are provided. 165 </p> 166<p> 167 Alternatively, <a class="link" href="roots_noderiv/bisect.html" title="Bisection">bisect</a> 168 is a simple <a href="https://en.wikipedia.org/wiki/Bisection" target="_top">bisection</a> 169 routine which can be useful in its own right in some situations, or alternatively 170 for narrowing down the range containing the root, prior to calling a more advanced 171 algorithm. 172 </p> 173<p> 174 All the algorithms in this section reduce the diameter of the enclosing interval 175 with the same asymptotic efficiency with which they locate the root. This is 176 in contrast to the derivative based methods which may <span class="emphasis"><em>never</em></span> 177 significantly reduce the enclosing interval, even though they rapidly approach 178 the root. This is also in contrast to some other derivative-free methods (for 179 example, Brent's method described at <a href="http://en.wikipedia.org/wiki/Brent%27s_method" target="_top">Brent-Dekker)</a> 180 which only reduces the enclosing interval on the final step. Therefore these 181 methods return a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code> containing the enclosing interval found, 182 and accept a function object specifying the termination condition. 183 </p> 184<p> 185 Three function objects are provided for ready-made termination conditions: 186 </p> 187<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 188<li class="listitem"> 189 <span class="emphasis"><em>eps_tolerance</em></span> causes termination when the relative 190 error in the enclosing interval is below a certain threshold. 191 </li> 192<li class="listitem"> 193 <span class="emphasis"><em>equal_floor</em></span> and <span class="emphasis"><em>equal_ceil</em></span> are 194 useful for certain statistical applications where the result is known to 195 be an integer. 196 </li> 197<li class="listitem"> 198 Other user-defined termination conditions are likely to be used only rarely, 199 but may be useful in some specific circumstances. 200 </li> 201</ul></div> 202</div> 203<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 204<td align="left"></td> 205<td align="right"><div class="copyright-footer">Copyright © 2006-2019 Nikhar 206 Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, 207 Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan 208 Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, 209 Daryle Walker and Xiaogang Zhang<p> 210 Distributed under the Boost Software License, Version 1.0. (See accompanying 211 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>) 212 </p> 213</div></td> 214</tr></table> 215<hr> 216<div class="spirit-nav"> 217<a accesskey="p" href="../root_finding.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_finding.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="roots_noderiv/bisect.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> 218</div> 219</body> 220</html> 221
