ceph/src/boost/libs/math/doc/html/math_toolkit/roots/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.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="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><h4 class="title">
  27 <a name="math_toolkit.roots.roots_noderiv.TOMS748"></a><a class="link" href="TOMS748.html" title="Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions">Algorithm
  28         TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions</a>
  29 </h4></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;15.&#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;15.&#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;15.&#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;15.&#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 and solve</a>
  80           rather than trying to bracket the root yourself as this function requires.
  81         </p>
  82 <p>
  83           This function is provided rather than <a href="http://en.wikipedia.org/wiki/Brent%27s_method" target="_top">Brent's
  84           method</a> as it is known to be more effient in many cases (it is asymptotically
  85           the most efficient known, and has been shown to be optimal for a certain
  86           classes of smooth functions). It also has the useful property of decreasing
  87           the bracket size with each step, unlike Brent's method which only shrinks
  88           the enclosing interval in the final step. This makes it particularly useful
  89           when you need a result where the ends of the interval round to the same
  90           integer: as often happens in statistical applications for example. In this
  91           situation the function is able to exit after a much smaller number of iterations
  92           than would otherwise be possible.
  93         </p>
  94 <p>
  95           The <a class="link" href="TOMS748.html" title="Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions">TOMS 748 algorithm</a>
  96           parameters are:
  97         </p>
  98 <div class="variablelist">
  99 <p class="title"><b></b></p>
 100 <dl class="variablelist">
 101 <dt><span class="term">f</span></dt>
 102 <dd><p>
 103                 A unary functor that is the function whose root is to be solved.
 104                 f(x) need not be uniformly increasing or decreasing on <span class="emphasis"><em>x</em></span>
 105                 and may have multiple roots. However, the bounds given must bracket
 106                 a single root.
 107               </p></dd>
 108 <dt><span class="term">a</span></dt>
 109 <dd><p>
 110                 The lower bound for the initial bracket of the root.
 111               </p></dd>
 112 <dt><span class="term">b</span></dt>
 113 <dd><p>
 114                 The upper bound for the initial bracket of the root. It is a precondition
 115                 that <span class="emphasis"><em>a &lt; b</em></span> and that <span class="emphasis"><em>a</em></span>
 116                 and <span class="emphasis"><em>b</em></span> bracket the root to find so that <span class="emphasis"><em>f(a)
 117                 * f(b) &lt; 0</em></span>.
 118               </p></dd>
 119 <dt><span class="term">fa</span></dt>
 120 <dd><p>
 121                 Optional: the value of <span class="emphasis"><em>f(a)</em></span>.
 122               </p></dd>
 123 <dt><span class="term">fb</span></dt>
 124 <dd><p>
 125                 Optional: the value of <span class="emphasis"><em>f(b)</em></span>.
 126               </p></dd>
 127 <dt><span class="term">tol</span></dt>
 128 <dd><p>
 129                 A binary functor that determines the termination condition for the
 130                 search for the root. <span class="emphasis"><em>tol</em></span> is passed the current
 131                 brackets at each step, when it returns true, then the current brackets
 132                 are returned as the result. See also <a class="link" href="root_termination.html" title="Termination Condition Functors">predefined
 133                 termination functors</a>.
 134               </p></dd>
 135 <dt><span class="term">max_iter</span></dt>
 136 <dd><p>
 137                 The maximum number of function invocations to perform in the search
 138                 for the root. On exit, <span class="emphasis"><em>max_iter</em></span> is set to actual
 139                 number of function invocations used.
 140               </p></dd>
 141 </dl>
 142 </div>
 143 <p>
 144           The final <a class="link" href="../../../policy.html" title="Chapter&#160;15.&#160;Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and
 145           can be used to control the behaviour of the function: how it handles errors,
 146           what level of precision to use etc. Refer to the <a class="link" href="../../../policy.html" title="Chapter&#160;15.&#160;Policies: Controlling Precision, Error Handling etc">policy
 147           documentation for more details</a>.
 148         </p>
 149 <p>
 150           <code class="computeroutput"><span class="identifier">toms748_solve</span></code> returns:
 151           a pair of values <span class="emphasis"><em>r</em></span> that bracket the root so that:
 152         </p>
 153 <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">&lt;=</span> <span class="number">0</span>
 154 </pre>
 155 <p>
 156           and either
 157         </p>
 158 <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>
 159 </pre>
 160 <p>
 161           or
 162         </p>
 163 <pre class="programlisting"><span class="identifier">max_iter</span> <span class="special">&gt;=</span> <span class="identifier">m</span>
 164 </pre>
 165 <p>
 166           where <span class="emphasis"><em>m</em></span> is the initial value of <span class="emphasis"><em>max_iter</em></span>
 167           passed to the function.
 168         </p>
 169 <p>
 170           In other words, it's up to the caller to verify whether termination occurred
 171           as a result of exceeding <span class="emphasis"><em>max_iter</em></span> function invocations
 172           (easily done by checking the updated value of <span class="emphasis"><em>max_iter</em></span>
 173           against its previous value passed as parameter), rather than because the
 174           termination condition <span class="emphasis"><em>tol</em></span> was satisfied.
 175         </p>
 176 </div>
 177 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 178 <td align="left"></td>
 179 <td align="right"><div class="copyright-footer">Copyright &#169; 2006-2010, 2012-2014 Nikhar Agrawal,
 180       Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert
 181       Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Johan R&#229;de, Gautam Sewani,
 182       Benjamin Sobotta, Thijs van den Berg, Daryle Walker and Xiaogang Zhang<p>
 183         Distributed under the Boost Software License, Version 1.0. (See accompanying
 184         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>)
 185       </p>
 186 </div></td>
 187 </tr></table>
 188 <hr>
 189 <div class="spirit-nav">
 190 <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>
 191 </div>
 192 </body>
 193 </html>