Successive parabolic interpolation
Encyclopedia
Successive parabolic interpolation is a technique for finding the extremum (minimum or maximum) of a continuous unimodal function by successively fitting parabola
s (polynomials of degree two) to the function at three unique points, and at each iteration replacing the "oldest" point with the extremum of the fitted parabola.
of approximately 1.324. The superlinear rate of convergence is superior to that of other methods with only linear convergence (such as line search). Moreover, not requiring the computation or approximation of function derivative
s makes successive parabolic interpolation a popular alternative to other methods that do require them (such as gradient descent
and Newton's method
).
, the resulting parabola is degenerate
and thus does not provide a new candidate point. Furthermore, if function derivatives are available, Newton's method is applicable and exhibits quadratic convergence.
is a popular choice) to choose candidates can greatly increase the probability of convergence without hampering the convergence rate.
Parabola
In mathematics, the parabola is a conic section, the intersection of a right circular conical surface and a plane parallel to a generating straight line of that surface...
s (polynomials of degree two) to the function at three unique points, and at each iteration replacing the "oldest" point with the extremum of the fitted parabola.
Advantages
Only function values are used, and when this method converges to an extremum, it does so with a rate of convergenceRate of convergence
In numerical analysis, the speed at which a convergent sequence approaches its limit is called the rate of convergence. Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of practical importance if we deal with a sequence of...
of approximately 1.324. The superlinear rate of convergence is superior to that of other methods with only linear convergence (such as line search). Moreover, not requiring the computation or approximation of function derivative
Derivative
In calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...
s makes successive parabolic interpolation a popular alternative to other methods that do require them (such as gradient descent
Gradient descent
Gradient descent is a first-order optimization algorithm. To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient of the function at the current point...
and Newton's method
Newton's method in optimization
In mathematics, Newton's method is an iterative method for finding roots of equations. More generally, Newton's method is used to find critical points of differentiable functions, which are the zeros of the derivative function.-Method:...
).
Disadvantages
On the other hand, convergence (even to a local extremum) is not guaranteed when using this method in isolation. For example, if the three points are collinearLine (mathematics)
The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...
, the resulting parabola is degenerate
Degeneracy (mathematics)
In mathematics, a degenerate case is a limiting case in which a class of object changes its nature so as to belong to another, usually simpler, class....
and thus does not provide a new candidate point. Furthermore, if function derivatives are available, Newton's method is applicable and exhibits quadratic convergence.
Improvements
Alternating the parabolic iterations with a more robust method (golden section searchGolden section search
The golden section search is a technique for finding the extremum of a unimodal function by successively narrowing the range of values inside which the extremum is known to exist. The technique derives its name from the fact that the algorithm maintains the function values for triples of points...
is a popular choice) to choose candidates can greatly increase the probability of convergence without hampering the convergence rate.
See also
- Inverse quadratic interpolationInverse quadratic interpolationIn numerical analysis, inverse quadratic interpolation is a root-finding algorithm, meaning that it is an algorithm for solving equations of the form f = 0. The idea is to use quadratic interpolation to approximate the inverse of f...
is a related method that uses parabolas to find roots rather than extrema. - Simpson's ruleSimpson's ruleIn numerical analysis, Simpson's rule is a method for numerical integration, the numerical approximation of definite integrals. Specifically, it is the following approximation:...
uses parabolas to approximate definite integrals.