Practice English Speaking&Listening with: General Order: Newton's Divided Difference Polynomial: Theory: Part 1 of 2

Normal
(0)
Difficulty: 0

.

.

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.

.

The Description of General Order: Newton's Divided Difference Polynomial: Theory: Part 1 of 2