Tip:
Highlight text to annotate it
X
So, before we start new topic of numerical integration we are going to solve some problems.
I will be giving you solutions but may be you can find some alternate solutions which
may be a better look at the problem that in the interval a, b we have got n plus 1 distinct
points look at the lagrange polynomial which is based on this n plus 1 points.
So, the lagrange polynomial has the property that a li at xj is equal to 1i if i is equal
to j and 0 if i not equal to j we want to show that summation i goes from 0 to n ,li
of x is equal to 1. Since the lagrange polynomial, they are not defined recursively induction
may not be a good idea. In order to prove this we are going to use
the property that if the function f is a polynomial of degree m which is less than or equal to
n then when we try to fit a polynomial of degree n or bigger than or equal to n then
the interpolating polynomial is going to be function itself here the interpolating polynomial
we know that it is given by pn of x is equal to summation f of x i li of x , i goes from
0 to n. We are interested in showing the summation
i goes from 0 to nli of x is equal to 1. So, the coefficients of li of x should be equal
to 1. So, the simplest choice is look at f of x is equal to 1.
For f of x is equal to 1it is a constant polynomial. So, when you look at pn to be a polynomial
of degree less than or equal to n which interpolates the constant function then that is going to
be the function itself. So, that is the idea. So, choose f x is equal to 1 for x belonging
to a, b and pn be the interpolating polynomial of degree less than or equal to n such that
pn xj is equal to f of xj pn x general form is summation i goes from 0 to n, f of xi li
of x. Pn of x is going to be equal to 1 function
is f of x is equal to 1. So, f of xi will be equal to 1 and hence we get summation i
goes from 0 to n ,li of x is equal to 1.
If instead of f of x is equal to 1, we look at f of x is equal to x in that case for n
bigger than or equal to 1, pn will be equal to function itself and that gives us a relation
summation xi li of x i goes from 0 to n is going to be equal to x in a similar fashion
for n bigger than or equal to 2 summation xi square li of x ,i goes from 0 to n will
be x square and so on. Now, look at the second problem. So, we are looking at f of x is equal
to 1 by xx in the interval 1 to 2 then we want to prove this expression that the divided
difference f of x0 x1 xn is given by minus 1 raise to n divided by x0 x1 xn .
In this problem the induction is going to work we will be using the recurrence formula
for the divided differences. So, for n is equal to 01 quickly sees that the result is
true. Assume the result to be true for n is equal to m minus 1 and then using the recurrence
formula for the divided differences one proves the result to be for n is equal to m you are
to look at the recurrence relation f of x0 x1 n to be given by the divided difference
based on x1 x2 xn minus divided difference based on x0 xn minus 1 and then whole thing
divided by xn minus x0 . We are assuming that x0 x1 xn these are all
distinct points when you put n is equal to 0 on the left hand side you have got f of
x0 and on the right hand side you have got 1 up on x0 and hence the result is true for
n is equal to 0 now assume the result for n is equal to m minus 1 consider divided difference
f based on x0 x1 xn we have got this recurrence relation we are assuming the result to be
true for n is equal to m minus 1. And hence we will have f of x1 x2 xm to be
minus 1 raise to m minus one divided by 1 up on or multiplied by 1 up on x1 x2 xm f
of x0 x1 xm minus 1 will be 1 up on x 0 x n minus 1 and then divided by xm minus x0
now when you simplify then you are going to get in the numerator x0 minus xm in the denominator
you have xm minus x0 and then multiplied by x0 x1 xm .
So, that adds one more minus one and then we have got minus 1 raise to m1 up on x0 x1
xm. So, for some functions we can have the divided difference to be given explicitly.
Our next problem is you are given a polynomial of degree 4 and you are to find 2 divided
differences one is based on 5 points and another is based on 6 points. So, what one can do
is construct the divided difference table you are given the function. So, construct
the divided difference table and then find the divided differences.
But here one can observe that f is a polynomial of degree 4 we are looking at divided difference
based on 5 points our definition of divided difference is look at the interpolating polynomial
which interpolates these 5 points and look at the coefficient of x raise to 4 in that
polynomial. Our function is a polynomial of degree 4.
So, interpolating polynomial of degree 4 is going to be the function itself.
And hence coefficient of x raise to n x raise to 4 in our function that will be the divided
difference based on 5 points if we look at the 6 points then we have to look at polynomial
of degree 5 which interpolates the given function at those 6 points the function is a polynomial
of degree 4 so a polynomial of degree less than or equal to 5 that is going to be the
function itself. So, treat our function which is a polynomial
of degree 4 as a polynomial of degree 5; that means, you add plus 0 into x raise to 5 and
now we have to look at the coefficient of x raise to 5 which is going to be 0.
Now, the same result one can obtain by using the fact that our function f is sufficiently
differentiable then when you look at the divided difference based on 5 points it is equal to
f 4 of c divided by c factorial divided by it should be 4 factorial not c factorial then
the function is a polynomial of degree 4 and hence when you take the fourth derivative
it is going to be constant and that will be nothing, but 279 when you look at the fifth
derivative that is going to be 0 and hence the divided difference is equal to 0.
So, you can either use the definition or you can use the formula in terms of the derivative
if you try to write down the divided difference you are going to get the same result but the
computations they are going to be missing.
So, far we had obtained upper bounds now let us look at anexample where f of x is equal
to ln x and look at a cubic polynomial of degree less than or equal to 3 interpolating
at 4 points and we want to find a lower bound. So, we have got f of x minus pn of x is equal
to f of x0 x1 xn x and then multiplied by x minus x0 x minus xn. So, this we denote
by w of x. We are looking at f of x minus p3 of x. So,
that will be f of x0 x1 x2 x3 x multiplied by w of x and this will be f4 of cx divided
by 4 factorial w of x our function is f of x is equal to ln of x, x belonging to 1 by
2. So, we will calculate the fourth derivative of this ln x and now because we want to be
consider the lower bound for the derivative f4 cx we will look at the least value and
for the w of x we are going to x0 x1 x2 x3 these are given to us we are going to substitute
x to be equal to 3 by 2 and then we are going to get a lower bound throughout.
So, far we had always considered upper bound. So, I wanted to show that one can also consider
a lower bound. So, that tells us that there is going to be at least this much of error
now the computations are straight forward.
Look at f of x minus p3 of x. So, that is f4 of x cx divided by 4 factorial into w of
x then you can verify that the fourth derivative at x will be given by minus 6 by x raise to
4 and we have to look the least value of this. So, the least value will be obtained when
x is equal to 2 so the least value for f4( x) is going to be 6 up on 2 raise to 4. So,
that is going to be 6 up on 16 and then you calculate the value of w of 3 by 2 and that
gives you the lower bound for x is equal to 3 by 2. So, we have modulus of f of 3 by 2
minus p3 of 3 by 2 is going to be bigger than or equal 1 up on 384. So, it is a lower bound.
Then now consider we are again going to consider interpolating polynomial but now our polynomial
is going to interpolate the function and a derivative values. So, suppose our function
has a double 0 at some point x0. So, we have got f of x0 is equal to f dash of x0 is equal
to 0 and at some other distinct point x1 we have got f of x1 is equal to f dash of x1
is equal to f double dash of x1 to be equal to 0.
Now, what we want to do is we want to fit a polynomial of degree less than or equal
to 5 which is going to interpolate the function value derivative value at x0 function value
derivative value and second derivative value at x1 and we want a polnomial of degree less
than or equal to 5. So, we need one more condition. So, let x to be another point which is distinct
from x0 and x1 . And it should interpolate the function at
this point then we want to find such a polynomial so our interpolation points are x0 is repeated
twice x1 is repeated thrice x2 is repeated once.
So, the usual way of constructing such a polynomial is you form the divided difference table once
you form the divided difference table then you look at the value f x0 then f of x0 x1
divided difference and so on. And then that is the newton form that is how
we construct the polynomial but here we can give a different proof our function our polynomial
it is going to match with the function value and derivative value at x 0 and the function
value and the derivative value both of them they are 0.
That means the polynomial p5 is going to have a factor x minus x0 square it is a double
you factorize similarly ,you look at the point x1 our polynomial should be such that it vanishes
at x1 its vanishes its derivative vanishes at x1 and second derivative vanishes at x1
that means in our polynomial there should be a factor x minus x1 cube. Now, look at
the polynomial we have got a factor x minus x0 square x minus x1 cube and it is a polynomial
of degree less than or equal to 5.
So, now what will be there will be a coefficient that has to be constant and we can we are
going to determine that constant so we can as I said either form divided difference table
or you look at the fact that p 5 it has got the double 0 at x0 triple 0 at x1. So, we
have got look at the factors x minus x0 square x minus x1 cube since it is a polynomial of
degree less than or equal to 5 you have to multiply only by a constant.
Otherwise if it was a higher degree polynomial here it would have been a function of x and
hence you get this polynomial form now we have to determine alpha. So, far we have not
use the fact that our polynomial is going to interpolate the given function at x2 also
so we have got x2 is equal to p5 x2 is equal to alpha times put x is equal to x2. So, x2
minus x0 square x2 minus x1 cube and that will give you alpha to be equal to f x2 divided
by x2 minus x0 square and x2 minus x1 cube. It will be a good exercise to try to complete
the divided difference table get the various divided differences which are going to come
into picture for the p5 of x and see that you are going to get the same result.
Now, we will consider one more example or one more problem and then we will go to the
next topic of numerical integration. Now, it is a simple example we are going to
look at f of x is equal to x square a simple function and then look at the interval n to
n plus 1. So, n is a integer or a natural number and what we want to do is we want to
find an upper bound now when we consider interpolating polynomials and then we know that the error
is in terms of the appropriate derivative of the function evaluated at a point now that
point is not known but look at function f of x is equal to x square.
We are looking at linear polynomial. So, in the error the second derivate comes into picture
and second derivative for x square it is going to be constant. So, using that fact one just
calculates what is an upper bound. So, we have norm of f minus p1 infinity this will
be less than or equal to norm f double dash infinity divided by 8 and then you have got
this will be equal to 1 by 4.
Because we have when we look at norm of f minus p1 infinity norm to be less than or
equal to it is norm f double dash infinity divided by 8 into b minus a square our a is
capital N b is N plus 1. So, b minus a is equal to 1. So, that is why norm f minus p
1 infinity norm is less than or equal to norm f double dash infinity by 8 and f double dash
being equal to2 it will be 2 by 8 which will be equal to 1 by 4.
So, on any interval n to n plus 1 this is going to be the bound now I want to recall
what forms of the polynomials we have consider. So, we have power form which is a 0 plus a
1 x plus a n x raise to n we have got lagrange form which involves lagrange polynomials and
we have got newton form.
Then we had this error. So, we have f of x is equal to f of x0 plus f of x1 x1 x minus
x0 plus f of x0 x1 xn x minus x0 x minus xn minus 1 and then the error f of x0 x1 xn x
and then x minus x0 x minus xn suppose our points are all identical then we have proved
that f of x0 x1 xn in this case we define it be equal to fn of x0 divided by n factorial.
So, thus our this result becomes f of x is equal to f of x0 plus f dash x0 into x minus
x0 plus f double dash of x0 by 2 x minus x0 square plus f of fn of x0 divided by n factorial
x minus x0 raise to n plus this divided difference is equal to f n plus 1 cx divided by n plus
1 factorial. So, it will be f n plus 1 cx divided by n plus 1 factorial multiplied by
x minus x0 raise to n plus 1. Now, you are familiar with this this is nothing
but Taylor's theorem so, this is an observation now we are going to start the new topic of
numerical integration suppose your function f is defined on interval a, b and it is continuous.
In that case one defines the riemann integration for that what one does is looks at the Riemann
sum, upper Riemann sum, lower Riemann sum, and in terms of those one define the integral
for a continuous function we can show that take the interval a,b subdivide it into 2
equal parts form the riemann sum by taking any. So, what you have to do is in each interval
you look at value a take a point any point and then you look at summation f at ci multiplied
by length of the interval. So, the length of the interval will be h submit over take
its limit as n tends to infinity and that is going to be our value of integral a to
b f of xd .
So, we have this for a continuous function limit n tending to infinity summation i goes
from 0 to n minus one h times f of ti, I had told you that you can take any point in the
interval ti to ti plus 1. So, let us choose it to be n point ti .
Form this sum and then take its limit as n tends to infinity our h is b minus a by n.
So, what you are doing is your looking at an average and then you are multiplying by
b minus a and then you get the limiting value is equal to integral a to b f of x dx. So,
using this definition one proves many important results and in numerical analysis now suppose
I give you a continuous function all continuous function they are going to be integrable.
So, if you are given a continuous function and you are ask tell me what is value of integral
a to b f of x dx. If not exact value may be some approximate
value then you are not going to look at this riemann sum take limit as n tends to infinity.
So, this is not how one finds the value of the integral. So, then there is a class of
functions for which one know how to integrate. So, if you know anti-derivative of your function;
that means, I want to find integral a to b f of x dx. So, suppose I know another function
capital F such that capital F its derivative is going to be my function f if I do that
if I know that then we have got integral a to b f of x dx is capital F of b minus capital
F of a. In fact, that is how one calculates the integration
that you know integration and differentiation these are opposite process. So, there are
some functions for which you can calculate anti derivative. So, one big class is to polynomial
functions. So, for polynomial functions we know there anti-derivatives there are also
trigonometric functions we know sin x cos x how to integrate exponential x. So, there
are there is some class of problems or class of functions rather one can calculate the
integral a to b f of x dx. So, our idea is that our function we know
how to approximated by polynomials. So, consider approximation of function f by a interpolating
polynomial integrate that polynomial whatever value you get that you are you will be able
to do even using computer. In fact, when we started the polynomial approximation that
is what we said that the polynomials they are nice functions you can derivative using
computer you can find the integral using the computer so you calculate the value of the
integral and then you are going to get an approximate value of the integration. So,
in order to have sufficient accuracy you have choose and begin up but we have seen that
if your function is only given to be continuous then we do not have a sequence of interpolating
polynomials which is going to converge to our function f.
So, then that is where now we went to piecewise polynomial approximation. So, why not look
at piecewise polynomial approximation. So, on each interval or on each subinterval
I will have a polynomial I will integrate that I will add it up and then I will get
value of the function. So, that is how one is going to do when you consider a single
polynomial.
Then you are going to get basic rule when you are going to look at piecewise polynomials
you are going to get what are known as composite rules. So, we are going to consider some of
the standard rules which are used in practice. So, here is if your function is a polynomial
a0 plus a1 x plus an x raise to n. Then if you look at capital F of x to be equal
to a0 x plus a1 x square by 2 plus an x raise to n plus 1 by n plus 1 then it satisfies
the property that F dash x is equal to small f of x.
And then this is one of the fundamental theorem of integral calculus that integral a to b
f x dx will be nothing but capital F of b minus capital Fof a.
So, now let us look at the interpolating polynomial. So, we have this form we have pn interpolates
f at x0 x1 xn then pn of x is going to be summation f of xi li of x, i goes from 0 to
n where li is a polynomial of degree n. So, integral a to b pn of x dx will be equal
to summation i goes from 0 to n f of xi integral a to b li of x dx. So, this is going to give
us some real number wi. So, you have summation i goes from 0 to n, wi f of xi note that here
there is no dependence on the function. So, this we will do once for all and then we get
a formula for a integral a to b pn of x dx in terms of these wi's and the function values
xi.
Now, look at the error. So, here we know the error in the interpolating polynomial. So,
we have f of x is equal to pn of x plus a error term the error term is a function of
x. So, you integrate so we are going to have integral a to b f of x dx is equal to integral
a to b pn of x dx plus integration of the error now for the error we will be calculating
only an upper bound. So, we have modulus of integral a to b f of x dx minus integral a
to b pn of x dx modulus. So, this is exact integral this will be of
the form summation wi f of xi, i goes from 0 to n this will be less than or equal to
modulus of integral a to b f of x0 x1 xn x into w of x dx where w of x is x minus x0
x minus xn. So, this will be less or equal to norm of f of n plus one infinity divided
by n plus 1 factorial and then we have got b minus a raise to n plus 1 and into b minus
a. So, norm of f of n plus 1 infinity is coming
from this factor this I am going to dominate by this. So, it will come out of the integration
sign modulus of w of x will be less than or equal to b minus a raise to n plus 1so that
also come out the integration sign and then you will have a integral a to b of 1 or a
to b dx that is going to give me b minus a. Now, this error which we have obtained it
have got n plus first derivative of the function its norm divided by n plus 1 factorial and
then we have got b minus a raise to n plus 2 now here what has happened is the x0 x1
xn they sort of we have lost we have used crude approximation that x0 x1 xn they all
lie the interval a, b. So, if our x is varying over the interval a b x minus x g also will
vary over the interval a, b. Now, the choice of interpolation points that
is important. So, we do not want to lose them. So, what will be a better estimate is that
w of x is a polynomial it is x minus x0 x minus x1 x minus xn we can integrate it. So,
that integration value that will retain the information about x0 x1 xn .
But then w of x in the error w of x is multiplied by n plus first derivative of the function
divided by n plus 1 factorial. So, I cannot just take it out and integrate. So, for that
purpose in order to get a finer bound we are going to prove what is known as mean value
theorem for integral also there will be cases when our if the points are such that for example
suppose you are looking at 1 point integral and that 1 point is the midpoint then integral
a to b x minus x0 dx that is going to be 0 and using that property one will get a higher
order of convergence or a better order of a convergence for the corresponding composite
rule. So, that is why we do not want to be satisfied
with this upper bound it is an upper bound but we want to have some better upper bound
and for that we prove mean value theorem for integrals. So, what it tells is that suppose
you are integrating 2 functions or you are looking at the product of 2 function f of
x into g of x over the interval a, b our function f suppose it is continuous.
The other function g what we want is it should be integrable continuous functions they are
integrable if your function has finite number of discontinuities then also it is integrable.
So, our g x should be a integrable function riemann integration I am always talking about
riemann integration and it should be either bigger than or equal to 0 or less than or
equal to 0 throughout the interval. So, one function should be continuous other function
should be either bigger than or equal to 0 or less than or equal to 0 if that happens
then integral a to b f x into g x dx will be equal to value of f at some point c into
integral a to b g of x dx. So, remember our error in the integration
it was consisting of 2 parts one was the divided difference based on x0 x1 xn x and we have
proved continuity of this function the other term was w of x that is x minus x0 x minus
1 x minus xn. So, depending on the choice of x0 x1 xn it can happen that w x is also
is bigger than or equal to 0 or less than or equal to 0.
Look at the linear polynomial which interpolates at the 2 end points in that case our w x is
going to be x minus a into x minus b our x varies over the interval a to b. So, x minus
a will be bigger than or equal to 0 x minus b will be less than or equal to 0. So, there
product will be less than or equal to 0. So, now if I can take out the divided difference
outside the integration by evaluating at a at a point then I will have a integral a to
b w of x dx and that value we can calculate
So, let us prove this mean value theorem for integrals. So, we have f is a map from a b
to R which is continuous and g is an integrable function such that either g of x bigger than
or equal to 0 or g x less than or equal to 0.
Then there exist apoint c in the interval a b such that integral a to b f of x g of
x dx is equal to f of c into integral a to b g of x dx. So, this is the theorem we are
going to prove now. The proof of this theorem it is going to be
best on property of continuous function our function f is defined on interval a b closed
interval closed and bounded interval a b and takes real values then such a function is
going to be bounded it is going to attain its infimum and supremum. So, supremum is
nothing but least upper bound amongst the upper bounds the one which is the smallest
when its attains its upper bound then that is known as maximum and similarly ,it is going
attain its minimum that is greatest lower bound among the lower bounds whichever is
the biggest. So, our function f will have absolute minimum small m and absolute maximum
capital M. So, small m will be less than or equal to f of x less or equal to capital M.
And then we have intermediate value property that between this small m and capital M our
function is going to assume each value. So, this is a crucial property which we are going
to use in the proof of this theorem. So, what let mere fresh the property this continuous
functions our function f is defined on interval it will be interval a b it will be its range
will be small m to capital M. So, it is going to be on 2 functions.
And any point in the interval small m to capital M that point that is going to be attain. So,
our we want to show that integral a to b f of x g of x dx is equal to f of c into integral
a to b g of x dx. So, if integral a to b g x dx is not 0 we divide. So, we look at integral
a to b f x g x dx divided by integral a to b g of x dx and show that it lies between
small m and capital M so.
Now, for the sake of definiteness we will assume g of x to be bigger than or equal to
0 if it is less than or equal to 0 some inequality is they will change but the proof is very
much similar. So, let us assume that g of x is bigger than or equal to 0 and let small
m and capital M denote the absolute minimum and absolute maximum of function f.
So, we have m less than or equal to f x less than or equal to capital M g of x is bigger
than or equal to 0. So, m into g of x is less than or equal to f of x into g of x less than
or equal to capital M into g of x. Now, you integrate using the property of integration
we will have the inequality science will be preserved and then small m and capital M they
do not depend on x. So, they come out of the integration sign and we have small m into
integral a to b g of x dx less than or equal to integral a to b f x g x dx less than or
equal to capital M into integral a to b g of x dx.
Now, our g we are assuming it to be bigger than or equal to 0 and integrable. So, g need
not be continuous so, integral a to b g of x dx it can be equal to 0.
Even when g of x is not identically 0 if g of x is identically 0 then of course, integral
a to b g of x dx is 0 but because g need not be continuous it can happen that integral
a to b g of x dx is equal to 0 when g of x is not identically 0 like look at function
g of x which is equal to 0 if x is not equal to a plus b by 2 and is equal to 1 if x is
equal to a plus b by 2 so g of x is not identically 0 and integral a to b g of x dx is equal to
0.
So, we have small m into integral a to b g of x dx this inequality we will look at 2
cases once when integral a to b g of x dx is equal to 0 and other when it is not equal
to 0 if this is equal to 0 then we have got 0 here 0 here which will mean integral a to
b f of x g of x dx is equal to 0. So, you can choose c to b any point the second case
will be integral a to b g of x dx is strictly bigger than 0 in that case I divide by integral
a to b g of x dx then the quotient is lying between small m to capital M. So, it has to
be equal to f of c. So, that is by the intermediate value theorem
and this will mean that integral a to b f of x g of x dx is equal to f of c multiplied
by integral a to b g of x dx that is the mean value theorem for integral and this mean value
theorem for integrals we are going use for calculating the error bounds in various rules
now what we are going to do in the next lecture is we will first consider some basic rules
which are coming from what are known as newton cotes formula.
Look at the interval a, b subdivide it into equal parts fi tan interpolating polynomial
integrate it and then we get a numerical quadrature rule you are familiar with these rules such
as if you choose a constant polynomial and choose the interpolating point to be the end
point then what you get is what is known as a rectangle rule if you take the midpoint
and consider the constant polynomial what you get is a midpoint rule.
Then if you consider polynomial of degree less than or equal to 1 choose 2 end points
of the interval as your interpolating point you get trapezoidal rule then you have got
simpson rule in which case you are interpolating points are three points a band midpoint a
plus b by 2 you are fitting a parabola and then are integrating. So, that gives you simpson's
rule and then we are going to look at the error in all these formally then from these
we go to composite rules. So, these will be the basic rules then we go to composite rules
where each of these basic rule instead of applying them at the whole of interval a,
b we will apply them on the sub interval that and then the gaussian rules.
So, this thing we will continue next time thank you!