On Sun, 13 Mar 2016 14:01:18 0700, Connor Petty wrote:
> On Fri, Mar 11, 2016 at 6:34 PM, Gilles
> <gilles@harfang.homelinux.org>
> wrote:
>
>> Hi.
>>
>> On Fri, 11 Mar 2016 17:50:59 0800, Connor Petty wrote:
>>
>>> I've been doing some investigation regarding MATH1333 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 3point
> 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, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
