INTERFACE BrentUniMin;

(*
  Richard P. Brent's algorithm for minimizing a univariate function
  without derivatives.

  Converted to Modula-3 by J.Stolfi on May-Jul 1994.
*)

IMPORT UniMin;

TYPE 
  T <: Public;
  Public = UniMin.T OBJECT
    END;
    (*
      The "minimize" method does not use the derivatives computed by
      "eval", and works only with the function values.  It uses a
      combination of golden section search and successive parabolic
      interpolation.  
      
      Convergence is never much slower than that for a Fibonacci
      search.  If "f" has a continuous second derivative which is
      positive at the minimum (which is not at "ax" or "bx"), then
      convergence is superlinear, and usually of the order of about
      1.324....

      The function "f" is never evaluated at two points closer together
      than "eps*abs(fmin)+(tol/3)", where "eps" is approximately the square
      root of the relative machine precision.  If "f" is a unimodal
      function and the computed values of "f" are always unimodal when
      separated by at least "eps*abs(x)+(tol/3)", then "fmin" approximates
      the abcissa of the global minimum of "f" on the interval "(ax,bx)" with
      an error less than "3*eps*abs(fmin)+tol".  If "f" is not unimodal,
      then "fmin" may approximate a local, but perhaps non-global, minimum
      to the same accuracy.

      This function subprogram is a slightly modified  version  of  the
      algol  60 procedure  "localmin"  given in Richard Brent, "Algorithms for
      minimization without derivatives", Prentice-Hall, Inc. (1973).
    *)

END BrentUniMin.