## Parabolic Interpolation

The extremum of the parabola*y = cx*where

^{2}+ bx + a*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 (

*x*,

_{1}*f (x*),

_{1})(

*x*,

_{2}*f (x*), and (

_{2})*x*,

_{3}*f (x*), where

_{3})*α ≤ x*such that

_{1}< x_{2}< x_{3}≤ β*f (x*>

_{1})*f (x*<

_{2})*f( x*. Then the location of minimum,

_{3})*x*, of the parabola through the same three points must lie between

^{*}*x*and

_{1}*x*. If

_{3}*x*=

^{*}*x*then perturb it by a small amount η either towards

_{2}*x*or

_{1}*x*depending on whether

_{3}*f*(

*x*) is less than or

_{1}*f*(

*x*) or not. Then either

_{3}*x*<

^{*}*x*or

_{2}*x*>

^{*}*x*. If

_{2}*x*<

^{*}*x*then either

_{2}*f*(

*x*) ≤

^{*}*f*(

*x*) or

_{2}*f*(

*x*) >

^{*}*f*(

*x*). If

_{2}*f*(

*x*) ≤

^{*}*f*(

*x*) then set

_{2}*x*←

_{3}*x*,

_{2}*x*←

_{2}*x*or if

^{*}*f*(

*x*) >

^{*}*f*(

*x*) then set

_{2}*x*←

_{1}*x*. The process is analogous to that above if

^{*}*x*>

^{*}*x*. Repeat the process unless the length of the interval of uncertainty is less than a preassigned tolerance in which case terminate the procedure.

_{2}### 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

- The file, min_search_parabolic_interpolation.c, contains the version of Min_Search_Parabolic_Interpolation( ) written in
*C*.

- The file, max_search_parabolic_interpolation.c, contains the version of Max_Search_Parabolic_Interpolation( ) written in
*C*.