Tip:
Highlight text to annotate it
X
In our last lecture we have derived the expression for the error of interpolation in Lagrange
interpolation. Let us just revise what we have done last time.
we have derived the error of interpolation, now we denoted this as En, n to denote the
order of the polynomial that we are taking, this we have defined it as f(x) minus P(x)
and we have derived that this expression is w(x) divided by x minus, w(x) by factorial
n plus 1 f(n+1) zhi, where w(x) is the product of all the factors in the given problem (x
minus x0) (x minus x1) so on (x minus xn). We can also find the bound for the error of
interpolation, so I can just take the magnitude and maximize the right hand side, therefore
I will have less than or equal to 1 upon n plus 1 the maximum of this I will write it
as Mn+1 and then I will write down the maximum of, in the given interval (a, b) of w(x),
where we have denoted Mn+1 is maximum of the n plus 1th derivative in the interval a to
b of this. Now from here we have derived the expressions for the linear and quadratic interpolations
which we would like to use it in an example.
Let us just write down what is the error in linear interpolation. Now here we are using
only 2 points out in the data that is (x0, f0) and (x1, f1), so these are the 2 points
of the data that we are using, these are any 2 arbitrary adjacent points in the entire
data. Then we have proved that error of the linear polynomial is less than or equal to
h square by 8 M2 and h is the distance between x1 and x0, x is equal to, h is equal to x1
minus x0. Now this formula would be the same whether we have got the data with equispaced
points or data is not equispaced, because we are taking only 2 consecutive data points
therefore the distance is h we are calling it, therefore the formula will hold in both
the cases. Now error in quadratic interpolation, we are now approximating by a polynomial of
degree 2 in other words we are using thereforth 3 arbitrary adjacent points in the entire
data as this. We are using the 3 consecutive data points in the entire data that is given
and using these 3, we are now writing the formula and then writing the error in interpolation
and this we have proved it as less than or equal to 1 upon 6, let us call it as M3 maximum
in the given interval, that is (x0, x2) is the given interval of magnitude of (x minus
x0) (x minus x1) (x minus x2), where M3 is the maximum in the interval x0 to x2, of f
triple dash of x. We have also proved that in the, if the data is equispaced in the quadratic interpolation,
equispaced data then we have proved that error in this case is bounded by h cubed by 9 root
3 M3. Now I would like to use the results that we have derived here to find the error
of interpolation in 2 examples which we have done last time.
Let us just revise one example, let me just show the example we have done last time. We
said construct the linear polynomial which fits this data; predict the value at 1 point
5. So now I want to find out what will be the error of interpolation in this example
and what will be the error at this point. If I want the error at any particular point
I can just substitute, let us suppose you have been given data values between say 1
and 10 and I want the error at a particular point, I can just substitute that value of
x over here, if suppose I wanted 1 point 5, I will substitute x at 1 point 5 over here
and then simply find out what are the right hand side and then write down the bound. If
I want the largest possible value to be written on the right hand side, I will maximize it
and then find out what is the largest value so that I have got required upper bound here.
So let us take this as an example, let us write it as, call it as example 3. In examples
1 and 2, 1 and 2 find the bound on the error, find the bounds on the errors, on the errors.
Now I will first take this example, this example 1 so let us put it as 1. In example 1 we are
talking about the linear interpolating polynomial therefore we have to find out what is the
value of magnitude of E1 is less than or equal to h square by 8 M2, here we have at x0 is
equal to 1, x1 is equal to 2, x0 is 1, x1 is 2, therefore h is equal to x1 minus x0
that is equal to 1. Therefore this is simply equal to 1 upon 8 M2. Now will see later on
how we may be able to get an approximate value for second derivative, we did not know exact
but we will, if the function is given to us we can do it, otherwise we will have some
other alternatives which we will discuss it later on.
So this is the bound on the error 1 by 8 of M2 in this example. Now if I take the other
example that we have done last time, that fit an interpolating polynomial for this data,
we have given 3 data points and then asked us to find, what the error is in this particular
one. So this is 3 points, therefore we have fitted there a quadratic polynomial for this
data. Now for this data I would write down that error, this is less than or equal to,
now notice that the data is not equispaced, we have the points as x0 is 1, x1 is equal
to 2 and x2 is equal to 4 so they are not equispaced, therefore I will have to use the
full formula that we have written, written here and that is 1 by 6 M3 of maximum of (x
minus x0) (x minus x1) (x minus 4). So I will write it again, this is, I want the maximum
of lying between 1 and 4, x0 is 1 x2 is 4, so I need the maximum of this lying in the
interval 1 to 4 of the quantity (x minus 1) (x minus 2) (x minus 4). Now we know this
is a 1 variable problem, therefore if I set this quantity as g(x) then I can just open
it up, multiply it out, this is x square minus 3 x plus 2 and multiply by x minus 4, I will
get here x cubed minus 7 x squared plus 14 x minus 8, I have just multiplied these 3.
Now I want to find the maxima minima of this absolute value, so I will just differentiate
this in 1 variable, g dash of x 3 x squared minus 14 x plus 14 and set it equal to 0.
Now this will give me 2 values for x and any 1 of these values can give us the maximum.
So I will find out the values of x from here that is minus 14 by 196 that is equal to 28
by 2 8. So this gives me 3 point 2 1 5 3 and 1 point 4 5 1 4. These are the 2 values of
x, out of these 2 values 1 of them will be the largest value; the other will be the smaller
value. So let us substitute it, what I will get therefore will be, I need the maximum
of, we need the maximum of, substitute this 3 minus 2 point 1 3 that will give you, let
us write down 1 value, this is 2 point 2 1 5 3 that is x minus 1, x minus 2 1 point 2
1 5 3, x minus 4 that is equal to 0 point 7 8 4 7. That is the (x minus 1) (x minus
2) (x minus 3) (x minus 4) and this is 1 value, the other value, the maximum of 2 values I
am writing, I will substitute this, therefore this will become (x minus 1) so that is 0
point 4 5 1 4, (x minus 2) therefore this will have 5 4 8 6, I am taking (x minus 2)
and then I am taking this with a negative sign, let us put it here and (x minus 4) that
will give you minus 2 point 5 4 8 6. Obviously this is larger of the 2 and this is actually
maximum of, this is equal to 2 point 1 1 2 6 and this is 6 3 1 1, so that the maximum
is 1 1 2 6.
Now remember we do not need to find the second derivate to find out maxima or minima, we
are not really talking of maxima minima of g(x), we are talking of the maximum of the
absolute value. Therefore it would be sufficient for you to just find the first derivative,
find the values of x that will be there, substitute it in the given expression and find the largest
of all of them. It is possible this smaller value here would give you, I mean which it
may be showing that it will be minimum may be giving actually maximum, maximum because
we are talking of absolute, when once you are talking of a large negative value the
absolute will be the positive sign, therefore that may give you this. Therefore it is a
not necessary that we should go for the second derivative and do anything. Now therefore
when once we found out this maximum value, I will put it over here and say that this
is less than or equal to 2 point 1 1 2 6 by 6 into M3. Now I should, I put here M3 yes.
Again I need the approximate value for M3 which we shall see later on how we can determine
them. Now let us take an application of this, so let us call this example 4. So what I would
say here, I would to construct a table of values, a function is given. A table of values
for f(x) is equal to cos x, I am taking a simple example, in (0, pi by 4) with equally
spaced step size is to be constructed, is to be constructed. Find the maximum step size, find the maximum
step size that can be used if the error, if the error in,
We will take 2 problems here; error in linear interpolation is to be less than 5 into 10 to the power
of minus 6. Quadratic interpolation is to be less than 5 into 10 to the power of minus 6. Now what we are really asking
here is that we have a known function, I want to construct a table of values for it, size
at the, I want to, I may use linear interpolation in that, as a second problem we may use a
quadratic interpolation but the error of interpolation should be bounded by this quantity, then find,
tell us what is the largest step size that you can use for constructing this data values.
This is the problem that we are looking at in reveres way as what we have earlier we
have given a data there; we are constructing the polynomial and the error.
Now we want to construct a data using a given function. Now for this let us straight away
write down what is the error in our linear interpolation, error in linear interpolation
is bounded by h square by 8 M2, h square by 8 M2, now M2 is maximum of, we are given the
interval 0 to pi by 4, so the interval 0 to pi by 4 of f double dash of x. Now the function given to us is f(x) is equal
to cos of x. Therefore this is maximum of, in the interval 0 to pi by 4 of magnitude
of cos x. I have differentiated it two times so minus sin x then cos x, we will have simply
magnitude of cos x. Now the largest value occurs at 0, cos 0 is 1, cos pi by 4 1 by
root 2, so it is a, so it is a decreasing function, so you will have the maximum value
as 1. Now I want this error to be less than h square
by 8 into 1 but this error should be bounded by 5 into 10 to the power of minus 6, that
is linear interpolation should be total error, largest possible error should be less than
10 to the power minus 6. Therefore I can write down h square is less than 40 into 10 to the
power of minus 6 or just h is less than root 40 into 10 to the power of minus 3 or this
is equal to 6 point 3 2 4 5 10 to the power of minus 3, so that this is 0 0 6 3 2 4 5.
Therefore I need to choose a step length smaller than point 0 0 6 3 in order that the maximum
error will be less than 5 into 10 to the power of minus 6.
Now let us take the case of quadratic interpolation. In the case of quadratic interpolation we
have error E2 is less than or equal to, now we have been given a simple example here,
we have been asked to do it in equally spaced step size, so the step length is equal. Therefore
we shall use the formula which we have derived h cubed by 9 root 3 M3, where M3 is the maximum
on interval 0 to pi by 4 magnitude of third derivative of x, third derivative with respect
to x of f(x). So this is maximum of 0 to pi by 4, third derivative will be sin x, so we
will write it as sin x. Whereas the maximum of this is 1 upon root 2, sin 0 is 0 it is
an increasing function so will have 1 upon root 2. Therefore I have h cubed upon 9 root
3 into 1 upon root 2 and this should be less than 5 into 10 to the power of minus 6. Which
I can write h cubed is less than, this is 45 root 6 into 10 to the power of minus 6
and h comes out to be, let me take it, h comes out to be 0 point 0 4 7 9 4 7, so cube root
we are taking of this and then we get the value of this one. Therefore I need to use
the step length which is smaller than 0 point 0 4 7 9 4 7. Now you can see that the quadratic
interpolation has improved tremendously over linear interpolation because when we have
used the linear interpolation we were requiring that the step length should be smaller than
0 0 6 6 3, whereas we are saying here it is sufficient to have a step length smaller than
0 point 0 4 8 which is approximately 8 times the step length that we can use in linear
interpolation than in this 1, so if you are going from 0 to pi by 4 actually the number
of points that you would come you can easily get it, that will be total length that is
pi by 4 minus 0 divided by h that will give you the total number of points. If you are
saying the number of points in the data table, it will be pi by 4 minus 0 divided by this,
whereas in this case pi by 4 minus 0 divided by 0 4 7, therefore the number of points that
you require in the table which will much less in the quadratic interpolation than linear
interpolation.
Now we have derived the Lagrange interpolation and shown its application over here and it
is the, among the all the interpolating polynomial Lagrange is the fundamental of all the results.
However computationally it is not very efficient. Why it is not computationally efficient is,
there are 2 reasons of this, 1 reason we can let us say the, let us call it as disadvantage,
let us call it as disadvantage of Lagrange interpolation. For obtaining the Lagrange
interpolating polynomial we need to find all the li(x) and that is the expression w(x)
upon (x minus xi) into w dash (xi). The data that is given let us suppose 100 data points
is given, if all the 100 data points are lying on a straight line it is representing polynomial
of degree 1 but all these li(x) are polynomials of degree 99, therefore I need to compute
each one of them, then combine them, collect all the terms and then cancel of all the ones
and in this example of 100 data points, you will cancel x to the power of 99, x to the
power of 98 everything, so you need to collect all these coefficients and then simplify it
which is an extremely tedious computation, therefore one disadvantage is the tedious
computations.
The second disadvantage is that, if I have a data given to me and if I add one more data
item to this, the form of li(x) is going to change completely because it adds one more
term. Therefore all li(x) have to recomputed if we are adding one or more data items, that
means again it is a, it is not a format in which one can use it easily, therefore the
li(x) are to be computed, are again to be computed, if an additional point or we can,
let us say one more point is added to the data.
Now would like to construct a interpolating polynomial which is simple, which will take
care of both of them, that is one is, it will not have that much tedious computation and
secondly if we add one more data item, we do not have to change anything expect you
add one more term to the given interpolating polynomial. To do that let us define what
is known as divided differences.
So I would like to define what is known as divided differences. Now what we have here
is the data, let us write x f(x), x0 f0, x1 f1, x2 f2, xn fn, so this is our data that
is given to us. Then I would like to define what is known as the first divided difference,
first divided difference, that I would have a notation, in square brackets I will put
the 2 data points I am using, the abscissa of the data points that I am using [x0, x1].
This is the f at 1 minus f at 0 divided by x1 minus x0 that is the distance of the ordinates
divided by the distance of the abscissa that is why it is called divided difference, we
are taking the difference of the ordinates divide it by the distance between the abscissa,
so this is f1 minus f0 by x minus x0. Similarly I can define, this is a general point so if
I take this as [xi, xi+1], this will be simply fi+1 minus fi by xi+1 minus xi. We are still
talking of the data which is random, in which it is not equally spaced, it is randomly spaced.
Therefore this I can take i is equal to 0, 1, so on n. Now I would define the second
divided difference, now before you write this one just leave some space, let us write the
table of divided differences; let us call it as divided difference table.
So let us write down divided difference table, just leave some space we will fill up for
the second divided difference and so on but let us just see what we have done, how it
goes. So let us put these data points vertically like this x1 f1, x2 f2, x3 f3, xn fn. Now
I will put here first divided difference, I will call it as first divided difference.
I am using these 2 values, these 2 data points and construct my first divided difference
as f1 minus f0 by x1 minus x0, so I would write here f1 minus f0 divided by x1 minus
x0 that will be equal to f (x0, x1). Now by the same argument I will use this and construct
my first divided difference with respected to x1 and x2, these are the 2 abscissa points
that I am using x1 and x2. Now I will use these 2 and get f(x2, x3), now the abscissa
for these 2 is x2 and x3, so this will be f3 minus f2 divided by the distance between
the abscissas. So here I will have f of xn-1, xn I will have. Therefore the first column
of this table will be all the first divided differences for the entire table. Okay now
let us go back to what we wanted, the second divided difference. Now the second divided
difference would be based on the values that we have computed already to construct a second
column which we shall call as the second divided difference.
So what I would define here is the second divided difference will be f [x0, x1, x2],
so I need to take 1 more abscissa point and that will be the next lower order divided
difference leaving the first argument, I will leave the first argument minus then I leave
the last argument f [x0, x1], then the distance between the abscissa x2 minus x0, x2 minus
x0.
Therefore if I generalize this now, I would have this as f [xi-2, xi-1, xi], these are
the 3 consecutive abscissa and that will be the, I leave the first argument, I will have
the divided difference with respect to these 2 abscissa, then I leave this last one, I
would have f [xi-2, xi-1] divided by xi minus xi-2. So I would go from i is equal to 2,
3 so on n, i is n minus 2, n minus 1, n and this will be the second divided difference.
Now therefore I can use this one and now construct my table of second divided difference, so
I would now make this as second divided difference. Now the second divided difference table, we
can see the identically as we have formed first divided difference is going to come,
so I need to take this divided difference minus this divided by the distance now, distance
is now increasing x2 minus x0. So this will be f of, I can now write like this and then
write this here f [x0, x1, x2], so I am using the three abscissa x0 x1 x2, f this minus
this divide by x2 minus x0.
Now if I use these two then this will be x1 x2 x3 therefore this will be second divide
difference with x1 x2 x3 and so on, I would get here f [xn-2 xn-1 xn]. Now the second
column is complete and these are all the second divided difference and then we can proceed
on like this and then write down all the differences, the nth divided difference, there are only
n plus 1 values here, therefore we can proceed upto nth divided difference and the last one
will be the nth divided difference and that will be f [x0 x1 x2 xn]. We will have only
nth divided difference as I said because they are only n plus 1 values over here. Now let
us just have, again let us just go back to the slide and then see every divided difference,
first, second or any, everyone can be written in terms of the ordinates f0 f1. I can open
it up, simplify and then collect all the terms and then write down explicitly as a linear
combination of f0 f1 f2 and if I do that let us just have a look at one of them and then
generalize it from there. For example if I take f[x0, x1], this is equal
to, I will take f0 first, f0 divided by (x0 minus x1), I will absorb the minus sign, so
that I will write this as (x0 minus x1) plus f1 upon (x1 minus x0). Now if do this for
the next divided deference and then collect all the terms, I would get f [x0, x1, x2]
is equal to f0 divided by (x0 minus x1) (x0 minus x2) plus f1 (x1 minus x0) (x1 minus
x2) plus f2 (x2 minus x0) (x2 minus x1). The denominator is a product of all the factors
with the first term being whatever the abscissa belongs to the numerator f x x0, therefore
all the differences using x0 (x0 minus x1) (x0 minus x2), f at x1 so the denominator
will be (x1 minus x0) (x1 minus x2), this is f at x2 therefore the denominator will
be (x2 minus x0) (x2 minus x1), therefore I will have f [x0 x1 xn] is equal to summation
of n is 0 to n, f of xi divided by all the products, j is equal to n except of course,
it cannot be equal to j, (xi minus xj). As I said the numerator is f at xi, the denominator
will be all the products with the first term with the xi and all the remaining abscissa
that are to be used except of course i not equal to j. So this is the general expression
for any divided difference to be written in terms of the ordinates. Now let us take a
simple example for this because that will be the base for our constructing the interpolating
polynomial.
Okay, I will just write it again. Construct the divided difference table, construct the
divided difference table for the data x f(x) minus 2, 15, minus 1, 1, 0, 1, 2, 19, 5, 631.
So let us put this in the vertical format so that I can write down all the differences
minus 2, 15, minus 1, 1, 0, 1, 2, 19, 5, 631. Now this, let us take these 2, this is 1 minus
15, 1 minus 15 divided by minus 1 plus 2, minus 1 plus 2 this is your x1 minus x0, so
this will give us minus 14. Now let us take these two, the numerator is 0, therefore let
us keep it as 0, 1 minus 1 is 0. This gives 19 minus 1 divided by 2 minus 0, 2 minus 0
that is 18 by 2 that is equal to 9. Then 631 minus 19 divided by 5 minus 2, 5 minus 2 that
is equal to 6 and 12 that is equal to 2 0 4, 2 0 4. So the first column is complete.
Now let us take the second divided difference. So if take these two I will have 0 plus 14,
now we have moved x0 x1 x2, therefore 0 plus 2; 0 plus 2 that is equal to 7. Then I take
these two, 9 minus 0 divided by, now I have to choose the x1 x2 x3, that is 2 minus minus
plus 1 that is equal to 3. Then I use this 2 0 4 minus 9, 5 minus 0 that is 39, 39. Then
we go to the third divided difference, will have this as 3 minus 7, now we have moved
x0 x1 x2 x3, so this will be 2 plus 2, that will be 2 plus 2 that gives you minus 1. Then
I moving to x1 to x5 this 5, therefore this will be 39 minus 3, 5 minus 1 that is 5 plus
1, 5 plus 1, 36 by 6 that is equal to 6 and here the fourth divided difference is 6 plus
1 divided by the distance 5 plus 2 that is equal to 1.
Now interestingly if the data was not a polynomial, full degree polynomial that means this is
a, 5 points are there it will be a polynomial of degree 4, if you want to construct the
Lagrange interpolation. If it is not a polynomial of degree 4 but it is less say 3 or 2 or 1,
so if all the points lying on the straight line, automatically the difference is, higher
order difference will become 0, the higher order difference is automatically would become
0 implying that they are not lying on the full polynomial but the polynomial of degree
less than that one. We will see how we are going to express that one, this will the,
this table itself would automatically tell us whether we are having a full degree polynomial
or we are not having a full degree polynomial.
Based on this let us construct the new interpolation polynomial which we shall call it as Newton's
divided difference interpolating polynomial. Now we write the polynomial as, when we have
written the Lagrange interpolation we have taken linear combination of f's and then we
have written it as the Lagrange polynomial, here we will not do that. What we do is, will
write in a altogether different form Pn(x), I will this as some a0, (x minus x0) into
a1, (x minus x0) (x minus x1) a2, so on (x minus x0) (x minus x1) (x minus xn-1) an.
There are various ways of writing a polynomial, for example you are writing a quadratic, you
can write down a plus b x plus c x square or you can also write it as a constant into
x minus alpha into x minus beta, you can also write it in a form like a constant plus (x
minus x0) a1 plus this. Now if you look, this is a constant this is linear, this is quadratic
and this finally is of the degree n, there are n terms, this is of degree n, this is
a polynomial of degree n, this is a polynomial of degree n. There are various ways of writing the polynomial
therefore we have chosen a way of writing a given polynomial. Now if this is the polynomial,
it should fit the data, it should fit the data. What is the data? Data is Pn at xi must
be equal to f at xi, that is our data that is given to us as (xi, fi) is given to us.
So if I substitute xi in this, I should get by xi. Let us do that, let us put x0 here,
Pn of x0 should be equal to f at x0. When I put x0, all the terms vanish except a0,
so this is a0, a0 is simply f at x0. Now let us Pn at x1 that is equal to f at x1 a0 plus
(x1 minus x0) into a1. Now the second term onwards all of them contain x1, (x minus x1)
is here, (x minus x1), all the terms contains (x1 minus x1). Therefore all of them would
vanish except these two terms. Now a0 is already determined, a0 is equal to f at x0 plus (x
minus x0) into a1.
Now let us bring f(x0) to this side and solve for a1. Therefore a1 is equal to, I will write
now this as f1 minus f0 by x1 minus x0, which turns out to be the first divided difference
this is equal to f[x0, x1]. Now I repeat, continue it like this, I now substitute x2
in this polynomial. If I substitute x2 then I will get a0, (x2 minus x0) a1 plus (x2 minus
x0) (x2 minus x1) into a2, all the remaining terms contain (x2 minus x2), so all of them
would vanish except these three terms of which we have already computed a0, a1 is also computed.
This is equal to, therefore left hand side is f of x2, right hand side is f0, (x2 minus
x0), a1 is (f1 minus f0 by x1 minus x0) and this is the second term a2. Therefore I can
find out a2 from here, bring everything to the left hand side, therefore a2 is 1 upon
(x2 minus x0) (x2 minus x1) that is the denominator over here, this is f2, this is minus f0 minus
(x2 minus x0) into (f1 minus f0 by x1 minus x0). Now I collect the coefficients of f0
f1 f2, f2 is alone here, so the denominator f2 is this, f1 has got only 1 term, so f1
is also there, only f0 is to be added. Let us put it reverse way, let us start with f2,
f2 is (x2 minus x0) (x2 minus x1). Let us take f1 this is (x2 minus x0) (x2 minus x0)
they cancel off. There is a minus sign here; let us observe the minus sign here into this
that is plus x1 minus x2, so I will have here f1, this is (x1 minus x0) which stays as it
is and this term is (x1 minus x2). I collect the third coefficient f0 and I would give
the result for this, this will be simply (x0 minus x1) (x0 minus x2) and this turns out
by definition our second divided difference, this is f [x0, x1, x2].
Now I can use induction procedure and then show that by induction an is f [x0 x1 so on xn]. Therefore we have completed
the derivation of the polynomial, therefore our polynomial is Pn(x) is f(x0) plus (x minus
x0) f[x0, x1], we are coming from the top of the table, this x0 x1 x2 is from the top
of the table (x minus x0) (x minus x1) f of x0 x1 x2 plus so on. We have a polynomial
of degree n here, therefore this is (x minus xn-1) f [x0, x1, xn]. This is called the Newton's
divided difference interpolation polynomial; this is the Newton's divided difference interpolating polynomial. We shall take up
the application of this in the next lecture.