CHAPTER 05.03: NEWTON DIVIDED DIFFERENCE METHOD: Newton's Divided Difference Polynomial: Quadratic Interpolation: Theory
In this segment, we will continue talking about Newton's divided difference polynomial method, this is Newton's divided difference polynomial, and we'll talk about the quadratic interpolation, and in this quadratic interpolation, we'll just talk about . . . in this segment, we'll just talk about theory. We'll talk about an example next time. So let's go ahead and look at the quadratic interpolation theory, what it's like. So again, chosen, let's suppose somebody chooses x0, y0, x1, y1, x2, y2, so three data points are needed, because we are talking about quadratic interpolation, so we are choosing three data points out of the once which might be given to us, we want to find the quadratic, or second-order, Newton's divided difference polynomial. So how do we go about doing that? So what that means is that, let's suppose somebody's giving us three data points, so this is y is equal to f of x. So we are given, let's suppose, three data points, and somebody's simply telling us to draw a second-order polynomial, or find the second-order polynomial which goes through these three data points, called x0, y0, x1, y1, x2, y2, and in our theory, we will show this as the value of the function at x0, this one we will show as the value of the function at x1, and this one, this y2, we will show as the value of the function at x3, so they're interchangeable, there's nothing different about it, but that's the way it is written in convenient form in most of the books, so I'm going to follow the same guidelines of same notation. So let's go ahead and see that how we can, once we have chosen three data points out of the points which are given to us, how can we draw a second-order polynomial? How can we find the coefficients of the second-order polynomial in the form of the Newton's divided difference polynomial method? So what that entails is that we are going to assume the second-order polynomial, so this is 2 standing, the subscript 2 standing for the second-order polynomial, will be of the form of b0, plus b1 times x minus x0, plus b2 times x minus x0, times x minus x1. So that's what's going to be the form of the second-order polynomial, which will allow us to find out the second-order polynomial, and again, what the unknowns are are b0, b1, and b2. This is a second-order polynomial, because if you expand it, you will see that the highest order of the value of x will be x squared, which will be coming from here, so it's a second-order polynomial, but it's in a different form, and again, there's a reason for it. The reason why that is so is because we know that the value of the function at x0 will be the same as the value of the function of the second-order polynomial, because it has to go through that data point, and so if I substitute x equal to x0 in here, I'll get b0, plus b1 times x0 minus x0, plus b2 times x0 minus x0, times x0 minus x1. And basically what you will find out, this is 0, and this is 0, so what I get is that f2 of x0 is nothing but b0. In fact, what you are finding out is that . . . or f of x0 is nothing but b0, and what you are finding out is this expression for b0 which you are getting right here is exactly the same which you get for the linear Newton's divided . . . linear interpolation by having done it by Newton's divided difference polynomial method. Now, again, the value of the function at x1 will be the same as the value of the interpolant at x1, because it has to go through x equal to x1. So if I substitute x equal to x1 in my general expression for the second-order polynomial, I get b0, plus b1 times x1 minus x0, plus b2 times x1 minus x0, times x1 minus x1. Now, this turns out to be 0, so I can forget about the third term totally. Now, this b0 is nothing but the value of the function at x0, which I just found out from the previous equation. So from here, if I want to find b1, b1 would be nothing but f of x1, which is right here, subtract f of x0 by taking it to the left-hand side, and then divide both sides by x1 minus x0. So this is what I get for the value of b1, and again, you've got to understand this b1 which I am obtaining here is the same, exactly the same expression which I have for the linear interpolation. So what you are finding out is as you are going from linear interpolation to quadratic interpolation, from linear interpolation to quadratic interpolation, as is in this case here, is that you don't have to re-find what the coefficients are. So here you're getting f of, again, this can be written as the divided difference of x0, comma, x1. So again, what you are finding out is that we are getting this, which I'm writing here, is the zeroth divided difference . . . sorry, the first divided difference definition here, and this will be the zeroth divided difference here, so this is a rewriting of these coefficients of b0 and b1. Now, the new coefficient which I . . . which I will find by using the quadratic interpolation, will be b2, because that's not something which we found out when we were doing linear interpolation. So how do I go about doing that? I go about doing that by the same thing, by knowing that the function at x2 will be same as the value of the interpolant at x2, because the function and the interpolant have to go through those points at those given points. So in this case it'll be b0, plus b1 times x1 minus . . . sorry, x2 minus x0, plus b2 times x2 minus x0, times x2 minus x1. So that's what I'm going to get by substituting that, but as you can very well see that b0 I already found as is the value of the function at x0, b1 is nothing but the value of the function at x1 minus x0, divided by x1 minus x0, so you already have two unknowns in that particular equation, b0 and b1 being found previously, so the only unknown is b2. So what that means is that b2, if you conduct the manipulation, this is what you're going to get, so after . . . you're going to get f of x2 minus f of x1, divided by x2 minus x1, minus f of x1 minus f of x0, divided by x1 minus x0, divided by x2 minus x0. So this involves a little bit of algebra, but I think if you continue the process, you will be able to see that it does turn out to be of this particular form. Now, the reason why we write it in this particular form is again because this b2 is now standing for the second divided difference, because now you have the subtraction of the two first divided differences and divided by the difference between the end points here, x2 and x0, so somehow this is an approximation of the second derivative of the function. And people rewrite it as f of x2, comma, x1, comma, x0 like this, which basically stands for that this is the second divided difference function here. And if you want to rewrite it, what that means is that simply as f of x2, comma, x1, minus divided difference, the first divided difference between these points, so it becomes the divided difference between these points, it becomes, sorry, it becomes equal to the first divided difference between these two points, minus the first divided difference between these two points, divided by the difference between the extreme points, which are x2 minus x0 here. So that is how we keep on finding out what these divided differences are, but this is just a different way of rewriting our value of b2. So eventually what that means is that the second-order polynomial which we have just found out is of the form f2 of x is equal to b0, plus b1 times x minus x0, plus b2 times x minus x0, times x minus x1. And of course, it is b0 is nothing but the first divided difference . . . or zeroth divided difference at x0, so that is just the function at x0, b1 is the first divided difference between x1 and x0, and b2 is the divided difference between x2, x1, and x0. Again, keep in mind that if you totally reverse x0 and x1, the divided difference stays the same, if you move x0 here, if you just reverse it completely, like x0, x1, x2, the divided difference will stay the same. So in some books, or even while I was writing this, I might have switched these over or switched these over, it gives you the same number. You cannot switch this and this, but if it's totally in the reverse order, you will find out that the divided difference will stay the same. And in the next segment, we'll take an example, but this is the end of this segment. |