3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
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.5.2">
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">
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>
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>
26 <div class="titlepage"><div><div><h4 class="title">
27 <a name="math_toolkit.roots.roots_noderiv.bracket_solve"></a><a class="link" href="bracket_solve.html" title="Bracket and Solve Root">Bracket
29 </h4></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>
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 15. 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 15. Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&);</span>
52 <code class="computeroutput"><span class="identifier">bracket_and_solve_root</span></code>
53 is 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
58 more foolproof than home-grown routines, unless the function can be analysed
59 to yield tight brackets.
62 Note that this routine can only be used when:
64 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
66 <span class="emphasis"><em>f(x)</em></span> is monotonic in the half of the real axis
67 containing <span class="emphasis"><em>guess</em></span>.
70 The value of the inital guess must have the same sign as the root:
71 the function will <span class="emphasis"><em>never cross the origin</em></span> when
72 searching for the root.
75 The location of the root should be known at least approximately, if
76 the location of the root differs by many orders of magnitude from
77 <span class="emphasis"><em>guess</em></span> then many iterations will be needed to bracket
78 the root in spite of the special heuristics used to guard against this
79 very situation. A typical example would be setting the initial guess
80 to 0.1, when the root is at 1e-300.
84 The <code class="computeroutput"><span class="identifier">bracket_and_solve_root</span></code>
87 <div class="variablelist">
88 <p class="title"><b></b></p>
89 <dl class="variablelist">
90 <dt><span class="term">f</span></dt>
92 A unary functor that is the function whose root is to be solved.
93 <span class="emphasis"><em>f(x)</em></span> must be uniformly increasing or decreasing
94 on <span class="emphasis"><em>x</em></span>.
96 <dt><span class="term">guess</span></dt>
98 An initial approximation to the root.
100 <dt><span class="term">factor</span></dt>
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
105 2 is a typical choice for <span class="emphasis"><em>factor</em></span>. In addition
106 <span class="emphasis"><em>factor</em></span> will be multiplied by 2 every 32 iterations:
107 this is to guard against a really very bad initial guess, typically
108 these occur when it's known the result is very large or small, but
109 not the exact order of magnitude.
111 <dt><span class="term">rising</span></dt>
113 Set to <span class="emphasis"><em>true</em></span> if <span class="emphasis"><em>f(x)</em></span> is
114 rising on <span class="emphasis"><em>x</em></span> and <span class="emphasis"><em>false</em></span> if
115 <span class="emphasis"><em>f(x)</em></span> is falling on <span class="emphasis"><em>x</em></span>. This
116 value is used along with the result of <span class="emphasis"><em>f(guess)</em></span>
117 to determine if <span class="emphasis"><em>guess</em></span> is above or below the
120 <dt><span class="term">tol</span></dt>
122 A binary functor that determines the termination condition for the
123 search for the root. <span class="emphasis"><em>tol</em></span> is passed the current
124 brackets at each step, when it returns true then the current brackets
125 are returned as the pair result. See also <a class="link" href="root_termination.html" title="Termination Condition Functors">predefined
126 termination functors</a>.
128 <dt><span class="term">max_iter</span></dt>
130 The maximum number of function invocations to perform in the search
131 for the root. On exit is set to the actual number of invocations
137 The final <a class="link" href="../../../policy.html" title="Chapter 15. Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and
138 can be used to control the behaviour of the function: how it handles errors,
139 what level of precision to use etc. Refer to the <a class="link" href="../../../policy.html" title="Chapter 15. Policies: Controlling Precision, Error Handling etc">policy
140 documentation for more details</a>.
143 <span class="bold"><strong>Returns</strong></span>: a pair of values <span class="emphasis"><em>r</em></span>
144 that bracket the root so that:
146 <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"><=</span> <span class="number">0</span>
151 <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>
156 <pre class="programlisting"><span class="identifier">max_iter</span> <span class="special">>=</span> <span class="identifier">m</span>
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.
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>
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-2010, 2012-2014 Nikhar Agrawal,
173 Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert
174 Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Johan Råde, Gautam Sewani,
175 Benjamin Sobotta, Thijs van den Berg, Daryle Walker and Xiaogang Zhang<p>
176 Distributed under the Boost Software License, Version 1.0. (See accompanying
177 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>)
182 <div class="spirit-nav">
183 <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>