Interactive Educational Modules in
Scientific Computing

Successive Parabolic Interpolation

This module demonstrates successive parabolic interpolation for minimizing a nonlinear function in one dimension. Given three approximate solution values, a new approximate solution value is given by the minimum of a quadratic polynomial interpolating the three given approximate solution values. The new approximate solution value replaces one of the old ones, and the process is repeated until convergence, which is usually quite rapid.

The user selects a problem either by choosing a preset example or typing in a desired objective function f(x) and initial guesses x0, x1, x2. The steps of successive parabolic interpolation are then carried out sequentially by repeatedly clicking on NEXT or on the currently highlighted step. The current points x and corresponding function values f(x) are indicated by bullets on the plot and are also shown numerically in the table below. At each iteration, a quadratic polynomial p(x) is fit to the three current function values, the next approximate solution is taken to be the minimum of the quadratic function, and the process is then repeated. If the starting guesses are close enough to the true minimum, then the successive parabolic interpolation method converges to it, typically with a superlinear convergence rate.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 6.4.2, especially Example 6.9.

Developers: Jeffrey Naisbitt and Michael Heath