Uploaded by numericalmethodsguy on 20.05.2009

Transcript:

.

.

In this segment, we're going to talk about quadratic

spline interpolation.|So I'm just going to talk

about the theory and background of quadratic spline interpolation in this segment.

An example will be shown in a separate segment.|So let's just talk about

the background, or some people might call it the theory, or something like that.

Now, let's go ahead and see what the motivation behind quadratic spline interpolation is.

Now, what is interpolation itself is that somebody's giving you

data points, so let's suppose somebody gives you data points like this and says, hey, what I want you to

do is I want you to do some interpolation to it, and before

quadratic spline interpolation is discussed, we talked about something called linear spline interpolation.

So you have y versus x data given to you.|In the linear spline interpolation, you will

simply draw straight lines from one point to another, that's what you are doing, that's all you're doing.|So you are

just simply drawing straight connecting the dots by using straight lines, and as we observed in

the linear spline interpolation, one of the problems is that there are two issues here.|One is that

that the only information which you are using in order to be able to do interpolation is two consecutive data points.

That means that, for example, when you are drawing this linear straight line, you are not

using any information from these other data points, because in order to able to draw a straight line, you just need the information

from two data points.|The other one is that you are getting discontinuous slope at

the interior data points right there, because just by looking at this graph, you can see that

the slope is changing . . . is changing as you go to the left of the point

to the right of the point, and that is a phenomenon which you are introducing, a numerical phenomenon which you're

introducing, as opposed to it being a physical phenomenon.|So the answer to this question might

be to use quadratic spline interpolants, because it's quite possible that we might

able to answer the question that, hey ,we can use the information

from other data points, and also that we won't get the problem of this slope

suddenly changing from to the left of the point to the right of the point.|So let's go ahead and

describe the problem statement, so what we have is that somebody says

given x0, y0, all the way up to xn,

yn, and says conduct quadratic

spline interpolation . . . conduct quadratic spline

interpolation.

So what that means is that somebody is giving you n plus 1 data points, and what they want you to

do is they want you to develop quadratic splines through the data.

So let's go ahead and illustrate this in a plot.|So let's suppose we're given

y as a function of x, so, and what we're going to do is we're going to show these points, we have x0, y0,

and then we have x1, y1, then we have x2, y2,

let's suppose, and then let's suppose we have x-sub-n-minus-1,

y-sub-n-minus-1, so this is the last but one data point, and then we have

another data point, xn, yn.|Now, what you are finding out here is that all the x values

are in some kind of an ascending order, so if the data is not given to you in that particular form, you

do have to sort it out to put it in that particular form.|Now, in the linear spline

interpolant what we did was we simply drew a straight line from one point to another.|In the quadratic

spline interpolant, what we want to do is we're going to just simply draw a second-order polynomial

going through consecutive data points, that's the only difference.|So what that

means is that, let's suppose if we have . . . if we have this first quadratic

spline here, this quadratic spline will be, let's call it

a1 x squared, plus b1 x, plus c1, that's what we're going

to be assuming, which is the quadratic polynomial going through the first data point . . .

two data points.|Now, through the second we'll have a2 x squared, plus

b2 x, plus c2 going through the second

and the third data point, and so on and so forth, and the last one what we'll have is that we'll have

an . . . yeah, an x squared,

plus bn x, plus cn.|So what you are finding out is that

through two consecutive data points, you have a quadratic spline, or a quadratic polynomial,

going through two consecutive data points.|So you have n plus 1 data points,

that's already given to us, because our data points are starting from x0, y0,

all the way up to xn, yn.|So we have n plus 1 data points, and how many splines do we have?|We have

n splines, okay?|Because we have one spline going through the first

and the second data point, then another spline going through the second and third data point, and the last spline going through

the last two data points, so we have n splines, but in each spline, each quadratic spline, what

you are seeing here is that we have three unknowns.|We have three unknowns

for each spline, so that means that we have 3 n unknowns.|So we have to

find out what the unknowns for each of the splines are.|These coefficients of

the second-order polynomial, a1, b1, c1, a2, b2, c2, an, bn, cn, they're

all unknowns, and what we're finding out that in each spline there are three unknowns, so we have 3 n unknowns,

so what we've got to do is we've got to set up 3 n equations, because

if we have 3 n unknowns, we need to solve 3 n simultaneous linear equations

so that we can find out those 3 n unknowns, and once we have those 3 n unknowns found,

we can then use our knowledge of these

as and bs and cs which we are calculating to be able to calculate the value of the function at any other point

which is of interest to us, and that's what interpolation's all about.|If somebody gives you the values of the function at

at certain data points, and you want to find the value of the function at some other data point . . . at

some other point which is not given to you.|So that is the bottom line of this whole theory about

the quadratic splines is that you have n plus 1 data points, you have n splines, 3 n unknowns, and

