Function to be analyzed
Left bound of initial range of f known to contain the minimum.
Right bound of initial range of f known to contain the minimum.
Relative tolerance.
Absolute tolerance.
Preconditions:
ax and bx shall be finite reals.
relTolerance shall be normal positive real.
absTolerance shall be normal positive real no less then T.epsilon*2.
A tuple consisting of x, y = f(x) and error = 3 * (absTolerance * fabs(x) + relTolerance).
The method used is a combination of golden section search and successive parabolic interpolation. Convergence is never much slower than that for a Fibonacci search.
References: "Algorithms for Minimization without Derivatives", Richard Brent, Prentice-Hall, Inc. (1973)
int i; double f(double x) { i++; return fabs(x-1); } //slow auto minD = findLocalMin(&f, -double.max/2, double.max/2, double.min_normal, 2*double.epsilon); with(minD) { assert(approxEqual(x, 1)); assert(approxEqual(y, 0)); assert(error <= 10 * double.epsilon); //assert(minD.error == 0); }
Find a real minimum of a real function f(x) via bracketing. Given a function f and a range (ax..bx), returns the value of x in the range which is closest to a minimum of f(x). f is never evaluted at the endpoints of ax and bx. If f(x) has more than one minimum in the range, one will be chosen arbitrarily. If f(x) returns NaN or -Infinity, (x, f(x), NaN) will be returned; otherwise, this algorithm is guaranteed to succeed.