CHAPTER 05.03: NEWTON DIVIDED DIFFERENCE METHOD: General Order: Newton's Divided Difference Polynomial: Theory: Part 2 of 2
Let's go ahead and see that how this would work out for a third-order polynomial. So let's suppose we have chosen x0, y0, x1, y1, x2, y2, and x3, y3. So somebody gives us . . . we choose four data points, and we want to . . . we want to see that how the third-order, find the third-order Newton’s divided difference polynomial. So if somebody asks us that, hey, okay, I've chosen four data points, can you find out the third-order Newton's divided difference polynomial. How would I go about doing that? And I'm going to show this to you as a tree of divided differences, because that's the way we're going to show the example in the next segment. So let's go ahead and look at this on the next board here. We have x0 here, we have x1 here, we have x2 here, and we have x3 here. So we are given the value of the function at three data points, and those values are given to us as f of x0, f of x1, f of x2, and f of x3, which means . . . which means the same thing as . . . this is same thing as y0, this is same thing as y1, this is same thing as y2, and this is same thing as y3, there's no difference between the two things. We write it in terms of the f function because that's the way it is written in most books, so in order to keep it simple, we just write it in terms of that y is a function of x, and it's given to you at these four data points. Now, the tree which I was talking to you about is that what's going to happen is that we already know that this is going to be the value of the function . . . value of the function at b0. So we already know that it's going to be the value of the function at b0, but what's going to happen is that these two numbers here will give you the bracketed function of x0, comma, x1, and that is nothing but . . . let me write x1, comma, x0, although there's no difference between the two, but just to follow convention, and to keep things simple and uncomplicated, this will be the bracket function, the first divided difference between the values of the function at x1 and x0, and that is b1. So somebody might say, hey, okay, I can find b2 by going down the tree, but you need another first divided difference here, so that's why you have to calculate all of these. You're going to calculate the divided difference between x2 and x1, then you're going to calculate the divided difference between x3 and x2. So you're going to calculate the first divided differences of all of these, all of these types, although you know that this is the only one which you're going to use for b1. That doesn't mean that the other ones which you are calculating are for no good reason. The reason why that is so is because when you're going to do this, you're going to get the divided difference now for x2, x1, and x0, and that is nothing but b2. Again, you're going to calculate the divided difference between these two data points, which will be nothing but f of x3, x2, and x1, and the reason why you are calculating this is because you'll have to go between these two and calculate the divided difference of x3, x2, x1, and x0, and this is nothing but b3. So that's how it's going to work out when I'm going to show you the example for a third-order polynomial. And also, the reason why I'm showing it to you like this is because that's how you will be writing this program algorithmically if you were going to write a subroutine or a function for it in any language you may desire, because you have to write down the function like this, and then you have to calculate all the first divided difference which are shown here, then the second divided difference which are shown here, and the third divided difference shown here, and then you will choose this to be b0, this to be b1, this to be b2, and this to be b3, in order to be able to having calculated all those coefficients. And this is the end of this segment. |