.
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.
.