libs/math/doc/html/math_toolkit/roots_noderiv/TOMS748.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions</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.11.0">
   8 <link rel="up" href="../roots_noderiv.html" title="Root Finding Without Derivatives">
   9 <link rel="prev" href="bracket_solve.html" title="Bracket and Solve Root">
  10 <link rel="next" href="brent.html" title="Brent-Decker Algorithm">
  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="bracket_solve.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="brent.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.TOMS748"></a><a class="link" href="TOMS748.html" title="Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions">Algorithm TOMS 748:
  28       Alefeld, Potra and Shi: Enclosing zeros of continuous functions</a>
  29 </h3></div></div></div>
  30 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</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">&gt;</span>
  31 <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">T</span><span class="special">&gt;</span>
  32    <span class="identifier">toms748_solve</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">&amp;</span> <span class="identifier">a</span><span class="special">,</span>
  35       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">b</span><span class="special">,</span>
  36       <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span>
  37       <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">);</span>
  38
  39 <span class="keyword">template</span> <span class="special">&lt;</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&#160;20.&#160;Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&gt;</span>
  40 <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">T</span><span class="special">&gt;</span>
  41    <span class="identifier">toms748_solve</span><span class="special">(</span>
  42       <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span>
  43       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">a</span><span class="special">,</span>
  44       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">b</span><span class="special">,</span>
  45       <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span>
  46       <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">,</span>
  47       <span class="keyword">const</span> <a class="link" href="../../policy.html" title="Chapter&#160;20.&#160;Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&amp;);</span>
  48
  49 <span class="keyword">template</span> <span class="special">&lt;</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">&gt;</span>
  50 <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">T</span><span class="special">&gt;</span>
  51    <span class="identifier">toms748_solve</span><span class="special">(</span>
  52       <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span>
  53       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">a</span><span class="special">,</span>
  54       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">b</span><span class="special">,</span>
  55       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">fa</span><span class="special">,</span>
  56       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">fb</span><span class="special">,</span>
  57       <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span>
  58       <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">);</span>
  59
  60 <span class="keyword">template</span> <span class="special">&lt;</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&#160;20.&#160;Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&gt;</span>
  61 <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">T</span><span class="special">&gt;</span>
  62    <span class="identifier">toms748_solve</span><span class="special">(</span>
  63       <span class="identifier">F</span> <span class="identifier">f</span><span class="special">,</span>
  64       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">a</span><span class="special">,</span>
  65       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">b</span><span class="special">,</span>
  66       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">fa</span><span class="special">,</span>
  67       <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">fb</span><span class="special">,</span>
  68       <span class="identifier">Tol</span> <span class="identifier">tol</span><span class="special">,</span>
  69       <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">,</span>
  70       <span class="keyword">const</span> <a class="link" href="../../policy.html" title="Chapter&#160;20.&#160;Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&amp;);</span>
  71 </pre>
  72 <p>
  73         These functions implement TOMS Algorithm 748: it uses a mixture of cubic,
  74         quadratic and linear (secant) interpolation to locate the root of <span class="emphasis"><em>f(x)</em></span>.
  75         The two pairs of functions differ only by whether values for <span class="emphasis"><em>f(a)</em></span>
  76         and <span class="emphasis"><em>f(b)</em></span> are already available.
  77       </p>
  78 <p>
  79         Generally speaking it is easier (and often more efficient) to use <a class="link" href="bracket_solve.html" title="Bracket and Solve Root">bracket
  80         and solve</a> rather than trying to bracket the root yourself as this
  81         function requires.
  82       </p>
  83 <p>
  84         This function is provided rather than <a href="http://en.wikipedia.org/wiki/Brent%27s_method" target="_top">Brent's
  85         method</a> as it is known to be more efficient in many cases (it is asymptotically
  86         the most efficient known, and has been shown to be optimal for a certain
  87         classes of smooth functions). It also has the useful property of decreasing
  88         the bracket size with each step, unlike Brent's method which only shrinks
  89         the enclosing interval in the final step. This makes it particularly useful
  90         when you need a result where the ends of the interval round to the same integer:
  91         as often happens in statistical applications, for example. In this situation
  92         the function is able to exit after a much smaller number of iterations than
  93         would otherwise be possible.
  94       </p>
  95 <p>
  96         The <a class="link" href="TOMS748.html" title="Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions">TOMS 748 algorithm</a>
  97         parameters are:
  98       </p>
  99 <div class="variablelist">
 100 <p class="title"><b></b></p>
 101 <dl class="variablelist">
 102 <dt><span class="term">f</span></dt>
 103 <dd><p>
 104               A unary functor (or C++ lambda) that is the function whose root is
 105               to be solved. f(x) need not be uniformly increasing or decreasing on
 106               <span class="emphasis"><em>x</em></span> and may have multiple roots. However, the bounds
 107               given must bracket a single root.
 108             </p></dd>
 109 <dt><span class="term">a</span></dt>
 110 <dd><p>
 111               The lower bound for the initial bracket of the root.
 112             </p></dd>
 113 <dt><span class="term">b</span></dt>
 114 <dd><p>
 115               The upper bound for the initial bracket of the root. It is a precondition
 116               that <span class="emphasis"><em>a &lt; b</em></span> and that <span class="emphasis"><em>a</em></span>
 117               and <span class="emphasis"><em>b</em></span> bracket the root to find so that <span class="emphasis"><em>f(a)
 118               * f(b) &lt; 0</em></span>.
 119             </p></dd>
 120 <dt><span class="term">fa</span></dt>
 121 <dd><p>
 122               Optional: the value of <span class="emphasis"><em>f(a)</em></span>.
 123             </p></dd>
 124 <dt><span class="term">fb</span></dt>
 125 <dd><p>
 126               Optional: the value of <span class="emphasis"><em>f(b)</em></span>.
 127             </p></dd>
 128 <dt><span class="term">tol</span></dt>
 129 <dd><p>
 130               A binary functor (or C++ lambda) that determines the termination condition
 131               for the search for the root. <span class="emphasis"><em>tol</em></span> is passed the
 132               current brackets at each step, when it returns true, then the current
 133               brackets are returned as the result. See also <a class="link" href="root_termination.html" title="Termination Condition Functors">predefined
 134               termination functors</a>.
 135             </p></dd>
 136 <dt><span class="term">max_iter</span></dt>
 137 <dd><p>
 138               The maximum number of function invocations to perform in the search
 139               for the root. On exit, <span class="emphasis"><em>max_iter</em></span> is set to actual
 140               number of function invocations used.
 141             </p></dd>
 142 </dl>
 143 </div>
 144 <p>
 145         The final <a class="link" href="../../policy.html" title="Chapter&#160;20.&#160;Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and can
 146         be used to control the behaviour of the function: how it handles errors,
 147         what level of precision to use etc. Refer to the <a class="link" href="../../policy.html" title="Chapter&#160;20.&#160;Policies: Controlling Precision, Error Handling etc">policy
 148         documentation for more details</a>.
 149       </p>
 150 <p>
 151         <code class="computeroutput"><span class="identifier">toms748_solve</span></code> returns: a
 152         pair of values <span class="emphasis"><em>r</em></span> that bracket the root so that:
 153       </p>
 154 <div class="blockquote"><blockquote class="blockquote"><p>
 155           <span class="emphasis"><em>f(r.first) * f(r.second) &lt;= 0</em></span>
 156         </p></blockquote></div>
 157 <p>
 158         and either
 159       </p>
 160 <div class="blockquote"><blockquote class="blockquote"><p>
 161           <span class="emphasis"><em>tol(r.first, r.second) == true</em></span>
 162         </p></blockquote></div>
 163 <p>
 164         or
 165       </p>
 166 <div class="blockquote"><blockquote class="blockquote"><p>
 167           <span class="emphasis"><em>max_iter &gt;= m</em></span>
 168         </p></blockquote></div>
 169 <p>
 170         where <span class="emphasis"><em>m</em></span> is the initial value of <span class="emphasis"><em>max_iter</em></span>
 171         passed to the function.
 172       </p>
 173 <p>
 174         In other words, it's up to the caller to verify whether termination occurred
 175         as a result of exceeding <span class="emphasis"><em>max_iter</em></span> function invocations
 176         (easily done by checking the updated value of <span class="emphasis"><em>max_iter</em></span>
 177         against its previous value passed as parameter), rather than because the
 178         termination condition <span class="emphasis"><em>tol</em></span> was satisfied.
 179       </p>
 180 </div>
 181 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 182 <td align="left"></td>
 183 <td align="right"><div class="copyright-footer">Copyright &#169; 2006-2019 Nikhar
 184       Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos,
 185       Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan
 186       R&#229;de, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg,
 187       Daryle Walker and Xiaogang Zhang<p>
 188         Distributed under the Boost Software License, Version 1.0. (See accompanying
 189         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>)
 190       </p>
 191 </div></td>
 192 </tr></table>
 193 <hr>
 194 <div class="spirit-nav">
 195 <a accesskey="p" href="bracket_solve.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="brent.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 196 </div>
 197 </body>
 198 </html>