On Sun, 13 Mar 2016 14:01:18 -0700, Connor Petty wrote:
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
Is the original method intended to return *all* roots?
but the solvers
You mean the CM implementations of the method?
There is a solver implementation that returns all (complex) roots:
"LaguerreSolver".
[IIRC, there is a pending issue that "complex" solvers should have
their own hierarchy.]
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
My opinion is that this must be fixed in any case since it does not
comply with the documented behaviour (in Javadoc and code).
while MullerSolver2 is designed to "handle" complex roots.
Does that mean that one root is picked "arbitrarily"?
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.
If that means that by changing undocumented "internal details" of the
implementation, the selected root can change, I wonder what purpose it
can have.
Regards,
Gilles
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]
