an exam now on I know that's a long homework and that has the kind of the
second homework mm-hmm maybe um okay well it would have been better if I cut
it into like two short homeworks or not
yeah instead of having the whole thing wait for two weeks and cut it in half
and would be better yeah okay it's harder to manage a big chunk of time
yeah so okay then content Lee speaking how is the homework how do we feel is it okay too hard
easy who dare to say that
was that okay the other cousins is horrible is too hard I mean I thought so
the program is the program means non-trivial above your first so that's
that I mean yeah that's just more tedious than anything the coding or
debugging yeah interpolation antics forever yeah okay so what is this this
times this times this I mean I like hard it just takes a while
okay yeah what you want to say oh that's a tricky one I know which one you're
asking has chicken yeah the Taylor expansion the local truncation error
that's chapter one the interpolation yeah okay so sometime during the weekend
maybe tomorrow morning or sometime I'll put the answer on angel it will be a
very detailed answer with words and just detailed all right so read it and also
in the other class a student complain about the the last problem the Newton's divided difference the coding was a
non-trivial maybe I could have been more instructive I think maybe the lab
session like just fix it on Friday doesn't really work because I don't know I'm Friday you're ready to deal with
this or not and or or we wait a week and on the Friday to pick up that thing
which it's too late for Tony in the homework right so
um you will have my codes in the answer for that homework okay so if you had
trouble writing that piece of code and then you might want to look at my code
and see how I did it and try to understand why I did this and why I did
that and any question come and ask me okay it's okay so yeah okay all right so
um now next Monday we have a computer lab mm-hmm I want to catch your
attention the room is to one four that's not the room we were right don't go
downstairs its second floor I think so give yourself a couple of minutes to
find that computer room how do that also and then we'll meet there so we'll
finish kind of a kind of a finish today on cubic spline at least a derivation of
the algorithm and it will be on the homework number three the homework
number three is a much shorter homework but there is a program in part on cubic
spline so it's perfect timing that we finish it today and and then you get help on that on Monday okay so to make
the lab session more efficient I will ask you to do the following then the
homework three is already on Angel take a look at it make an attempt try to see
what you have to do kind of a prepare yourself so what questions you will have
and then on Monday I will tell you a few hints of what to do and hopefully during
the lab session you can finish the programming part for homework three is
that okay sounds like a plan so don't come in and
try to hold words homework three or what do I have to do and then you sit there
15 minutes you're reading it you don't get help okay
so prepare yourself right okay that's that so let's go into cubic spline
so it's a kind of a heavy class a heavy in the sense that I have to write a lot
my arms already sore okay we will try to derive an algorithm that will compute the natural cubic spline so last time we
set up so let's kind of a put the beginning pot so we call these the eyes
equal to second derivative of actually it's just as at CI right so we say we
started from the second derivative and we try to go back we integrate once and
twice and go back so these are the Z is the second derivative and because it's
natural so we have those two additional conditions c1 is the end right right and
I also have the notation H I will be the interval length between two neighboring
knots and then we wrote out the Lagrange form
for the s double prime which we did last time so let's write it again so we'll be
focusing on the interval from TI to TI plus 1 so we're writing everything on
that interval okay is a generic index okay so let me write it in this way so Z
I plus 1 over home H I x minus TI minus
Zi and I X minus T I plus 1 so that's the Lagrange form so what we're going to
do today will be our integrated twice integrate twice okay so which means I can integrate once to get s Prime and
then you integrate again you will get S is all right so the goal is to reach
this si so you know each time you integrate you obtain an integration
constant so you do twice you have two integration constant these are arbitrary
constants right they're arbitrary in value and also there is some hard assign
a little bit kind of arbitrary the way you write it as long as you have two
constants okay so so I will have a say that there will be two arbitrary
constants okay and I will write them in the following way
so this is one of the little trick I said there will be various tricks along
the way so this is one of them this special way of writing those integration
constants so as I Prime
you'll be integrating this once I will write it in the following way so see I
plus 1 over 2 H I x minus TI square minus Zi 2 H AI X minus 2 I plus 1
square and I know I need some constants right so instead of writing one constant
I write it as this sei a constant minus di that's another constant so adding
them together it's still a constant okay so that's 1 and then I'm going to write
si in this one integrating this one more time I get the following Z I plus 1 over
6 H 5 X minus GI 3 minus CI 6 h pi x minus TI plus 1 cube plus CI x minus TI
minus bi x minus t okay oh gosh so long okay so you would
say you would you might ask well why do you write them like this well you know
you have two arbitrary constants how many constant do I have I have two
arbitrary constants right and you can go and verify that if I differentiate this
expression here do I get the derivative meaning is this an antiderivative of
that function do we see that it does the job if you differentiate this would you get three
times this square right three with six cancels you got two exactly do we see
and you differentiate that three cancel six you got two and the power reduces to
two right and you differentiate this one you can see I when you differentiate this one you get negative di so this is
an antiderivative do you see and how about this expression if I differentiate this once do I get three s double prime
there do you see you differentiate this you get two times x minus TI two cancels
the two you just get this thing x minus TI is that right and you differentiate
that and you exactly get this one and those two constants you differentiate
they're gone do you see so you can verify
verify the the differentiation relation or the anti-derivative relations so you you take your ESI you differentiate and
you verify that's okay can you take your SI pry and you
differentiate it once when you verify that it's okay
okay so that's the correct antiderivative twice so the advantages
of writing it in this form will come very soon so okay so so far what do we
know we know that the second derivative is continuous right Zi Zi they are
actually unknown at the time being but we just call them the eyes but to
qualify as a cubic spline there are many many other properties it must satisfy so let's go through some of these
properties so important first important is that it has to interpolate right
interpreting properties so on this interval from TI to TI plus 1 I have
this function si it must interpret at the 2 and all right so if you look at si
evaluated at TI this must equal to Y I agree mm-hmm and then second if I look
at the the right end of this interval TI plus 1 and this must interpret the data
which is why I plus 1 there right so those two must be satisfied okay so
let's check
so the first one okay so I'm going to use this expression here and I will put
in x equals 2t I that clear so now you see if I put in x equals 2t I what
happened to the first term zero and what happened to that term is zero
agree so and this show you go to Y I so I have Y I equals to the first term is
zero what about the second term if x equals 2t I what is TI minus TI plus 1
negative H I is that right can I put that in right away I'll be okay
VI over six H I and then I get a negative H hi to the cube is it okay
okay and then if it equals 2t I that's zero so nothing to do and then if it equals to TI and this is again a
negative H I say right so that gives me um plus actually di inch
okay okay so we see that this actually cancels one power of it and I get a
square mm-hmm and then in this whole expression let's write it one more time
to be cleaner so why I equals to negative zi h i square plus di h i okay
i just rewrite it so it's cleaner so you see if the eyes are given then i can use that to compute to the eye because yih i
they're beta i know them right question yeah there is a six okay
I lost the six yep what if you cubed it first then one of the negative signs counts tomorrow yeah I lost
there's no no yeah it's not a dumb question
now it's correct right so can we solve this for di and write the I in terms of
the others mm-hmm so I could divide both sides by H I right so I get Y I over H I
- and then I move this term over this gives me Z I gotta H high over six okay
that's that and then let's do the second interpolating property so if I put in T
I plus one for each X I should get Y I plus one so we see that this term will be zero and that term will be zero so
from the experience we had we already know in the end I would just get CI in
the expression right okay so this gives me to Z I plus 1 over m so this will
give me H Q price illness put it to bhi square I canceled an H I and that's 0 and this will be CI time H I is that ok
and then I do the same thing I now write it CI in terms of the others y plus 1 over h pi minus z pi plus 1 H PI over 6
yep we okay
so what have we achieved we find the expression for CI and di right so in
terms of Z so Z we don't know yet so but at least I can say now if I know
Z if the eyes are fond which we will find then I can plug that in and I can
find all the sea-ice and all the the eyes
is that right they can be computed and once I have the CI in the eyes I can
plug them in I can find s I and s Prime I do we see okay and this will allow me
to compute the SI of X and the s prime I of X ok so let me be painful and write
it out so how write out now yes I of X I'll be
just copying that thing and plug in the CI & di with these expressions okay
so it's Zi plus 1 over 6 h pi x minus TI cube - ok and z i6 h i x minus TI plus 1
that's the first two times and then i put in the CI which is that's my c which is multiplied with x minus TI let me
come over then now I putting my D which is one I over h i- z IH pi over six x -
2 pi plus 1 so if the sea-ice are found then you know your spline agree that's
the expression each si is not given okay and also the derivative is given so
let's try this out so this actually I have to write out now
this it's useful to write it out because you have to code this ok no you don't
have to I didn't tell you the code for natural cubic spline will be provided to
you for the next homework so your job will be understanding the derivation today and knowing what has to go into
the code and then you read this piece of code and understand what it's doing so
you know how to use it all right it's a bit easier okay
all right but okay this piece you will see it will be coded okay in the program
that will give it they'll be given to you
okay so then I have some now this as prime is actually important I have to
write it out minus zi over to H I of
plus so what would I be adding here will be a is CI - Adi right what's here is
the CI - di so what I will be doing will be um I will join the terms with y together and join the turns with Z
together that okay I'll be writing this - that okay so why I plus 1 minus y I
over H AI minus Zi plus 1 minus zi / 6h I
is that okay so that's the way I wrote it
okay and this time here why join them together well that's actually my data
do you realize once your tea eyes and your Y eyes are given the H eyes are
given it's just here I plus 1 minus e I and then this expression is given right
so that's kind of a the data so instead I'll keep writing this tongue over and
over I'm gonna call this guy a shorthand this is my B I is that okay
so they don't just write B I to be bit easier okay so now we say if the C eyes
are given I can write s and s prime like this so keep keep your heads cool and
review it what have I done what the informations what conditions I have
already used and is there something that I haven't used yet so for a cubic spline
the definition says it has to satisfy a bunch of conditions right first of all
he has to interpolate the data which is guaranteed we check so the function is
continuous right and also there are continuity's of the derivatives are they
satisfied have we checked all of them
hmm I showed the check that the Z's are equal to zero these one no these are
given they are set to be zero that's a boundary condition yeah so for
cubic spline k equals to 3 right 3 minus 1 is 2 which means first derivative has to be continuous second derivative had
to be continuous of your spline function is that right so do we need to worry
about the second derivative what it always be continuous
yes because we started with a linear spline for that so what's missing which
one I haven't checked the first derivative so must so the last condition
but we haven't used is continuity of s Prime right at the knot ok so this means
I need to verify the following at the knot TI mm-hmm
so from the left that's the derivative of the spline from the left at TI must
equal to the derivative of the spline from the right the right and this holds
I from zero zero in the inner knots 1 2 2 n minus 1 exactly we haven't checked
that right we haven't imposed that condition ok let's see what does that
give me if I do so
oh that's the okay so I use the space right next to it okay so you see the connection
hot connection
all right so I think that shall be good space okay so let's write out as I Prime
at T hi what does that equal to because I have
to set that equal to the other one so s prime is given here I'm going to put in
x equals to TI and I see that guy is zero and so convenient you see our
brilliant idea of writing into X minus the eyes right that's zero and I only
have this turn if it's t i TI minus TI plus 1 that's H I right squared okay and
then these are the fixed stuff okay so I would have first a zero the second I
will have if this is H I and it cancels one so I get u- h i over to see i there right okay
that's all I have get from that mm-hmm
plus okay those two times so let me write the BI so it's quick and then - um Zi plus one minus Zi over six times
H who's that okay so that's that and then
I need to also figure out um the thing on the left so I need a step so let's
write out this guy here so it's this function when I reduce the index by one
right because I need index I minus one so let's take a step so try this out
with the index and it's become one less so this will be zi over 2 H minus one
times X minus T PI minus 1 square and then just reduce all the index by one
plus this will be PI minus 1 by Z I VI minus 1 over 6 H by minus 1
all right that's the derivative as a function so let's now put it on putting on x equals 2 TI okay so when x equals 2
TI and i see that this guy is 0 here I minus the answer that tone is gone I only have that time TI minus TI minus 1
what is that H I minus 1 right 1 index less so
cancels one of this I get by Z PI over 2 H I minus 1 J right ok and then with
others so be PI minus 1 minus TI minus TI minus 1 over 6 h pi minus 1 okay you
know it's a bit tedious now we need to set them to be equal to each other ok so
now I do the following I do on s prime minus 1 prime TI minus s PI prime TI the
question zero is that ok I take this and subtract that and set it to be 0 ok so
which I'll do here
alright okay so um I have the eye let's see Zi is my unknown okay let's do
that first / - mm-hmm okay the B eyes I'll take
care of them later okay so - VI - Zi minus 1 over 6 times H R minus 1 so I
took care of this time and that time right and then subtract the other negative negative is positive
take your H I VI / - mm-hmm I'll take care of the eye later and then I get
plus Zi plus 1 minus VI / 6h hi okay since the V eyes are my data they don't involve any of my unknowns I'll move
them to the right hand side is that okay if I move that to the right hand side if
you move this to the right hand side it's negative this is negative because
it's - move to the right hand side is positive so bi minus B by - what
that okay okay it's annoying to have that fraction expression how about I
multiply the whole thing by six so I get rid of the fraction can we do that let's do that how so I'm gonna mess it up so
I'm gonna multiply by six which means this 2 is not there actually I have a
three and then I want to get rid of this six okay so I got that and then the two
is not there I get a three I get rid of the six I have a bracket and then this whole thing is multiplied by a six I'm
sorry we're squeezing in okay and let's collect like terms so on the left hand
side so okay keep our heads cool what's my unknown
what am I trying to solve here I'm trying to solve for H I chose the eyes
CI is on my unknown right so I want to write them in terms of the unknown zi
okay the like terms so how many different Z eyes there are on the on the
left hand side I have the I minus 1 and I have zi appear a couple times and I have a Zi plus one lose all right I'm
gonna collect these like tones okay so for Zi minus one what do I have
what's the coefficient in front of it
did I mess up with a sign
I think so did I
I know I didn't so the I minus one negative negative positive times h pi
minus 1 that's the coefficient in front it is that right okay what about the I so for the I how many times do I have I
have 3 times H I minus 1 minus 1 times H I minus 1 which gives me 2 times H I
minus 1 okay keep that in your head and look at here I have 3 h i- nhi which
gives me 2h i right so the 2 is a common factor and then i have h pi minus 1 plus
h I is that ok and then for the I plus 1 I have only one ton what is its coefficient is H I
okay on the right hand side six times VI minus VI minus 1 and the index I runs
from one two three all the way to n minus one so in principle you have n
minus 1 equations linear equations right so what are you doing MATLAB you make
this into a matrix times a vector isn't it can we do this so matrix electric form
okay so this takes some time to write out so much
- big matrix we need a big matrix here and give me more space I never have
enough space for this matrix and my unknown and my right hand side my right
hand side is easy so my unknown I know are diseased so be e 1 Z 2 Z 3 all the
way to on that's right one of Z on and minus 2 and Z and minus 1 that's your
last one okay and then I put the right hand side in sort of six of when Z one
its Z 1 and what do I get is B 1 minus B 0 6 a 2 minus B 1 6 b3 minus b2 this is
the easy one and all the way down to 6 be home
and minus one minus B and minus two
okay okay so what about this coefficient matrix we'll try to fill in here okay
let's look at the first equation that I will fill in here so for the first
equation I equals to 1 this will be Z 0 right so what is Z 0 Z 0 is 0
that's my boundary condition so this term is not there so the first equation
actually contains only Z 1 and Z 2 right so which will give me two coefficients
the first column and the second column is that clear so what's for the first
column is 2 times H 0 plus h 1 that would be the first column and the second
column will be H 1 and it's all 0 afterwards is that clear so what about I equals to 2 what do we
have Z 1 Z 2 Z 3 Z right which will give me a number and the first in the second and the third column is i right so
what's in front of Z 1 is H 1 what's in front of Z 2 is 2 times H 1 plus h 2 in
front of these three is H 2 when it's all 0 everyone outside
is that clear let's do one more when I equals to three then I get Z 2 Z
3 Z 4 right so the second and the third and the fourth column is that clear so the actually the first one is zero so
whatever zero I don't write I only fill in the nonzero elements okay so then the
first one will be h2 and then what in front of here will be 2 h2 plus h3 and
then in front of that one will be h3 so now you see for each equation there are
only three unknowns right appearing so they're always together if you keep
doing it you will see this group of three numbers we just move down along
the diagonal in the matrix till we see that okay so this goes down and this
goes down so let me write out the second last one and then I'll write out the
last one so kind of a conclude so the second last one would be on H and minus
3 and then the diagonal is 2 H and minus 3 plus h and minus 2 and then this was H
and minus 2 and then the last equation you would have when I equals 2 and minus
1 this becomes Z and and you know putting the boundary condition Z and is
0 so this term is not there you actually get only two unknowns so you have two
places with nonzero so that will give me H and minus 2 and 2 times H and minus 2
and - okay so the diagonal the upper
diagonal and the lower diagonal are the only three kind of a lines of nonzero
elements in this matrix okay so what do we call such a matrix anybody knows that terminology the fu matrix have nonzero
only along the diagonal what do we call it by revenue matrix now you have three
of such lines what do you think we call it yes okay so I will write it as H
times Z equals to my right hand side B so is it clear for they are referring to
H is that matrix disease my unknown and B is that right hand side vector all right something special about this H
matrix that's or most important because want to solve that okay so we notice
that it's a tri diagonal matrix but it has more
I know we haven't talked about numerical linear algebra it's kind of a motivating
you everything we run into have we notice we always end up solving ax equal
to B right that's so important in the end we'll deal with it we'll know how to
do that so this is tri diagonal okay so but it has other properties um okay you have to believe me
that it's desirable to have a symmetric matrix because it has many other nice
properties and we have well-developed theorems to deal with symmetric matrix
so we know what is a symmetric matrix as definition is this matrix symmetric if
you transpose it you flip this one up is it the same it is right so it's
symmetric so anybody knows some nice property for symmetric matrix say with
respect to eigenvalues if a matrix symmetric who happen to the eigenvalues
guaranteed there will be
Oh and they'll be real right nobody has taken 436 441 no okay then you just have
to trust me I can tell you anything if it's a symmetric matrix the nice
property is that all the eigenvalues are real all right they can be zero but they
will be real so what what's so nice about it that if you use it combine it
in inner product that operator is caught self adjoint but okay we don't have to
know that but it has something else maybe you have heard look at the diagonal elements compare the diagonal
elements to the elements that's non diagonal comparing to their size you
know these HS are all positive do you see something
those that are underlined that's the diagonal line do you see those numbers
are big it's like the boss sitting there mm-hmm
if you add up all the non diagonal elements this guy steals bigger it's
what do you call that yes
so why it's so nice to be diagonal dominant if it's diagonal dominant what
does it mean okay I know I know it's this is not a course of of matrix up in
your bra but okay I just want to convince you that linear algebra is so
important it's everywhere whatever you run into you you write it
into ax equal to B you have to deal with these things okay so if it is diagonally
dominant then we know the matrix is non-singular meaning the determinant is
not zero mean it's invertible meaning there's unique solution okay so this
will give me a unique solution unique solution for the C vector and not only
that if it's diagonal dominant it means that you can perform this thing called
Gaussian elimination are we familiar with Gaussian elimination how do you solve a 3x3 system equation you perform
this Gauss the information make it zero and then you do backward substitution
have you done that if it's diagonal dominant then the Gaussian elimination will always work you're never run into
trouble okay so this works without any anything okay we'll get into details on this when we
talk about numerical linear algebra which is a big topic
so this piece of code on solving this as a tri-diagonal matrix using Gaussian
elimination will be provided to you in the code for cubic spline all you need
to do is read it and understand that path does it okay so I'm not asking you
to call that so okay now let's summarize looking back
into all that we have derived what will be our algorithm so how would you
compute and find the cubic spline what would you do first the previous
discussion says if the Z's are given I can find my spline which is over there
s eyes are given right and then we figure out a way to compute to the Z
right so we're deriving it in the backward order when you're actually
computing it you will have to compute this piece first to find the Z is that
clear so your code will be given TI given Y I
I will set up I will compute all the B eyes I'll set the right hand side vector I'll set up this matrix and I'll solve
it is that clear so that's your step so step one set it
up set up this H Z equals to B and so for Z
is that right and once you have all disease well then you can plug it back
in in here and that's just lying and you have it okay so step two and then compute the spline with the Z's that you
have just found okay can we visualize a program like that being carried out
there's one little piece which I like to talk a little bit about before I let you
go today so
let's say that's our t0 this is my TN and then you have these knots t1 t2 t3
da da da let's say this is ti and this is TI plus 1 TI plus 2 dot dot dot okay
and you know the spline that you find out all these s i--'s let's say on this
interval you would use the expression as two there right it's piecewise defined
isn't it each cubic polynomial is defined for the
interval right so on this interval from TI to TI plus 1 we were putting the
expression as I write okay in this faith let's say this will be the expression as
I plus 1 and this will be let's say as 0 and this is s1 the piecewise defined
okay so you computed all the Z and you know for each si you can compute so here
comes the question I give you an X I want to find the value the spline value
at s of X so here the question how do you know which SI to use
mmm-hmm question how to find basically the index I such that CI your ex lies on
that interval you have to write that little piece of code or you have to
identify that little piece of code in the cubic spline code which I gave to
you because you will need this for the linear spline which you have the code
which is much easier so how would you do it can we design some pseudo code do we
need full loop if test while loop or whatever what would you do
you will have to have some kind of a you can do a for loop or a while loop right
you have to go through all the t's let's say let's say my ex is here for some
index I mm-hmm so you check if X is bigger than t1 okay keep going
and then it's ax ax a bigger than T to keep going bigger than t3 keep going at certain I X is bigger than it I keep
going and then a TI plus 1 oops I found X is less than that that means I just crossed my ax is it when you stop and
keep their precious eye that you have there and subtracted by one that's the
interval where axes are as I clear can you write a little short code like that
is it clear this piece you have to code for your linear spline alright okay
we'll talk more details on Monday during the lab session