Hello,
Le 29/07/2011 11:15, Luc Maisonobe (JIRA) a écrit :
> High order Brentlike bracketing solver
> 
>
> Key: MATH635
> URL: https://issues.apache.org/jira/browse/MATH635
> Project: Commons Math
> Issue Type: New Feature
> Reporter: Luc Maisonobe
> Assignee: Luc Maisonobe
> Fix For: 3.0
>
>
> The new bracketing solvers greatly improve usage. Unfortunately, for now there are only
secantbased bracketing solvers available, and a wrapper which basically ends by adding a
few secant steps to regular nonbracketing solvers.
>
> Changing the Brent solver to provide bracket selection on the final result would depart
from the standard algorithm, which is a wrong move (see MATH599 for a similar case recently
resolved).
> It would be nice to set up another solver in the same spirit as Brent (i.e. using inverse
polynomial interpolation when possible and falling back to dichotomy) while retaining bracketing.
A nice and simple improvement is also to use higher order inverse polynomial interpolation
by retaining several previous points. This allows to build a solver that have an higher order
than Newton for example but still only needs function values and no derivatives at all.
As you have probably guessed, this solver is already developed. I have
played with this idea for a while and implemented it last week end
during two long train trips. It works pretty well.
The idea is really simple: start with a two or three points array
containing min, max and if present startValue to build the inverse
interpolation polynomial exactly in the same spirit as Brent (inverse
interpolation is *really* a fabulous trick). Then as new points are
computed trying to find the root, they are added to the array and the
order of the inverse interpolation increases (quadratic with 3 points,
cubic with four points ...). Strangely enough, I did not find any
reference on such a method, but I still think it should be well known
(Brent method is from the 60's). So if anybody can point me to a
reference paper and analysis, I would be glad to adapt my home grown
method to something more standard. If there are no paper, I probably can
write a small analysis on it and publish it on my site but I doubt it
would be interesting.
As I was testing the implementation, I noticed we had no Dfpbased
solver, so I converted (it was a 10 minutes work) the solver to have
a Dfpbased one. I have open another issue for that (MATH636). It seems
to work well. However, I don't know were I should put this. It would be
probably overkill to set a complete set of interfaces, abstract classes
and implementations in the analysis.solver packe for Dfp functions. I
think about setting simply a UnivariateDfpFunction interface and only
one BracketingNthOrderBrentSolverDFP class, both in the dfp package.
What do you think about it ?
Another thing I want to ask fellow developers it to try to stresstest
these implementation (I'll commit them probably later today).
thanks,
Luc

To unsubscribe, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
