Mathematics Source Library
C & ASM


Parabolic Interpolation

Parabolic Interpolation

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.

Suppose that we are given a smooth function f : [α,β] → R, where α < β for which we seek to locate a relative minimum. Assume that also we are given the initial data (x1, f (x1) ),
(x2, f (x2) ), and (x3, f (x3) ), where α ≤ x1 < x2 < x3 ≤ β such that f (x1) > f (x2) < f( x3). Then the location of minimum, x*, of the parabola through the same three points must lie between x1 and x3. If x* = x2 then perturb it by a small amount η either towards x1 or x3 depending on whether f (x1) is less than or f (x3) or not. Then either x* < x2 or x* > x2. If x* < x2 then either f (x*) ≤ f (x2) or f (x*) > f (x2). If f (x*) ≤ f (x2) then set x3x2, x2x* or if f (x*) > f (x2) then set x1x*. The process is analogous to that above if x* > x2. Repeat the process unless the length of the interval of uncertainty is less than a preassigned tolerance in which case terminate the procedure.

Function List

  • int Min_Search_Parabolic_Interpolation( double (*f)(double), double* x0, double* fx0, double tolerance )

    Given initial data ( x0[0], fx0[0] ), ( x0[1], fx0[1] ), and ( x0[2], fx0[2] ) where
    x0[0] < x0[1] < x0[2], fx0[0] > fx0[1] < fx0[2] and fx0[i] = f ( x0[i] ), i = 0, 1, 2 this routine reduces the interval of uncertainty [ x0[0], x0[2] ] by an extension of the iterative process described above. The iteration halts when the length of the interval of uncertainty relative to its midpoint is less than tolerance. Upon return, x0[0] is the lower endpoint of the interval of uncertainty, x0[2] is the upper endpoint and x0[1] is the current best estimate of the location of the minimum. The array fx0 will contain the value of f ( x ) evaluated at the three points.

  • int Max_Search_Parabolic_Interpolation( double (*f)(double), double* x0, double* fx0, double tolerance )

    Given initial data ( x0[0], fx0[0] ), ( x0[1], fx0[1] ), and ( x0[2], fx0[2] ) where
    x0[0] < x0[1] < x0[2], fx0[0] < fx0[1] > fx0[2] and fx0[i] = f ( x0[i] ), i = 0, 1, 2 this routine reduces the interval of uncertainty [ x0[0], x0[2] ] by an extension of the iterative process described above. The iteration halts when the length of the interval of uncertainty relative to its midpoint is less than tolerance. Upon return, x0[0] is the lower endpoint of the interval of uncertainty, x0[2] is the upper endpoint and x0[1] is the current best estimate of the location of the maximum. The array fx0 will contain the value of f ( x ) evaluated at the three points.

C Source Code