[jira] [Issue Comment Edited] (MATH-631) RegulaFalsiSolver failure
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=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] [Issue Comment Edited] (MATH-631) RegulaFalsiSolver failure
[ https://issues.apache.org/jira/browse/MATH-631?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=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