[Bug-gsl] min/brent.c: Implementation of Brent's algorithm

[Peter Brommer]

Dear Developers,

I am switching a program of mine from Numerical Recipes to gsl due to 
licence issues. One of the programs I try to switch uses Brent's algorithm 
of minimization without derivatives.

While checking the gsl implementation of that algorithm I noticed a marked 
difference between what is in the code and what Brent writes in his 
publication (R P Brent, Algorithms for Minimization without Derivatives, 
Prentice-Hall).

In the publication it says near the end (in pseudo-code)
(with f_v >= f_w >= f_z, f_u new value)

if (f_u <= f_z)
        then do "A"
else
        do "B"
        if (f_u <= f_w) or (w == z)
                then do "C"
        else if (f_u <= f_v) or (v == z) or (v == w)
                then do "D"
        end
end

whereas what your algorithm does is:

if (f_u > f_z)
        then do "B"
else if (f_u < f_z)
        then do "A"
else if (f_u <= f_w) or (w == z)
        then do "C"
else if (f_u <= f_v) or (v == z) or (v == w)
        then do "D"
end

A, B, C and D signify identical code.

In your algorithm, the checks that lead to C and D are only executed if
(f_u == f_z), whereas they are executed if (f_u > f_z) in the original 
implementation.

I was wondering if you had any specific reason for changing the 
implementation compared to Brent's publication. Perhaps you could tell me 
whether I am completely mistaken (or have overseen a crucial part of the 
picture).

I have included a patch for brent.c to implement the original algorithm as 
published. Perhaps this is of any help to you.

Kind regards,

Peter

-- 
------------------------------------------------------------------------
Peter Brommer                     Dipl.-Phys.
Institut für Theoretische und Angewandte Physik
Universität Stuttgart
Pfaffenwaldring 57, 6.347         Phone  +49 711 685 5267
70550 Stuttgart                   Fax    +49 711 685 5271
Germany                           email  address@hidden

pgphfA7MZGFmx.pgp
Description: PGP signature