To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Successive parabolic interpolation

From Wikipedia, the free encyclopedia

Successive parabolic interpolation is a technique for finding the extremum (minimum or maximum) of a continuous unimodal function by successively fitting parabolas (polynomials of degree two) to a function of one variable at three unique points or, in general, a function of n variables at 1+n(n+3)/2 points, and at each iteration replacing the "oldest" point with the extremum of the fitted parabola.

YouTube Encyclopedic

  • 1/3
    Views:
    32 977
    11 095
    14 404
  • Direct Method of Interpolation: Quadratic Interpolation
  • Mod-01 Lec-29 Interpolation Methods
  • Lecture - 39 Soil Mechanics

Transcription

. . In this segment, we will talk about quadratic interpolation, and, again, we are doing this quadratic interpolation by using the direct method.|So in quadratic interpolation, what you're going to do is you're going to choose three of the data points which are given to you.|Keep in mind, again, that you might be given several data points, hundreds, or millions, but for quadratic interpolation, you're going to choose the three data points which are of use to you, and then let's suppose this is x0, y0, this is x1, y1, this is x2, y2, so you're going to simply draw a second-order polynomial which goes through those data points, so this will be a second-order polynomial, and it'll be the form a0, plus a1 x, plus a2 x squared.|And the question arises that how do I find a0, a1, and a2? That's simply by substituting the values of y at these values of x, and you will be able to set up three equations, three unknowns, and then you should be able to find the value of y at any value of x which might be of interest to you.|So let's go ahead and look at this particular problem through an example. . So let's suppose the upward velocity of a rocket is given at these particular times, that the value at time, t equal to 0 is 0, at 10 it's 227.04, at 15 it's 362.78, at 20 it is 517.35, at 22.5 it is 602.97, at 20 it is 901.67.|So let's suppose we are given the value of the velocity at these six different data points, and we want to do quadratic interpolation. So the first question arises that I need to find out which points I should choose for the value of the velocity to be calculated at 16.|So what I need to do is I need to see that which are the three closest points to 16, but I also need to make sure that the three points which I will choose closest to 16 should also bracket the number 16.|So let's suppose if I choose 15, that's 1 away, 20, that's 4 away, and those bracket the closest.|Then should I choose 22.5 or should I choose 10?|10 is 6 away from 16, while 22.5 is 6.5 away from 16, so I'd be choosing 10. So once . . . so you've made the decision about the three data points based on what is the distance between these data points and 16, but at the same time also make sure that the three data points which you're going to choose for the quadratic interpolation also bracket this point of 16, otherwise it'll be extrapolation.|So, let's go ahead and see that what I'm going to do is I'm going to choose the velocity expression to be a0, plus a1 t, plus a2 t squared, that's what I'm going to choose, and now what I need to do is I need to substitute the values of velocity at 10, 15, and 20 to set up my three equations, three unknowns. So I'll have 227.04 will be the value of the velocity at . . . at 10, 362.78 is the value of the velocity at . . . at 15, and 517.35 is the value of the velocity at . . . at 20. So this, what this is going to do, it's going to give us three equations, three unknowns, so you can set them up in the matrix form.|So if I set them up in the matrix form, I have three unknowns, a0, a1, a2, and the coefficient matrix will be 1, 10, 100, 1, 15, 225, 1, 20, 400, and the right-hand sides will be the velocity numbers which I have, 227.04, 362.78, and 517.35.|So I get three equations, three unknowns, and what I need to do now is to take those three equations, three unknowns, and solve them by using any of the methods which I learned in my simultaneous linear equations, whether it's Gauss elimination, Gauss-Seidel method.|So what I'll do is, I'll . . . what I find is these are the constants I get, a0 I get to be 12.05, a1 I get 17.733, a2 I get 0.3766. So what that means is that the velocity expression which I have is a0, plus a1 times t, plus a2 times t squared.|And, again, it's important to say that this is the interpolant, and in what domain this particular interpolation is valid, and the domain in which this interpolation is valid, it is between time, t 10 and 20.|So now I want to find the velocity at 16, it turns out to be 12.05, plus 17.733 times 16, plus 0.3766 times 16 squared, and this value here turns out to be 392.19 meters per second, and that's the value of the velocity which you're getting at 20. Now, the question arises that we are doing quadratic interpolation, how do we know that how much we can trust this solution, or which significant digits can I trust in this solution?|So in order to be able to do this, what you're going to do is you're going to look at what did you get for the value of the velocity at 16 when you were doing linear interpolation.|When you did linear interpolation, you got 393.70 meters per second, this was from linear interpolation, and the value of velocity at 16 is 392.19, which we just got by using quadratic interpolation. So what we can do is we can look at this as our previous value, and we can look at this as our current value.|So this is the previous value which we obtained by using linear interpolation, and this is the value which we obtain now, by using quadratic interpolation.|So I'm going to calculate my absolute relative approximate error by current approximation, which is from the quadratic interpolant, minus the previous approximation, which is from the linear interpolant, and then multiply it by 100, and in this case which I get is 0.384 percent, which basically tells me that I can trust two significant digits in my answer, because less than 5 . . . less than or equal to 5 percent would be one significant digit, less than or equal to 0.5 would be two significant digits, and in that case what that means is I can trust this 3, and I can trust this 9, because this is less than or equal to 0.5 percent, which represents two significant digits to be at least correct in my solution.|And that's the end of this segment. . .

Advantages

Only function values are used, and when this method converges to an extremum, it does so with an order of convergence of approximately 1.325. 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 derivatives makes successive parabolic interpolation a popular alternative to other methods that do require them (such as gradient descent and Newton's 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 collinear, 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.

Improvements

Alternating the parabolic iterations with a more robust method (golden-section search is a popular choice) to choose candidates can greatly increase the probability of convergence without hampering the convergence rate.

See also

References

Michael Heath (2002). Scientific Computing: An Introductory Survey (2nd ed.). New York: McGraw-Hill. ISBN 0-07-239910-4.

This page was last edited on 25 April 2023, at 10:54
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.