Mathematics Source Library
C & ASM


Parabolic Extrapolation for Bracketing an Extremum

Parabolic Extrapolation for Bracketing an Extremum

The extremum of the parabola y = cx2 + bx + a where c ≠ 0 is located at x* = - b / 2c. If
c < 0, then the extremum is a maximum and if c > 0, then the extremum is a minimum. Assume that f : [α,β] → R is smooth, where α < β and α could be -∞ and β could be . By bracketing a minimum we mean to find points (x1, f(x1) ), (x2, f(x2) ), and (x3, f(x3) ), where
α ≤ x1 < x2 < x3 ≤ β such that f(x1) > f(x2) < f(x3). By bracketing a maximum we mean to find points (x1, f(x1) ), (x2, f(x2) ), and (x3, f(x3) ), where α ≤ x1 < x2 < x3 ≤ β such that
f(x1) < f(x2) > f(x3). Assume further that we want to find a subinterval which brackets the location of a minimum. Given three noncollinear points, (x1, f(x1) ), (x2, f(x2) ), and (x3, f(x3) ), where α ≤ x1 < x2 < x3 ≤ β then if f(x1) > f(x2) < f(x3) then the location of a relative minimum is bracketed between x1 and x3. And if f(x1) < f(x2) > f(x3) then there exist a minimum
( on [α,β] ) between α and x1 and another minimum between x3 and β and in this case if either α or β then chose one of the two possible intervals and select point between them, evaluate the function at that point and try again. The last two possibilities are either
f(x1) < f(x2) < f(x3) or f(x1) > f(x2) > f(x3) in which case calculate the location of the minimum of the parabola through the three points and evaluate the function there. Discard the point furtherest from new point and repeat the process until either we are within ε of an endpoint of the domain or the minimum is bracketed.

The procedure for bracketing a maximum is analogous.

Function List

  • int Min_Search_Parabolic_Extrapolation( double (*f)(double), double x[], double fx[], double a, double b, double cut_off_scale_factor )

    This routine brackets a local minimum of the user-supplied function f:[a,b] → R by parabolic extrapolation. On input two initial points are given ( x[0], f (x[0]) ) and
    ( x[2], f (x[2]) ) for which a < x[0] < x[2] < b. The return values of the function call are 0 for success, -1 if we could not bracket a minimum, i.e. the minimum is probably on the boundary or -2 if the input data is not valid. If the function call returns 0 (the minimum is bracketed) then x[0] is the lower bound of the bracket, x[2] is the upper bound of the bracket, and x[1] is a point between x[0] and x[2] such that
    f(x[0]) > f(x[1]) < f(x[2]). For each iteration, the parameter cut_off_scale_factor is used to limit the displacement from current interval under investigation. The maximum displacement is the length of the current interval times the cut_off_scale_factor.

  • int Max_Search_Parabolic_Extrapolation( double (*f)(double), double x[], double fx[], double a, double b, double cut_off_scale_factor )

    This routine brackets a local maximum of the user-supplied function f:[a,b] → R by parabolic extrapolation. On input two initial points are given ( x[0], f (x[0]) ) and
    ( x[2], f (x[2]) ) for which a < x[0] < x[2] < b. The return values of the function call are 0 for success, -1 if we could not bracket a maximum, i.e. the maximum is probably on the boundary or -2 if the input data is not valid. If the function call returns 0 (the maximum is bracketed) then x[0] is the lower bound of the bracket, x[2] is the upper bound of the bracket, and x[1] is a point between x[0] and x[2] such that
    f(x[0]) > f(x[1]) < f(x[2]). For each iteration, the parameter cut_off_scale_factor is used to limit the displacement from current interval under investigation. The maximum displacement is the length of the current interval times the cut_off_scale_factor.

C Source Code