we have to set up 3 n equations.|So let's go ahead and see how we can set up these 3 n equations.|Now, the first

thing which you have to realize is that each spline is going through two consecutive data points, so let me draw it

right here, let me just write down it first here.|So the set of 3 n

equations which you're going to do . . . which you're going to get is, part of that is going to come from

this observation that each spline goes through

two consecutive data points.

.

So if you have each spline going through two consecutive data points, so I'm going to draw this again, just

for purposes of illustration, so I'm just going to show you, let's suppose,

these data points which are here.|So here I have a1

x squared, plus b1 x, plus c1, so here I have x0,

comma, y0, and here I have x1, comma, y1, so those are the data points which

I have.|So I can very well see that this particular spline is going through these two consecutive data points, that means that

a1 x0 squared, plus b1 x0, plus c1 should be equal to

y0, as simple as that, okay?|Because . . . and then the same

thing here, a1 x1 squared, plus b1 x1, plus c1

is equal to y1, because this spline here is also going through this particular

data point.|So what you are finding out is since each spline is going through two consecutive data points, so what you're going to

find out is that you will have 2 n equations which are going to come out of this,

because we have n splines, and each spline is going through two consecutive data points, you're going to set up 2 n equations

like that one.|So let's suppose if this was, if I'm going to write a general formula,

if this was x-sub-i-minus-1 and y-sub-i-minus-1, and this is xi,

and this is yi, for example, then what I'm going to get is that,

hey, I'll have this particular spline will be

ai x squared, plus bi x, plus ci, so I'm just taking

a general point i minus 1 and i there.|So in that case, I will

get ai xi-minus-1 squared, plus

bi x-sub-i-minus-1, plus ci will be equal to

to y-sub-i-minus-1, and then I'll have ai xi

squared, plus bi xi, plus ci will be equal

to yi, because as I said, each spline has to go through two pairs of data points, and this is saying

that, hey, it is going through x-sub-i-minus-1, and this is saying that it's going through xi,

and I know that this will be i will be going from 1 to n,

and that's where the 2 n equations are going to come from.

So i will take any value from 1 to n, in fact, if you put i equal to 1, you get this set of

equations which I just showed you there.|So that's where the 2 n equations are going to come from.|So if we have

2 n equations now already taken care of, that means that we needed 3 n equations,

we already have 2 n equations, so n more equations are needed.

So we need n equations again

to be able to set up . . . to be able to set up the 3 n equations.|So where am I going to get these

n equations from?

.

.

In this segment, we're going to talk about quadratic

spline interpolation.|So I'm just going to talk

about the theory and background of quadratic spline interpolation in this segment.

An example will be shown in a separate segment.|So let's just talk about

the background, or some people might call it the theory, or something like that.

Now, let's go ahead and see what the motivation behind quadratic spline interpolation is.

Now, what is interpolation itself is that somebody's giving you

data points, so let's suppose somebody gives you data points like this and says, hey, what I want you to

do is I want you to do some interpolation to it, and before

quadratic spline interpolation is discussed, we talked about something called linear spline interpolation.

So you have y versus x data given to you.|In the linear spline interpolation, you will

simply draw straight lines from one point to another, that's what you are doing, that's all you're doing.|So you are

just simply drawing straight connecting the dots by using straight lines, and as we observed in

the linear spline interpolation, one of the problems is that there are two issues here.|One is that

that the only information which you are using in order to be able to do interpolation is two consecutive data points.

That means that, for example, when you are drawing this linear straight line, you are not

using any information from these other data points, because in order to able to draw a straight line, you just need the information

from two data points.|The other one is that you are getting discontinuous slope at

the interior data points right there, because just by looking at this graph, you can see that

the slope is changing . . . is changing as you go to the left of the point

to the right of the point, and that is a phenomenon which you are introducing, a numerical phenomenon which you're

introducing, as opposed to it being a physical phenomenon.|So the answer to this question might

be to use quadratic spline interpolants, because it's quite possible that we might

able to answer the question that, hey ,we can use the information

from other data points, and also that we won't get the problem of this slope

suddenly changing from to the left of the point to the right of the point.|So let's go ahead and

describe the problem statement, so what we have is that somebody says

given x0, y0, all the way up to xn,

yn, and says conduct quadratic

spline interpolation . . . conduct quadratic spline

interpolation.

So what that means is that somebody is giving you n plus 1 data points, and what they want you to

do is they want you to develop quadratic splines through the data.

So let's go ahead and illustrate this in a plot.|So let's suppose we're given

y as a function of x, so, and what we're going to do is we're going to show these points, we have x0, y0,

and then we have x1, y1, then we have x2, y2,

let's suppose, and then let's suppose we have x-sub-n-minus-1,

y-sub-n-minus-1, so this is the last but one data point, and then we have

another data point, xn, yn.|Now, what you are finding out here is that all the x values

