commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From er...@apache.org
Subject svn commit: r1164474 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math/analysis/solvers/ test/java/org/apache/commons/math/analysis/solvers/
Date Fri, 02 Sep 2011 11:10:00 GMT
Author: erans
Date: Fri Sep  2 11:09:59 2011
New Revision: 1164474

URL: http://svn.apache.org/viewvc?rev=1164474&view=rev
Log:
MATH-631
Early detection of "Regula Falsi" algorithm being stuck due to finite
precision.
Javadoc makes it clear that either the Pegasus or the Illinois solver should
be preferred over the Regula Falsi one (due to D. Hendriks).

Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/BaseSecantSolver.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/IllinoisSolver.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/PegasusSolver.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolver.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolverTest.java

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/BaseSecantSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/BaseSecantSolver.java?rev=1164474&r1=1164473&r2=1164474&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/BaseSecantSolver.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/BaseSecantSolver.java
Fri Sep  2 11:09:59 2011
@@ -19,6 +19,7 @@ package org.apache.commons.math.analysis
 
 import org.apache.commons.math.util.FastMath;
 import org.apache.commons.math.analysis.UnivariateRealFunction;
+import org.apache.commons.math.exception.ConvergenceException;
 import org.apache.commons.math.exception.MathInternalError;
 
 /**
@@ -61,8 +62,8 @@ public abstract class BaseSecantSolver
     /**
      * Construct a solver.
      *
-     * @param absoluteAccuracy absolute accuracy
-     * @param method <em>Secant</em>-based root-finding method to use
+     * @param absoluteAccuracy Absolute accuracy.
+     * @param method <em>Secant</em>-based root-finding method to use.
      */
     protected BaseSecantSolver(final double absoluteAccuracy, final Method method) {
         super(absoluteAccuracy);
@@ -73,9 +74,9 @@ public abstract class BaseSecantSolver
     /**
      * Construct a solver.
      *
-     * @param relativeAccuracy relative accuracy
-     * @param absoluteAccuracy absolute accuracy
-     * @param method <em>Secant</em>-based root-finding method to use
+     * @param relativeAccuracy Relative accuracy.
+     * @param absoluteAccuracy Absolute accuracy.
+     * @param method <em>Secant</em>-based root-finding method to use.
      */
     protected BaseSecantSolver(final double relativeAccuracy,
                                final double absoluteAccuracy,
@@ -183,7 +184,11 @@ public abstract class BaseSecantSolver
                     f0 *= f1 / (f1 + fx);
                     break;
                 case REGULA_FALSI:
-                    // Nothing.
+                    // Detect early that algorithm is stuck, instead of waiting
+                    // for the maximum number of iterations to be exceeded.
+                    if (x == x1) {
+                        throw new ConvergenceException();
+                    }
                     break;
                 default:
                     // Should never happen.

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/IllinoisSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/IllinoisSolver.java?rev=1164474&r1=1164473&r2=1164474&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/IllinoisSolver.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/IllinoisSolver.java
Fri Sep  2 11:09:59 2011
@@ -26,7 +26,9 @@ package org.apache.commons.math.analysis
  * <p>Like the <em>Regula Falsi</em> method, convergence is guaranteed
by
  * maintaining a bracketed solution. The <em>Illinois</em> method however,
  * should converge much faster than the original <em>Regula Falsi</em>
- * method.</p>
+ * method. Furthermore, this implementation of the <em>Illinois</em> method
+ * should not suffer from the same implementation issues as the <em>Regula
+ * Falsi</em> method, which may fail to convergence in certain cases.</p>
  *
  * <p>The <em>Illinois</em> method assumes that the function is continuous,
  * but not necessarily smooth.</p>
@@ -49,7 +51,7 @@ public class IllinoisSolver extends Base
     /**
      * Construct a solver.
      *
-     * @param absoluteAccuracy absolute accuracy
+     * @param absoluteAccuracy Absolute accuracy.
      */
     public IllinoisSolver(final double absoluteAccuracy) {
         super(absoluteAccuracy, Method.ILLINOIS);
@@ -58,8 +60,8 @@ public class IllinoisSolver extends Base
     /**
      * Construct a solver.
      *
-     * @param relativeAccuracy relative accuracy
-     * @param absoluteAccuracy absolute accuracy
+     * @param relativeAccuracy Relative accuracy.
+     * @param absoluteAccuracy Absolute accuracy.
      */
     public IllinoisSolver(final double relativeAccuracy,
                           final double absoluteAccuracy) {
@@ -69,8 +71,8 @@ public class IllinoisSolver extends Base
     /**
      * Construct a solver.
      *
-     * @param relativeAccuracy relative accuracy
-     * @param absoluteAccuracy absolute accuracy
+     * @param relativeAccuracy Relative accuracy.
+     * @param absoluteAccuracy Absolute accuracy.
      * @param functionValueAccuracy Maximum function value error.
      */
     public IllinoisSolver(final double relativeAccuracy,
@@ -78,5 +80,4 @@ public class IllinoisSolver extends Base
                           final double functionValueAccuracy) {
         super(relativeAccuracy, absoluteAccuracy, functionValueAccuracy, Method.PEGASUS);
     }
-
 }

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/PegasusSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/PegasusSolver.java?rev=1164474&r1=1164473&r2=1164474&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/PegasusSolver.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/PegasusSolver.java
Fri Sep  2 11:09:59 2011
@@ -24,10 +24,13 @@ package org.apache.commons.math.analysis
  *
  * <p>Like the <em>Regula Falsi</em> method, convergence is guaranteed
by
  * maintaining a bracketed solution. The <em>Pegasus</em> method however,
- * should converge much faster than the original <em>Regula Falsi</em> method.
- * Furthermore, it should converge faster than the
- * {@link IllinoisSolver <em>Illinois</em>} method, another
- * <em>Regula Falsi</em>-based method.</p>
+ * should converge much faster than the original <em>Regula Falsi</em>
+ * method. Furthermore, this implementation of the <em>Pegasus</em> method
+ * should not suffer from the same implementation issues as the <em>Regula
+ * Falsi</em> method, which may fail to convergence in certain cases. Also,
+ * the <em>Pegasus</em> method should converge faster than the
+ * {@link IllinoisSolver <em>Illinois</em>} method, another <em>Regula
+ * Falsi</em>-based method.</p>
  *
  * <p>The <em>Pegasus</em> method assumes that the function is continuous,
  * but not necessarily smooth.</p>
@@ -50,7 +53,7 @@ public class PegasusSolver extends BaseS
     /**
      * Construct a solver.
      *
-     * @param absoluteAccuracy absolute accuracy
+     * @param absoluteAccuracy Absolute accuracy.
      */
     public PegasusSolver(final double absoluteAccuracy) {
         super(absoluteAccuracy, Method.PEGASUS);
@@ -59,8 +62,8 @@ public class PegasusSolver extends BaseS
     /**
      * Construct a solver.
      *
-     * @param relativeAccuracy relative accuracy
-     * @param absoluteAccuracy absolute accuracy
+     * @param relativeAccuracy Relative accuracy.
+     * @param absoluteAccuracy Absolute accuracy.
      */
     public PegasusSolver(final double relativeAccuracy,
                          final double absoluteAccuracy) {
@@ -70,8 +73,8 @@ public class PegasusSolver extends BaseS
     /**
      * Construct a solver.
      *
-     * @param relativeAccuracy relative accuracy
-     * @param absoluteAccuracy absolute accuracy
+     * @param relativeAccuracy Relative accuracy.
+     * @param absoluteAccuracy Absolute accuracy.
      * @param functionValueAccuracy Maximum function value error.
      */
     public PegasusSolver(final double relativeAccuracy,
@@ -79,5 +82,4 @@ public class PegasusSolver extends BaseS
                          final double functionValueAccuracy) {
         super(relativeAccuracy, absoluteAccuracy, functionValueAccuracy, Method.PEGASUS);
     }
-
 }

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolver.java?rev=1164474&r1=1164473&r2=1164474&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolver.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolver.java
Fri Sep  2 11:09:59 2011
@@ -17,13 +17,30 @@
 
 package org.apache.commons.math.analysis.solvers;
 
-
 /**
  * Implements the <em>Regula Falsi</em> or <em>False position</em>
method for
  * root-finding (approximating a zero of a univariate real function). It is a
- * modified {@link SecantSolver <em>Secant</em>} method. Unlike the
- * <em>Secant</em> method, convergence is guaranteed by maintaining a
- * bracketed solution.
+ * modified {@link SecantSolver <em>Secant</em>} method.
+ *
+ * <p>The <em>Regula Falsi</em> method is included for completeness, for
+ * testing purposes, for educational purposes, for comparison to other
+ * algorithms, etc. It is however <strong>not</strong> intended to be used
+ * for actual problems, as one of the bounds often remains fixed, resulting
+ * in very slow convergence. Instead, one of the well-known modified
+ * <em>Regula Falsi</em> algorithms can be used ({@link IllinoisSolver
+ * <em>Illinois</em>} or {@link PegasusSolver <em>Pegasus</em>}).
These two
+ * algorithms solve the fundamental issues of the original <em>Regula
+ * Falsi</em> algorithm, and greatly out-performs it for most, if not all,
+ * (practical) functions.
+ *
+ * <p>Unlike the <em>Secant</em> method, the <em>Regula Falsi</em>
guarantees
+ * convergence, by maintaining a bracketed solution. Note however, that due to
+ * the finite/limited precision of Java's {@link Double double} type, which is
+ * used in this implementation, the algorithm may get stuck in a situation
+ * where it no longer makes any progress. Such cases are detected and result
+ * in a {@code ConvergenceException} exception being thrown. In other words,
+ * the algorithm theoretically guarantees convergence, but the implementation
+ * does not.</p>
  *
  * <p>The <em>Regula Falsi</em> method assumes that the function is continuous,
  * but not necessarily smooth.</p>
@@ -46,7 +63,7 @@ public class RegulaFalsiSolver extends B
     /**
      * Construct a solver.
      *
-     * @param absoluteAccuracy absolute accuracy
+     * @param absoluteAccuracy Absolute accuracy.
      */
     public RegulaFalsiSolver(final double absoluteAccuracy) {
         super(absoluteAccuracy, Method.REGULA_FALSI);
@@ -55,8 +72,8 @@ public class RegulaFalsiSolver extends B
     /**
      * Construct a solver.
      *
-     * @param relativeAccuracy relative accuracy
-     * @param absoluteAccuracy absolute accuracy
+     * @param relativeAccuracy Relative accuracy.
+     * @param absoluteAccuracy Absolute accuracy.
      */
     public RegulaFalsiSolver(final double relativeAccuracy,
                              final double absoluteAccuracy) {
@@ -66,8 +83,8 @@ public class RegulaFalsiSolver extends B
     /**
      * Construct a solver.
      *
-     * @param relativeAccuracy relative accuracy
-     * @param absoluteAccuracy absolute accuracy
+     * @param relativeAccuracy Relative accuracy.
+     * @param absoluteAccuracy Absolute accuracy.
      * @param functionValueAccuracy Maximum function value error.
      */
     public RegulaFalsiSolver(final double relativeAccuracy,

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolverTest.java?rev=1164474&r1=1164473&r2=1164474&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolverTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/solvers/RegulaFalsiSolverTest.java
Fri Sep  2 11:09:59 2011
@@ -18,7 +18,7 @@
 package org.apache.commons.math.analysis.solvers;
 
 import org.apache.commons.math.analysis.UnivariateRealFunction;
-import org.apache.commons.math.exception.TooManyEvaluationsException;
+import org.apache.commons.math.exception.ConvergenceException;
 import org.junit.Test;
 import org.junit.Assert;
 
@@ -41,7 +41,7 @@ public final class RegulaFalsiSolverTest
         return new int[] {3, 7, 8, 19, 18, 11, 67, 55, 288, 151, -1};
     }
 
-    @Test(expected=TooManyEvaluationsException.class)
+    @Test(expected=ConvergenceException.class)
     public void testIssue631() {
         final UnivariateRealFunction f = new UnivariateRealFunction() {
                 /** {@inheritDoc} */



Mime
View raw message