home | career | drupal | java | mac | mysql | perl | scala | uml | unix  
<tr BGCOLOR="#EEEEFF"> <tr> <td>Bisection <td>univariate real-valued functions <td>linear, guaranteed <td>yes <td>yes </tr> <tr> <td>Brent-Dekker <td>univariate real-valued functions <td>super-linear, guaranteed <td>yes <td>no </tr> <tr> <td>bracketing nth order Brent <td>univariate real-valued functions <td>variable order, guaranteed <td>yes <td>yes </tr> <tr> <td>Illinois Method <td>univariate real-valued functions <td>super-linear, guaranteed <td>yes <td>yes </tr> <tr> <td>Laguerre's Method <td>polynomial functions <td>cubic for simple root, linear for multiple root <td>yes <td>no </tr> <tr> <td>Muller's Method using bracketing to deal with real-valued functions <td>univariate real-valued functions <td>quadratic close to roots <td>yes <td>no </tr> <tr> <td>Muller's Method using modulus to deal with real-valued functions <td>univariate real-valued functions <td>quadratic close to root <td>yes <td>no </tr> <tr> <td>Newton-Raphson's Method <td>differentiable univariate real-valued functions <td>quadratic, non-guaranteed <td>no <td>no </tr> <tr> <td>Pegasus Method <td>univariate real-valued functions <td>super-linear, guaranteed <td>yes <td>yes </tr> <tr> <td>Regula Falsi (false position) Method <td>univariate real-valued functions <td>linear, guaranteed <td>yes <td>yes </tr> <tr> <td>Ridder's Method <td>univariate real-valued functions <td>super-linear <td>yes <td>no </tr> <tr> <td>Secant Method <td>univariate real-valued functions <td>super-linear, non-guaranteed <td>yes <td>no </tr> </table> <p> Some algorithms require that the initial search interval brackets the root (i.e. the function values at interval end points have opposite signs). Some algorithms preserve bracketing throughout computation and allow user to specify which side of the convergence interval to select as the root. It is also possible to force a side selection after a root has been found even for algorithms that do not provide this feature by themselves. This is useful for example in sequential search, for which a new search interval is started after a root has been found in order to find the next root. In this case, user must select a side to ensure his loop is not stuck on one root and always return the same solution without making any progress. </p> <p> 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. </p> <p> In order to use the root-finding features, first a solver object must be created by calling its constructor, often providing relative and absolute accuracy. Using a solver object, roots of functions are easily found using the <code>solve methods. These methods takes a maximum iteration count <code>maxEval, a function f, and either two domain values, <code>min and max, or a <code>startValue as parameters. If the maximal number of iterations count is exceeded, non-convergence is assumed and a <code>ConvergenceException exception is thrown. A suggested 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. <a href="../apidocs/org/apache/commons/math3/analysis/solvers/BracketedUnivariateSolver.html">Bracketed solvers</a> also take an enum parameter to specify which side of the final convergence interval should be selected as the root. It can be <code>ANY_SIDE, LEFT_SIDE, RIGHT_SIDE, <code>BELOW_SIDE or ABOVE_SIDE. Left and right are used to specify the root along the function parameter axis while below and above refer to the function value axis. The solve methods compute a value <code>c such that: <ul> <li>f(c) = 0.0 (see "function value accuracy") <li>min <= c <= max (except for the secant method, which may find a solution outside the interval) </ul> </p> <p> Typical usage: </p> <source>UnivariateFunction function = // some user defined function object final double relativeAccuracy = 1.0e-12; final double absoluteAccuracy = 1.0e-8; final int maxOrder = 5; UnivariateSolver solver = new BracketingNthOrderBrentSolver(relativeAccuracy, absoluteAccuracy, maxOrder); double c = solver.solve(100, function, 1.0, 5.0, AllowedSolution.LEFT_SIDE);</source> <p> Force bracketing, by refining a base solution found by a non-bracketing solver: </p> <source>UnivariateFunction function = // some user defined function object final double relativeAccuracy = 1.0e-12; final double absoluteAccuracy = 1.0e-8; UnivariateSolver nonBracketing = new BrentSolver(relativeAccuracy, absoluteAccuracy); double baseRoot = nonBracketing.solve(100, function, 1.0, 5.0); double c = UnivariateSolverUtils.forceSide(100, function, new PegasusSolver(relativeAccuracy, absoluteAccuracy), baseRoot, 1.0, 5.0, AllowedSolution.LEFT_SIDE); </source> <p> The <code>BrentSolver uses the Brent-Dekker algorithm which is fast and robust. 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. </p> <p> The <code>BracketingNthOrderBrentSolver uses an extension of the Brent-Dekker algorithm which uses inverse n<sup>th order polynomial interpolation instead of inverse quadratic interpolation, and which allows selection of the side of the convergence interval for result bracketing. This is now the recommended algorithm for most users since it has the largest order, doesn't require derivatives, has guaranteed convergence and allows result bracket selection. </p> <p> The <code>SecantSolver uses a straightforward secant algorithm which does not bracket the search and therefore does not guarantee convergence. It may be faster than Brent on some well-behaved functions. </p> <p> The <code>RegulaFalsiSolver is variation of secant preserving bracketing, but then it may be slow, as one end point of the search interval will become fixed after and only the other end point will converge to the root, hence resulting in a search interval size that does not decrease to zero. </p> <p> The <code>IllinoisSolver and PegasusSolver are well-known variations of regula falsi that fix the problem of stuck end points by slightly weighting one endpoint to balance the interval at next iteration. Pegasus is often faster than Illinois. Pegasus may be the algorithm of choice for selecting a specific side of the convergence interval. </p> <p> The <code>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. </p> <p> The <code>UnivariateSolver interface exposes many properties to control the convergence of a solver. The accuracy properties are set at solver instance creation and cannot be changed afterwards, there are only getters to retriveve their values, no setters are available. <table> <tr> <tr> <td>Absolute accuracy <td> 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 chosen 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. </td> </tr> <tr> <td>Relative accuracy <td> 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 chosen 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. </td> </tr> <tr> <td>Function value accuracy <td> 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. </td> </tr> </table> </p> </subsection> <subsection name="4.4 Interpolation" href="interpolation"> <p> A <a href="../apidocs/org/apache/commons/math3/analysis/interpolation/UnivariateInterpolator.html"> UnivariateInterpolator</a> is used to find a univariate real-valued function <code>f which for a given set of ordered pairs (<code>xi,yi) yields <code>f(xi)=yi to the best accuracy possible. The result is provided as an object implementing the <a href="../apidocs/org/apache/commons/math3/analysis/UnivariateFunction.html"> UnivariateFunction</a> interface. It can therefore be evaluated at any point, including point not belonging to the original set. Currently, only an interpolator for generating natural cubic splines and a polynomial interpolator are 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. </p> <p>Typical usage:

