Tip:
Highlight text to annotate it
X
So, today we are going to consider composite quadrature formulae and corrected trapezoidal
rule. So, last time, we had considered four basic rules - rectangle rule, then midpoint
rule, trapezoidal rule and the Simpson's rule. For Simpson's rule, we saw that even though
we are fitting a quadratic polynomial, there is no error if the function is a cubic polynomial.
For the midpoint rule, we were fitting a constant polynomial between got exactitude for polynomials
of degree less than or equal to 1. Let me look at the comparison of the rules. So, for
the rectangle, the degree of the interpolating polynomial was 0 and you got exact for polynomials
of degree 0.
This is expected for trapezoidal, it was 1 1. In both the cases, this is also expected,
but for the midpoint degree of the interpolating polynomial was 0, and you had exactitude for
linear polynomials for Simpson's quadratic polynomial was interpolated, and we got exactitudes
for cubic polynomial. This trapezoidal rule and the Simpson's rule, they come under what
are known as Newton-Cotes formula. So, you have a interval a b. You sub divide it in
to n equal parts and then you consider these n plus 1 points. You fit a polynomial of degree
less than or equal to n, you will get a formula and that is the Newton-Cotes formula.
So, if you choose n is equal to 1 and the 2 end points, which gives us trapezium rule.
If you choose n is equal to 3 2 end points and the midpoint that gives us Simpson's rule.
You can choose the n is equal to 3 and then you will get a formula of the form b minus
a into 3 by 8 and then f x 0 plus 3 f x 1 plus 3 f x 2 plus f of x 3.
You should note that if you had the coefficients 1 3 3 and 1, then these they will add up to
8. Now, you can choose general n and find a approximate Quadrature formula. We have
seen Runge's example which was f x is equal to 1 upon 1 plus 25 x square for x belonging
to minus 1 to 1. When we looked at the error between f and p n, then instead of the error
being decreasing as n tends to infinity, the error tends to infinity.
This is the classic example that the interpolating polynomials, they may not converge in the
maximum norm. That is why we went to piecewise polynomial. So, same thing we are going to
do now that instead of integrating polynomials, we will integrate piecewise polynomials and
that will give us the composite rules.
Now, one of the disadvantage with piecewise polynomials is that they are not smooth functions,
they lack differentiability properties at the patrician point, but when you are integrating,
then we are it does not matter. So, for the composite rules, we are going to get the good
results. We will have convergence the problem will come when we talk about numerical differentiation
but that little later. If you look at the Runge's example, f x is
equal to 1 upon 1 plus 25 x square x belonging to minus 1 to 1, then norm of f minus p n
infinity norm tends to infinity, and if you integrate p n x dx, then the error instead
of decreasing, it will increase.
So now, we are going to consider the corrected trapezoidal rule. Suppose you choose your
interpolation points to be x 0 is equal to x 0 is equal to a and x 1 is equal to x 1
is equal to b, then your interpolating polynomial will be given by f of a plus f dash a into
x minus a plus f of a a b x minus a square plus f of a a b b x minus a square x minus
b plus the error term a a b b x x minus a square x minus b square.
So, this is our p 3 x, because we want to make use of the earlier results. Let us write
p 3 x as f of a plus f of a b x minus a plus f of a b a x minus a into x minus b plus f
of a b a b x minus a square x minus b. So, both the polynomials, they are the same.
When you integrate, you are going to get the same result, but we have already done integrations
for the trapezoidal rule, for the Simpson's rule; so, we want to make use of that. That
is why I am taking my interpolation points as a b a b.
So, the set remains the same, whether you take them the interpolation points as a a
b b or whether you choose them as a b a b, they are going to be the same. Now, the method
is the same. In this case, the error is going to be f the divided difference of f based
on a a b b x multiplied by w x; w x is our products of x minus x j - where x j's are
interpolation point. In this case, our interpolation points are
x 0 is equal to a repeated x 1 x 0 is equal to a x 1 is equal to a x 2 is equal to b x
c is equal to b. So, our w x becomes x minus a square x minus b square. So, w x is always
going to be bigger than or equal to 0. The divided difference based on a repeated twice
b repeated twice and x is going to be continuous.
So, we apply mean value theorem and then you work out the details and then one gets the
formula. So, you have this first thing, that is going to give us b minus a by 2 f a plus
a f b; that was the trapezoidal rule. Then this f of a a b comes out of the integration
sign. Integral x minus a into x minus b dx that
we had already seen it to be equal to minus b minus a cube by 6. Then this will come out
of the integration sign and you integrate this by parts. So, x minus b integration of
x minus a square, so, that will be x minus a cube by 3 evaluated between a and b minus
integral a to b x minus a cube by 3 and the derivative of x minus b, so, that is x minus
a cube by 3 dx. Then this is that b minus a by 2 f a plus
f b term minus we make the adjustments and one can check that this comes out to be equal
to minus divided difference of f based on a b minus f dash a divided by b minus a and
then minus f dash b minus f of a b. This 12 should be b minus a into b minus a cube by
12, then f of a b will get cancelled.
And we will have integral a to b p 3 x d x to be equal to b minus a by 2 f a plus f b
plus this extra term. So, that is why it is called corrected trapezoidal rule. So, it
is b minus a square by 12 f dash a minus f dash b, and now, for the error, the divided
difference is continuous. This is bigger than or equal to 0 by mean value theorem for integrals.
This will come out as divided difference based on a a b b and some point c.
We want to integrate x minus a square x minus b square d x between a to b make the substitution
as before y is equal to x minus a plus b by 2 and k to be equal to b minus a by 2.
Then x minus a is nothing but y plus k, so, you will have y plus k square; x minus b will
be nothing but y minus k, so, you will have y minus k square dy; x varies between a to
b, so, y will vary between minus b minus a by 2 to plus b minus a by 2. So, it is minus
k to k. If your function f is four times differentiable, this term is going to be f 4 eta divided by
4 factorial; that means 24, and then, you have integration of this. The integration
when you simplify, then you are going to have f 4 eta b minus a raise to 5 divided by 720.
So, we have treated a polynomial of degree less than or equal to 3. We got the error
to be exact for polynomials of degree less than or equal to 3. So, if you look at the
Simpson's method, in Simpson's method, we had three points - f a, f b and f of a plus
b by 2 and the error was 0 for cubic polynomials. Here we had considered cubic hermite interpolation.
We got again the error to be 0 for cubic polynomials, but there is a catch. We have the derivative
values f dash a and f dash b coming into picture. So, if they are available well and good; otherwise,
this formula is not applicable, but look at a case - when f dash a is equal to f dash
b, suppose your function, f is periodic function with period to be b minus a and your derivatives
are also periodic, in that case, the term f dash a minus f dash b will be equal to 0,
and then, what we will have will be for the trapezoidal rule because then our integral
a to b f x dx will be approximating by b minus a by 2 f a plus f b.
So, for the trapezoidal rule, we will have exactitude for polynomials of degree less
than or equal to 3, and then, afterwards, we are going to consider what is known as
euler-maclaurin series expansion and so on. So, if your function f is infinitely many
times differentiable and the derivatives are periodic with period a b, like this is the
case, for example, for sin x, sin x has period 0 to 2 pi. When you take their derivatives,
again they are periodic with period 0 to 2 pi.
So, for such functions, the trapezoidal rule is to be preferred, because then we are going
to get very good convergence and the condition is your function should be periodic. So, function
should be periodic and their derivatives also should have periodic property.
So, this is for the basic rules. Now, we are going to consider composite rules. So, in
the composite rules, what we are going to do is divide interval a b into n equal parts.
On each interval, you apply some basic rule like look at the rectangle rule.
So, on each interval, you are going to apply rectangle rule, and then, we are interested
in integral a to b f x dx. This integral will be equal to summation of integration over
t i to t i plus 1, the smaller intervals, and then, we have got error formulae; so,
you will add it up and then you will get an expression for error.
The basic rectangle rule is integral a to b f x dx is approximately equal to f of a
into b minus a and the error is f dash eta b minus a square by 2 - where eta is some
point in the interval a b. We have our interval t 0 to t n which is equal to a b.
We have subdivided into smaller intervals, and on the interval t i to t i plus 1, we
apply the basic rule. So, we will have integral t i to t i plus 1 f x dx will be approximately
equal to f of t i the length of the interval b minus a is h. So, you will have h here,
and then, h is t i plus 1 minus t i which is equal to b minus a by n.
So, this is the error f dash eta i h square by 2. Now, integral a to b f x dx is summation
i goes from 0 to n minus one integral t i to t i plus 1 f x dx. This integral t i to
t i plus 1 f x dx is approximately equal to value of f at the left hand point t i multiplied
by length of the interval which is h and you add it up.
So, you are going to have integral a to b f x dx to be summation I goes from 0 to n
minus one f t i into h and the error will be f dash eta i h square by 2 summation i
goes from 0 to n minus 1. So, it is h square by 2 and then this summation. So, look at
this error.
It is h square by 2 summation i goes from 0 to n minus 1 f dash of t i. h is b minus
a by n, so h square is going to tend to 0 as n tends to infinity, but in this term,
as your n increases, the number is going to increase.
So, this is not something constant times h square by 2. Let us look at this error more
carefully. Let me assume that f dash is continuous on interval a b. Let small m be minimum of
f dash x x belonging to a b and capital M be maximum of f dash x x belonging to a b.
So, m is going to b less than or equal to f dash t i less than or equal to M, for i
is equal to 0 1 up to n minus 1. So, if I look at summation I goes from 0 to n minus
1 f dash t i, this will be less than or equal to n times capital M and bigger than or equal
to small n into small m because we have got n terms, so summation i goes from 0 to n minus
1 f dash t i divided by n will lie between small m and capital m. Now, by the intermediate
value theorem, this summation i goes from 0 to n minus 1 f dash t i divided by n will
be equal to f dash of c for some c. So here, this error I keep h by 2 as it is
h is b minus a by n; so, I will have b minus a and then summation I goes from 0 to n minus
one f dash t i. So, this will be equal to h by 2 b minus a; here, it should be this
divided by n and because there is h is b minus a by n and this is equal to f dash of c. So,
we have got error to be equal to h by 2 b minus a f dash c.
So, this is a constant independent of n and this will tend to 0 as n tends infinity. So,
our modulus of error will be less than or equal to constant times h - where constant
is independent of n. So, we say that error is of the order of h.
So, this is the error in the composite rectangle room. Now, what we did for the rectangle rule?
We are going to do for our other rules, that is, the midpoint rule; then trapezoidal rule;
then we had Simpson's rule and corrected trapezoidal rule.
So, our interval a b is sub divided into small part small intervals. On each interval apply
a basic rule. The integral a to b f x dx is split into n integrals. You get value, you
add it up. For the error also it will add it up. In the error, there is going to be
some power of h, because in all the errors, we had b minus a raise to something. Now,
that b minus a is going to be replaced by h, and then, you will have summation, summation
of n terms. So, that summation of n terms we get rid of by say adjoining 1 h to h. So,
that is why you are going to have always 1 power of h to be less. In the sense, in the
rectangle rule, our error had b minus a square. So, corresponding error in the composite rectangle
rule, we had not h square but only h.
In the midpoint rule, we had b minus a cube; so, that will be replaced by h square, and
then, it is the exactly same argument. So, what I am going to do is write down the composite
rule and then write down the error, but whatever we have worked out the details there exactly
the same, so, we are not going to work them out again. Look at the midpoint rule - integral
a to b f x d x is approximately equal to b minus a f of a plus b by 2. The error was
f double dash eta b minus a cube by 24. When you consider the composite rule, in the interval
t i to t i plus 1 integral f x dx that is approximated by length of the interval, which
is h multiplied by value of f at t i t i plus 1 by 2.
In the error, we are going to have summation f double dash eta i h cube by 24. Then 1 h,
we take from 1 h n and then you have got this average. This average will be equal to f double
dash of psi. So, you have got b minus a by 24 h square and then f double dash psi. You
need the function to be two times differentiable and the error is going to be of the order
of h square. Then when we look at the composite trapezoidal rule, it is similar. You are going
to have the error to be minus b minus a cube by 12. So, instead of b minus a cube by 24,
you have got b minus a cube by 12. That is the only difference, and then, you are going
to have the error to be minus b minus a f double dash psi divided by 12 into h square.
If you look at the composite rule, the basic trapezoidal rule is b minus a by 2 f a plus
f b. So, when I look at the intervals t i minus 1 t i t i plus 1 integral t i to t i
plus 1 f x dx will be approximated by h by 2 f of t i plus f of t i plus 1 integral t
i minus 1 to t i f x dx will be approximated by h by 2 f of t i minus 1 plus f t i. So,
this f t i is common. So, this is for trapezoidal rule. If you had considered midpoint rule,
you will be considering midpoint here, midpoint here. So, when you are looking at two intervals,
you need to evaluate the function at three points. Here your you need to evaluate it
at two point, and in general, when you have n intervals, for midpoint rule, you will have
n points; for trapezoidal rule, you will have n plus 1 point. So, the composite trapezoidal
rule is given by integral a to be f x dx is equal to h by 2 f a plus f b plus h times
summation i goes from 1 to n minus 1 f of t i. So, at the two end points, the weight
is different that is h by 2, and at the interior partition points, the weight is h and the
error is constant times h square.
The function evaluations are n plus 1, you need function to be 2 times differentiable
and the error is of the order of h square. For the Simpson's rule, we have got value
of the function at two end points and value at the midpoint and the error was given by
this formula, which involved fourth derivative of the function and then b minus a by 2 raise
to 5. When you consider the composite rule, you are going to have on each interval t i
to t i plus one it is f of t i plus four times f of s i plus f of t i plus 1 divided by 6
- where s i is the midpoint of t i and t i plus 1.
And then, when you arrange the terms, it will be h by 6 f a plus f b plus h by 3 summation
f t i and plus 2 h by 3 summation f of s i. So, you have got weights to be different.
At the two end points, a and b at the partition points t 1 t 2 t n minus 1 and at the mid
points of the intervals. Next, we look at the error. So, the error will be given by
this b minus a by 2 is replaced by h by 2 raise to 5 minus 1 by 90 and then this is
from each interval you are going to have f 4 eta i. So, that is why you have summation
i goes from 0 to n minus 1. Now, this summation we associate 1 h with it and then you get
f 4 psi into b minus a and then you have h by 2 raise to 4 and then divided by 180. So,
this is the error in the Simpson's rule the function evaluations are 2 n plus 1. You need
function to be four times differentiable and the error is of the order of h raise to 4.
And now, we look at the corrected trapezoidal rule. So, corrected trapezoidal rule is given
by b minus a by 2 f a plus f b plus b minus a square by 12 f dash a minus f dash b. So,
you have integral a to b f x dx to be equal to b minus a by 2 f a plus f b plus b minus
a square by 12 f dash a minus f dash a minus f dash b.
Now, since we had f dash a minus f dash b, when we will apply the composite rule, when
we will apply it to the sub intervals t i to t i plus 1, corrected trapezoidal rule
applied to the interval t i to t i plus 1 will involve b minus a by 2 f of t i plus
f of t i plus 1. So, this is one term. The other term will
be b minus q square by 12 f dash a minus f dash b. So, you will have instead of b minus
a, you will have h square by 2 and then you will have f dash t i minus f dash t i plus
1, that is from the interval t i to t i plus 1.
If you consider the interval t i minus 1 to t i, there it will be f dash t i minus 1 minus
f dash t i. So, when you add it up, f dash t i will get cancelled. So, you have got summation
I goes from 0 to n minus 1 f dash t i minus f dash t i plus 1.
So, all the derivative get cancelled and you are left with only f dash a and f dash b.
So, this minus sign, it was good, because then when you add it up, the value of the
function f at all the patrician points that comes in to picture, but the derivatives values,
they get cancelled and you need only f dash a and f dash b.
So, you have integral a to b f x dx to be equal to summation i goes from 0 to n minus
1 integral t i to t i plus 1 f x dx. This will be approximately equal to summation i
goes from 0 to n minus 1 h by 2 f of t i plus f of t i minus 1 plus h square by 12 summation
i goes from 0 to n minus 1 f dash t i minus f dash t i plus 1.
So, this is our trapezoidal rule, - composite - and this simplifies to h square by 12 f
dash a minus f dash b. So, you adjust you have to just add 1 extra term. So, you have
integral a to b f x d x this h by 2 f a plus f b plus h times summation i goes from 1 to
n minus 1 f t i plus this term.
Correct correction h square by 12 f dash a minus f dash b, and if f dash a is equal to
f dash b, then this term will not be there, and when you look at the error, error is going
be h raise to 5 divided by 720 and this summation it is summation of n terms. So, we associate
1 h with it and that will give us b minus a f 4 at evaluated at some point psi and then
you have h raise to 4 and 720.
So, if the function f is four times continuously differentiable, the error is going to be of
the order h raise to 4 we need n plus 1 function evaluations that was from the composite trapezoidal
rule and then we need to evaluate two derivative functions. So, here is the comparison for
the rectangle rule the smoothness required is c 1. For the midpoint, it was c 2 midpoint
and trapezoidal c 2 and Simpson and corrected trapezoidal c 4.
The function evaluations in rectangle and midpoint, they are the same n but the order
of convergence is h in rectangle and h square in midpoint. So, you should prefer midpoint
over rectangle, between midpoint and trapezoidal both need the function to be two times differentiable.
The order of convergence is h square and the function evaluation is n here and n plus 1
in trapezoidal. For n big enough, there is not much difference between n and n plus 1.
So, midpoint and trapezoidal they are on par. For the Simpson, you are getting the improvement
in the order of convergence from h square to h raise to 4, but the function evaluations
are instead of n plus 1, you have got 2 n plus 1; so, that means it is double, but this
improvement is or this increase in the function evaluation, it is arithmetic and the order
of convergence that improvement is geometric. So, if your function is sufficiently differentiable,
Simpson's rule will be preferable compare to the trapezoidal rule, and then, corrected
trapezoidal rule it will have the same function evaluation. You will have two derivatives.
So, if the derivative values at the end points it is available, then you should prefer corrected
trapezoidal rule over all the other rules. So, we have looked at some basic rules and
then we considered the corresponding composite rules and we have got way to find approximate
value of the integration. We wanted to find the order of convergence; that is why we had
assumed certain differentiability properties of our function, but look at the rectangle
rule. In the rectangle rule, when you consider the composite rectangle rule, it is given
by h times summation i goes from 0 to n minus 1 f at t I; that means we have got our partition
uniform partition of interval a b. In each subinterval, we are choosing the left end
point. So, we are looking at f of t i and then you are multiplying by h. So, that is
nothing but the better Riemann sum.
So, if your function f is continuous, then this composite rectangle rule h times summation
f t i i goes from 0 to n minus 1, that is going to converge to integral a to b f x dx.
So, this f to be continuously differentiable, that we need to say that the order of convergence
is h in the composite rule. It is not necessary for the convergence. Look
at the midpoint rule. In the midpoint rule, we are looking at the in each interval t i
to t i plus 1, we are looking at the midpoint, and then, we are forming the Riemann sum.
For the Riemann sum, in the interval t i to t i plus 1, you can choose any point multiply
by h add it up and then it is going to converge if your function is continuous.
Now, what happens for the trapezoidal rule? In the trapezoidal rule, we had h by 2 into
f a plus p b and then we had f of t i summation i goes from 1 to n minus 1 multiplied by h.
So, let us look at the composite trapezoidal rule.
So, it is integral a to b f x dx is approximately equal to h by 2 f a plus f b plus h times
summation i goes from 1 to n minus 1 f of t n. Now, the question is whether this argument
about the Riemann sum, whether we can apply it to the composite trapezoidal rule, that,
suppose the function is given to be only continuous, we do not know that; it may not be differentiable.
In that case, whether the composite trapezoidal rule is going to converge?
So, let us try to write this composite trapezoidal rule as Riemann sums. So, we had the weight
at the two end point was h by 2, and at the interior points, it was h. So, let us look
at the Riemann sum where you are choosing the left end point; that means what points
will come into picture will be a t 1 t 2 up to t n minus 1 and then you have to multiply
by h; so, that will be one Riemann sum. Another Riemann sum will be choose the right end point.
In that case, in the interval t 0 to t 1, we will be choosing f of t 1; that means a
will not come in to picture. So, you will have t 1 t 2 and t n is equal to b.
So here, we have got h by 2. Then f a plus h by 2 summation i goes from 1 to n minus
1 f of t i. This is plus h by 2 summation i goes from 1 to n minus 1 f of t i plus h
by 2 f of b. So, this will be equal to, let me call r n 1 or r n plus s n divided by 2
- where r n is summation f t i i goes from 0 to n minus 1 s n is summation f t i i goes
from 1 to n. So, here, in the Riemann sum, you are choosing the left end point, that
gives us r n. If you choose the right end point, that will give us s n.
Our r n will tend to integral a to b f x dx s n also will tend to integral a to b f x
dx. So, this will tend to integral a to b f x dx. So, thus, even for the composite trapezoidal
rule, we are going to have convergence under the condition that function is continuous.
If you want to know the order of convergence, then you assume f to be twice differentiable.
Now, I will leave it to you to do it for Simpson's, like look at the composite Simpson's rule
and then try to write it as some Riemann sums and show that the Simpson's rule is also convergent
provided your function is continuous. So, just continuity is enough; all these composite
rules they are going to converge. The order of convergence that needs the function to
be differentiable or more than once differentiable. Now, we are going to look at another important
rule and that is known as Gaussian integration. So, the idea is so far what we have done is
we have fixed our points x 0 x 1 x n. Look at the basic rules how we have calculated
or how we have derived them. We have fixed x 0 x 1 x n some way, then we fit a polynomial
of degree less than or equal to n. you may know how to integrate, so, you integrate and
then you get a rule. The rule which we got was of the type value of the function at interpolation
points x i and then multiplied by some weight w i, like look at the rectangle, there it
was b minus a into f of a. For the midpoint, it was b minus a into f
of a plus b by 2. For the trapezoidal, it is b minus a by 2 f a plus f b. So, both f
a and f b, they had the same weight. So now, is it possible that we do not fix x 0 x 1
x n to be beforehand. We want a integration rule of the form summation w i f x i i goes
from 0 to n. Treat the w i's x i's as unknowns; that means try to determine w 0 w 1 w n x
0 x 1 x n in such a manner that we have error to be 0 for adds high degree polynomial as
possible. So, we have got w 0 w 1 w n x 0 x x 1 x n; so, we have got 2 n plus 2, points
to be determined. So, we can hope to have exactitude for polynomials
of degree less than or equal to 2 n plus one. So this, we are going to consider in our next
lecture. Thank you.