commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dennis Hendriks (JIRA)" <>
Subject [jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Date Fri, 12 Aug 2011 13:29:29 GMT


Dennis Hendriks commented on MATH-631:

The discussions for this issue have left me with a lack of overview, so I'll (try to) objectively
summerize the discussions above:

The problems are:
 # Regula Falsi states it always converges, but the implementation doesn't.
 # The main loop may continue, even when it no longer makes any progress, and subsequently
ends with a TooManyEvaluationsException exception.

The cause of both problems is:
 - The limited/finite precision of the Java double type.

Proposed solutions:
 # The patch from revision 1154614, which modifies the Regula Falsi algorithm.
   #- Consensus seems to be that this change, which modifies the algorithm, is undesireable.
We should keep the original algorithm.
 # Detect that the algorithm no longer makes progress and throw an exception, instead of continuing
the loop which no longer makes progress.
   #- This is just earlier detection of the algorithm getting stuck.
   #- We could throw the TooManyEvaluationsException exception, that continuing the loop would
also get us.
     #-- The class only states "Exception to be thrown when the maximal number of evaluations
is exceeded.".
     #-- The exception message only states: "illegal state: maximal count (100) exceeded:
     #-- Both may benefit from more extended documentation/messages.
   #- We could also throw an other exception that more clearly states this issue (NoMoreProgressException,
AlgorithmStuckException, ...?).
     #-- It could for instance mention that changing the function value accuracy may be a
solution, or asking for a different kind of solution?
 # Add documentation to the Regula Falsi algorithm that it is not intended to be used for
actual problems, but only to compare algorithms, for testing, educational purposes, etc.
 # Add documentation to the Regula Falsi algorithm that users should use Illinois or Pegasus
instead, which should outperform the algorithm for most if not all problems.
 # Add documentation to the Regula Falsi algorithm that it theoretically converges, but the
implementation may not, due to the limited/finite precision of Java's double type. This will
result in an exception (or 2 if we also do solution number 2).
 # Remove the Regula Falsi algorithm, and document why it is not included/implemented.
   #- This seems to have been accepted as a last resort solution only.

Other notes:
 - The following problem was also indicated: a solution is found after a certain number of
iterations, but the algorithm does not return the solution (it does not terminate)
   -- This should only happen if the user asked for a different solution. That is, there are
several accuracy parameters, as well as an allowedSolution parameter.
   -- If the solution requested by the user is found, it should return the solution immediately,
otherwise it is a bug.

New notes:
 - I think the Regula Falsi algorithm does not state a fixed convergence criteria: it is left
to the user to decide on one.
   -- When I implemented the algorithm, I think I copied the convergence checks for Brent.
   -- I subsequently modified the convergence criteria when I added the allowedSolution parameter.

My personal opinions on the proposed solutions:
 - (1) Revert part of 1154614, so get the original algorithm back. The other changes of that
commit, that don't change the actual algorith, can stay.
 - (2) If we keep the algorithm, earlier detection would be nice. Not sure which exception
to throw in these cases.
   -- This would result in a single 'if' that detects that the new approximation is the same
as the previous one, and we thus no longer make progress, in which case we throw the exception
earlier, instead of later.
 - (3-5) If we keep the algorith, all 3 documentation extensions would be a good idea.
 - (6) If possible, keep the algorithm, and don't remove it.

New issue:
 - TooManyEvaluationsException currently seems to use LocalizedFormats.MAX_COUNT_EXCEEDED("maximal
count ({0}) exceeded"), but maybe should use LocalizedFormats.MAX_EVALUATIONS_EXCEEDED("maximal
number of evaluations ({0}) exceeded") instead?

> "RegulaFalsiSolver" failure
> ---------------------------
>                 Key: MATH-631
>                 URL:
>             Project: Commons Math
>          Issue Type: Bug
>            Reporter: Gilles
>             Fix For: 3.0
> The following unit test:
> {code}
> @Test
> public void testBug() {
>     final UnivariateRealFunction f = new UnivariateRealFunction() {
>             @Override
>             public double value(double x) {
>                 return Math.exp(x) - Math.pow(Math.PI, 3.0);
>             }
>         };
>     UnivariateRealSolver solver = new RegulaFalsiSolver();
>     double root = solver.solve(100, f, 1, 10);
> }
> {code}
> fails with
> {noformat}
> illegal state: maximal count (100) exceeded: evaluations
> {noformat}
> Using "PegasusSolver", the answer is found after 17 evaluations.

This message is automatically generated by JIRA.
For more information on JIRA, see:


View raw message