minimization using the Brent algorithm (brent.c)
Fabrice Rossi
rossi@ufrmd.dauphine.fr
Mon Mar 17 18:43:00 GMT 2003
Z F wrote:
> Hello Brian
>
> Sorry for my rudness, but I think that it is not prudent to require
> a "test" point inside the interval. (I know that standard libraries
> require that). The test F(a)>F(x)F(a) or F(y)>F(b) so the test is
> useless and only requires an extra computation of F() which might be
> time consuming.
The purpose of requiring F(a)>F(x)<F(b) is not only a protection against
stupid mistake.
First of all, it guarantees that there is actually a minimum in the open
interval ]a,b[ (as long as F is continuous). The whole rationnal of
Brent algorithm is to take an input interval on which the studied
function has a minimum (strictly inside the interval) and to produce
(after a given number of steps or up to a given precision) a smaller
interval, included into ]a,b[ that satisfies the same requirement.
The fact that there might be a point y such that F(y)>F(a) or F(y)>F(b)
is quite irrelevent and cannot be rule out by an efficient algorithm
unless you make stronger assumption on F (in which case using
derivatives might be a good idea).
Moreover, evaluation of F(x) is required for the Brent algorithm (or the
golden section search), so there is no useless evaluation.
Fabrice Rossi
More information about the Gsl-discuss
mailing list