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