CHAPTER 05.03: NEWTON DIVIDED DIFFERENCE METHOD: Newton's Divided Difference Polynomial: Linear Interpolation: Theory  

In this segment, we will talk about Newton's divided difference polynomial method to do interpolation. So we'll go ahead and get started with linear interpolation to see that how Newton's divided difference polynomial interpolation is done when we have linear interpolation.  So the way we're going to present the problem is that chosen x0, y0, x1, y1, find the linear Newton's divided difference polynomial.  So we're going to use a contraction here . . . or an abbreviation here, NDDP here. So let's go ahead and see that how linear interpolation is done by using Newton's divided difference polynomial.  Now, some people might say, hey, what does this mean, chosen? The reason why we're talking about chosen is because we may be given a lot of points, but when we are doing linear interpolation, we only choose two points, and we'll leave it, so far as how we choose those two points once somebody gives us, let's suppose, a hundred data points. we'll leave that up to an example and show you that how we're going to choose those points. Again, we are given these points, so basically what we are given is y as a function of x, but we are given y at only two points, that is at x0 and x1, so it's a discrete function.  So many times you'll find out that we'll be using like y0 and f of x0 interchangeably, they mean the same thing. Same thing with y1 we'll use interchangeably with f of x1, because basically the problem is that you are given your function of x, y as a function of x, and that function is given at, let's suppose, a certain number of data points.  So these are interchangeable when we talk about Newton's divided difference polynomial or any other polynomial interpolation.  So let's go ahead and see that how this method works is that if you look at . . . if you go back and look at direct method, you would have chosen the linear interpolant to be y is equal to a0, plus a1 x, that is the interpolant which you would have chosen.  So in that case, what happens is that you have a0 and a1, these are the two coefficients of the linear interpolant which you have to find, and you will set up two equations, two unknowns by basically saying that, hey, this particular value of . . . at x equal to x0, the value is y0 . . . so let me just go ahead and write it down, you will have done this, and you have y1 equal to a0, plus a1 times x1. So that's what you have done, you have set up two equations, two unknowns, solved for a0 and a1, and there is your linear interpolant.  But in the Newton's divided difference polynomial method, it's . . . we're still using a first-order polynomial, but it is used in a different form, and the form looks like this, we have f1 of x, this f1 stands for the first-order polynomial, is given by the form like this.  So we are choosing the form to be still a linear interpolant, but the form is chosen to be b0, plus b1 times x minus x0, you still have the two unknowns, b0 and b1, and the reason why I showed you the direct method right here is so that you can develop an appreciation for why Newton's divided difference polynomial, although it's going to give us the same polynomial as the direct method or any other method, why does it become attractive?  And you will see that in a little bit. So let's go ahead and see that how we're going to find b0 and b1.  So we know that the value of the function . . . of the function, so we know that the value of the function at x0 is same as the value of the function at x0, which is same as y0, will be equal to b0, plus b1 times x0 minus x0. So all I'm doing is substituting the value of x equal to x0 in there, and I'm saying that, hey, I know that the value of the function at x0, which is the function f of x0, or y0 you may call it.  So I know that, so I get f of x0 is equal to just b0, because this is going to become 0.  Same thing, I know that this first-order polynomial which I have at x1 will be equal to the value of the function at x1, which is given to me, which is the same as the value of y1, will be equal to b0, plus b1 times x1 minus x0, and then since I know . . . so this is f of x1, since I know that b0 is f of x0, I'm going to just substitute, because I just found out what the value of b0 is, I'm going to substitute it back in here, plus b1 times x1 minus x0, and this gives me b1 is equal to the value of the function at x1 minus the value of the function at x0, divided by x1 minus x0.  So what you are finding out is that I'm able to find the value of b1 also, by simply subtracting the values of the function at the two points which are given to me, divided by the difference between the two x values which are given to me.  So what you are finding out which is different from what we have in the direct method is that the values of the unknowns coefficients b0 and b1, which you are finding them here, are found without having to solve equations . . . two simultaneous linear equations.  We're still solving two equations, but they don't have to be solved simultaneously. So that's the beauty of Newton's divided difference polynomial method, that the coefficients of the polynomial are obtained by just solving one equations at a time, so, as opposed to direct method, where you would have to solve two simultaneous linear equations, hence use some numerical method such as Gauss elimination or LU decomposition to find out what the unknown coefficients of the polynomial are.  So based on this, what we have is that our first-order polynomial which we have used to approximate our function from x1 . . . x0 to x1 is given by this, where b0 is nothing but the value of the function at x0, and b1 is nothing but the value of the function . . . is the slope between x1 and x0, a straight-line slope between those two points, and is given by that.  So what you are finding out is that it is simply given by the value of the function at the first point, and the value of the slope between . . . the first derivate slop between x0 and x1. This one is written as f of x0, so this is called the zeroth divided difference, and I can write this a f of x1, comma, x0, so this is called the first divided difference.  And that's why it's called the divided difference method, because you are using divided difference approximations for the slope and for the function itself.  This will be called the zeroth divided difference. Now, this may not make too much sense right now, but once we talk about second-order interpolation, and general order interpolation you will see what the significance of rewriting these unknown coefficients in this particular form is. So this basically, the definition of the first divided difference is just exactly this, the definition of the zeroth divided difference is exactly this, so there's nothing more to explain there, but it's just a rewriting of our coefficients of b0 and b1.  And in the next segment, we'll take an example, but this is the end of this segment.