[math] improving bracketing

[Luc Maisonobe <lu...@spaceroots.org>]

Hi all,

I have always been frustrated by the behavior of
UnivariateSolverUtils.bracket. The two problems I see
are the following ones:

 - the loop always uses increments of 1.0 to increase its
   search interval,

 - the loop always return the full current interval once
   it brackets a root.


The fact 1.0 is hard-coded is hard-coded is a problem because many
functions are limited to domains where 1.0 is far too large for
searching. Rescaling functions just because the bracket method has
an hard-coded constant is really a pain.

The fact the loop always return the full interval is a waste of
computing power. Suppose for example that some function has a root at x
= 0.5 and that your initial guess is that the root is somewhere near x =
10. Then you will compute the pairs f(9), f(11), then f(8), f(12), then
f(7), f(13) ... and finally f(0), f(20) and you will return the
bracketing interval [0, 20], despite you already know the interval [0,
1] is also bracketing since you have already computed these values in
the last two iterations.

I have a fix for that and would like to commit it. It simply adds a new
signature for "bracket" with a new parameter delta to replace the
hard-coded 1.0 and some logic to select a better interval at the end.
The existing signatures would simply delegate to it by calling it with
delta = 1.0.

However, implementing it implies the returned value of the interval is
not the same as before (the interval will often be smaller). Do you
think there would be any reason why this change would break user code?

best regards,
Luc

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org

Re: [math] improving bracketing

[Phil Steitz <ph...@gmail.com>]

On 3/16/14, 1:21 PM, Luc Maisonobe wrote:
> Hi all,
>
> I have always been frustrated by the behavior of
> UnivariateSolverUtils.bracket. The two problems I see
> are the following ones:
>
>  - the loop always uses increments of 1.0 to increase its
>    search interval,
>
>  - the loop always return the full current interval once
>    it brackets a root.
>
>
> The fact 1.0 is hard-coded is hard-coded is a problem because many
> functions are limited to domains where 1.0 is far too large for
> searching. Rescaling functions just because the bracket method has
> an hard-coded constant is really a pain.
>
> The fact the loop always return the full interval is a waste of
> computing power. Suppose for example that some function has a root at x
> = 0.5 and that your initial guess is that the root is somewhere near x =
> 10. Then you will compute the pairs f(9), f(11), then f(8), f(12), then
> f(7), f(13) ... and finally f(0), f(20) and you will return the
> bracketing interval [0, 20], despite you already know the interval [0,
> 1] is also bracketing since you have already computed these values in
> the last two iterations.
>
> I have a fix for that and would like to commit it. It simply adds a new
> signature for "bracket" with a new parameter delta to replace the
> hard-coded 1.0 and some logic to select a better interval at the end.
> The existing signatures would simply delegate to it by calling it with
> delta = 1.0.
>
> However, implementing it implies the returned value of the interval is
> not the same as before (the interval will often be smaller). Do you
> think there would be any reason why this change would break user code?

I can't imagine this breaking anyone, though I suppose that it is in
theory possible.  The contract is just that the interval contains a
root, so I think it is fair to improve the precision.  My view on
this kind of thing is that behavior changes that do not change the
API contract are OK and expected.  Improved precision, fewer
iterations to converge, etc. are all expected changes as code is
improved.  So I would say go ahead and commit.

Phil
>
> best regards,
> Luc
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org