About Us Home Contributors License Components Sandbox Dormant Math Overview Proposal Developers Guide Javadoc (1.0 release) Javadoc (1.1 release) Source Repository (current) Wiki (Wish List) User Guide Contents Overview Statistics Data Generation Linear Algebra Numerical Analysis Special Functions Utilities Complex Numbers Distributions Fractions Project Documentation About Math Project Info Project Reports Development Process General Information Charter Volunteering Contributing Patches Building Components Releasing Components Wiki Jakarta Community Get Involved Mailing Lists Related DB Commons XML Commons | ### 4 Numerical Analysis #### 4.1 Overview The analysis package provides numerical root-finding and interpolation implementations for real-valued functions of one real variable. Possible future additions may include numerical differentation, integration and optimization. #### 4.2 Root-finding A org.apache.commons.math.analysis.UnivariateRealSolver. provides the means to find roots of univariate real-valued functions. A root is the value where the function takes the value 0. Commons-Math includes implementations of the following root-finding algorithms: Bisection Brent-Dekker Newton's Method Secant Method There are numerous non-obvious traps and pitfalls in root finding. First, the usual disclaimers due to the way real world computers calculate values apply. If the computation of the function provides numerical instabilities, for example due to bit cancellation, the root finding algorithms may behave badly and fail to converge or even return bogus values. There will not necessarily be an indication that the computed root is way off the true value. Secondly, the root finding problem itself may be inherently ill-conditioned. There is a "domain of indeterminacy", the interval for which the function has near zero absolute values around the true root, which may be large. Even worse, small problems like roundoff error may cause the function value to "numerically oscillate" between negative and positive values. This may again result in roots way off the true value, without indication. There is not much a generic algorithm can do if ill-conditioned problems are met. A way around this is to transform the problem in order to get a better conditioned function. Proper selection of a root-finding algorithm and its configuration parameters requires knowledge of the analytical properties of the function under analysis and numerical analysis techniques. Users are encouraged to consult a numerical analysis text (or a numerical analyst) when selecting and configuring a solver. In order to use the root-finding features, first a solver object must be created. It is encouraged that all solver object creation occurs via the `org.apache.commons.math.analysis.UnivariateRealSolverFactory` class. `UnivariateRealSolverFactory` is a simple factory used to create all of the solver objects supported by Commons-Math. The typical usage of `UnivariateRealSolverFactory` to create a solver object would be:
    UnivariateRealFunction function = // some user defined function object
    UnivariateRealSolverFactory factory = UnivariateRealSolverFactory.newInstance();
    UnivariateRealSolver solver = factory.newDefaultSolver(function);
The solvers that can be instantiated via the `UnivariateRealSolverFactory` are detailed below:
Solver | Factory Method | Notes on Use
--- | --- | ---
Bisection | newBisectionSolver | Root must be bracketted. Linear, guaranteed convergence
Brent | newBrentSolver | Root must be bracketted. Super-linear, guaranteed convergence
Newton | newNewtonSolver | Uses single value for initialization. Super-linear, non-guaranteed convergence Function must be differentiable
Secant | newSecantSolver | Root must be bracketted. Super-linear, non-guaranteed convergence
Using a solver object, roots of functions are easily found using the `solve` methods. For a function `f`, and two domain values, `min` and `max`, `solve` computes a value `c` such that: `f(c) = 0.0` (see "function value accuracy") `min <= c <= max` Typical usage:
    UnivariateRealFunction function = // some user defined function object
    UnivariateRealSolverFactory factory = UnivariateRealSolverFactory.newInstance();
    UnivariateRealSolver solver = factory.newBisectionSolver(function);
    double c = solver.solve(1.0, 5.0);
The `BrentSolve` uses the Brent-Dekker algorithm which is fast and robust. This algorithm is recommended for most users and the `BrentSolver` is the default solver provided by the `UnivariateRealSolverFactory`. If there are multiple roots in the interval, or there is a large domain of indeterminacy, the algorithm will converge to a random root in the interval without indication that there are problems. Interestingly, the examined text book implementations all disagree in details of the convergence criteria. Also each implementation had problems for one of the test cases, so the expressions had to be fudged further. Don't expect to get exactly the same root values as for other implementations of this algorithm. The `SecantSolver` uses a variant of the well known secant algorithm. It may be a bit faster than the Brent solver for a class of well-behaved functions. The `BisectionSolver` is included for completeness and for establishing a fall back in cases of emergency. The algorithm is simple, most likely bug free and guaranteed to converge even in very adverse circumstances which might cause other algorithms to malfunction. The drawback is of course that it is also guaranteed to be slow. The `UnivariateRealSolver` interface exposes many properties to control the convergence of a solver. For the most part, these properties should not have to change from their default values to produce good results. In the circumstances where changing these property values is needed, it is easily done through getter and setter methods on `UnivariateRealSolver`:
Property | Methods | Purpose
--- | --- | ---
Absolute accuracy | getAbsoluteAccuracy resetAbsoluteAccuracy setAbsoluteAccuracy | The Absolute Accuracy is (estimated) maximal difference between the computed root and the true root of the function. This is what most people think of as "accuracy" intuitively. The default value is choosen as a sane value for most real world problems, for roots in the range from -100 to +100. For accurate computation of roots near zero, in the range form -0.0001 to +0.0001, the value may be decreased. For computing roots much larger in absolute value than 100, the default absolute accuracy may never be reached because the given relative accuracy is reached first.
Relative accuracy | getRelativeAccuracy resetRelativeAccuracy setRelativeAccuracy | The Relative Accuracy is the maximal difference between the computed root and the true root, divided by the maximum of the absolute values of the numbers. This accuracy measurement is better suited for numerical calculations with computers, due to the way floating point numbers are represented. The default value is choosen so that algorithms will get a result even for roots with large absolute values, even while it may be impossible to reach the given absolute accuracy.
Function value accuracy | getFunctionValueAccuracy resetFunctionValueAccuracy setFunctionValueAccuracy | This value is used by some algorithms in order to prevent numerical instabilities. If the function is evaluated to an absolute value smaller than the Function Value Accuracy, the algorithms assume they hit a root and return the value immediately. The default value is a "very small value". If the goal is to get a near zero function value rather than an accurate root, computation may be sped up by setting this value appropriately.
Maximum iteration count | getMaximumIterationCount resetMaximumIterationCount setMaximumIterationCount | This is the maximal number of iterations the algorithm will try. If this number is exceeded, non-convergence is assumed and a `ConvergenceException` exception is thrown. The default value is 100, which should be plenty, given that a bisection algorithm can't get any more accurate after 52 iterations because of the number of mantissa bits in a double precision floating point number. If a number of ill-conditioned problems is to be solved, this number can be decreased in order to avoid wasting time.
#### 4.3 Interpolation A org.apache.commons.math.analysis.UnivariateRealInterpolator is used to find a univariate real-valued function `f` which for a given set of ordered pairs (`xi`,`yi`) yields `f(xi)=yi` to the best accuracy possible. Currently, only an interpolator for generating natural cubic splines is available. There is no interpolator factory, mainly because the interpolation algorithm is more determined by the kind of the interpolated function rather than the set of points to interpolate. There aren't currently any accuracy controls either, as interpolation accuracy is in general determined by the algorithm. Typical usage:
    double x[]={ 0.0, 1.0, 2.0 };
    double y[]={ 1.0, -1.0, 2.0);
    UnivariateRealInterpolator interpolator = SplineInterpolator();
    UnivariateRealFunction function = interpolator.interpolate();
    double x=0.5;
    double y=function.evaluate(x);
    System.out println("f("+x+")="+y);
A natural cubic spline is a function consisting of a polynominal of third degree for each subinterval determined by the x-coordinates of the interpolated points. A function interpolating `N` value pairs consists of `N-1` polynominals. The function is continuous, smooth and can be differentiated twice. The second derivative is continuous but not smooth. The x values passed to the interpolator must be ordered in ascending order. It is not valid to evaluate the function for values outside the range `x0`..`xN`.