forked from johannesgerer/jburkardt-cpp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathzero_rc.html
303 lines (264 loc) · 9.32 KB
/
zero_rc.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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
<html>
<head>
<title>
ZERO_RC - Nonlinear Equation Solver, Reverse Communication
</title>
</head>
<body bgcolor="#EEEEEE" link="#CC0000" alink="#FF3300" vlink="#000055">
<h1 align = "center">
ZERO_RC <br> Nonlinear Equation Solver, Reverse Communication
</h1>
<hr>
<p>
<b>ZERO_RC</b>
is a C++ library which
seeks solutions of a scalar nonlinear equation f(x)=0,
or a system of nonlinear equations,
using reverse communication (RC).
</p>
<p>
One of the standard problems in numerical analysis is to determine
an approximate solution to a scalar nonlinear equation of the form f(x)=0.
</p>
<p>
Reliable and efficient procedures for this task, sometimes called
"zero finders" or "root solvers" are available in many libraries.
These procedures typically require the user to write a sub-procedure
to evaluate the function for any argument x; the form and list of
arguments for this sub-procedure are strictly prescribed by the
library procedure. The user must somehow make this sub-procedure
available to the solver, either by using a fixed name for the
sub-procedure, or by passing in the actual name as an argument.
</p>
<p>
In many cases, it can be inconvenient to use such a library routine,
because it is inserted between the main user program and the user function.
This means that data defining the function, which might be chosen in
the main program, must then somehow be communicated to the user function,
perhaps by declaring some kind of global memory, or by sneaking the data
through in an extra argument provided by the library procedure, or
by the use of auxilliary data files.
</p>
<p>
Moreover, the user essentially loses control of the process until the
library procedure returns. It might, however, be the case that the
user could detect important error conditions, or gather useful information,
if the intermediate x values generated by the library procedure were
visible.
</p>
<p>
If we denote this typical method of interaction between a user and
a library an instance of "forward communication", then there is an
alternative approach, known as "reverse communication", which allows
the user much more freedom in designing the function evaluation,
and in observing and intervening in the iteration that is seeking
the solution.
</p>
<p>
An idealized version of the use of a reverse communication zero finder might
look like this:
<pre>
x = initial approximation.
while ( not satisfied )
fx = f(x)
x = root ( x, fx )
end
</pre>
Here, "not satisfied" might simply be a test of the magnitude of f(x).
But note two things:
<ul>
<li>
The function f(x) is evaluated within the main program. The user
could write an actual procedure to evaluate f(x), but in that case
the user is free to design the interface to f(x) in any desired way.
More importantly, the user can evaluate f(x) directly in the main program,
and has access to all the data in the main program that might
be needed to evaluate the function;
</li>
<li>
The user sees every iterate x produced by the zero finder. This means
the user can catch and occasionally correct problems that might arise
if x goes out of prescribed bounds; the user can print a table of
the computed values, or plot the sequence of function values.
</li>
</ul>
</p>
<p>
Reverse communication zero finders can be very useful in situations
where the function to be evaluated is actually the outcome of a
complicated process. For instance, if we are seeking an eigenvalue
x that makes the determinant of some matrix zero, then our function
evaluation may require us to form a large matrix and to factor it
in order to evaluate the determinant. This may be cumbersome to do
if we must perform all these operations in a sub-procedure.
</p>
<p>
Similarly, we might be solving a boundary value problem using the
shooting method, and f(x) might be the deviation at the final time
between the computed and desired boundary values. In that case,
a subprocedure formulation would require us to set up and solve
a boundary value problem repeatedly in an isolated piece of code.
</p>
<h3 align = "center">
Licensing:
</h3>
<p>
The computer code and data files described and made available on this
web page are distributed under
<a href = "../../txt/gnu_lgpl.txt">the GNU LGPL license.</a>
</p>
<h3 align = "center">
Languages:
</h3>
<p>
<b>ZERO_RC</b> is available in
<a href = "../../c_src/zero_rc/zero_rc.html">a C version</a> and
<a href = "../../cpp_src/zero_rc/zero_rc.html">a C++ version</a> and
<a href = "../../f77_src/zero_rc/zero_rc.html">a FORTRAN77 version</a> and
<a href = "../../f_src/zero_rc/zero_rc.html">a FORTRAN90 version</a> and
<a href = "../../m_src/zero_rc/zero_rc.html">a MATLAB version</a>.
</p>
<h3 align = "center">
Related Data and Programs:
</h3>
<p>
<a href = "../../cpp_src/backtrack_binary_rc/backtrack_binary_rc.html">
BACKTRACK_BINARY_RC</a>,
a C++ library which
carries out a backtrack search for a set of binary decisions, using
reverse communication (RC).
</p>
<p>
<a href = "../../cpp_src/bisection_rc/bisection_rc.html">
BISECTION_RC</a>,
a C++ library which
seeks a solution to the equation F(X)=0 using bisection
within a user-supplied change of sign interval [A,B].
The procedure is written using reverse communication (RC).
</p>
<p>
<a href = "../../cpp_src/brent/brent.html">
BRENT</a>,
a C++ library which
contains routines for finding zeroes or minima of a scalar
function of a scalar variable, without the use of derivative information,
including a reverse communication option,
by Richard Brent.
</p>
<p>
<a href = "../../cpp_src/cg_rc/cg_rc.html">
CG_RC</a>,
a C++ library which
implements the conjugate gradient method for solving
a positive definite sparse linear system A*x=b,
using reverse communication (RC).
</p>
<p>
<a href = "../../cpp_src/sort_rc/sort_rc.html">
SORT_RC</a>,
a C++ library which
can sort a list of any kind of objects,
using reverse communication (RC).
</p>
<p>
<a href = "../../cpp_src/test_zero/test_zero.html">
TEST_ZERO</a>,
a C++ library which
implements test problems for the solution
of a single nonlinear equation in one variable.
</p>
<h3 align = "center">
Reference:
</h3>
<p>
<ol>
<li>
Gaston Gonnet,<br>
On the Structure of Zero Finders,<br>
BIT Numerical Mathematics,<br>
Volume 17, Number 2, June 1977, pages 170-183.
</li>
<li>
Werner Rheinboldt,<br>
Algorithms for finding zeros of a function,<br>
UMAP Journal,<br>
Volume 2, Number 1, 1981, pages 43-72.
</li>
</ol>
</p>
<h3 align = "center">
Source Code:
</h3>
<p>
<ul>
<li>
<a href = "zero_rc.cpp">zero_rc.cpp</a>, the source code.
</li>
<li>
<a href = "zero_rc.hpp">zero_rc.hpp</a>, the include file.
</li>
<li>
<a href = "zero_rc.sh">zero_rc.sh</a>,
BASH commands to compile the source code.
</li>
</ul>
</p>
<h3 align = "center">
Examples and Tests:
</h3>
<p>
<ul>
<li>
<a href = "zero_rc_prb.cpp">zero_rc_prb.cpp</a>,
a sample calling program.
</li>
<li>
<a href = "zero_rc_prb.sh">zero_rc_prb.sh</a>,
BASH commands to compile and run the sample program.
</li>
<li>
<a href = "zero_rc_prb_output.txt">zero_rc_prb_output.txt</a>,
the output file.
</li>
</ul>
</p>
<h3 align = "center">
List of Routines:
</h3>
<p>
<ul>
<li>
<b>ROOT_RC</b> solves a single nonlinear equation using reverse communication.
</li>
<li>
<b>ROOTS_RC</b> solves a system of nonlinear equations using reverse communication.
</li>
<li>
<b>R8MAT_FS</b> factors and solves a system with one right hand side.
</li>
<li>
<b>R8_EPSILON</b> returns the R8 roundoff unit.
</li>
<li>
<b>R8_HUGE</b> returns a "huge" R8.
</li>
<li>
<b>R8_SIGN</b> returns the sign of an R8.
</li>
<li>
<b>TIMESTAMP</b> prints out the current YMDHMS date as a timestamp.
</li>
</ul>
</p>
<p>
You can go up one level to <a href = "../cpp_src.html">
the C++ source codes</a>.
</p>
<hr>
<i>
Last revised on 24 January 2013.
</i>
<!-- John Burkardt -->
</body>
<!-- Initial HTML skeleton created by HTMLINDEX. -->
</html>