[Bug-gsl] [bug #43496] Possible error in brent minimizer convergence criteria

[Patrick Alken]

URL:
  <http://savannah.gnu.org/bugs/?43496>

                 Summary: Possible error in brent minimizer convergence
criteria
                 Project: GNU Scientific Library
            Submitted by: psa
            Submitted on: Wed 29 Oct 2014 02:16:09 PM GMT
                Category: Runtime error
                Severity: 3 - Normal
        Operating System: 
                  Status: None
             Assigned to: None
             Open/Closed: Open
                 Release: 
         Discussion Lock: Any

    _______________________________________________________

Details:

In GSL, min/brent.c:128 has this for the evaluation of the parabolic fit:

 

  if (fabs (p) < fabs (0.5 * q * r) && p < q * w_lower && p < q * w_upper)

 

This matches the Algol60 implementation given by Richard Brent in the book.
Unfortunately, there seems to be a transcription (or similar) error and the
code should actually be

 

  if (fabs (p) < fabs (0.5 * q * r) && p > q * w_lower && p < q * w_upper)

 

which matches the actual text of the book which says that the algorithm takes
the golden section path under some conditions, including “x+p/q not in
(a,b)” which would translate to:

 

x + p/q <= a || x +p/q >= b …

p <= q * (a - x) || p >= q * (b - x) …

p > q * (a - x) && p < q * (b - x)

 

In fact, other authors such as Forsythe have found and corrected the error.
Netlib implementation of fmin.f is also corrected (seems to be the same as
that in the Forsythe book). The Numerical Recipes and boost implementations
are also fixed.

 

Some references for further information:

 

·         http://www.netlib.org/go/fmin.f

·         http://www.nr.com/forum/showthread.php?p=4893

·         Computer Methods for Mathematical Computations – G.E. Forsythe,
Michael A. Malcolm, Cleve B. Moler. Prentice Hall. ISBN 0-13-165332-6.




    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?43496>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/