<source>double x[] = { 0.0, 1.0, 2.0 }; double y[] = { 1.0, -1.0, 2.0}; UnivariateInterpolator interpolator = new SplineInterpolator(); UnivariateFunction function = interpolator.interpolate(x, y); double interpolationX = 0.5; double interpolatedY = function.value(x); System.out println("f(" + interpolationX + ") = " + interpolatedY);</source> <p> A natural cubic spline is a function consisting of a polynomial of third degree for each subinterval determined by the x-coordinates of the interpolated points. A function interpolating <code>N value pairs consists of <code>N-1 polynomials. 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 <code>x0..xN. </p> <p> The polynomial function returned by the Neville's algorithm is a single polynomial guaranteed to pass exactly through the interpolation points. The degree of the polynomial is the number of points minus 1 (i.e. the interpolation polynomial for a three points set will be a quadratic polynomial). Despite the fact the interpolating polynomials is a perfect approximation of a function at interpolation points, it may be a loose approximation between the points. Due to <a href="http://en.wikipedia.org/wiki/Runge's_phenomenon">Runge's phenomenom</a> the error can get worse as the degree of the polynomial increases, so adding more points does not always lead to a better interpolation. </p> <p> Loess (or Lowess) interpolation is a robust interpolation useful for smoothing univariate scaterplots. It has been described by William Cleveland in his 1979 seminal paper <a href="http://www.math.tau.ac.il/~yekutiel/MA%20seminar/Cleveland%201979.pdf">Robust Locally Weighted Regression and Smoothing Scatterplots</a>. This kind of interpolation is computationally intensive but robust. </p> <p> Microsphere interpolation is a robust multidimensional interpolation algorithm. It has been described in William Dudziak's <a href="http://www.dudziak.com/microsphere.pdf">MS thesis</a>. </p> <p> <a href="http://en.wikipedia.org/wiki/Hermite_interpolation">Hermite interpolation
is an interpolation method that can use derivatives in addition to function values at sample points. The <a href="../apidocs/org/apache/commons/math3/analysis/interpolation/HermiteInterpolator.html">HermiteInterpolator</a> class implements this method for vector-valued functions. The sampling points can have any spacing (there are no requirements for a regular grid) and some points may provide derivatives while others don't provide them (or provide derivatives to a smaller order). Points are added one at a time, as shown in the following example: </p> <source>HermiteInterpolator interpolator = new HermiteInterpolator; // at x = 0, we provide both value and first derivative interpolator.addSamplePoint(0.0, new double[] { 1.0 }, new double[] { 2.0 }); // at x = 1, we provide only function value interpolator.addSamplePoint(1.0, new double[] { 4.0 }); // at x = 2, we provide both value and first derivative interpolator.addSamplePoint(2.0, new double[] { 5.0 }, new double[] { 2.0 }); // should print "value at x = 0.5: 2.5625" System.out.println("value at x = 0.5: " + interpolator.value(0.5)[0]); // should print "derivative at x = 0.5: 3.5" System.out.println("derivative at x = 0.5: " + interpolator.derivative(0.5)[0]); // should print "interpolation polynomial: 1 + 2 x + 4 x^2 - 4 x^3 + x^4" System.out.println("interpolation polynomial: " + interpolator.getPolynomials()[0]);</source> <p> A <a href="../apidocs/org/apache/commons/math3/analysis/interpolation/BivariateGridInterpolator.html"> BivariateGridInterpolator</a> is used to find a bivariate real-valued function <code>f which for a given set of tuples (<code>xi,yj,fij) yields <code>f(xi,yj)=fij to the best accuracy possible. The result is provided as an object implementing the <a href="../apidocs/org/apache/commons/math3/analysis/BivariateFunction.html"> BivariateFunction</a> interface. It can therefore be evaluated at any point, including a point not belonging to the original set. The arrays <code>xi and yj must be sorted in increasing order in order to define a two-dimensional grid. </p> <p> In <a href="http://en.wikipedia.org/wiki/Bicubic_interpolation">bicubic interpolation, the interpolation function is a 3rd-degree polynomial of two variables. The coefficients are computed from the function values sampled on a grid, as well as the values of the partial derivatives of the function at those grid points. From two-dimensional data sampled on a grid, the <a href="../apidocs/org/apache/commons/math3/analysis/interpolation/BicubicSplineInterpolator.html"> BicubicSplineInterpolator</a> computes a <a href="../apidocs/org/apache/commons/math3/analysis/interpolation/BicubicSplineInterpolatingFunction.html"> bicubic interpolating function</a>. Prior to computing an interpolating function, the <a href="../apidocs/org/apache/commons/math3/analysis/interpolation/SmoothingPolynomialBicubicSplineInterpolator.html"> SmoothingPolynomialBicubicSplineInterpolator</a> class performs smoothing of the data by computing the polynomial that best fits each of the one-dimensional curves along each of the coordinate axes. </p> <p> A <a href="../apidocs/org/apache/commons/math3/analysis/interpolation/TrivariateGridInterpolator.html"> TrivariateGridInterpolator</a> is used to find a trivariate real-valued function <code>f which for a given set of tuples (<code>xi,yj,zk, <code>fijk) yields <code>f(xi,yj,zk)=fijk to the best accuracy possible. The result is provided as an object implementing the <a href="../apidocs/org/apache/commons/math3/analysis/TrivariateFunction.html"> TrivariateFunction</a> interface. It can therefore be evaluated at any point, including a point not belonging to the original set. The arrays <code>xi, yj and <code>zk must be sorted in increasing order in order to define a three-dimensional grid. </p> <p> In <a href="http://en.wikipedia.org/wiki/Tricubic_interpolation">tricubic interpolation, the interpolation function is a 3rd-degree polynomial of three variables. The coefficients are computed from the function values sampled on a grid, as well as the values of the partial derivatives of the function at those grid points. From three-dimensional data sampled on a grid, the <a href="../apidocs/org/apache/commons/math3/analysis/interpolation/TricubicSplineInterpolator.html"> TricubicSplineInterpolator</a> computes a <a href="../apidocs/org/apache/commons/math3/analysis/interpolation/TricubicSplineInterpolatingFunction.html"> tricubic interpolating function</a>. </p> </subsection> <subsection name="4.5 Integration" href="integration"> <p> A <a href="../apidocs/org/apache/commons/math3/analysis/integration/UnivariateIntegrator.html"> UnivariateIntegrator</a> provides the means to numerically integrate <a href="../apidocs/org/apache/commons/math3/analysis/UnivariateFunction.html"> univariate real-valued functions</a>. Commons-Math includes implementations of the following integration algorithms: <ul> <li> Romberg's method</a> <li> Simpson's method</a> <li> trapezoid method</a> <li> Legendre-Gauss method</a> </ul> </p> </subsection> <subsection name="4.6 Polynomials" href="polynomials"> <p> The <a href="../apidocs/org/apache/commons/math3/analysis/polynomials/package-summary.html"> org.apache.commons.math3.analysis.polynomials</a> package provides real coefficients polynomials. </p> <p> The <a href="../apidocs/org/apache/commons/math3/analysis/polynomials/PolynomialFunction.html"> PolynomialFunction</a> class is the most general one, using traditional coefficients arrays. The <a href="../apidocs/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.html"> PolynomialsUtils</a> utility class provides static factory methods to build Chebyshev, Hermite, Jacobi, Laguerre and Legendre polynomials. Coefficients are computed using exact fractions so these factory methods can build polynomials up to any degree. </p> </subsection> <subsection name="4.7 Differentiation" href="differentiation"> <p> The <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/package-summary.html"> org.apache.commons.math3.analysis.differentiation</a> package provides a general-purpose differentiation framework. </p> <p> The core class is <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/DerivativeStructure.html"> DerivativeStructure</a> which holds the value and the differentials of a function. This class handles some arbitrary number of free parameters and arbitrary derivation order. It is used both as the input and the output type for the <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/UnivariateDifferentiableFunction.html"> UnivariateDifferentiableFunction</a> interface. Any differentiable function should implement this interface. </p> <p> The main idea behind the <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/DerivativeStructure.html"> DerivativeStructure</a> class is that it can be used almost as a number (i.e. it can be added, multiplied, its square root can be extracted or its cosine computed... However, in addition to computed the value itself when doing these computations, the partial derivatives are also computed alongside. This is an extension of what is sometimes called Rall's numbers. This extension is described in Dan Kalman's paper <a href="http://www1.american.edu/cas/mathstat/People/kalman/pdffiles/mmgautodiff.pdf">Doubly Recursive Multivariate Automatic Differentiation</a>, Mathematics Magazine, vol. 75, no. 3, June 2002. Rall's numbers only hold the first derivative with respect to one free parameter whereas Dan Kalman's derivative structures hold all partial derivatives up to any specified order, with respect to any number of free parameters. Rall's numbers therefore can be seen as derivative structures for order one derivative and one free parameter, and primitive real numbers can be seen as derivative structures with zero order derivative and no free parameters. </p> <p> The workflow of computation of a derivatives of an expression <code>y=f(x) is the following one. First we configure an input parameter <code>x of type normally by passing this parameter to the f function.At the end, we extract from <code>y the value and the derivatives we want. As we have specified 3<sup>rd order when we built x, we can retrieve the derivatives up to 3rd order from <code>y. The following example shows that (the 0 parameter in the DerivativeStructure constructor will be explained in the next paragraph): </p> <source>int params = 1; int order = 3; double xRealValue = 2.5; DerivativeStructure x = new DerivativeStructure(params, order, 0, xRealValue); DerivativeStructure y = f(x); System.out.println("y = " + y.getValue(); System.out.println("y' = " + y.getPartialDerivative(1); System.out.println("y'' = " + y.getPartialDerivative(2); System.out.println("y''' = " + y.getPartialDerivative(3);</source> <p> In fact, there are no notions of <em>variables in the framework, so neither x nor <code>y are considered to be variables per se. They are both considered to be <em>functions and to depend on implicit free parameters which are represented only by indices in the framework. The <code>x instance above is there considered by the framework to be a function of free parameter <code>p0 at index 0, and as y is computed from <code>x it is the result of a functions composition and is therefore also a function of this <code>p0 free parameter. The p0 is not represented by itself, it is simply defined implicitely by the 0 index above. This index is the third argument in the constructor of the <code>x instance. What this constructor means is that we built <code>x as a function that depends on one free parameter only (first constructor argument set to 1), that can be differentiated up to order 3 (second constructor argument set to 3), and which correspond to an identity function with respect to implicit free parameter number 0 (third constructor argument set to 0), with current value equal to 2.5 (fourth constructor argument set to 2.5). This specific constructor defines identity functions, and identity functions are the trick we use to represent variables (there are of course other constructors, for example to build constants or functions from all their derivatives if they are known beforehand). From the user point of view, the <code>x instance can be seen as the x variable, but it is really the identity function applied to free parameter number 0. As the identity function, it has the same value as its parameter, its first derivative is 1.0 with respect to this free parameter, and all its higher order derivatives are 0.0. This can be checked by calling the getValue() or getPartialDerivative() methods on <code>x. </p> <p> When we compute <code>y from this setting, what we really do is chain f after the identity function, so the net result is that the derivatives are computed with respect to the indexed free parameters (i.e. only free parameter number 0 here since there is only one free parameter) of the identity function x. Going one step further, if we compute <code>z = g(y), we will also compute <code>z as a function of the initial free parameter. The very important consequence is that if we call <code>z.getPartialDerivative(1), we will not get the first derivative of g with respect to <code>y, but with respect to the free parameter p0: the derivatives of g and f <em>will be chained together automatically, without user intervention. </p> <p> This design choice is a very classical one in many algorithmic differentiation frameworks, either based on operator overloading (like the one we implemented here) or based on code generation. It implies the user has to <em>bootstrap the system by providing initial derivatives, and this is essentially done by setting up identity function, i.e. functions that represent the variables themselves and have only unit first derivative. </p> <p> This design also allow a very interesting feature which can be explained with the following example. Suppose we have a two arguments function <code>f and a one argument function g. If we compute <code>g(f(x, y)) with x and y be two variables, we want to be able to compute the partial derivatives <code>dg/dx, dg/dy, <code>d2g/dx2 d2g/dxdy d2g/dy2. This does make sense since we combined the two functions, and it does make sense despite g is a one argument function only. In order to do this, we simply set up <code>x as an identity function of an implicit free parameter <code>p0 and y as an identity function of a different implicit free parameter <code>p1 and compute everything directly. In order to be able to combine everything, however, both <code>x and y must be built with the appropriate dimensions, so they will both be declared to handle two free parameters, but <code>x will depend only on parameter 0 while <code>y will depend on parameter 1. Here is how we do this (note that <code>getPartialDerivative is a variable arguments method which take as arguments the derivation order with respect to all free parameters, i.e. the first argument is derivation order with respect to free parameter 0 and the second argument is derivation order with respect to free parameter 1): </p> <source>int params = 2; int order = 2; double xRealValue = 2.5; double yRealValue = -1.3; DerivativeStructure x = new DerivativeStructure(params, order, 0, xRealValue); DerivativeStructure y = new DerivativeStructure(params, order, 1, yRealValue); DerivativeStructure f = DerivativeStructure.hypot(x, y); DerivativeStructure g = f.log(); System.out.println("g = " + g.getValue(); System.out.println("dg/dx = " + g.getPartialDerivative(1, 0); System.out.println("dg/dy = " + g.getPartialDerivative(0, 1); System.out.println("d2g/dx2 = " + g.getPartialDerivative(2, 0); System.out.println("d2g/dxdy = " + g.getPartialDerivative(1, 1); System.out.println("d2g/dy2 = " + g.getPartialDerivative(0, 2);</source> <p> There are several ways a user can create an implementation of the <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/UnivariateDifferentiableFunction.html"> UnivariateDifferentiableFunction</a> interface. The first method is to simply write it directly using the appropriate methods from <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/DerivativeStructure.html"> DerivativeStructure</a> to compute addition, subtraction, sine, cosine... This is often quite straigthforward and there is no need to remember the rules for differentiation: the user code only represent the function itself, the differentials will be computed automatically under the hood. The second method is to write a classical <a href="../apidocs/org/apache/commons/math3/analysis/UnivariateFunction.html">UnivariateFunction</a> and to pass it to an existing implementation of the <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/UnivariateFunctionDifferentiator.html"> UnivariateFunctionDifferentiator</a> interface to retrieve a differentiated version of the same function. The first method is more suited to small functions for which user already control all the underlying code. The second method is more suited to either large functions that would be cumbersome to write using the <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/DerivativeStructure.html"> DerivativeStructure</a> API, or functions for which user does not have control to the full underlying code (for example functions that call external libraries). </p> <p> Apache Commons Math provides one implementation of the <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/UnivariateFunctionDifferentiator.html"> UnivariateFunctionDifferentiator</a> interface: in order to have a Newton-Raphson's solver is a very bad idea. The reason is that finite differences are not really accurate and needs lots of additional calls to the basic underlying function. If user initially have only the basic function available and needs to find its roots, it is <em>much more accurate and much more efficient to use a solver that only requires the function values and not the derivatives. A good choice is to use <a href="../apidocs/org/apache/commons/math3/analysis/solvers/BracketingNthOrderBrentSolver.html">bracketing n<sup>th order Brent method, which in fact converges faster than and can be configured to a highere order (typically 5) than Newton-Raphson which is an order 2 method. </p> <p> Another implementation of the <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/UnivariateFunctionDifferentiator.html"> UnivariateFunctionDifferentiator</a> interface is under development in the related project <a href="http://commons.apache.org/sandbox/nabla/">Apache Commons Nabla. This implementation uses automatic code analysis and generation at binary level. However, at time of writing (end 2012), this project is not yet suitable for production use. </p> </subsection> </section> </body> </document>

Other Java examples (source code examples)

Here is a short list of links related to this Java analysis.xml source code file:

Java example source code file (analysis.xml)

This example Java source code file (analysis.xml) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

apache, derivativestructure, license, localexception, method, the, there, this, univariatefunction

The analysis.xml Java example source code

<?xml version="1.0"?>

   Licensed to the Apache Software Foundation (ASF) under one or more
  contributor license agreements.  See the NOTICE file distributed with
  this work for additional information regarding copyright ownership.
  The ASF licenses this file to You under the Apache License, Version 2.0
  (the "License"); you may not use this file except in compliance with
  the License.  You may obtain a copy of the License at


   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   See the License for the specific language governing permissions and
   limitations under the License.
<?xml-stylesheet type="text/xsl" href="./xdoc.xsl"?>
<document url="analysis.html">
    <title>The Commons Math User Guide - Numerical Analysis
    <section name="4 Numerical Analysis">
      <subsection name="4.1 Overview" href="overview">
         The analysis package is the parent package for algorithms dealing with
         real-valued functions of one real variable. It contains dedicated sub-packages
         providing numerical root-finding, integration, interpolation and differentiation.
         It also contains a polynomials sub-package that considers polynomials with real
         coefficients as differentiable real functions.
         Functions interfaces are intended to be implemented by user code to represent
         their domain problems. The algorithms provided by the library will then operate
         on these function to find their roots, or integrate them, or ... Functions can
         be multivariate or univariate, real vectorial or matrix valued, and they can be
         differentiable or not.
      <subsection name="4.2 Error handling" href="errorhandling">
          For user-defined functions, when the method encounters an error
          during evaluation, users must use their <em>own unchecked exceptions.
          The following example shows the recommended way to do that, using root
          solving as the example (the same construct should be used for ODE
          integrators or for optimizations).
        <source>private static class LocalException extends RuntimeException {

   // the x value that caused the problem
   private final double x;

   public LocalException(double x) {
     this.x = x;

   public double getX() {
     return x;


 private static class MyFunction implements UnivariateFunction {
   public double value(double x) {
     double y = hugeFormula(x);
     if (somethingBadHappens) {
       throw new LocalException(x);
     return y;

 public void compute() {
   try {
     solver.solve(maxEval, new MyFunction(a, b, c), min, max);
   } catch (LocalException le) {
     // retrieve the x value
        As shown in this example the exception is really something local to user code
        and there is a guarantee Apache Commons Math will not mess with it.
        The user is safe.
      <subsection name="4.3 Root-finding" href="rootfinding">
          <a href="../apidocs/org/apache/commons/math3/analysis/solvers/UnivariateSolver.html">
          UnivariateDifferentiableSolver</a> and 
          PolynomialSolver</a> provide means to find roots of
          <a href="../apidocs/org/apache/commons/math3/analysis/UnivariateFunction.html">univariate real-valued functions,
          <a href="../apidocs/org/apache/commons/math3/analysis/differentiation/UnivariateDifferentiable.html">differentiable univariate real-valued functions,
          and <a href="../apidocs/org/apache/commons/math3/analysis/polynomials/PolynomialFunction.html">polynomial functions respectively.
          A root is the value where the function takes the value 0.  Commons-Math
          includes implementations of the several root-finding algorithms:
          <table border="1" align="center">
            <tr BGCOLOR="#CCCCFF">
Root solvers
NameFunction typeConvergenceNeeds initial bracketingBracket side selection

my book on functional programming


new blog posts


Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.