Tip:
Highlight text to annotate it
X
We are considering Piecewise Polynomial Approximation, our function f is defined on interval a, b
closed and bounded interval a, b taking real values, we divide this interval into n equal
parts. So, each sub interval is going to have length h, which is equal to b minus a divided
by n, we fix k to be the degree of the polynomial, and then, on each interval we are going to
fit a polynomial of degree less than or equal to k.
We have already considered the case of Piecewise Linear Interpolation, in that case, we had
considered the interpolation points to be the partition points, so there are n plus
1 partition points, we are dividing the interval into n equal parts, so there are n plus 1
partition points, so far each interval t i to t i plus 1, we look at the value of the
function at t i and value at t i plus 1 and join it by straight line, so that gives us
polynomial of degree less than or equal to 1.
Because, we are considering the interpolation points to be the end points of the interval,
our function which is a Piecewise Linear Function, it is going to be a continuous function, and
last time we saw that the maximum error norm of f minus p n, its maximum norm or infinity
norm is less than or equal to constant times h square, h x b minus a by n b minus a is
fixed so as n tends to infinity h square will tend to 0 and error will tend to 0.
So, thus the degree of the polynomial in each sub interval was fixed to be less than or
equal to 1 and then we increase the number of intervals and then under the assumption
of function to be two times continuously differentiable we have proved the convergence of Piecewise
Linear Interpolation. Today, we are going to consider Piecewise
Quadratic Interpolation and Piecewise Cubic Interpolation. We will show that in the case
of Piecewise Quadratic Interpolation, the maximum error is going to be less than or
equal to constant times h cube, so instead of h square we get h cube, so we have got
faster convergence and in case of Piecewise Cubic we will get the maximum error to be
less than or equal to constant times h raise to 4, so still faster convergence.
Now, let me consider the notations, which we are going to use so for k bigger than or
equal to 1. C k a b is going to consist of functions, which are k times continuously
differentiable on interval a, b. This is going to be a vector space.
For a continuous function we have already defined the maximum norm that is maximum of
mod f x, x belonging to a, b. Throughout this lecture we are going to consider
the following uniform partition of interval a, b, which is a is equal to t 0 less than
t 1 less than t n is equal to b, for i is equal to 0 1 up to n minus 1, t i plus 1 minus
t i which is equal to h, that is going to be equal to b minus a by n.
Let us, recall the error in the interpolating polynomial, I had told you that this is the
very important relation, so p n is a polynomial of degree less than or equal to n, interpolating
the given function at n plus 1 points x 0, x 1, x n, then the we have got an expression
for the error f x minus p n x and if the function f is n plus 1 times differentiable, then we
get the error in terms of the derivative of the function evaluated at some point.
The error consist of 2 parts, it consist of divided difference f of x 0, x 1, x n, x which
if the function is n plus 1 times differentiable, then it is going to be equal to n plus first
derivative evaluated at some point C, that point C is going to depend on x, it also depends
on x 0, x 1, x n but x 0, x 1, x n are fixed and x varies over interval a, b. So, this
is 1 part and other part is the function w x that is x minus x 0, x minus x 1, x minus
x n. Last time we have seen that maximum norm of
w is minimized by choosing x 0, x 1, x n to be Chebyshev points. Now, today we are going
to replace the interval a, b by interval t i to t i plus 1 and in each polynomial in
each subinterval we are going to have a polynomial of degree less than or equal to k, so we are
going to join 2 polynomials together.
Let us, look at first the case of linear polynomial, so let p 0 x to be a 0 plus a 1 x, x belongs
to 0 to 1, then let q 0 x to be equal to b0 plus b 1 x, x belonging to 1 to 2.
So, we have interval 0, 1 and 2, if we do not impose any continuity condition at 1 then
we have got 4 constants which can vary independently, so a 0, a 1, b 0, b 1.
Suppose we impose continuity that means we want p 0 at 1 should be equal to q 0 at 1,
the problem of continuity comes only at the partition points, otherwise in the interval
0 to 1 p 0 being a polynomial, it is infinitely many time differentiable in the interval 1
to 2, the polynomial q 0 is going to be infinitely many times differentiable, so the question
is whether the values at 1 whether they match. So, that gives us a 0 plus a1 is equal to
b 0 plus b1, so that means now if I fix a 0, a1 and b0 then I have no choice for b1,
if I want the function which is formed by p 0 and q 0 to be continuous, then b 1 has
to satisfy a 0 plus a 1 minus b 0. So, earlier we could vary a 0, a 1, b 0, b
1 independently, now we can vary only 3 constants independently a 0, a 1 and b 0 and then b
1 is determined in terms of a 0, a 1 and b 0, then suppose we want the derivatives to
be continuous, so we want p 0 dash at 1 is equal to q 0 dash at 1, p 0 dash at x is equal
to a1, q 0 dash at x is equal to b 1 and hence we get a 1 to be equal to b 1.
Now, we have two relations, we have got this relation and we have got this relation, so
from these two relations 1 concludes that a 0 has to be equal to b 0, a 1 has to be
equal to b 1 that means it is a single polynomial. So, if we look at 2 polynomials of degree
less than or equal to 1, then we can ask the resulting function to be continuous and still
retain the Piecewise nature, but if we ask the function to be continuous and differentiable
then it becomes the single polynomial.
Next, let us look at the case of quadratic polynomials, so look at p 0 x to be equal
to a 0 plus a1 x plus a2 x square, x belonging to 0 to 1 and q 0 x to be equal to b 0 plus
b 1 x plus b 2 x square x belonging to 1 to 2.
So, we have got 6 constants which can vary independently, continuity at point 1 implies
that a 0 plus a 1 plus a 2 has to be equal to b 0 plus b 1 plus b 2, so that means we
have got only 5 constants which are independent. Then, suppose we want p 0 dash at 1 is equal
to q 0 dash at 1 then we have a1 plus 2 a 2 should be equal to b1 plus 2 b 2, so 1 more
degree of liberty is lost. If, we say that p 0 double dash 1 is equal
to q 0 double dash 1, then this will imply that 2 a 2 should be equal to 2 b 2, so thus
from here we have got b 2 is equal to a 2, from here we get b 1 to be equal to a 1 and
from here we get b 0 to be equal to a 0.
So, as in the case of the Piecewise Liner Polynomials, if you say that 2 quadratic polynomials
p 2 and q 2, they should together form a 2 times continuously differentiable function,
in that case it becomes a single polynomial defined on these 2 interval, so if we want
to retain the Piecewise structure, then for quadratic polynomial we can go up to the continuity
of the derivative. If, we increase the degree of the polynomial
that means if we consider 2 cubic polynomials, then we can demand that the resulting function
should be two times differentiable and still we can have two different cubic polynomials
respectively on the interval 0 to 1 and interval 1 to 2.
If for cubic polynomials we ask for the function to be continuous first derivatives, second
derivative and third derivative to be continuous, then it will reduce to a single cubic polynomial
l. So, when we demand the continuity or the continuity
of the derivatives, then for each of this demand the degree of liberty gets reduced
by 1. So, now we are going to here we had considered
only 2 polynomials, now we are going to consider n intervals and on each interval we consider
a polynomial. So, first we are going to look at the dimension
of such a space and then Piecewise Linear case we have already considered, so we will
go to Piecewise Quadratic and Piecewise Cubic.
So, as I said our interval a, b is going to be divided into n equal parts and then you
consider x n to be set of all f or set of all g defined on interval a, b such that restriction
of g 2 interval t i to t i plus 1 is a polynomial of degree less than or equal to k.
We have got n intervals, in each interval it is a polynomial of degree less than or
equal to k, that means we have got k plus 1 coefficients at our disposal, so total there
are going to be n into k plus 1 and that is going to be the dimension of the space x n.
If we consider the space y n, where once again g restricted to t i to t i plus 1 is a polynomial
of degree less than or equal to k, but we impose the function to be continuous.
So, we have got, this is our interval a, b then we are subdividing into n equal parts,
so this is t 0, t 1, t 2, t n minus 1, t n, here it is a polynomial of degree less than
or equal to k. So, we saw that the total degrees of liberty
they are n into k plus 1, now we will want these 2 polynomials to be continuous, so that
will impose 1 constraint, then continuity at t 2 and continuity at t n minus 1. So,
we are imposing total n minus 1 constraint, so it will be minus n minus 1 and thus, we
get the dimension to be equal to n k plus 1, so this is if you are assuming continuity.
If we want the function, its derivative and f double dash to be continuous then the dimension
will be equal to n into k plus 1 minus at each point t 1, t 2, t n minus 1 we are putting
2 constraints, so that will be minus 2 into n minus 1, so that will be the dimension of
the space, so this was general case. Now, let me recall the Piecewise Linear Continuous
Polynomials. We have got n intervals in each interval linear, means we have got two coefficients
so it is 2 into n, at interior nodes the continuity considerations so they are n minus 1 t 1,
t 2, t n minus 1. So, the dimension of the space is 2 n minus
n minus 1, so that is going to be n plus 1. So, this is going to be dimension of our vector
space which consists of Piecewise Linear Continuous Functions.
If we look at the value of the function f at the partition points that means t 0, t
1 up to t n, so these partition points they are n plus 1 in number, so if we try to determine
a Piecewise Linear Continuous Function which matches with the given function at t 0, t
1 up to t n, then such a function is going to be unique.
This part we had seen last time that for linear polynomial interpolation norm of f minus p1
its infinity norm is less than or equal to norm f double dash infinity divided by 2 into
b minus a by 2 square. Our function is going to be linear on each interval t i to t i plus
1, so this bound we will write for the interval t i to t i plus 1 and the bound will be norm
f double dash infinity norm divided by 2 b minus a will be replaced by h by 2 square.
So, that will be for maximum of modulus of f x minus g 1 x, where g 1 is our Piecewise
Linear Continuous Function for x belonging to t i to t i plus 1, but then the bound is
going to be independent of I, so the same bound works for each interval t i to t i plus
1 and we get norm of f minus g n its infinity norm to be less than or equal to norm f double
dash infinity divided by 8 h square. So, it is the bound for the linear polynomial
we had applied 2 Piecewise Linear Polynomial on each interval t i to t i plus 1.
So, thus we have got the error in the Piecewise Linear Continuous Functions to be less than
or equal to constant times h square where constant is second derivative norm f double
dash its infinity norm divided by h. What we are going to do is? Consider an example,
look at the function f x is equal to root x, x belonging to closed interval 1 to 2.
So, root x on interval 1 to 2 is going to be infinitely many time differentiable, what
we want is? It should be differentiable twice and then we will look at the second derivative,
so we can find a value of norm f double dash infinity, in this special case f x is equal
to root x, then we will look at this upper bound and suppose, we want the error to be
less than 10 raise to minus 6, then we will get our error, which involves b minus a by
n whole square multiplied by some constant to be less than 10 raise to minus 6 and from
that we can get the value of n. So, by looking at the upper bound we can beforehand
tell what n we should use, so as to obtain the desired accuracy.
The same example we are also going to consider for the Piecewise Quadratic Polynomial, so
we have f x is equal to root x, x belonging to 1 to 2 we have norm of f minus g n infinity
to be less than or equal to norm f double dash infinity divided by 8 into h square,
where h is b minus a by n and in this case it is going to be 1 by n, f dash x is going
to be 1 upon 2 root x, f double dash x will be equal to minus 1 by 4 x raise to 3 by 2.
When you consider mod of f double dash x, this is going to be 1 upon 4 x raise to 3
by 2, so this is a decreasing function on interval 1 to 2 and hence, maximum of mod of f double dash x, x belonging to 1 to 2,
this will be attend at the left end 0.1 and then you get it to be equal to 1 by 4.
So, we have norm of f minus g n infinity norm to be less than or equal to 1 upon 32 and
then 1 upon n square, because h is equal to 1 by n, now this will be less than say 10
raise to minus 6 provided n square is bigger than 10 raise to 6 divided by 32.
So, if you choose n is equal to 200 then that will work, so in fact any number n to be bigger
than 200 will work and this is a rough estimate. So, this was about Piecewise Linear Interpolation.
Now we are going to consider Piecewise Quadratic, so first let us look at quadratic polynomials,
so 1 single quadratic polynomial defined on interval a, b. For quadratic polynomial interpolation
we need 3 points. So, let us choose those 3 points to be 2 n
points of the interval a, b and the midpoint of the interval a, b, because we are choosing
the end points and afterwards when we consider the interval a, b subdivide into n equal parts
and for each subinterval t i to t i plus 1, we will be choosing two end points and the
mid-point. So, because the partition points are going
to be the interpolation points for Piecewise Quadratic Function, our resulting function
is going to be continuous.
Let me first recall that if f is from a, b to R, p 2 x is a polynomial of degree less
than or equal to 2, such that p 2 at a is equal to f of a, p 2 at the midpoint a plus
b by 2 is f of a plus b by 2 and p 2 b is equal to f of b, then f x is going to be equal
to f of a plus divided difference based on a, a plus b by 2 into x minus a plus divided
difference based on a, a plus b by 2, b, x minus a, x minus a plus b by 2.
So, this is p 2 x and the error term is going to be f of a, a plus b by 2, b, x and x minus
a, x minus a plus b by 2, x minus b, so let me call this as w x, so we have f x minus
p 2 x is equal to f triple dash at some point C divided by 3 factorial and then w x.
So, when we look at the error, norm of f minus p 2 infinity norm this will be less than or
equal to norm f triple dash divided by 3 factorial and into norm of w infinity, so w x is our
function x minus a, x minus a plus b by 2, x minus b,, we can find the infinity norm
for this function, we have got a continuous function when we want to find its maximum.
What we have to do is? Look at the value at the n points, look at the value where the
derivative vanishes or derivative does not exist.
So, such points they are known as the critical points, so we get hopefully finitely many
points, 2 end points and critical points compare the value of the function at this finitely
minute points, whichever is the maximum that is going be absolute maximum of the function,
whichever is the minimum it is absolute minimum, you should not go for second derivative test,
because the second derivative tells you only about the local maximum or local minimum.
So, let us calculate maximum of mod of w x, x belonging to a, b, so for the sake of convenience
we will make a change of variable and then we will calculate.
So, we have maximum of modulus of w x, x belonging to a, b is equal to maximum of mod of x minus
a, x minus a plus b by 2, x minus b, x belonging to a, b, so let y be equal to x minus a plus
b by 2 and k to be equal to b minus a by 2. Then when we look at y plus k, that will be
nothing but x minus a, y minus k will be x minus b.
And hence, this maximum it reduces to maximum of mod of y minus a or it is going to be maximum
of y plus k, y, y minus k, where y is going to vary over, x varies over interval a, b,
so x minus a plus b by 2 that is going to vary over minus k to k, since k is b minus
a by 2, so we have this is maximum of mod of y cube minus y k square, y belonging to
minus k to k. This function vanishes at the 2 end points minus k and k.
Now, let us look at the critical points, so critical point will be given by 3 y square
minus k square is equal to 0, this is the derivative value. So, you get y is equal to
plus or minus k by root 3, so these are critical points. When you put y is equal to k by root
3 then modulus of y cube minus y k square is going to be k cube by 3 root 3 minus k
cube by root 3. So, this will be 2 k cube divided by 3 root
3 it is modulus and for y is equal to minus k by root 3 you are going to get the same
value, so the maximum of this is going to be equal to 2 upon 3 root 3 and k cube is
b minus a by 2 whole cube. So, that is for the norm w infinity and then
for the error in the quadratic polynomial we have got norm w infinity and then norm
f triple dash infinity divided by 3 factorial.
So, this is our norm of f minus p 2 infinity which is less than or equal to norm f triple
dash infinity upon 9 root 3 b minus a by 2 cube. So this was for a single polynomial.
Now, we consider Piecewise Quadratic, we look at uniform partition x n is the vector space
of functions which are continuous and which are such that on each sub interval it is a
polynomial of degree less than or equal to 2.
So, the dimension of the space x n is going to be n intervals on each interval a polynomial
of degree less than or equal to 2 that means 3 coefficients so it is 3 n and then interior
partition points are n minus 1 in number t 1, t 2, t n minus 1, you want continuity so
subtract n minus 1 and then you get 2n plus 1. Now, in order to have a unique g n belonging
to x n we need to provide 2 n plus 1 condition, so consider g n which belongs to x n, which
interpolates the given function at t i and also at the mid points of the sub interval,
such a piece wise polynomial is going to be unique.
And now look at the error, so the error for single polynomial was norm f triple dash infinity
upon 9 root 3 b minus a by 2 cube. Look at the interval t i to t i plus 1, so replace
the interval a, b by t i to t i plus 1, then upper bound is norm f triple dash infinity
by 9 root 3 into h by 2 cube, we could have taken maximum for the third derivative only
on the interval t i to t i plus 1. Still it could have provided us an upper bound but
we wanted upper bound which is independent of I, so for each interval t i to t i plus
1 we have got the same bound, so if you take maximum over the whole interval a, b, it is
going to be the same bound and notice that here the error is less than or equal to constant
times h cube. The constant will involve the third derivative
of the function and then the constants 9 root 3 and then it in the denominator. We look
at again the same function f x is equal to root x, for this root x for Piecewise Linear
Continuous Approximation we saw that the in order to have the error to be less than 10
raise to minus 6 we have to choose n to be about 200.
Now, here because our error is less than or equal to constant times h cube definitely
the constant here and a constant in Piecewise Linear these two constantans they are different.
For Piecewise Linear Approximation the constant was depending on the second derivative, now
here it is depending on third derivative, so here for piece wise quadratic the convergence
proved under the condition that f is 3 times differentiable.
So, now we have constant times h cube and then we hope that the accuracy 10 raise to
minus 6 should be achieved for a smaller value of n, because h cube converges faster to 0
than h square, and this turns out to be the case.
And when you do a bit of computation we had calculated up to f double dash, now we have
to calculate f triple dash, so that is going to be 3 by 8 x raise to 5 by 2.
Once again 1 upon x raise to 5 by 2 is a decreasing function on closed interval 1 to 2 and hence,
the maximum will be attend at the left hand point which is 1 and hence, norm of f triple
dash infinity is equal to 3 by 8. Then we get norm of f minus g n infinity which
is less than or equal to a constant into 1 by n cube, so this upper bound will be less
than n raise to minus 6 provided n cube is bigger than 10 raise to 6 divided by 192 into
root 3. So in this case n is equal to 20 will work, the values of n is equal to 200 and
n is equal to 20 these are rough estimates, you can try to find the better estimate.
So, far we had considered Piecewise Interpolation where you were interpolating the function,
now we are going to consider Piecewise Cubic Polynomial which interpolates function values
and the derivative values at the partition points.
So, here the interpolation which we are going to explain, it can be done provided your derivative
values of the function they are also available. This may not be always the case if only function
values are available then we cannot do this Piecewise Cubic Hermite Interpolation.
Now, the method or the methodology is the same, consider the cubic hermite interpolation
and then do that for each subinterval. We have already seen cubic polynomial interpolation,
which interpolates the given function at two end points a and b and its derivative values
at a and b. In order to determine a cubic polynomial,
since there are 4 coefficients to be determined we need 4 interpolation condition, these 4
interpolation conditions can be either 4 distinct interpolation points or 4 points which can
be repeated.
So, we are repeating the left hand point a twice and right hand point b twice. In this
case we had seen, that the error involves the divided difference based on a repeated
twice b repeated twice x and multiplied by function w x which is x minus a, into x minus
b whole square. Already we had seen that maximum of modulus
of x minus a, x minus b, it is attend at the midpoint a plus b by 2, so for the square
x minus a square x minus b square again the maximum is going to be attend at a plus b
by 2 and that gives us a upper bound for the cubic hermite interpolation.
This result for a single cubic hermite interpolation we will apply for each interval and then obtain
a Piecewise Cubic function which is not only continuous, but it is differentiable.
If we had decided to choose four distinct points in each interval, like for linear we
had chosen two points to be end points, for quadratic we had chosen three points which
involve two end points and a midpoint, so similarly for the Piecewise Cubic Interpolation
we could have chosen two end points and two other points in the interior of the interval.
So we get four distinct points, if you do that then because we are choosing the interpolation
points, our interpolation points include the partition points the function will be continuous.
But, then for the Cubic Hermite Interpolation by vary fact that you are interpolating the
given function and its derivative at the two end points our function is going to be continuously
differentiable function. So, you get continuously differentiable function,
you are going to get the error to be less than or equal to constant times h raise to
4, the drawback is you may not know the derivative values at the points t i.
So, what 1 will like to have is have a Piecewise Cubic Polynomial, then because it is cubic,
I can ask for over all continuity to be C 2 continuity that means the function is continuous,
the derivative is continuous and second derivative is continuous, so still I retain the Piecewise
structure and then we will also like to have the order of convergence to be h raise to
4. So that is the Cubic Spline Interpolation,
so we will be considering that and so far we could write down explicit formula for the
polynomials in in terms of the function values for cubic spline we will have to solve a systems
of equation. So, Piecewise Cubic Hermite Interpolation
and Cubic Spline Interpolation are going to be the topic of our next lecture thank you.