On Fri, Mar 11, 2016 at 6:34 PM, Gilles <[email protected]> wrote:
> Hi. > > On Fri, 11 Mar 2016 17:50:59 -0800, Connor Petty wrote: > >> I've been doing some investigation regarding MATH-1333 and I cam across >> some bounds issues in MullerSolver and MullerSolver2. There are a few test >> cases I've created which cause these solvers to return values outside of >> their initial bracket. I've created fixes for MullerSolver but >> MullerSolver2 baffles me. MullerSolver is more or less an implementation >> of >> the algorithm you can find at >> https://en.wikipedia.org/wiki/Muller's_method >> while MullerSolver2 is an implementation of the algorithm at >> http://mathworld.wolfram.com/MullersMethod.html. But the major difference >> between MullerSolver 1 & 2 is that MullerSolver2 was designed to work >> without bracketing. This turns out to make it fairly easy to make it >> return >> faulty values. >> >> Now my question is: How much should these solvers stick to their original >> algorithms? >> > > Fully. > Or the name and documentation of the class must clearly reflect that > it is a variation. > > If the original algorithm is flawed should solver exhibit those >> same flaws? >> > > Yes (if the flaw is in the algorithm itself, not just in the > implementation, > e.g. because the expected properties assume infinite precision). > > But whenever possible the implementation should (_must_, IMHO) check that > it has not hit one of its own limitation, and "fail early". > > There is some precedent for that in SecantSolver which has the same >> guarantees of convergence as the original algorithm (which has none). >> But MullerSolver2 is clearly a patched version of the algorithm >> > > Do you have the possibility to check another implementation of that > algorithm? > Since the Javadoc says that the original deals with complex values but CM > avoids it, I wonder whether this could be the problem. > Well, the concepts of Muller's Method will remain the same regardless of implementation: root finding by using quadratic 3-point interpolation. Muller's method will find real and complex roots but the solvers only care about the real roots so changes have to be made to make sure that you either never encounter complex roots or you somehow handle encounters with complex roots. MullerSolver is designed to never encounter complex roots using bracketing while MullerSolver2 is designed to "handle" complex roots. Now I say "handle" because the only way you can escape a situation where the interpolation produces a complex root is to essentially make up a value and hope it is closer to the real root (usually is). So yes, the way complex values are dealt with is large part of the problem. > > it is based >> off of and exhibits some very characteristic flaws from the original >> algorithm. Should MullerSolver2's bounds issue be fixed or should that >> issue just be accepted a limitation of that algorithm? >> > > Cf. above. > > Best regards, > Gilles > > >> Best Regards, >> Connor Petty >> > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [email protected] > For additional commands, e-mail: [email protected] > >
