-
Notifications
You must be signed in to change notification settings - Fork 223
/
TOMS748.html
196 lines (193 loc) · 16.3 KB
/
TOMS748.html
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
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions</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.0">
<link rel="up" href="../roots_noderiv.html" title="Root Finding Without Derivatives">
<link rel="prev" href="bracket_solve.html" title="Bracket and Solve Root">
<link rel="next" href="brent.html" title="Brent-Decker Algorithm">
<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="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>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<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:
Alefeld, Potra and Shi: Enclosing zeros of continuous functions</a>
</h3></div></div></div>
<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>
<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>
</pre>
<p>
These functions implement TOMS Algorithm 748: it uses a mixture of cubic,
quadratic and linear (secant) interpolation to locate the root of <span class="emphasis"><em>f(x)</em></span>.
The two pairs of functions differ only by whether values for <span class="emphasis"><em>f(a)</em></span>
and <span class="emphasis"><em>f(b)</em></span> are already available.
</p>
<p>
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> rather than trying to bracket the root yourself as this
function requires.
</p>
<p>
This function is provided rather than <a href="http://en.wikipedia.org/wiki/Brent%27s_method" target="_top">Brent's
method</a> as it is known to be more efficient in many cases (it is asymptotically
the most efficient known, and has been shown to be optimal for a certain
classes of smooth functions). It also has the useful property of decreasing
the bracket size with each step, unlike Brent's method which only shrinks
the enclosing interval in the final step. This makes it particularly useful
when you need a result where the ends of the interval round to the same integer:
as often happens in statistical applications, for example. In this situation
the function is able to exit after a much smaller number of iterations than
would otherwise be possible.
</p>
<p>
The <a class="link" href="TOMS748.html" title="Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions">TOMS 748 algorithm</a>
parameters are:
</p>
<div class="variablelist">
<p class="title"><b></b></p>
<dl class="variablelist">
<dt><span class="term">f</span></dt>
<dd><p>
A unary functor (or C++ lambda) that is the function whose root is
to be solved. f(x) need not be uniformly increasing or decreasing on
<span class="emphasis"><em>x</em></span> and may have multiple roots. However, the bounds
given must bracket a single root.
</p></dd>
<dt><span class="term">a</span></dt>
<dd><p>
The lower bound for the initial bracket of the root.
</p></dd>
<dt><span class="term">b</span></dt>
<dd><p>
The upper bound for the initial bracket of the root. It is a precondition
that <span class="emphasis"><em>a < b</em></span> and that <span class="emphasis"><em>a</em></span>
and <span class="emphasis"><em>b</em></span> bracket the root to find so that <span class="emphasis"><em>f(a)
* f(b) < 0</em></span>.
</p></dd>
<dt><span class="term">fa</span></dt>
<dd><p>
Optional: the value of <span class="emphasis"><em>f(a)</em></span>.
</p></dd>
<dt><span class="term">fb</span></dt>
<dd><p>
Optional: the value of <span class="emphasis"><em>f(b)</em></span>.
</p></dd>
<dt><span class="term">tol</span></dt>
<dd><p>
A binary functor (or C++ lambda) that determines the termination condition
for the search for the root. <span class="emphasis"><em>tol</em></span> is passed the
current brackets at each step, when it returns true, then the current
brackets are returned as the result. See also <a class="link" href="root_termination.html" title="Termination Condition Functors">predefined
termination functors</a>.
</p></dd>
<dt><span class="term">max_iter</span></dt>
<dd><p>
The maximum number of function invocations to perform in the search
for the root. On exit, <span class="emphasis"><em>max_iter</em></span> is set to actual
number of function invocations used.
</p></dd>
</dl>
</div>
<p>
The final <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and can
be used to control the behaviour of the function: how it handles errors,
what level of precision to use etc. Refer to the <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">policy
documentation for more details</a>.
</p>
<p>
<code class="computeroutput"><span class="identifier">toms748_solve</span></code> returns: a
pair of values <span class="emphasis"><em>r</em></span> that bracket the root so that:
</p>
<div class="blockquote"><blockquote class="blockquote"><p>
<span class="emphasis"><em>f(r.first) * f(r.second) <= 0</em></span>
</p></blockquote></div>
<p>
and either
</p>
<div class="blockquote"><blockquote class="blockquote"><p>
<span class="emphasis"><em>tol(r.first, r.second) == true</em></span>
</p></blockquote></div>
<p>
or
</p>
<div class="blockquote"><blockquote class="blockquote"><p>
<span class="emphasis"><em>max_iter >= m</em></span>
</p></blockquote></div>
<p>
where <span class="emphasis"><em>m</em></span> is the initial value of <span class="emphasis"><em>max_iter</em></span>
passed to the function.
</p>
<p>
In other words, it's up to the caller to verify whether termination occurred
as a result of exceeding <span class="emphasis"><em>max_iter</em></span> function invocations
(easily done by checking the updated value of <span class="emphasis"><em>max_iter</em></span>
against its previous value passed as parameter), rather than because the
termination condition <span class="emphasis"><em>tol</em></span> was satisfied.
</p>
</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="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>
</div>
</body>
</html>