[jira] [Created] (MATH-631) "RegulaFalsiSolver" failure

classic Classic list List threaded Threaded
34 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[jira] [Created] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
"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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Issue Comment Edited] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Issue Comment Edited] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-631) "RegulaFalsiSolver" failure

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ 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

       
12