Quadratic Spline Interpolation: Theory Part 1 of 2
![I'm on a Mac (I'm on a Boat parody) [Clean]](http://img.youtube.com/vi/PmSwHpK_NrU/2.jpg)
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?
.