You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Luc Maisonobe (JIRA)" <ji...@apache.org> on 2011/07/29 11:15:09 UTC
[jira] [Created] (MATH-635) High order Brent-like bracketing solver
High order Brent-like bracketing solver
---------------------------------------
Key: MATH-635
URL: https://issues.apache.org/jira/browse/MATH-635
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 secant-based bracketing solvers available, and a wrapper which basically ends by adding a few secant steps to regular non-bracketing 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 MATH-599 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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
Re: [jira] [Created] (MATH-635) High order Brent-like bracketing
solver
Posted by Luc Maisonobe <Lu...@free.fr>.
Hello,
Le 29/07/2011 11:15, Luc Maisonobe (JIRA) a écrit :
> High order Brent-like bracketing solver
> ---------------------------------------
>
> Key: MATH-635
> URL: https://issues.apache.org/jira/browse/MATH-635
> 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 secant-based bracketing solvers available, and a wrapper which basically ends by adding a few secant steps to regular non-bracketing 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 MATH-599 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 Dfp-based
solver, so I converted (it was a 10 minutes work) the solver to have
a Dfp-based one. I have open another issue for that (MATH-636). 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 stress-test
these implementation (I'll commit them probably later today).
thanks,
Luc
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
[jira] [Resolved] (MATH-635) High order Brent-like bracketing
solver
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-635?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Luc Maisonobe resolved MATH-635.
--------------------------------
Resolution: Fixed
Fixed in subversion repository as of r1152276.
> High order Brent-like bracketing solver
> ---------------------------------------
>
> Key: MATH-635
> URL: https://issues.apache.org/jira/browse/MATH-635
> 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 secant-based bracketing solvers available, and a wrapper which basically ends by adding a few secant steps to regular non-bracketing 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 MATH-599 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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira