commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles <gil...@harfang.homelinux.org>
Subject Re: [Math] MullerSolver2 does not respect initial bracketing
Date Tue, 15 Mar 2016 23:48:12 GMT
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 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: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message