Mercurial > hg > de.mpg.mpiwg.itgroup.digilib.core

comparison libs/commons-math-2.1/docs/userguide/analysis.html @ 10:5f2c5fb36e93

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commons-math-2.1 added
author dwinter
date Tue, 04 Jan 2011 10:00:53 +0100
parents
children
comparison
equal deleted inserted replaced
9:e63a64652f4d 10:5f2c5fb36e93
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
2
3
4
5
6
7
8
9
10
11
12
13 <html xmlns="http://www.w3.org/1999/xhtml">
14 <head>
15 <title>Math - The Commons Math User Guide - Numerical Analysis</title>
16 <style type="text/css" media="all">
17 @import url("../css/maven-base.css");
18 @import url("../css/maven-theme.css");
19 @import url("../css/site.css");
20 </style>
21 <link rel="stylesheet" href="../css/print.css" type="text/css" media="print" />
22 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
23 </head>
24 <body class="composite">
25 <div id="banner">
26 <span id="bannerLeft">
27
28 Commons Math User Guide
29
30 </span>
31 <div class="clear">
32 <hr/>
33 </div>
34 </div>
35 <div id="breadcrumbs">
36
37
38
39
40
41
42
43
44 <div class="xright">
45
46
47
48
49
50
51
52 </div>
53 <div class="clear">
54 <hr/>
55 </div>
56 </div>
57 <div id="leftColumn">
58 <div id="navcolumn">
59
60
61
62
63
64
65
66
67 <h5>User Guide</h5>
68 <ul>
69
70 <li class="none">
71 <a href="../userguide/index.html">Contents</a>
72 </li>
73
74 <li class="none">
75 <a href="../userguide/overview.html">Overview</a>
76 </li>
77
78 <li class="none">
79 <a href="../userguide/stat.html">Statistics</a>
80 </li>
81
82 <li class="none">
83 <a href="../userguide/random.html">Data Generation</a>
84 </li>
85
86 <li class="none">
87 <a href="../userguide/linear.html">Linear Algebra</a>
88 </li>
89
90 <li class="none">
91 <strong>Numerical Analysis</strong>
92 </li>
93
94 <li class="none">
95 <a href="../userguide/special.html">Special Functions</a>
96 </li>
97
98 <li class="none">
99 <a href="../userguide/utilities.html">Utilities</a>
100 </li>
101
102 <li class="none">
103 <a href="../userguide/complex.html">Complex Numbers</a>
104 </li>
105
106 <li class="none">
107 <a href="../userguide/distribution.html">Distributions</a>
108 </li>
109
110 <li class="none">
111 <a href="../userguide/fraction.html">Fractions</a>
112 </li>
113
114 <li class="none">
115 <a href="../userguide/transform.html">Transform Methods</a>
116 </li>
117
118 <li class="none">
119 <a href="../userguide/geometry.html">3D Geometry</a>
120 </li>
121
122 <li class="none">
123 <a href="../userguide/optimization.html">Optimization</a>
124 </li>
125
126 <li class="none">
127 <a href="../userguide/ode.html">Ordinary Differential Equations</a>
128 </li>
129
130 <li class="none">
131 <a href="../userguide/genetics.html">Genetic Algorithms</a>
132 </li>
133 </ul>
134 <a href="http://maven.apache.org/" title="Built by Maven" class="poweredBy">
135 <img alt="Built by Maven" src="../images/logos/maven-feather.png"></img>
136 </a>
137
138
139
140
141
142
143
144
145 </div>
146 </div>
147 <div id="bodyColumn">
148 <div id="contentBox">
149 <div class="section"><h2><a name="a4_Numerical_Analysis"></a>4 Numerical Analysis</h2>
150 <div class="section"><h3><a name="a4.1_Overview"></a>4.1 Overview</h3>
151 <p>
152 The analysis package is the parent package for algorithms dealing with
153 real-valued functions of one real variable. It contains dedicated sub-packages
154 providing numerical root-finding, integration, and interpolation. It also
155 contains a polynomials sub-package that considers polynomials with real
156 coefficients as differentiable real functions.
157 </p>
158 <p>
159 Functions interfaces are intended to be implemented by user code to represent
160 their domain problems. The algorithms provided by the library will then operate
161 on these function to find their roots, or integrate them, or ... Functions can
162 be multivariate or univariate, real vectorial or matrix valued, and they can be
163 differentiable or not.
164 </p>
165 <p>
166 Possible future additions may include numerical differentiation.
167 </p>
168 </div>
169 <div class="section"><h3><a name="a4.2_Root-finding"></a>4.2 Root-finding</h3>
170 <p>
171 A <a href="../apidocs/org/apache/commons/math/analysis/solvers/UnivariateRealSolver.html">
172 org.apache.commons.math.analysis.solvers.UnivariateRealSolver.</a>
173 provides the means to find roots of <a href="../apidocs/org/apache/commons/math/analysis/UnivariateRealFunction.html">univariate real-valued functions</a>.
174 A root is the value where the function takes the value 0. Commons-Math
175 includes implementations of the following root-finding algorithms: <ul><li><a href="../apidocs/org/apache/commons/math/analysis/solvers/BisectionSolver.html">
176 Bisection</a></li>
177 <li><a href="../apidocs/org/apache/commons/math/analysis/solvers/BrentSolver.html">
178 Brent-Dekker</a></li>
179 <li><a href="../apidocs/org/apache/commons/math/analysis/solvers/NewtonSolver.html">
180 Newton's Method</a></li>
181 <li><a href="../apidocs/org/apache/commons/math/analysis/solvers/SecantSolver.html">
182 Secant Method</a></li>
183 <li><a href="../apidocs/org/apache/commons/math/analysis/solvers/MullerSolver.html">
184 Muller's Method</a></li>
185 <li><a href="../apidocs/org/apache/commons/math/analysis/solvers/LaguerreSolver.html">
186 Laguerre's Method</a></li>
187 <li><a href="../apidocs/org/apache/commons/math/analysis/solvers/RidderSolver.html">
188 Ridder's Method</a></li>
189 </ul>
190 </p>
191 <p>
192 There are numerous non-obvious traps and pitfalls in root finding.
193 First, the usual disclaimers due to the way real world computers
194 calculate values apply. If the computation of the function provides
195 numerical instabilities, for example due to bit cancellation, the root
196 finding algorithms may behave badly and fail to converge or even
197 return bogus values. There will not necessarily be an indication that
198 the computed root is way off the true value. Secondly, the root finding
199 problem itself may be inherently ill-conditioned. There is a
200 &quot;domain of indeterminacy&quot;, the interval for which the function has
201 near zero absolute values around the true root, which may be large.
202 Even worse, small problems like roundoff error may cause the function
203 value to &quot;numerically oscillate&quot; between negative and positive values.
204 This may again result in roots way off the true value, without
205 indication. There is not much a generic algorithm can do if
206 ill-conditioned problems are met. A way around this is to transform
207 the problem in order to get a better conditioned function. Proper
208 selection of a root-finding algorithm and its configuration parameters
209 requires knowledge of the analytical properties of the function under
210 analysis and numerical analysis techniques. Users are encouraged
211 to consult a numerical analysis text (or a numerical analyst) when
212 selecting and configuring a solver.
213 </p>
214 <p>
215 In order to use the root-finding features, first a solver object must
216 be created. It is encouraged that all solver object creation occurs
217 via the <code>org.apache.commons.math.analysis.solvers.UnivariateRealSolverFactory</code>
218 class. <code>UnivariateRealSolverFactory</code> is a simple factory
219 used to create all of the solver objects supported by Commons-Math.
220 The typical usage of <code>UnivariateRealSolverFactory</code>
221 to create a solver object would be:</p>
222 <div class="source"><pre>UnivariateRealSolverFactory factory = UnivariateRealSolverFactory.newInstance();
223 UnivariateRealSolver solver = factory.newDefaultSolver();</pre>
224 </div>
225 <p>
226 The solvers that can be instantiated via the
227 <code>UnivariateRealSolverFactory</code> are detailed below:
228 <table class="bodyTable"><tr class="a"><th>Solver</th>
229 <th>Factory Method</th>
230 <th>Notes on Use</th>
231 </tr>
232 <tr class="b"><td>Bisection</td>
233 <td>newBisectionSolver</td>
234 <td><div>Root must be bracketted.</div><div>Linear, guaranteed convergence</div></td>
235 </tr>
236 <tr class="a"><td>Brent</td>
237 <td>newBrentSolver</td>
238 <td><div>Root must be bracketted.</div><div>Super-linear, guaranteed convergence</div></td>
239 </tr>
240 <tr class="b"><td>Newton</td>
241 <td>newNewtonSolver</td>
242 <td><div>Uses single value for initialization.</div><div>Super-linear, non-guaranteed convergence</div><div>Function must be differentiable</div></td>
243 </tr>
244 <tr class="a"><td>Secant</td>
245 <td>newSecantSolver</td>
246 <td><div>Root must be bracketted.</div><div>Super-linear, non-guaranteed convergence</div></td>
247 </tr>
248 <tr class="b"><td>Muller</td>
249 <td>newMullerSolver</td>
250 <td><div>Root must be bracketted.</div><div>We restrict ourselves to real valued functions, not complex ones</div></td>
251 </tr>
252 <tr class="a"><td>Laguerre</td>
253 <td>newLaguerreSolver</td>
254 <td><div>Root must be bracketted.</div><div>Function must be a polynomial</div></td>
255 </tr>
256 <tr class="b"><td>Ridder</td>
257 <td>newRidderSolver</td>
258 <td><div>Root must be bracketted.</div><div></div></td>
259 </tr>
260 </table>
261 </p>
262 <p>
263 Using a solver object, roots of functions are easily found using the <code>solve</code>
264 methods. For a function <code>f</code>, and two domain values, <code>min</code> and
265 <code>max</code>, <code>solve</code> computes a value <code>c</code> such that:
266 <ul><li><code>f(c) = 0.0</code> (see &quot;function value accuracy&quot;)</li>
267 <li><code>min &lt;= c &lt;= max</code></li>
268 </ul>
269 </p>
270 <p>
271 Typical usage:
272 </p>
273 <div class="source"><pre>UnivariateRealFunction function = // some user defined function object
274 UnivariateRealSolverFactory factory = UnivariateRealSolverFactory.newInstance();
275 UnivariateRealSolver solver = factory.newBisectionSolver();
276 double c = solver.solve(function, 1.0, 5.0);</pre>
277 </div>
278 <p>
279 The <code>BrentSolve</code> uses the Brent-Dekker algorithm which is
280 fast and robust. This algorithm is recommended for most users and the
281 <code>BrentSolver</code> is the default solver provided by the
282 <code>UnivariateRealSolverFactory</code>. If there are multiple roots
283 in the interval, or there is a large domain of indeterminacy, the
284 algorithm will converge to a random root in the interval without
285 indication that there are problems. Interestingly, the examined text
286 book implementations all disagree in details of the convergence
287 criteria. Also each implementation had problems for one of the test
288 cases, so the expressions had to be fudged further. Don't expect to
289 get exactly the same root values as for other implementations of this
290 algorithm.
291 </p>
292 <p>
293 The <code>SecantSolver</code> uses a variant of the well known secant
294 algorithm. It may be a bit faster than the Brent solver for a class
295 of well-behaved functions.
296 </p>
297 <p>
298 The <code>BisectionSolver</code> is included for completeness and for
299 establishing a fall back in cases of emergency. The algorithm is
300 simple, most likely bug free and guaranteed to converge even in very
301 adverse circumstances which might cause other algorithms to
302 malfunction. The drawback is of course that it is also guaranteed
303 to be slow.
304 </p>
305 <p>
306 The <code>UnivariateRealSolver</code> interface exposes many
307 properties to control the convergence of a solver. For the most part,
308 these properties should not have to change from their default values
309 to produce good results. In the circumstances where changing these
310 property values is needed, it is easily done through getter and setter
311 methods on <code>UnivariateRealSolver</code>:
312 <table class="bodyTable"><tr class="a"><th>Property</th>
313 <th>Methods</th>
314 <th>Purpose</th>
315 </tr>
316 <tr class="b"><td>Absolute accuracy</td>
317 <td><div>getAbsoluteAccuracy</div><div>resetAbsoluteAccuracy</div><div>setAbsoluteAccuracy</div></td>
318 <td>
319 The Absolute Accuracy is (estimated) maximal difference between
320 the computed root and the true root of the function. This is
321 what most people think of as &quot;accuracy&quot; intuitively. The default
322 value is chosen as a sane value for most real world problems,
323 for roots in the range from -100 to +100. For accurate
324 computation of roots near zero, in the range form -0.0001 to
325 +0.0001, the value may be decreased. For computing roots
326 much larger in absolute value than 100, the default absolute
327 accuracy may never be reached because the given relative
328 accuracy is reached first.
329 </td>
330 </tr>
331 <tr class="a"><td>Relative accuracy</td>
332 <td><div>getRelativeAccuracy</div><div>resetRelativeAccuracy</div><div>setRelativeAccuracy</div></td>
333 <td>
334 The Relative Accuracy is the maximal difference between the
335 computed root and the true root, divided by the maximum of the
336 absolute values of the numbers. This accuracy measurement is
337 better suited for numerical calculations with computers, due to
338 the way floating point numbers are represented. The default
339 value is chosen so that algorithms will get a result even for
340 roots with large absolute values, even while it may be
341 impossible to reach the given absolute accuracy.
342 </td>
343 </tr>
344 <tr class="b"><td>Function value accuracy</td>
345 <td><div>getFunctionValueAccuracy</div><div>resetFunctionValueAccuracy</div><div>setFunctionValueAccuracy</div></td>
346 <td>
347 This value is used by some algorithms in order to prevent
348 numerical instabilities. If the function is evaluated to an
349 absolute value smaller than the Function Value Accuracy, the
350 algorithms assume they hit a root and return the value
351 immediately. The default value is a &quot;very small value&quot;. If the
352 goal is to get a near zero function value rather than an accurate
353 root, computation may be sped up by setting this value
354 appropriately.
355 </td>
356 </tr>
357 <tr class="a"><td>Maximum iteration count</td>
358 <td><div>getMaximumIterationCount</div><div>resetMaximumIterationCount</div><div>setMaximumIterationCount</div></td>
359 <td>
360 This is the maximal number of iterations the algorithm will try.
361 If this number is exceeded, non-convergence is assumed and a
362 <code>ConvergenceException</code> exception is thrown. The
363 default value is 100, which should be plenty, given that a
364 bisection algorithm can't get any more accurate after 52
365 iterations because of the number of mantissa bits in a double
366 precision floating point number. If a number of ill-conditioned
367 problems is to be solved, this number can be decreased in order
368 to avoid wasting time.
369 </td>
370 </tr>
371 </table>
372 </p>
373 </div>
374 <div class="section"><h3><a name="a4.3_Interpolation"></a>4.3 Interpolation</h3>
375 <p>
376 A <a href="../apidocs/org/apache/commons/math/analysis/interpolation/UnivariateRealInterpolator.html">
377 org.apache.commons.math.analysis.interpolation.UnivariateRealInterpolator</a>
378 is used to find a univariate real-valued function <code>f</code> which
379 for a given set of ordered pairs
380 (<code>x<sub>i</sub></code>,<code>y<sub>i</sub></code>) yields
381 <code>f(x<sub>i</sub>)=y<sub>i</sub></code> to the best accuracy possible. The result
382 is provided as an object implementing the <a href="../apidocs/org/apache/commons/math/analysis/UnivariateRealFunction.html">
383 org.apache.commons.math.analysis.UnivariateRealFunction</a> interface. It can therefore
384 be evaluated at any point, including point not belonging to the original set.
385 Currently, only an interpolator for generating natural cubic splines and a polynomial
386 interpolator are available. There is no interpolator factory, mainly because the
387 interpolation algorithm is more determined by the kind of the interpolated function
388 rather than the set of points to interpolate.
389 There aren't currently any accuracy controls either, as interpolation
390 accuracy is in general determined by the algorithm.
391 </p>
392 <p>Typical usage:</p>
393 <div class="source"><pre>double x[] = { 0.0, 1.0, 2.0 };
394 double y[] = { 1.0, -1.0, 2.0);
395 UnivariateRealInterpolator interpolator = new SplineInterpolator();
396 UnivariateRealFunction function = interpolator.interpolate(x, y);
397 double interpolationX = 0.5;
398 double interpolatedY = function.evaluate(x);
399 System.out println(&quot;f(&quot; + interpolationX + &quot;) = &quot; + interpolatedY);</pre>
400 </div>
401 <p>
402 A natural cubic spline is a function consisting of a polynomial of
403 third degree for each subinterval determined by the x-coordinates of the
404 interpolated points. A function interpolating <code>N</code>
405 value pairs consists of <code>N-1</code> polynomials. The function
406 is continuous, smooth and can be differentiated twice. The second
407 derivative is continuous but not smooth. The x values passed to the
408 interpolator must be ordered in ascending order. It is not valid to
409 evaluate the function for values outside the range
410 <code>x<sub>0</sub></code>..<code>x<sub>N</sub></code>.
411 </p>
412 <p>
413 The polynomial function returned by the Neville's algorithm is a single
414 polynomial guaranteed to pass exactly through the interpolation points.
415 The degree of the polynomial is the number of points minus 1 (i.e. the
416 interpolation polynomial for a three points set will be a quadratic
417 polynomial). Despite the fact the interpolating polynomials is a perfect
418 approximation of a function at interpolation points, it may be a loose
419 approximation between the points. Due to <a href="http://en.wikipedia.org/wiki/Runge's_phenomenon" class="externalLink">Runge's phenomenom</a>
420 the error can get worse as the degree of the polynomial increases, so
421 adding more points does not always lead to a better interpolation.
422 </p>
423 <p>
424 Loess (or Lowess) interpolation is a robust interpolation useful for
425 smoothing univariate scaterplots. It has been described by William
426 Cleveland in his 1979 seminal paper <a href="http://www.math.tau.ac.il/~yekutiel/MA%20seminar/Cleveland%201979.pdf" class="externalLink">Robust
427 Locally Weighted Regression and Smoothing Scatterplots</a>. This kind of
428 interpolation is computationally intensive but robust.
429 </p>
430 <p>
431 Microsphere interpolation is a robust multidimensional interpolation algorithm.
432 It has been described in William Dudziak's <a href="http://www.dudziak.com/microsphere.pdf" class="externalLink">MS thesis</a>.
433 </p>
434 <p>
435 A <a href="../apidocs/org/apache/commons/math/analysis/interpolation/BivariateRealGridInterpolator.html">
436 org.apache.commons.math.analysis.interpolation.BivariateRealGridInterpolator</a>
437 is used to find a bivariate real-valued function <code>f</code> which
438 for a given set of tuples
439 (<code>x<sub>i</sub></code>,<code>y<sub>j</sub></code>,<code>z<sub>ij</sub></code>)
440 yields <code>f(x<sub>i</sub>,y<sub>j</sub>)=z<sub>ij</sub></code> to the best accuracy
441 possible. The result is provided as an object implementing the
442 <a href="../apidocs/org/apache/commons/math/analysis/BivariateRealFunction.html">
443 org.apache.commons.math.analysis.BivariateRealFunction</a> interface. It can therefore
444 be evaluated at any point, including a point not belonging to the original set.
445 The array <code>x<sub>i</sub></code> and <code>y<sub>j</sub></code> must be sorted in
446 increasing order in order to define a two-dimensional regular grid.
447 </p>
448 <p>
449 In <a href="../apidocs/org/apache/commons/math/analysis/interpolation/BicubicSplineInterpolatingFunction.html">
450 bicubic interpolation</a>, the interpolation function is a 3rd-degree polynomial of two
451 variables. The coefficients are computed from the function values sampled on a regular grid,
452 as well as the values of the partial derivatives of the function at those grid points.
453 </p>
454 <p>
455 From two-dimensional data sampled on a regular grid, the
456 <a href="../apidocs/org/apache/commons/math/analysis/interpolation/SmoothingBicubicSplineInterpolator.html">
457 org.apache.commons.math.analysis.interpolation.SmoothingBicubicSplineInterpolator</a>
458 computes a <a href="../apidocs/org/apache/commons/math/analysis/interpolation/BicubicSplineInterpolatingFunction.html">
459 bicubic interpolating function</a>. The data is first smoothed, along each grid dimension,
460 using one-dimensional splines.
461 </p>
462 </div>
463 <div class="section"><h3><a name="a4.4_Integration"></a>4.4 Integration</h3>
464 <p>
465 A <a href="../apidocs/org/apache/commons/math/analysis/integration/UnivariateRealIntegrator.html">
466 org.apache.commons.math.analysis.integration.UnivariateRealIntegrator.</a>
467 provides the means to numerically integrate <a href="../apidocs/org/apache/commons/math/analysis/UnivariateRealFunction.html">univariate real-valued functions</a>.
468 Commons-Math includes implementations of the following integration algorithms: <ul><li><a href="../apidocs/org/apache/commons/math/analysis/integration/RombergIntegrator.html">
469 Romberg's method</a></li>
470 <li><a href="../apidocs/org/apache/commons/math/analysis/integration/SimpsonIntegrator.html">
471 Simpson's method</a></li>
472 <li><a href="../apidocs/org/apache/commons/math/analysis/integration/TrapezoidIntegrator.html">
473 trapezoid method</a></li>
474 <li><a href="../apidocs/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.html">
475 Legendre-Gauss method</a></li>
476 </ul>
477 </p>
478 </div>
479 <div class="section"><h3><a name="a4.5_Polynomials"></a>4.5 Polynomials</h3>
480 <p>
481 The <a href="../apidocs/org/apache/commons/math/analysis/polynomials/package-summary.html">
482 org.apache.commons.math.analysis.polynomials</a> package provides real coefficients
483 polynomials.
484 </p>
485 <p>
486 The <a href="../apidocs/org/apache/commons/math/analysis/polynomials/PolynomialFunction.html">
487 org.apache.commons.math.analysis.polynomials.PolynomialFunction</a> class is the most general
488 one, using traditional coefficients arrays. The <a href="../apidocs/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.html">
489 org.apache.commons.math.analysis.polynomials.PolynomialsUtils</a> utility class provides static
490 factory methods to build Chebyshev, Hermite, Lagrange and Legendre polynomials. Coefficients
491 are computed using exact fractions so these factory methods can build polynomials up to any degree.
492 </p>
493 </div>
494 </div>
495
496 </div>
497 </div>
498 <div class="clear">
499 <hr/>
500 </div>
501 <div id="footer">
502 <div class="xright">&#169;
503 2003-2010
504
505
506
507
508
509
510
511
512
513 </div>
514 <div class="clear">
515 <hr/>
516 </div>
517 </div>
518 </body>
519 </html>