Quadratic Interpolation Method

by admin in , , , on April 27, 2019

This code conducts an Interpolation for a given set of data using the Quadratic Interpolation method, where the function’s critical value is bracketed, and a quadratic interpolant is fitted to the arc contained in the interval. Then, the interpolant is minimized, and the new interval is determined based on the relation of the minimizer to the original endpoints of the interval.

Code Outputs:

  • Printed Table of Interpolated Values
  • Chart Compare of Interpolated Values with Given Points.

  Xi                F(Xi)
3.0000          0.2274
11.0000          0.4123
31.0000          0.5464
53.0000         0.5287
71.0000          0.6455
93.0000          0.5624
111.0000          0.7551

 

Input Requirements:

  • X-Axis Points
  • Y-Axis Points

About the Method:

Interpolation methods are a common approach to the more general area of line search for optimization. In the case of quadratic interpolation, the function’s critical value is bracketed, and a quadratic interpolant is fitted to the arc contained in the interval. Then, the interpolant is minimized, and the new interval is determined based on the relation of the minimizer to the original endpoints of the interval.

Put more formally, let x* maximize (or minimize) f(x). If x* is not easily found through analytic methods, then it is significantly easier to bracket the interval over which this critical point occurs. Let q(x) denote the quadratic interpolant of f(x). Minimizing a quadratic function is trivial, and so the critical point of q is easily obtained. We then form a new bracketing interval by throwing away the ”worst” point, which for our purposes would be the point that is the largest or smallest, depending on whether we want to approximate a maximum or minimum. The process is then iterated until the desired precision is reached.

 

Quadratic Interpolation Method:

This is a 3 point interpolation-optimization method.  Choose 3 points, 2 endpoints to bracket our critical point, and then a point within the interval as well. Using the Lagrange Interpolation formula, we can easily find our
interpolant q(x). We have:

To find the optimum value, we of course take the derivative of q(x) and set it to 0. By doing this, we obtain:

And the iteration scheme is easily deduced:

This method differs slightly from the previous two methods, because it is not as simple to determine the new bracketing interval. If xmin lies between x1 and x3, then we want to compare the distance between
xmin and x2. If  |xmin − x2| < er

Where er is the prescribed tolerance, then we are done. Otherwise we create the new interval by checking which point is the largest or smallest, depending on the nature of our critical point. If xmin lies outside of our bracketing interval [x1, x3], then we immediately create a new bracketing interval in the same way as we just described.

 

References:

[1] KELLER VANDEBOGERT, METHOD OF QUADRATIC INTERPOLATION, September 3, 2017.

[2] Wenyu Sun, YaXiang Yuan. Optimization Theory and Methods: Nonlinear Programming. 89-98.

1 Sale

Share Now!

Release Information

  • Price
    :

    $4.99

  • Released
    :

    April 27, 2019

  • Last Updated
    :

    July 23, 2020

Share Your Valuable Opinions