Tip:
Highlight text to annotate it
X
In our last lecture, we considered Piecewise Linear and Piecewise Quadratic Approximation.
Today, we are going to consider Piecewise Cubic Polynomial Approximation, so first we
will consider Piecewise Cubic Hermite Interpolation, in that our approximating function is going
to be continuously differentiable, and we will interpolate the given function and its
derivative values, at the partition points of our interval a b.
Next, we will consider Cubic Spline Interpolation, Cubic Spline is going to be a Piecewise Cubic
Polynomial which is overall c 2, that means it is 2 times continuously differentiable
and it will interpolate the given function f its values at the partition point.
In the case of Piecewise Cubic Hermite Interpolation we will show that the error is going to be
less than or equal to constant times h raised to 4, where h is length of the sub interval,
which is b minus a by n if we are dividing our interval a b into n equal parts.
In case of Cubic Spline Interpolation, the error is going to be less than or equal to
constant times h square or constant times h raise to four, depending upon the end conditions
which we imports. In the case of cubic spline interpolation, it will be necessary to add
to the n plus 1 interpolation conditions, 2 more extra conditions which will make our
cubic spline a unique function. For the cubic hermite polynomial, the construction
is going to be straight forward and the error analysis also is straight forward, it will
be like in the case of Piecewise Linear and Piecewise Quadratic Polynomial, the drawback
in Piecewise Cubic Hermite Interpolation is we need to know the derivative values of the
function at the partition points which may not be available, that is why one goes to
Cubic Spline Interpolation.
Let, me recall Cubic Hermite Interpolation, so when we have a function f defined on interval
a b to real line, look at p 3 to be a polynomial of degree less than or equal to 3, such that
p 3 at a is equal to f of a, p 3 at b is equal to f of b and p3 dash at a is equal to f dash
a, p 3 dash b is equal to f dash b, where dash denotes the derivative.
So, that means we need to assume the function f to be differentiable, we have seen that
p 3 x can be written in terms of divided differences as f of a plus x minus a, f dash a plus divided
difference based on a a b, the point a is repeated twice multiplied by x minus a square
and plus the divided difference based on 4 points a a b b, a repeated twice b repeated
twice x minus a square, x minus b, the error f x minus p 3 x is given by f of a a b b x
multiplied by x minus a square, x minus b square for x in the interval a to b, so this
is the error. Now, if f is 4 times differentiable then we
can write the divided difference as fourth derivative of f evaluated at some point c,
c is going to depend on x divided by 4 factorial x minus a square, x minus b square.
Now, we look at the maximum error, so maximum of modulus of f x minus p 3 x, x belonging
to a b to be less than or equal to maximum of mod of f4 x divided by 4 factorial x belonging
to a b and multiplied by maximum of modulus of x minus a, x minus b square x belonging
to a b. Thus, norm of f minus p 3 infinity norm is
going to be less than or equal to norm f 4 infinity divided by 4 factorial and the maximum
is going to be attend at the midpoint a plus b by 2, so that will giveus b minus a by 2
raise to 4. So, thus we have obtained the upper bound
an upper bound for the cubic hermite interpolating polynomial, this upper bound we are going
to use for finding an upper bound for the error in the Piecewise Cubic Hermite Interpolation.
So, it is this bound is applicable on interval a b, so the same bound we will use with interval
a b replaced by interval t i to t i plus 1, where i going from 1 to up to n minus 1 and
that will give us the an upper bound for the error in the Piecewise Cubic Hermite Interpolation,
f defined on interval a b taking real values the differentiability property of f which
we are going to need is, f should be 4 times differentiable on a b and the fourth derivative
should be continuous on interval a b, because we are going to take the maximum of mod of
f4 x for x belonging to a b. We look at uniform partition a is equal to
t 0 less than t 1 less than t n is equal to b, t i plus 1 minus ti which is length of
the sub interval which is equal to h, that is b minus a by n. Let us, look at x n to
be set of all f or let me write g, set of all g belonging to c 1 a b, so the all functions
which are continuously differentiable, such that g restricted to t i to t i plus 1 is
a polynomial of degree less than or equal to 3, then the dimension of x n is equal to
we had done such calculation before, on each interval it is a polynomial of degree 3 degree
less than or equal to 3 so we have got 4 degrees of freedom, there are n intervals, so it will
be 4 n minus, there are n minus 1 interior nodes t 1 t 2 t n minus 1.
We want the function to be continuously differentiable that means at each of the interior node we
are putting 2 constraints, so then those 2 constraints they will decrease the dimension
of our spline, so it will be 4 n minus 2 into n minus 1, so that is going to be equal to
2 n plus 2, so we have dimension of x n to be equal to 2 n plus 2. If we consider a value
of function f at t i's and the derivative values at t I, we have got n plus 1 partition
points and if we say that, look at a function g which is going to be continuously differentiable
and which is Piecewise Cubic on the interval t i to t i plus 1 and it interpolates our
function f and derivative at this n plus 1 points.
So, dimension of our space is 2 n plus 2, we are putting 2 n plus 1 condition, 2 n plus
2 conditions and then such a function is going to be unique. We have f is from a b to R and
g n should belong x n, such that g n at t i is equal to f at t i and g n dash at t i
should be equal to f dash at t I, i going from 0 1 up to n, so we have this is our partition
and we are specifying at all the partition points value of g n at t i and value of g
n dash at t i. So, by vary construction our g n is going
to be belonging to x n and g n x will be given by on the interval t i to ti plus 1, because
it is a cubic polynomial it is g n at t i plus g n dash at t i into x minus t I plus
g n t i, t i, t i plus 1 the divided difference into x minus t i square plus divided difference
based on 4 points t i, t i, t i plus 1 t i plus 1, x minus t i square x minus t i plus
1.
So, exactly similar formula as on the interval a b only now the interval is t i to t i plus
1. We had found the bound for the interval a b and that bound was norm of f minus p 3
infinity norm to be less than or equal to norm f 4 infinity divided by 4 factorial b
minus a by 2 raise to 4 and hence, maximum of mod of f x minus g n x, x in the interval
ti to ti plus 1, this will be less than equal to maximum of mod of f4 x, x belonging to
t i to t i plus 1 divided by 4 factorial and then we have to replace b minus a by h, so
we are going to have h by 2 raise to 4. Now, this will be less than or equal to norm
f 4 infinity divided by 4 factorial h by 2 raise to 4, the bound which I am writing now
that is true for each i and hence, when we look at maximum of mod of f x minus g n x,
x belonging to a b this is going to be equal to maximum over i maximum of mod of f x minus
g n x, x belonging to t i to t i plus 1, 0 less than or equal to i less than or equal
to n minus 1, which will be less than or equal to norm f four infinity by 4 factorial h by
2 raise 4 and this is norm f minus g n infinity this is the error for Piecewise Cubic Hermite
Interpolation.
Let us, recall the bounds for Piecewise Linear and Piecewise Quadratic, so in case of piecewise
linear, our function was continuous and the error it was less than or equal to constant
times h square where the constant involved the second derivative, in case of piecewise
quadratic again the function is continuous and the error now is less than or equal to
norm f triple dash infinity that means the third derivative is coming into picture divided
by 92 root 3 into h cube and now for Piecewise Cubic Hernite Interpolation our function is
continuously differentiable and the error is less than or equal to constant times h
raise to 4. So, the constants in the 3 cases they are
going to be different but these are the constants which are independent of h, so in case of
cube Piecewise Cubic Hermite Interpolation we have got the error to be constant times
h raise to 4 which will tend to 0 faster than in the case of Piecewise Linear and Piecewise
Quadratic Polynomials and in addition our function is continuously differentiable. The
approximating function is continuously differentiable, the only problem is the derivative of f at
t i's they may not be known. Next we go to cubic spline interpolation,
we want our approximating function to depend only on the function values at the partition
points and if possible we will like to make our function to be 2 times differentiable.
When we looked at joining of 2 polynomials together we have seen that if you join 2 cubic
polynomials together in c 2 fashion still we retain the piecewise nature of our function
on the other hand, if we say that the there are 2 cubic polynomials and you join them
together, such that the function value derivative value second derivative and third derivative
values they should match then it has to be a single polynomial.
So, the best we can do by still retaining the Piecewise nature is a Piecewise Cubic
Polynomial which is 2 times continuously differentiable, now here the construction of such a function
is going to be little more complicated. So, far we could write we could look at the
divided differences and then we could write down the explicitly our Approximating Polynomial
or Approximating Piecewise Polynomial.
Now, here in case of cubic specific line interpolation, so look at as before the uniform partition
and look at the space x n to be set of all f belonging to c 2 a b such that f restricted to t i to
t i plus 1 is a polynomial of degree less than or equal to 3, i is equal to 0 1 up to
n, dimension of x n is going to be 4 times n minus 3 times n minus 1, n intervals on
each interval a polynomial of degree less than or equal 3, so that is why 4 n degrees
of liberty and then at the interior partition points t 1 t 2 t n minus 1, we want the function
to be 2 times differentiable , so that is why you have got minus 3 into n minus 1, so
then that is going to be equal to n plus 3. Suppose, our function f is defined on interval
a b to real line and look at g n belonging to x n such that g n at t i is equal to f
at t i, i is equal to 0 1 up to n, so these are n plus 1 conditions.
The dimension of the space is n plus 3, so in order to have such a unique interpolating
function we will need to add 2 conditions, now these 2 conditions generally they are
put at the 2 end points and those are the end conditions.
So, we will come to the end conditions little later, let us look at the construction of
g n, on the interval t i to t i plus 1, g n is going to be a polynomial of degree less
than or equal to 3, so suppose you have got g n at t i and g n at t i plus 1 they are
already fixed they are equal to f is our function which is given to us so g n at t i is equal
to f at t i g n at t i plus 1 is equal to f at t i plus 1, treat the derivative values
g n dash at t i and g n dash at t i plus 1 as unknowns and use a fact that our g n is
going to be 2 times differentiable to get a relation which will be satisfied by g n
dash t I, so the unknown s g n dash t i they will be obtained by solving a linear system
of equations.
And then once you get g n dash t i on the interval t i to t i plus 1 our polynomial
of degree less than or equal to 3 will be determined, because we know g n t i g n dash
t i g n at t i plus 1 g n dash at t i plus 1, so let me explain how we are going get
the relation, so let us look at 2 intervals, so this is our interval t i to t i plus 1
and this is interval t i minus 1 to t i. Here, let me denote the polynomial by p i, so that
is g n restricted to t i to t i plus 1 the polynomial here we denote it by p i minus
1, so it is going to be g n restricted to t i minus 1 to t i.
The polynomial p i we are going to write in terms of the value of g n at t i and value
of g n dash at t I, so at present the derivatives are unknown, so we have got p i x to be equal
to the same cubic hermite polynomial g n at t i plus g n dash at t i into x minus t i
plus divided difference based on ti, ti, ti plus 1 x minus t i square plus g n ti, ti,
ti plus 1, t i plus 1 x minus t i square, x minus t i plus 1.
So, how is it different from the cubic hermite interpolation. In case of cubic hermite interpolation
we wrote exactly the same formula but g n dash at t i was given to us, g n dash at t
i was equal to f at t i. Now, in our case g n at t i is going to be
equal to f at t i that is given to us but at present g n dash at t i they are going
to be unknown, so this is we have found or we have written down a formula for the cubic
polynomial in the interval t i to t i plus 1 in terms of g n at t i g n dash at t i of
which g n dash t i are unknown. Now, you look at the second derivative, so we can calculate
p i double dash x, you calculate the second derivative and then you look at p i double
dash of t i plus and p i double dash at t i plus 1 minus, we have got a formula for
pi x take its second derivative, the second derivative will be in terms of again g n at
t i and g n dash at t i, I have written p i double dash t i plus, because our p i is
defined on the interval t i to t i plus 1. So, the second derivative is at t i is going
to be the right handed derivative and at t i plus 1 it is going be left handed derivative
so we calculate these values, then from here we write p i minus 1 double dash t i minus
1plus and p i minus 1 double dash t i minus, so once we obtain the formulae for this you
have to just shift replace i by i minus 1 in order to get this expression, now this
continuity of second derivative comes into picture. What we want is? We want p i double
dash at t i plus is equal to p i minus 1 double dash of t i minus the value of the second
derivative from the right and the value of the second derivative from the left, we equate
these 2 and that is going to give us a relation which the derivatives they should satisfy.
So, now what comes is the technical thing like I have explained to you what is the idea
and now let us work out the details look at the interval t i to t i plus 1 and then we
have written g n x in terms of g n t i g n dash at t i and then the divided differences,
these divided differences they also will be in terms of the g value of g n at t i and
value of g n dash at t i. Now, look at the derivative, so when you take the derivative
you get g n dash at t i the g n at t i is constant so the derivative term vanishes,
then we have g n dash at t i plus the divided difference based on t i, t i, t i plus 1 the
derivative of x minus t i square which will be 2 into x minus t i plus the divided difference
based on t i, t i, t i plus 1 t i plus 1 and then the derivative of x minus t i square,
x minus t i plus 1 that is going to be 2 times x minus t I, x minus t i plus 1 plus x minus
t i square, so we have found the first derivative.
Now, you differentiate once more to get the second derivative, so when you look at the
second derivative g n dash at t i being constant, its derivative will be 0, derivative of x
minus t i will be 1, so that gives usterm 2 times divided difference based on t i, t
i, t i plus 1 plus divided difference based on t i, t i, t i plus 1 t i plus 1 and then
the derivative. So, we are going to have 4 times x minus t
i plus 2 times x minus t i plus 1, so this is expression for the second derivative of
p i on the interval t i to t i plus 1 and p i is nothing, but restriction of g n to
the interval t i to t i plus 1, the value of p i double dash at t i from the right that
is given by putting x is equal to t i. So, when you do that you get the expression
on the right, the term x minus t i vanishes, x minus t i plus 1, so that is t i minus t
i plus 1 that gives us minus h. Next, you put x is equal to t i plus 1 in
the expression then you get 2 times g n t i, t i, t i plus 1 the divided difference
plus 4 h times divided difference based on t i, t i, t i plus 1 ti plus 1. We want to
equate pi double dash at t i plus and pi minus 1 double dash at t i minus, so in the expression
for pi double dash at t i plus 1 minus replace i by i minus 1, so you get it to be equal
to 2 times g n divided difference based on now t i minus 1 t i minus 1 t i plus 4 h times
divided difference based on t i minus 1 and t i repeated twice
And now we will do the simplifications, so look at pi double dash at t i plus use the
recurrence relation for the divided differences, so the divided difference g n t i, t i, t
i plus 1 will be g n t i, t i plus 1 minus g n dash t i divided by t i plus 1 minus t
i which is going to be equal to h. Then, similarly use the recurrence relation
for the divided difference based on ti and ti plus 1 repeated twice do the simplifications
and you get the second derivative to be 6 times divided difference based on t i, t i
plus 1 minus 4 times g n dash t i minus 2 times g n dash t i plus 1 divided by h.
The simplification of p i minus 1 double dash at t i minus gives us minus 6 times g n t
i minus 1t i plus 4 times g n dash t i plus 2 times g n dash t i minus 1divided by h.
Look at the expression 6 times g n t i, t i plus 1 in p i double dash t i plus, so that
divided difference is going to be g n at t i plus 1 minus g n at t i divided by h and
we know that g n at t i has to be equal to f at t I, so that is known.
Whereas, g n dash t i minus 1 g n dash t i g n dash t i plus 1 these are unknowns, so
we will equate these 2 expressions, on the left hand side we will leave the unknowns
which involve the derivatives of g n and on the right hand side we will have the function
values of g n at t i which are known.
And thus, equating we get the system to be g n dash t i minus 1 plus 4 times g n dash
t i plus g n dash of t i plus 1 is equal to on the right hand side we have g 3 times g
n of t i plus 1 minus g n of t i minus 1 divided by h and which we denote by beta i. Here i
is going to vary from 1 2 up to n minus 1, because the equating the second derivatives
that we need to do only at the interior node points.
This was our uniform partition t 0 t 1 t 2 t n minus 1 and t n, we want g n to be in
c 2 a b, g n restricted to t i to t i plus 1 it is a polynomial of degree less than or
equal to 3, so on the interval open interval t i to t i plus 1, our g n will be infinitely
differentiable, it being a polynomial. When you look at say interval t 1 t 2 and
t 2 to t 3, here we have one cubic polynomial say p 1 here you have another cubic polynomial
p 2, so on the open interval t 1 to t 2 p 1 is infinitely many times differentiable.
On the open interval t 2 to t 3 p 2is infinitely many times differentiable, the problem is
the partition point t 2 that is where the 2 polynomials we are joining them together.
So, thus what will come into picture will be the interior partition points t1 t 2 t
3 t n minus 1, when you look at t 0 there is nothing on the left for t n there is nothing
on the right, so that is why we need to equate the second derivatives only at the interior
node points.
We have got a system of equations g n dash at t i minus 1 plus 4 times g n dash t i plus
g n dash of t i plus 1 is equal to beta i, i going from 1 to up to n minus 1, so these
are n minus 1 equations, whereas unknowns are going to be g n dash at t 0, g n dash
at t 1, g n dash at t n, so we have got n plus 1 unknowns.
So n minus 1 equation and n plus 1 unknowns, so it is going to be undetermined system and
we will have 2 variables to be free and hence, in order to do the fix the uniqueness or in
order to determine g n uniquely we add 2 extra conditions.
So, now the first one the first extra condition we do is that, suppose you know the derivative
value at 2 end points, if we know derivative value at all the partition points then we
have cubic Piecewise Cubic Hermite interpolation.
Now, suppose your function values they are known at t 0 t 1 t n and only at the 2 end
points we know the derivative of the function, then in that case let g dash at t 0 be equal
to f dash at a, g dash at t n to be equal to f dash at p n, so then our unknowns are
only g dash t 1 g dash t 2 g dash t n minus 1, so we have got n minus equations in n minus
1 unknowns and then the system of equations its coefficient matrix is diagonally dominant
matrix. So, if the matrix is diagonally dominant then
it is invertible and hence the system of equations will have unique solution and thus we calculate
g n dash at t i at i is equal to 1 2up to n minus one by solving this system of equations.
The right hand side it is known and this is known as complete cubic spline interpolation
,in this case what one can show is that if your function f is 4 times differentiable
then the error is going to be less than or equal to constant times h raise to 4.
Now, this proof of the error it is a bit involved and I am going to skip that, but let us look
at another end condition that end condition is known as the natural end condition.
So, in this case we have got the we consider or the end condition which we put is second
derivative at 2 end pointsit should be equal to 0, so g n is the approximating function
which is Piecewise Cubic, it is 2 times continuously differentiable and we put that g n double
dash at a is equal to g n double dash at b is equal to 0. This condition is known as
natural end condition, because it comes from a minimization problem. When the cubic spline
they were discovered, they were considered or they came as solution of a minimization
problem, but what happens is these conditions they are arbitrary in the sense that we are
trying to approximate a function f, this function f may not have second derivatives to be equal
to 0 at the 2 end point. So, if this is not the case then our natural
end conditions they will have the error to be only less than or equal to constant times
h square, so see in case of Piecewise Linear Interpolation we had the error to be less
than or equal to constant times h square and it is much easier to construct Piecewise Linear
Interpolation. Of course for Piecewise Linear Interpolation we had only continuity now this
function is going to be 2 times continuously differentiable, but still there is a loss
of order of convergence, so then one looks at what one will have like to have is the
best of both that your error should be less than or equal to constant times h raise to
4 and it should depend only on the function value, may be even the derivative values at
the two end points are also not known, so that gives raise to one more condition, so
before we consider that condition which depends only on the function values and which has
order of convergence h raise to 4.
Let us, quickly look at the system of equations in case of the natural end conditions, so
we have g n double dash at a is equal to g n double dash at b is equal to 0, g n double
dash at a is going to be second derivative p 0 double dash at p 0 plus, so we have got
the formula, so you substitute that formula we had the formula for p i double dash at
t i plus in that formula you put i is equal to 0 and then we get the formula which involves
the value of the function g n at t 0 and t 1 and value of the derivative of g n at t
0 and t 1 keeping on the left the unknowns g n dash t 0 and g n dash t 1 and on the right
hand side the known values which are g n t one and g n t 0, they are respectively equal
to f at t 1 and f at t 0, so we get an equation. Similarly, look at the g n double dash b is
equal to 0 and obtain an a condition which involves the derivatives of g n at t n minus
1 and t n and a function values, so we get 2 additional equations, we already had n minus
1 equation to that add these 2 equations, so total there will be n plus 1 equations
in n plus 1 unknowns with the coefficient matrix to be diagonally dominant and hence
invertible.
So, here is the coefficient matrix, it is a tri diagonal matrix with diagonal entries
to be 2 in the first and last row and all other diagonal entries to be equal to 4, sub
diagonal and super diagonal entries are equal to 1, n plus 1 equations in n plus 1 unknowns,
so 1 solves those gets g n dash at t i's, g n at t i they are equal to f at t i and
that will completely determine Piecewise Cubic Polynomial which is c 2.
Look at the order of convergence, so as I said for complete Cubic Spline Interpolation,
it is constant times norm of f minus g n infinity norm to be less than or equal to constant
times h raise to four for the natural end conditions, it reduces two constant times
h square, so we look at one more condition which is known as not a knot condition, so
in this case what we do is we look at the partition points t 1 and t n minus 1 only
2 partition points. At these partition points we say that the function should be 3 times
continuously differentiable. So, at all other partition points it is only
twice differentiable, but at t 1 and t n minus 1 we say that it should be three times differentiable,
so in the interval t 0 to t 1it is a polynomial of degree 3, in the interval t 1 to t 2 it
is a polynomial of degree 3, then when you say that third derivative should match then
it is going to be only a single polynomial in the interval t 0 to t 2 and in the interval
t n minus 1, t n minus 2 to t n similarly it is going to be a single cubic polynomial,
so such a polynomial is going to be unique and in this case the order of convergence
it is restored to h raise to 4. Now this completes our polynomial interpolation.
Our next topic is numerical integration, so what we are going to do is now we have got
interpolating polynomial, so the function f x is equal to interpolating polynomial p
n x plus there is some error, then integral a to b, f x d x is going to be approximately
equal to integral a to b, p n x d x, p n is the interpolating polynomial interpolating
given function at x zero x one x n, so depending on the choice of n and choice of the interpolating
points we are going to get different numerical quadrature rules, so this going to be the
topic of our next lecture.