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