CHAPTER 05.01: BACKGROUND OF INTERPOLATION: Uniqueness of Polynomial Interpolant: Part 1 of 2
In this segment, we're going to talk about the uniqueness of the interpolating polynomial. We want to be able to figure out that if we are interpolating to a polynomial, is that polynomial unique? Now, it's based on a theorem. The theorem goes like this, given n-plus-1 data points, like x0, y0, x1, y1, all the way up to x-sub-n-minus-1, y-sub-n-minus-1, xn, yn, so you have n-plus-1 data points given to you, what you want to be able to show is that the polynomial of order n or less, it's very important to realize that it's n or less, the polynomial order n or less that goes through these n-plus-1 data points, it is unique. So what we want to be able to show is that if somebody gives us n-plus-1 data points, that if there is a polynomial order n or less which goes through these n-plus-1 data points, that it is unique, that if you try to draw some other polynomial through those n-plus-1 data points, you should end up with the same one. So let me give an example first, so let's suppose if you have . . . if you have three data points, let's suppose, like that, then the polynomial which goes through those three data points, the interpolant, if it is of second-order polynomial or less, then that particular polynomial is unique. When we talk about this n or less business, what that means is that I can have, let's suppose points like 2, comma, 4, 3, comma, 6, and 4, comma, 8, let's suppose, and if I draw a polynomial through those three data points, that polynomial which goes through those three data points will be y is equal to 2 x. So you can very well see here you have three data points, the polynomial order only 1 goes through those three data points, and that particular polynomial is unique, for any order which is of n or less, which in this case is 2 or less. So that's where the n or less comes from, that you may have a situation like this where you have three data points, let's suppose, and you are able to draw a straight line through those data points, because these all fall under the straight line of y is equal to 2 x. So let's go for the proof of this, and what I'm going to do is I'm going to show you the proof for three data points, and you can . . . you can extend it to any number of data points. The reason why I'm doing that for two . . . or three data points is mainly to keep the discussion simple. So let's suppose somebody gives you three data points, and let's call it x0, y0, x1, y1, and x2, y2, and somebody's saying that, hey, go ahead and let us draw a second-order polynomial which goes through those data points, so let's suppose I call this to be P2 of x. Now, if I'm going to throw that kind of contradiction, that, hey, there is another polynomial which goes through the same three data points, so let's suppose somebody says, hey, let me take another polynomial, Q2 of x, 2 standing for second-order polynomial, which goes through those same three data points, then what we need to show is we need to show that P2 of x is identically same as Q2 of x, and that's how we're able to prove the theorem. If we are not able to show that, that means that, hey, there is some other polynomial which can go through those three data points. So what I want to be able to show is that if there are three data points, a polynomial order 2 or less which is going through those three data points is unique by saying that, hey, let there be another polynomial which goes through those three data points, other than the one which you might have found, and I want to show that it is unique. So what that means is that I have P2 of x and Q2 of x going through all these three data points, so let me say, hey, what is R2 of x? R2 of x is something which I am defining as P2 of x minus Q2 of x, so let me call it identically equal to this. So basically what I am doing is I'm taking this polynomial P2 of x and Q2 of x, subtracting the two, and I know that I'll get another polynomial called R2 of x, let's suppose, because if you one second-order polynomial from another second-polynomial, you will get the . . . you'll get some other second-order polynomial, but there's something which I know about R2 of x, because if I put for x I put x0, what I will get is I'll get P2 of x2 minus Q2 of x2. And what is P2 of x? It's nothing but y0, and Q2 of x0 is also y0, so I'll get 0. So what I'm able to say here is that this particular new polynomial R2 of x which I have has a zero at x0. Similarly I can show that R2 of x1 is 0 and R2 of x1 . . . x2 is 0. So it is 0 at x0, 0 at x1, 0 at x2. That doesn't necessarily mean it's 0 everywhere, the only thing which I have shown here is that the polynomial R2 is 0 . . . the polynomial R2 is zero at these three data points, x0, x1, and x2, because P2 and Q2 has to go through those three data points. So basically what I have shown is that R2 of x has three zeros. So I have shown that has three zeros, and those are x equal to x0, x1, and x2, but how can a second-order polynomial have three zeros? The only way . . . the only way a second-order polynomial can have three zeros is if R2 of x is identically equal to 0. That means it's 0 everywhere, because if you look at a second-order polynomial, and you put second-order polynomial equal to 0, you get a quadratic equation, and a quadratic equation has two roots, which means that the quadratic polynomial has two zeros, but how's it possible if a second-order polynomial can have three zeros? The only way it's possible is R2 of x identically equal to 0. In the segment I'll show you the proof of this, right now I'm just telling you that if a second-order polynomial has three zeros, then R2 of x is identically equal to 0. So if it's identically equal to 0, that means that I had R2 of x identically equal to P2 of x minus Q2 of x, and if this is equal to 0 everywhere, then P2 of x is identically equal to Q2 of x. So what I have basically shown is that the polynomial, the second-order polynomial is unique, because if I choose some other polynomial, it turns out to be the same polynomial, the one which goes through those three data points, so the polynomial is unique of order 2 or less is unique. And you can extend now this argument which I showed you here to any number of data points. So I showed you specifically for three data points, and here drawing a second-order polynomial or less through it, but you can extend this to any number of data points, n number of data points, or n-plus-1 data points, and say, hey, there's an nth-order polynomial which goes through those n-plus-1 data points, and let me figure out whether that particular polynomial is unique. You follow the same argument, you will come up with the same conclusion. And that's the end of this segment. |