CHAPTER 05.03: NEWTON DIVIDED DIFFERENCE METHOD: General Order: Newton's Divided Difference Polynomial: Theory: Part 1 of 2

In this segment, we're going to talk about the Newton's divided difference polynomial method of interpolation, and we're going to talk about the general order.  In the previous segments, we have talked about linear interpolation done by Newton's divided difference polynomial.  We also talked about Newton's divided difference polynomial interpolation being done by a quadratic polynomial. So in this case, we want to be able to figure out how to do a general order Newton's divided difference polynomial interpolation.  If you remember, then we had, let's suppose, again, chosen x0, y0, x1, y1, x2, y2, so we have three data points, and we said that we will be able to conduct Newton's divided difference polynomial interpolation, and be able to find a second-order derivative by using NDDP, and it turns out to be that the form which we assumed for the second-order polynomial is of this type. And it so happens that b0 turns out to be the zeroth divided difference of the value of the function at x0.  So this is sometimes called the bracketed function, or you can look at it as that, hey, this is the zeroth divided difference.  b1 turned out to be the first divided difference of the values of the function at x1 and x0. And this was nothing but the value of the function at x1 minus the value of the function at x0, divided by x1 minus x0, and that's what we proved last time.  And then we have b2, which is the, now the second divided difference of the values of the function at these points, and again, it's called a bracketed function of those three points, points x2, x1, and x0, and again, we found out that this is nothing but the bracketed function of x2 and x1, or the first divided difference of the values of the function at those points, and then x1 and x0, divided by x2 minus x0, which are the extreme two data points right there, and then, I should say the two endpoints, I should say, because these necessarily do not need to be in any kind of ascending or descending order, but again, then we can look at this one, the first divided difference as 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 that's what we obtained for b0, b1, and b2.  So what you are finding out, there is some kind of a trend going on in terms of the second-order polynomial that the first unknown is the zeroth divided difference of that point, then b1, which is the second unknown, is the first divided difference at those two points, and then b2 is the second divided difference at those three data points.  So you can very well see that what the general order polynomial would look like.  So this is what we're going to do, so we're going to write down the Newton's divided difference polynomial interpolant for a general order polynomial.  So basically what we are . . . the way we're going to state the problem is that given n plus 1 data points, so we are given n plus 1 data points, so we're given x0, y0, x1, y1, all the way up to xn, yn, and what we want to do is we want to find the nth-order Newton's divided difference polynomial. So we want to find the nth-order Newton's divided difference polynomial. So how do we go about writing this up?  Again, we are going to say that fn x, which is simply saying that is the nth-order polynomial, because we are given n plus 1 data points.  So of course, you've got to understand that each of these x0, x1, x2, all the way up to xn are distinct data points. Also the fact that x0, x1, all the way up to xn do not need to . . . do not need to be in any kind of ascending or descending order, and we can write down the nth-order Newton's divided difference polynomial in this particular form, we'll have b0, plus b1 times x minus x0, just like we had for the first-order Newton's divided difference polynomial, plus b2 times x minus x0, times x minus x1, just like we had it for the second-order Newton's divided difference polynomial, and we'll go all the way up to bn, where it'll be x minus x0, all the way up to x minus x-sub-n-minus-1.  So that's how the nth-order Newton's divided difference polynomial is going to look like.  And again, these values for these unknowns now, b0, b1, b2, all the way to bn, will be given as the divided differences, or the bracketed functions.  So b0 will be the same thing as you obtained for your first-order or second-order Newton's divided difference polynomial, b1 will be, again, the first divided difference, which will look like this, b2 will be same as x2, comma, x1, comma, x0, so it'll be the second divided difference which looks like that. So you can very well see that the last, let's suppose you'll have several, all of these unknown coefficients, b0, b1, all the way up to bn, they'll be defined in these terms of divided difference, so we'll get f of, this will be at xn-minus-1, this will be at xn-minus-2, all the way up to x0.  And same thing, the last unknown coefficient in the Newton's divided difference polynomial will be of this particular form, it will be in terms of the last data point all they way up to the first data point which you have. So basically what we have to do is we have to calculate these divided differences, all the way from the zeroth, first, second, n-minus-1th, and nth divided difference, based on the bracketed function which we talked about, and we should be able to find out what these constants of this Newton's divided difference polynomial method are.  So in a general basis, if we want to define what is bm, where m is going from anywhere from m to n, it is defined as follows, it is defined as f of xm, all the way up to x0, and we've defined as f times xm all the way up to x1, so we are just taking one point less, that divided difference, minus starting from the next point, which will be x-sub-m-minus-1, all the way up to the last data point, divided by xm minus x0. So maybe I should simply talk about this as 1, from 1 to n.  That's how each of these divided differences will be developed. So what you are finding out that here you have m plus 1 points in the divided difference, and here you have m points in the divided difference, because you start from xm, go all the way only up to x1, so far as calculating this divided difference is concerned, then minus f at x-sub-m-minus-1, which is the next point after that, going all the way up to x0, so you only have m points of x in here, so you're going from m plus 1 to m, and so you can very well see that how you can continue to do this until you find out it in terms of the values of the function itself, divided by the data points at the end, which is xm minus x0. So that's how this is going to work out to be able to find out what the coefficients of the Newton's divided difference polynomial method are.