You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Gilles (JIRA)" <ji...@apache.org> on 2011/07/24 01:49:09 UTC
[jira] [Created] (MATH-631) "RegulaFalsiSolver" failure
"RegulaFalsiSolver" failure
---------------------------
Key: MATH-631
URL: https://issues.apache.org/jira/browse/MATH-631
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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13081162#comment-13081162 ]
Luc Maisonobe commented on MATH-631:
------------------------------------
{code}
May I please know *why it is OK that a bit of code does loop counting and repeatedly computes the same thing!*
{code}
We didn't say that. We said that regula falsi is a standard *bad* algorithm. We said that very smart people have enhanced it 40 years ago and the enhanced versions are known and already implemented in Commons Math. These algorithms are *not* blind loop counters and they insert smart target shifts that *prevent* the behavior we observe here. These algorithms not only detect the problem, they fix it! They allow convergence along x. They allow selection of the side of the root.
{code}
The function is potentially evaluated millions of times at the same point.
{code}
The maxEvaluations is already here to prevent this, and in fact now this max number is even mandatory in the solve method (you placed it if I remember correctly). So the function is called millions of time only if the users wishes so by setting the maxEvaluations to a number in the range of millions.
{code}
And may I please know *why it is OK that an algorithm that finds the right result does not return it.*
{code}
If the user asked for a convergence in x or for a convergence on y on the side that is stuck, then no, the algorithm did not find the right result. One of its bounds converged but the users asked for something else.
{code}
You just have to run the code and print "x" and "x1" to see what is going on!
{code}
We know exactly what is going on! We know the algorithm is stuck. We know why it is stuck. We know why it did not detect it is stuck. We know it will finally hit the safety maxEvaluation threshold that is just waiting for that. And we know that removing all these problems is done by using other algorithms which are already there.
Regula falsi is doomed. It is an algorithm used for educational purposes, or for comparison purposes, not something suited for production use. It is just like Euler for ODE (and by the way we did implement Euler for ODE and we don't recommend users to use it as we also did implement better algorithms that were also designed by smart mathematicians decades ago).
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080817#comment-13080817 ]
Luc Maisonobe commented on MATH-631:
------------------------------------
I don't understand.
When it was created, the maxIteration threshold was exactly designed for this purpose: get out of infinite loops. It was later renamed maxEvaluation but the purpose is still the same: don't get stuck. The reason why we get stuck is irrelevant. This limit is simply a safety limit, not a tuning parameter that user are expected to raise once they hit it hoping they will converge later on. If they could raise it later, then they should set it to an appropriate value at once. Hitting it implies computation failed. Regula falsi just like any algorithm can fail if applied with the wrong parameters or to the wrong function (in fact, even with a good setting of function accuracy, it fails to converge if we require a bracket selection on the side that does not move).
Also detecting one bound is not updated is what Illinois and Pegasus are designed to do.
So I think we should completely get rid of regula falsi and only keep the better algorithms.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080641#comment-13080641 ]
Gilles commented on MATH-631:
-----------------------------
"fails to converge" and "large number of iteration to converge" are completely different things.
The documentation says: "convergence is guaranteed". Is _that_ false?
Moreover, for the function reported in this issue, the problem is not that it takes a large number iterations, it is that the loop is _literally_ infinite because at some point, nothing changes anymore.
Stated otherwise: If implemented with larger/infinite precision, would it converge?
In the affirmative, then in my opinion it means that the plain "Regula Falsi" method cannot be implemented with double precision (or that its convergence properties are not as stated in the docs) or that there is a bug in the implementation.
In the former case, why keep something that will never be used (as we'll warn users that they should use "Pegasus" or "Illinois" but certainly not "RegulaFalsi")? IMHO, we could just state in the docs that "RegulaFalsi" was not implemented because it is demonstrably less efficient and sometimes fails to work.
A less radical alternative would be to keep the test I've inserted in the code (at line 186) and throw a {{MathIllegalStateException}} if it passes. The previous behaviour (infinite loop) is a bug in CM.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Dennis Hendriks (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13084113#comment-13084113 ]
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: evaluations"
#-- 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: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080873#comment-13080873 ]
Gilles commented on MATH-631:
-----------------------------
{quote}
I think we should completely get rid of regula falsi and only keep the better algorithms.
{quote}
That was my first idea. And that would be the simplest one, the safest one, and the only viable one as I can't seem to state clearly enough that
* Problem 1: When the doc says "guaranteed convergence", the algorithm should provide the answer.
* Problem 2: When the (absolute) accuracy threshold is set to 1e-6, and the correct root *is* found (after 2200 iterations) within the requirements, it should be returned, instead running idle and finish with an exception
{quote}
The reason why we get stuck is irrelevant.
{quote}
But why? If we *can* be more precise on the cause of failure, why not do it?
{quote}
This limit is simply a safety limit, not a tuning parameter that user are expected to raise once they hit it hoping they will converge later on.
{quote}
In principle, some possible use would be to compare the efficiency of different methods where the main criterion would be a time limitation (assuming that the function evaluation time overwhelms the of the root solver algorithm time). Thus with the function that triggered this issue:
* If you set maxeval to "3000", then both "Pegasus" (17 evals) and (a fixed) "RegulaFalsi" (2200 evals) would fill the bill.
* If you set maxeval to "1000", then "Pegasus" will be the only winner.
Anyways:
+1 for removing it altogether, and include somewhere the reason for it not being implemented in CM.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13084473#comment-13084473 ]
Gilles commented on MATH-631:
-----------------------------
Yes. In the file "LocalizedFormats.java", I've started to write
{noformat}
/* keep */
{noformat}
after each enum that is supposedly to be kept. All the others are still to be examined for redundancy with another one, or the possibility to create something close using the "multi-item" approach.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080682#comment-13080682 ]
Phil Steitz commented on MATH-631:
----------------------------------
I disagree with your statement about setting accuracy. All of this is configurable and if not set, you get the (documented) defaults. This is all documented. If the documentation is not clear, then we can improve it. A user who applies Regula Falsi to the problem instance being examined here will end up maxing iterations. I see no problem with that and in fact I see it as *correct* behavior (given the documented execution context of the algorithm).
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MATH-631) "RegulaFalsiSolver"
failure
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080665#comment-13080665 ]
Luc Maisonobe edited comment on MATH-631 at 8/7/11 9:01 PM:
------------------------------------------------------------
{quote}
The documentation says: "convergence is guaranteed". Is that false?
{quote}
It depends on what is called convergence.
If convergence is evaluated only as the best of the two endpoints (measured along y axis), yes convergence is guaranteed and in this case it is very slow. This is what appears in many analysis books.
If convergence is evaluated by ensuring the bracketing interval (measured along x axis) reduces to zero (i.e. both endpoints converge to the root), convergence is not guaranteed.
The first case is achieved with our implementation by using the function accuracy setting. The second case is achieved with our implementation by using relative accuracy and absolute accuracy settings, which both are computed along x axis.
I fear that there are several different references about convergence for this method (just as for Brent). So we already are able to implement both views.
Without any change to our implementation, we reach convergence for this example by setting the function accuracy to 7.4e-13 or above, and it is slow (about 3500 evaluations). The default setting for function accuracy is very low (1.0e-15) and in this case, given the variation rate of the function near the root, it is equivalent to completely ignore convergence on y on only check the convergence on the interval length along x.
was (Author: luc):
{quote}
The documentation says: "convergence is guaranteed". Is that false?
{quote}
It depends on what is called convergence.
If convergence is evaluated only as the best of the two endpoints, yes convergence is guaranteed and in this case it is very slow. This is what appears in many analysis books.
If convergence is evaluated by ensuring the bracketing interval reduces to zero (i.e. both endpoints converge to the root), convergence is not guaranteed.
The first case is achieved with our implementation by using the function accuracy setting. The second case is achieved with our implementation by using relative accuracy and absolute accuracy settings, which both are computed along x axis.
I fear that their are several different references about convergence for this method (just as for Brent). So we already are able to implement both views.
Without any change to our implementation, we reach convergence for this example by setting the function accuracy to 7.4e-13 or above, and it is slow (about 3500 evaluations). The default setting for function accuracy is very low (1.0e-15) and in this case, given the variation rate of the function near the root, it is equivalent to completely ignore convergence on y on only check the convergence on the interval length along x.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Dennis Hendriks (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Dennis Hendriks updated MATH-631:
---------------------------------
Attachment: ticket631.patch
The 'ticket631.patch' file is my attempt to resolve this issue with a solution (or maybe I should call it a compromise?) that is satisfactory for all people that participated in the discussions for this issue, without having to remove the Regula Falsi algorithm from Commons Math.
I changed the following:
- Added early detection of no longer making progress ('getting stuck'), and documented it.
-- I used ConvergenceException for this, as it seems to fit... Do we want a custom error message with it?
- Extended RegulaFalsiSolver documentation to indicate:
-- that the algorithm should not be used for actual problems.
-- that Illinois and Pegasus are improved versions and should be prefered.
-- that the implementation does not guarantee convergence, while the algorithm theoretically does.
- Extended IllinoisSolver and PegasusSolver documentation to indicate that they don't suffer from the RegulaFalsiSolver's implementation/convergence issues.
Please comment on whether this patch is an acceptable solution/compromise, and if not, why it is not.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> Project: Commons Math
> Issue Type: Bug
> Reporter: Gilles
> Fix For: 3.0
>
> Attachments: ticket631.patch
>
>
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13081193#comment-13081193 ]
Phil Steitz commented on MATH-631:
----------------------------------
This is a pointless discussion. Gilles, you obviously don't share the views that Luc and I have on implementing standard algorithms or even what the meaning of a numerical algorithm is. Some algorithms perform well for some classes of problems and not others. There is an art to choosing the right algorithm for the problem instance at hand. If we modify our implementations to try to work around shortcomings of the algorithms we implement, then we are not implementing the standard algorithms, and we need to document exactly what it is that we are implementing, because in this case we are actually making it harder for users to choose (because we are not longer advertising standard numerics). This is what I meant when I said it is both harder for us (because we have to document the hacks and non-standard contracts) and users (because the standard numerical analysis theory that they may be using to choose among implementations will no longer apply). It is, IMO, a "pathetic compromise" to drop the implementation because we can't agree on what it means to implement the algorithm. So be it. Lets drop it and resolve this issue as "fixed."
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080697#comment-13080697 ]
Phil Steitz commented on MATH-631:
----------------------------------
Is there actually a possibility of an infinite loop in the code? Looks to me like the max evaluations bound will stop the while loop, so there is no potential for an infinite loop. Apologies if I am misreading the code and there the loop can fail to terminate, in which case I agree this is a problem. (As a side note, from a style perspective, I prefer to explicitly bound loops to avoid this kind of uncertainty. The natural hard bound here is the evaluation count.)
Trying to detect when a sequence of iterates has gotten "stuck" and is destined to hit max iterations without converging is walking down a path that I think is unwise for us and users. I see no reason not to stick with the standard impl here, which is nicely documented in the original submission. Trying to workaround numerical problems in simple algorithms and change contracts to include these workarounds is asking for trouble - both for us and users. In a simple case like this, it is much better to just stick with the documented algorithm, which should in this case (again unless I am missing something) end with max evaluations exceeded, which is the right exception to report.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13081242#comment-13081242 ]
Gilles commented on MATH-631:
-----------------------------
{quote}
Gilles, you obviously don't share the views that Luc and I have on implementing standard algorithms
{quote}
That's simply _not true_.
I was the one pointing out that standard algorithms should have precedence: Please recall that it was considered fine that "Levenberg-Marquardt" and "Brent" would be, unknowingly to the user, "twisted" to perform _non-standard_ convergences check.
In those cases, there was the risk that the result of the algorithm would not be the same as the reference implementation.
In this case, there is no such thing as deviating from standard numerics! It was just a matter of throwing the right exception. So: "The algorithm fails? Let's tell it sooner rather than later."
Very interesting question that you ask: "what it means to implement the algorithm". But please note that I asked it several posts ago[1], and an answer would have helped sort out this discussion. What is your definition?
[1] 08/Aug/11 07:24
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Dennis Hendriks (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080575#comment-13080575 ]
Dennis Hendriks commented on MATH-631:
--------------------------------------
I just got back from a 3 week vacation, so I couldn't reply earlier.
The documentation for the RegulaFalsiSolver states: "Unlike the Secant method, convergence is guaranteed by maintaining a bracketed solution." While this is theoretically true, in this case it is not so, because (if I understand correctly) only a single bound is updated repeatedly, and the update is too small to matter (has no effect), due to the double representation.
The change you propose (which is difficult to see as you also change other things in the same commit) is to modify x0 and f0 if the new value of x and x1 are equal. As I see it, this changes the algorithm, and it is no longer the Regula Falsi method as known from literature. I'm therefore against this change.
The problem that is identified in this issue is very similar to the well-known problem of the Regula Falsi method: it converges very slowly for certain problems, due to one side being updated all the time, while the other one stays the same. The Illinois and Pegasus algorithms solve exactly this problem, and are well-documented in literature.
I therefore think it would be better if the RegulaFalsiSolver kept it's original implementation, and for this problem the Illinois or Pegasus method should then be used instead.
The other changes (if statements to switch with default, extracting bound switch statements, etc) can be kept, if you wish.
The suggestion to add a warning to the Secant and Regula Falsi solvers that this is a possible problem, and the solution (use Illinois or Pegasus), would indeed be a good idea. In general, adding a note that the Illinois and Pegasus algorithms perform better, would be a good idea regardless of this issue.
Once more, to be clear, I don't think this issue is a bug. It is a result of the limited convergence of the Regula Falsi method combined with the implications of limited double precision. The limited convergence of the algorithm is a property of the algorithm, and should in my opinion not be changed. I also don't think that trying to work around the limited double precision would be a good idea.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080675#comment-13080675 ]
Gilles commented on MATH-631:
-----------------------------
I understand what you say. But however you put it, there is a bug; if not in the implementation, then in the API. It is not expected behaviour that something which must be changed (function accuracy threshold) to ensure correct behaviour (avoid an undetected infinite loop) is not a mandatory parameter.
To debug this, I started by raising the absolute accuracy threshold (the first default parameter, thus the first obvious thing to do) to 1e-2 and was stunned that I couldn't get anything after 1000000 iterations!
Therefore I maintain that, at a minimum, we put a line that will detect the infinite loop and raise an exception identifying _that_ problem and not let the user wait for "TooManyEvaluationsException" to be raised, as that will induce the unaware (me) to just allow more evaluations and try again.
This solution does not corrupt the algorithm; it just adds protection.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13081150#comment-13081150 ]
Gilles commented on MATH-631:
-----------------------------
May I please know *why it is OK that a bit of code does loop counting and repeatedly computes the same thing*!
You insist that I'd be "hacking" whereas I've indicated 3 or 4 times that there is no hack: just a test that will exit the loop as soon as it detects that the algorithm has failed. Why is it not understandable that the busy loop could last for a long time? The function is potentially evaluated millions of times at the same point. What if the evaluation is costly? Imagine the computation running for days, only to discover that it could have been be stopped after a few seconds. Is that robust code and good advertising for a library? It is one thing to expect that there are unknown bugs in CM, but refusing to fix a known one is so obviously wrong...
And may I please know *why it is OK that an algorithm that finds the right result does not return it*.
I had been trying to provide alternatives to the removal, but I can't do much more if nobody answers the above two questions.
You just have to run the code and print "x" and "x1" to see what is going on!
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080608#comment-13080608 ]
Gilles commented on MATH-631:
-----------------------------
> (which is difficult to see as you also change other things in the same commit)
Sorry, but I didn't hit the solution right away, i.e. before changing those two additional little things to make the code clearer (for me)...
The only actual change is that the {{REGULA_FALSI}} enum was not used (i.e. with the {{switch}} little change, the corresponding {{case}} would have been empty) whereas now it contains the update of x0 to avoid an infinite loop.
The other (cosmetic) change was to take these two statements
{code}
x1 = x;
f1 = fx;
{code}
out of the previous {{if}} and {{else}} blocks, as they were duplicated there (which made me wonder whether it was a bug that they were _not_ different).
You say
> [...] convergence is guaranteed [...]
> [...] it converges very slowly for certain problems, [...]
> [...] The limited convergence of the algorithm is a property of the algorithm, [...]
All the above imply that one expects that the algorithm _can_ find the solution.
However, in this implementation, it _can't_.
Therefore there is a bug, somewhere.
I agree that it is a limitation of double precision. But, IMHO, leaving the code as-is is not a good idea because because it leads to the impression that the "Regula Falsi" mathematical algorithm can fail to converge, which is not correct (IIUC).
Therefore, we could add a comment stating that the _implementation_ with limited precision can fail to converge but that would be akin to saying to users: "Here is a code, but don't use it."
Personally, I would prefer to say: "Because of limited precision, the implementation can fail to converge. In those cases, we slightly modified the original algorithm in order to avoid failure."
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080689#comment-13080689 ]
Gilles commented on MATH-631:
-----------------------------
How can it be correct to have an infinite loop?
The problem is not slow convergence, which you can overcome by allowing more iterations.
It is too low function value accuracy which you cannot overcome by allowing more iterations. Thus my point: We must raise the appropriate exception (the doc for which will state that it can happen if the function value accuracy is too low for the implementation to provide a result).
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MATH-631) "RegulaFalsiSolver"
failure
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080697#comment-13080697 ]
Phil Steitz edited comment on MATH-631 at 8/7/11 11:56 PM:
-----------------------------------------------------------
Is there actually a possibility of an infinite loop in the code? Looks to me like the max evaluations bound will stop the while loop, so there is no potential for an infinite loop. Apologies if I am misreading the code and the loop can fail to terminate, in which case I agree this is a problem. (As a side note, from a style perspective, I prefer to explicitly bound loops to avoid this kind of uncertainty. The natural hard bound here is the evaluation count.)
Trying to detect when a sequence of iterates has gotten "stuck" and is destined to hit max iterations without converging is walking down a path that I think is unwise for us and users. I see no reason not to stick with the standard impl here, which is nicely documented in the original submission. Trying to workaround numerical problems in simple algorithms and change contracts to include these workarounds is asking for trouble - both for us and users. In a simple case like this, it is much better to just stick with the documented algorithm, which should in this case (again unless I am missing something) end with max evaluations exceeded, which is the right exception to report.
was (Author: psteitz):
Is there actually a possibility of an infinite loop in the code? Looks to me like the max evaluations bound will stop the while loop, so there is no potential for an infinite loop. Apologies if I am misreading the code and there the loop can fail to terminate, in which case I agree this is a problem. (As a side note, from a style perspective, I prefer to explicitly bound loops to avoid this kind of uncertainty. The natural hard bound here is the evaluation count.)
Trying to detect when a sequence of iterates has gotten "stuck" and is destined to hit max iterations without converging is walking down a path that I think is unwise for us and users. I see no reason not to stick with the standard impl here, which is nicely documented in the original submission. Trying to workaround numerical problems in simple algorithms and change contracts to include these workarounds is asking for trouble - both for us and users. In a simple case like this, it is much better to just stick with the documented algorithm, which should in this case (again unless I am missing something) end with max evaluations exceeded, which is the right exception to report.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13081633#comment-13081633 ]
Gilles commented on MATH-631:
-----------------------------
Also:
Phil,
Could you please leave out dismissive qualifiers such as "pointless" and "pathetic" (and, elsewhere, "silly") and stick to more or less objective arguments?
That will certainly help keep the conversation tone to a courteous level.
Luc,
Thanks for stating in full details what you meant by "convergence" in this case. However, it is still a "post-mortem" description.
Do you really expect that the average user of the CM library (a.o. me and the original reporter of the issue) to be able to figure out that "obvious" explanation just by getting a "TooManyEvalutationsException", setting the along-x accuracy threshold to a ridiculously high value and still getting the same exception?
If just for educational purposes, don't you think that it is more instructive to get a specific hint that the algorithm is stuck, rather than hit the ultimate fail-safe barrier much much later, and then download the source code and sprinkle the code with "println" statements to do forensic analysis?
Phil,
I tried to handle this issue out of respect for a real user who reported an issue that would have looked suspicious to many CM users. [How many of them would be experts in numerical analysis?]
You do not do me a favour by removing this algorithm; I don't want it to be a _compromise_ (pathetic or not). If you prefer to keep it, I don't care anymore. But, in that case, _you_ should have answered to Axel Kramer to go and read some books on numerical analysis.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13082210#comment-13082210 ]
Phil Steitz commented on MATH-631:
----------------------------------
Gilles, I apologize for tone of comments.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Resolved] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Gilles resolved MATH-631.
-------------------------
Resolution: Fixed
No objection raised; setting to "Resolved".
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> Project: Commons Math
> Issue Type: Bug
> Reporter: Gilles
> Fix For: 3.0
>
> Attachments: ticket631.patch
>
>
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Dennis Hendriks (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13084454#comment-13084454 ]
Dennis Hendriks commented on MATH-631:
--------------------------------------
bq. contains everything
I agree. I was just wondering why a message that seems to be exactly the same as the exception was not used, as it kind of looked like it was created just for this purpose...
bq. I proposed to use this approach (combining message items with the "addMessage" method of "ExceptionContext") in order to reduce the number of messages in the "LocalizedFormats" enum. Too many of them are just slight variations on a same theme.
Ah, so then the MAX_EVALUATIONS_EXCEEDED is just a remnant of the past that should be eliminated, by replacing it everywhere by the more general MAX_COUNT_EXCEEDED?
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13084242#comment-13084242 ]
Gilles commented on MATH-631:
-----------------------------
Thanks for the neat summary!
{quote}
* (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.
{quote}
Done in revision 1157185.
{quote}
* (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.
{quote}
+1 (my position in the "07/Aug/11 20:28" post)
As suggested there, the exception could be "MathIllegalStateException" but with a clear message stating that the algorithm is stuck. Or maybe a new subclass of it which we could call "NumericalPrecisionException" or even a general-purpose "ImplementationException".
{quote}
[...] all 3 documentation extensions would be a good idea.
{quote}
+1
About the "new issue", the message string:
{quote}
"illegal state: maximal count (100) exceeded: evaluations"
{quote}
contains everything:
# error type: illegal state
# failure description: maximal count (100) exceeded
# context: evaluations
I proposed to use this approach (combining message items with the "addMessage" method of "ExceptionContext") in order to reduce the number of messages in the "LocalizedFormats" enum. Too many of them are just slight variations on a same theme.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080478#comment-13080478 ]
Gilles commented on MATH-631:
-----------------------------
The problem was due to the fact that at some point, the update formula always gave the same value: Nothing was being updated and the loop went on until the number of evaluations was exhausted.
I've committed a tentative solution in revision 1154614.
However:
# I'm not sure that it doesn't have any adverse side-effects on the bracketing property.
# It is quite probably not a pristine "regula falsi" algorithm anymore.
Please review.
Anyways, for the function that triggered the problem (see "testIssue631" in "RegulaFalsiSolverTest.java"), the (modified) {{RegulaFalsiSolver}} takes 3624 evaluations (versus 17 for {{PegasusSolver}}). We should probably add a word of warning in the class Javadoc.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080673#comment-13080673 ]
Phil Steitz commented on MATH-631:
----------------------------------
I think we should either stick with the standard implementation of Regula Falsi or drop the class altogether. Different rootfinders are going to perform better / worse for different functions and parameter values and I don't think it is a good idea to try to modify our implementations of the algorithms to try to work around their shortcomings for problem instances for which they are not well-suited. It is much better to stick with standard algorithms, document them, and leave it to users to choose among implementations.
Regula Falsi is not a good general-purpose rootfinder, but it does perform well for some problems (or parts of problems) and the original submission was a working implementation, so I would say revert the changes and keep it.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080665#comment-13080665 ]
Luc Maisonobe commented on MATH-631:
------------------------------------
{quote}
The documentation says: "convergence is guaranteed". Is that false?
{quote}
It depends on what is called convergence.
If convergence is evaluated only as the best of the two endpoints, yes convergence is guaranteed and in this case it is very slow. This is what appears in many analysis books.
If convergence is evaluated by ensuring the bracketing interval reduces to zero (i.e. both endpoints converge to the root), convergence is not guaranteed.
The first case is achieved with our implementation by using the function accuracy setting. The second case is achieved with our implementation by using relative accuracy and absolute accuracy settings, which both are computed along x axis.
I fear that their are several different references about convergence for this method (just as for Brent). So we already are able to implement both views.
Without any change to our implementation, we reach convergence for this example by setting the function accuracy to 7.4e-13 or above, and it is slow (about 3500 evaluations). The default setting for function accuracy is very low (1.0e-15) and in this case, given the variation rate of the function near the root, it is equivalent to completely ignore convergence on y on only check the convergence on the interval length along x.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080792#comment-13080792 ]
Gilles commented on MATH-631:
-----------------------------
I surely hope that your last post is not an answer to mine from 23:46.
I'll try to answer here in case it was in reply to my previous one (23:06).
Of course, the code will not run forever because of the "maxeval" bound.
But it will run for a time that depends on the value of "maxeval" *with no added benefit*! From a certain point, the loop is like
{code}
while (true) {
// Do nothing useful, just count!
++count;
if (count > maxeval) {
throw new TooManyEvalutationsException(maxeval);
}
}
{code}
{quote}
from a style perspective, I prefer to explicitly bound loops
{quote}
>From an *OO* style perspective, the reuse of the "Incrementor" is better, and you don't have to rewrite the same "test and throw exception if failed" boiler plate code each time there is such a loop.
{quote}
Trying to detect when a sequence of iterates has gotten "stuck" and is destined to hit max iterations without converging is walking down a path that I think is unwise for us and users.
{quote}
Why?
{quote}
I see no reason not to stick with the standard impl here
{quote}
A busy idle loop is a compelling reason IMO.
{quote}
Trying to workaround numerical problems in simple algorithms and change contracts to include these workarounds is asking for trouble
{quote}
The trouble is there with the current implementation. I'm not criticizing the contribution but this issue shows that it should be made more robust.
Also, the documentation about "convergence is guaranteed" can lead to a false sense of security.
Moreover, is the "regula falsi" a mathematical algorithm (with a guaranteed converge property if computed with infinite precision) or a numerical one, which this issue proves that it cannot guarantee convergence? In the former case, CM's (numerical) implementation is not strictly "regula falsi" and there would be no such thing as respect for an original/standard implementation if we can make it more robust.
I've already indicated that the fix does *not* change the contract; it stops the busy idle loop as soon as it is detected and reports that it won't do any good to increase the number of iterations. That's _obviously_ more robust.
Now, if you were answering to my 23:46 post, I'd be glad to read an explanation of why the first paragraph describes expected behaviour.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080629#comment-13080629 ]
Luc Maisonobe commented on MATH-631:
------------------------------------
{quote}
All the above imply that one expects that the algorithm can find the solution.
However, in this implementation, it can't.
Therefore there is a bug, somewhere.
{quote}
Here, the bug is in the algorithm itself, not in the implementation.
{quote}
it leads to the impression that the "Regula Falsi" mathematical algorithm can fail to converge, which is not correct (IIUC).
{quote}
It is correct. Regula Falsi fails to converge, or rather it can take a too large number of iteration to converge. This is exactly this behavior that has lead to the construction of other algorithms like Illinois or Pegasus. These two algorithms try to detect the case when the same end of the interval is always updated, and the other end remains unchanged. Once they have detected this, they slightly change the value at one end to trick the linear evaluation into choosing a value that is very likely to have the required sign to update this other end. In fact, in many cases depending of the sign of the curvature near the root, as soon as one end is very close to the root the linear interpolation will always remain on the same side of the root and hence will update this end.
I agree with Dennis here, the change needed to ensure convergence is not tool long is to choose a better algorithm, such as Illinois, Pegasus ... or the nth order bracketing solver I recently added. Regula Falsi should remain the reference Regula Falsi, just as secant and Brent should remain the reference ones.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080690#comment-13080690 ]
Gilles commented on MATH-631:
-----------------------------
[My comment starting with "I understand what you say." was an answer to Luc. I hadn't read Phil's previous one which was posted while I was writing mine.]
I agree that it is better not to change the standard algorithm, as I indicated in my first comment.
The fix which I'm proposing is not an algorithm change, it is an implementation detail similar to the many hundreds checks performed in CM. Just it is not a precondition test. It adequately indicates that something went wrong and can help the user figure out what it was. It makes the implementation more robust.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080695#comment-13080695 ]
Gilles commented on MATH-631:
-----------------------------
The original implementation, for the "problem instance being examined here", would find the root with absolute accuracy lower than *10e-12* after 3560 evaluations (note: using the default value of *1e-6*).
In fact, the root was found, at the required accuracy, after around 2200 evaluations.
That does not sound like correct behavior.
The problem is that, "x0" never being updated, the convergence test always fails... until we reach the limitation of double precision, which entails an infinite loop.
In fact my fix should not be necessary, as things have gone awry before it would apply, but there is a bug to fix nonetheless.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13095914#comment-13095914 ]
Gilles commented on MATH-631:
-----------------------------
Committed (with minor additional Javadoc fixes) in revision 1164474.
Leaving open until confirmation that {{ConvergenceException}} is the right one to use. I thought that we could make a difference between _theoretical_ and _implementation_ convergence failures. But it might not be worth introducing the distinction just for this one case, especially since it is quite clear clear now that the class should not be used.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> Project: Commons Math
> Issue Type: Bug
> Reporter: Gilles
> Fix For: 3.0
>
> Attachments: ticket631.patch
>
>
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13081180#comment-13081180 ]
Gilles commented on MATH-631:
-----------------------------
{quote}
So the function is called millions of time only if the users wishes so by setting the maxEvaluations to
a number in the range of millions.
{quote}
No, the user should not expect that any algorithm will go on a single iteration more than necessary.
This is a plain bug.
Why do you see that a test such as I proposed (exit the loop early) is wrong while CM (and any good program) is full of tests to ensure that you don't do useless computations?
This has nothing to do with "regula falsi", it is robustness in the face of limited precision.
However, if you insist that the bug (failing to detect that it is stuck) is really an integral part of the algorithm, then removing it is not a "pathetic compromise", it is the only right thing to do!
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13081104#comment-13081104 ]
Phil Steitz commented on MATH-631:
----------------------------------
I am OK removing Reg Falsi, but stand by comments above that it is a very bad idea to hack standard algorithms and agree with Luc that maxing iterations is the correct behavior in the case we have been discussing. It is kind of pathetic that the compromise is to drop the impl; but in this case I don't see it as a real loss, since I can't think of any examples where Reg Falsi would be preferable to one of the other solvers - other than for educational purposes.
> "RegulaFalsiSolver" failure
> ---------------------------
>
> Key: MATH-631
> URL: https://issues.apache.org/jira/browse/MATH-631
> 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: http://www.atlassian.com/software/jira