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