are in some kind of an ascending order, so if the data is not given to you in that particular form, you

do have to sort it out to put it in that particular form.|Now, in the linear spline

interpolant what we did was we simply drew a straight line from one point to another.|In the quadratic

spline interpolant, what we want to do is we're going to just simply draw a second-order polynomial

going through consecutive data points, that's the only difference.|So what that

means is that, let's suppose if we have . . . if we have this first quadratic

spline here, this quadratic spline will be, let's call it

a1 x squared, plus b1 x, plus c1, that's what we're going

to be assuming, which is the quadratic polynomial going through the first data point . . .

two data points.|Now, through the second we'll have a2 x squared, plus

b2 x, plus c2 going through the second

and the third data point, and so on and so forth, and the last one what we'll have is that we'll have

an . . . yeah, an x squared,

plus bn x, plus cn.|So what you are finding out is that

through two consecutive data points, you have a quadratic spline, or a quadratic polynomial,

going through two consecutive data points.|So you have n plus 1 data points,

that's already given to us, because our data points are starting from x0, y0,

all the way up to xn, yn.|So we have n plus 1 data points, and how many splines do we have?|We have

n splines, okay?|Because we have one spline going through the first

and the second data point, then another spline going through the second and third data point, and the last spline going through

the last two data points, so we have n splines, but in each spline, each quadratic spline, what

you are seeing here is that we have three unknowns.|We have three unknowns

for each spline, so that means that we have 3 n unknowns.|So we have to

find out what the unknowns for each of the splines are.|These coefficients of

the second-order polynomial, a1, b1, c1, a2, b2, c2, an, bn, cn, they're

all unknowns, and what we're finding out that in each spline there are three unknowns, so we have 3 n unknowns,

so what we've got to do is we've got to set up 3 n equations, because

if we have 3 n unknowns, we need to solve 3 n simultaneous linear equations

so that we can find out those 3 n unknowns, and once we have those 3 n unknowns found,

we can then use our knowledge of these

as and bs and cs which we are calculating to be able to calculate the value of the function at any other point

which is of interest to us, and that's what interpolation's all about.|If somebody gives you the values of the function at

at certain data points, and you want to find the value of the function at some other data point . . . at

some other point which is not given to you.|So that is the bottom line of this whole theory about

the quadratic splines is that you have n plus 1 data points, you have n splines, 3 n unknowns, and

we have to set up 3 n equations.|So let's go ahead and see how we can set up these 3 n equations.|Now, the first

thing which you have to realize is that each spline is going through two consecutive data points, so let me draw it

right here, let me just write down it first here.|So the set of 3 n

equations which you're going to do . . . which you're going to get is, part of that is going to come from

this observation that each spline goes through

two consecutive data points.

.

So if you have each spline going through two consecutive data points, so I'm going to draw this again, just

for purposes of illustration, so I'm just going to show you, let's suppose,

these data points which are here.|So here I have a1

x squared, plus b1 x, plus c1, so here I have x0,

comma, y0, and here I have x1, comma, y1, so those are the data points which

I have.|So I can very well see that this particular spline is going through these two consecutive data points, that means that

a1 x0 squared, plus b1 x0, plus c1 should be equal to

y0, as simple as that, okay?|Because . . . and then the same

thing here, a1 x1 squared, plus b1 x1, plus c1

is equal to y1, because this spline here is also going through this particular

data point.|So what you are finding out is since each spline is going through two consecutive data points, so what you're going to

find out is that you will have 2 n equations which are going to come out of this,

because we have n splines, and each spline is going through two consecutive data points, you're going to set up 2 n equations

like that one.|So let's suppose if this was, if I'm going to write a general formula,

if this was x-sub-i-minus-1 and y-sub-i-minus-1, and this is xi,

and this is yi, for example, then what I'm going to get is that,

hey, I'll have this particular spline will be

ai x squared, plus bi x, plus ci, so I'm just taking

a general point i minus 1 and i there.|So in that case, I will

get ai xi-minus-1 squared, plus

bi x-sub-i-minus-1, plus ci will be equal to

to y-sub-i-minus-1, and then I'll have ai xi

squared, plus bi xi, plus ci will be equal

to yi, because as I said, each spline has to go through two pairs of data points, and this is saying

that, hey, it is going through x-sub-i-minus-1, and this is saying that it's going through xi,

and I know that this will be i will be going from 1 to n,

and that's where the 2 n equations are going to come from.

So i will take any value from 1 to n, in fact, if you put i equal to 1, you get this set of

equations which I just showed you there.|So that's where the 2 n equations are going to come from.|So if we have

2 n equations now already taken care of, that means that we needed 3 n equations,

we already have 2 n equations, so n more equations are needed.

So we need n equations again

to be able to set up . . . to be able to set up the 3 n equations.|So where am I going to get these

n equations from?

.