Spline

Is anyone else battling with Splines?

Maybe start with what you think you understand well, and then indicate from there what seems to be the difficulty?

That way if the problem is rooted in some basic misconception, those of us who know absolutely everything about splines </irony> can put you right, and you'll find the rest of the way yourself?

Each spline is a little piece of polynomial, built around an appropriate number of points for the degree of that polynomial. (For instance if I recall correctly you only need 2 points per piece if your splines are linear).

There, now I've said something for someone to correct. : - )

Howdy,

Up until this section I've understood everything pretty well. Splines and Beziers broke my brain. But ja I understand what a spline is.

Take Q6 of the assignment for example. It asks you to construct the polynomial and define the boundary conditions for the given data. Where do I even start?

Well you start at page 170, obviously. : -)

I'm on a supp, so I don't have the TLs for this semester.

I assume you know at least something about splines. However the problem may be with what you "know". If you've gotten the wrong end of the stick somewhere then before getting to something specific like your Q6, this needs to be cleared up. The way to debug your theoretical model is to express it, the way you understand it, and then maybe someone here might have a look and see some fundamental misconception. If you don't set out what you, personally, mean by "splines" then nobody's going to know how to help.

Splines are a lot of work. That I do know. Somewhere in the study matter (maybe the answers from last semester) they explain why they do splines. It's because it's difficult enough, theoretically deep enough, but not too much of either.

One of the first things you need to do is adjust your expectations of how much time it's going to take to get this assignment done (although at least you're on splines already, so you're up to speed). It's going to go slowly. There are going to be quite a lot of numbers floating around. Do one thing at a time.

Each spline has to have that set of pretty much commonsense conditions on it. That gives you a system of equations. You solve that system of equations, and you get some formulas, I think. One problem is that you don't have enough equations in the system, so you make simplifying assumptions on the ends so as to add equations to the system. So the splines are quadratic or linear or something on their start and end points. They're not perfectly cubic everywhere.

If you can spare about 40 minutes or so in total, go and find the numericalmethodsguy on You Tube, and get a different perspective.

What else can I say (short of writing an essay on splines)?

Here's a way of visualising the Bezier spline (what's going on behind the formulas). The section is cubic (unique for any set of four points), and the Bezier spline is a shifting of the proportional point along the inner line, geometrically.

http://www.youtube.com/watch?v=03MJE-50pFs

Hey Eddy,

Yeah numericalmethodsguy has been helping in other areas quite a bit. Let me watch the video you posted.

The issue is the splines are so damn complicated in every sense. Theres about 6 pages in the textbook but it means nothing. They just point you at matlab and leave it there.

The assignment is due on Monday. I'm busy knocking off everything else I need to do so I can sit the entire weekend with this stuff. Hopefully with a clear head it will make some sense.

Where about are you? Not Durban I don't suppose?

p170, 171, 172 = developing the formulas. Maybe on your first next iteration just accept them on faith. That'll simplify things for the time being.

Right, so then we launch on p172 with an equation that "just must be true". The only thing to perhaps note about the notation used is that "S" stands for "second derivative" here. (Maybe it could help to change all the subscripts temporarily to eg. "this" "prev" "next" or something of the nature of a "comment", too?)

So starting with that equation we just take as given for now, carry on from the middle of page 172. It says that you have to specify end conditions (and numericalmethodsguy explains that this is because you don't have enough equations to cover all the variables unless you make these assumptions at the ends).

If the assignment specifies that you must use a specific form of the end condition, you've reduced your reading (for this iteration) to just one item. Actually if the assignment doesn't specify what kind of ends you want (geometrically, whether they're stiff or have some flex, but don't worry about that overmuch) then you're free to pick whatever seems easiest. This is a matter of personal choice. At a glimpse it looks like you get to do some extra calculations with option 4, for instance.

Now once you've picked your end conditions, you just choose the appropriate matrix from those given on p173, 174. Look at the matrix you get, and you'll see it looks less dire than the development that led there. So maybe you've now found a point to begin at least understanding something...

I seem to recall making a mess of a similar question in last semester's assignment, so hopefully I haven't just reconstructed the wrong way of going about it there.

There's either a lot more on the Internet about this than there was a few months ago, or it all went straight through the brain cavity last time round. Among all the fascinating stuff, I'm reminded of this point (which I had so utterly forgotten that it's as if it's the first encounter, really):

You use a piece of cubic polynomial between points because to have any change in curvature you must have a second derivative. That's putting it backwards, but you know what I mean, right?

To have a nice smooth interpolating curve, linear won't do. For smoothness you have to go to quadratics. These have changing slopes which can be set to be changing at the same rate when they hit the knot from either side. However, that doesn't allow for a curve whose rate of change in curvature is changing as it hits the knot. You can only have a constant curvature with a quadratic. Sometimes what you might want is for the curve to be upfacing on the left, and downfacing on the right or something like that? For that you need a second derivative, and hence a third degree polynomial.

OK Eddy, I'm winning slowly here. Still going through the end conditions a bit. But I'm making some progress.

As a side note regarding Jacobi Method, do you know whether we're expected to compute the values using the matrix equation 2.23 on page 123? I think I might be doing it quicker by just moving x1, x2,..,xn as given here: http://www.youtube.com/watch?v=HbqGnFU62-Y

The formula is much friendlier than it looks if you step it out a bit. Take the example matrix and see where each equation in the set goes, and how it looks when just solved for "the equation way", compared to how it all looks for when done "the matrix way", etc. However you probably want to just go down the page a bit to the algorithm. Set up a sufficient condition for convergence, and away you go.

The video does a fair job of showing what's going on in practice, and how a weird idea like just taking a wild guess can lead to a reasonable estimate.

I suppose the only requirement really is that you apply the Jacobi method.

To lay to rest all doubts about splines, try setting up matrix based on everything you know about "the arbitrary spline" in your interpolation. Count your equations, count your variables ... and I think watch the numerical methods guy's cubic spline lecture ... and you'll at least see how the equations (for the coefficients at the end) arise.

Glad to hear you're getting on top of it. It'll be handy to have someone around here who can answer questions at last.

OK, I get the boundary conditions matrices now. Its a lot to remember.

With regards to the example on page 175, the vector [12.7020 30.2754], how did they arrive at that?

I must have missed something somewhere...

It's not going to help you much memorising it, because they're not likely to ask you to regurgitate in the exam. Once you've been through the process of making sure you understand (at least for a while) what's going on, you simply appreciate what the matrices you'll actually work with are all about. Exam last year was almost entirely practical. However you can only really start on that practical application if you have some idea why you do the various steps.

The short version of that paragraph is: Don't fret too much if you can't memorise it. Worry about that later.

As for the example, purely to allow you the pleasure of mainly discovering your own answer, I'll start with a more cryptic answer than is absolutely necessary. See how you go with it, and if you're still stuck, ask again, and I'll give you a better clue:

Look at the RHS of equation 3.17.

OK, the right hand side of equation 3.17 brought it together nicely. To think I spent an entire morning trying to work out where those figures came from. It's hardly intuitive some of this stuff. I hate having to just believe it works.

Tutorial Letter 101


So I'm going through question 6 now. Because there are only 3 values, we will only get 1 entry for equation 3.17: -3.084

That said, the condition 2 matrix looks like this:
0.04 0.02
0.02 0.10

One cannot augment just -3.084 to that and solve. My logic here is to select S1 = -3.084 / 0.04.

Thoughts?

Um ...
Very provisional thought would be, "Don't you use your boundaries?"

I have no idea whether that's of any use at all.

At this point I think you could safely say I'm hitting a blank on Q6. Will look at it sometime tomorrow when brain is less dead.

Thanks Eddy. Going to call the lecturer just now. I can't see myself finish this assignment by the end of today. I might even go so far as to cancel the subject and take it next semester.

It will give me the opportunity to do the spadework now and get a good symbol later. Everyone I have spoken to has battled with this subject. I'm also working at the same time which doesn't help!

OK, spoke to the lecturer. She is going to take a look and I must call her this afternoon. In the meantime I'm moving on to working with Bezier curves.

I asked her whether Numerical Methods 2 is as bad as this, she reckons its not. Apparently that course is not as crammed with such a broad array of stuff.

Well I had plans of redoing it in say 15 years time, but then they surprised me with the supp, so here I am again...

Mixing Numerical Methods and work sounds very onerous. Still it is a very interesting subject, isn't it? In spite of basically failing it, I felt quite pleased to have done it. If you're struggling too much, maybe canceling and starting again later will help? But how much will it help doing this if you don't use almost as much time now as you would've? - ie. keep on doing numerical methods, without the joys of the exam to lure you onward?

A valid point indeed Eddy. I get the Bezier curves after looking at it for just an hour this morning. It's not rocket science. I've completed question 7 without much difficulty and have now moved on to Least Squares Polynomials.

Question 6 is clearly the toughest part of this assignment from my point of view. We'll see what shows up shortly.

I really wonder where everyone else is. Are you and I the only ones battling? I usually get distinctions on my mathematics papers..... : (

Once upon a time I reached a point where I managed the occasional distinction for maths, too. So us "ordinary-level-distinction" maths students tend to suffer a bit with Numerical Methods. However, we relish this! It's character building!

"Higher-level-distinction" students also suffer a little with this course, so at least one's not alone. Take for example Murdock, who has more distinctions than most of the lecturers had during their studies. He cried for help, didn't he? Take for example M Alberts from last year, who has moved on to better things than Osprey. He is now lecturing the lecturers, and he took a hit from this course.

Anyway, at a glimpse the least squares question looks quite fair.

As far as Q6 goes, I'm trying to make sure I understand why S_n is singled out for special attention just after equation 3.14. I count n S-values for the S_i expression. Maybe the extra one helps somehow. Any thoughts?

One thing I did need to notice a second time round was that the (x - x_i+1) factors in 3.12 are none other than our good friend "h". (For some reason the way to get this seems to me to ask "Can you show me why the x expressions in 3.12 are not h?"

No need to memorise the formula for the b_i; just remember that x_i - x_i == 0. (And for i + 1 "convince me that that's not an h".

I've answered the first of my own questions. There are n+1 points, not n, so we need an extra [n+1]^th point derivative.

3.12 makes sense to me to quite an extent. I do see what you're saying about S_n being singled out under 3.14 though. I never noticed that before and leaves me wondering.

I will make a point of asking the lecturer in the morning.

Regarding least squares, I created a new topic.

Take 3.12 and 3.13.
Develop 3.12 and 3.13 in terms of Q0(x1), Q1(x2), Q'0(x1) and Q'(x2) . Also look just after 3.14make Si and Si+1 in terms of Q''i+1(x+1) = Q''i(x+1) ; Q''i+1(x+1) -Q''i(x+1) = 0 - this will be your fifth equation.
You already know Q0(x0) = f0 = d0 and Q1(x1) = f1 = d1 from the given experimental data. You also know c0 = Q'(x0) from the same data.
All the above will give you five equations. Solve the system and find a0, b0, a,1,b1,c1 - replace the values at the cubic polynomial and you will get the answer

Ihristov, welcome to the party.

I've figured out how the splines work a little. That said I still left Q6 out completely because I done know what to do with just 2 equations that will be determined from the table. The lecturer never got back to me either. Are you able to elaborate by way of submitting a scan of your workings?

It took me a lot of time to figure it out + I failed this subject last year so this is my second time around.

You have to construct a spline that satisfies the following:
-Q0 and Q1 are cubic polynomials on the intervals [x0, x1] and [x1, x2]
-Q(xi) = fi;
-Q1(x1) = Q0(x1)
-Q'1(x1) = Q'0(x1)
-Q''1(x1) = Q''0(x1)
-Q'1(x1) = f'(x1)

Expand the above equations by using 3.12, .3.13, and 3.14
First look at some values that you already have:
Q'1(x1) = Q'0(x1) = f'(x1) = c0 = -0.29552 (from experimental data)
Q0(x0) = d0 = f0 = 0.95534 (from experimental data)
Q1(x1) = d1 = f1 = 0.94924 (from experimental data)
These are from the given table of data.
The rest of the conditions are:
Q1(x2) = a1(x2-x1)3 + b1(x2-x1)2 + c1(x2-x1) + d1 = f2 = f2 – d1 (3.12)
Q0(x1) = a0(x1-x0)3 + b0(x1-x0)2 + c0(x1-x0) + d0 = f0 = f0 – d0 - c0(x1-x0) (3.12)
Q'0(x1) = 3a0(x1-x0)2 + 2b0(x1-x0) - c1 = -c0 (boundary condition, Q msut be continuous)
Q''0(x1) = 6a0(x1-x0) + 2b0 = 2b1 = 6a0(x1-x0) + 2b0 - 2b1 = 0 (after 3.14 - g''i(xi+1) = g''i-1(xi+1) from 3.10d )
Q'(x2) = 3a1(x2-x1)2 + 2b1(x2-x1) + c1 = F'(x2) = -0.3429 (from experimental data)

Now solve this system. Your cubic spline polynomials are Q0(x) (with a0,b0,c0, and d0) and Q1(x) (with a1,b1,c1, and d1)- write these in terms of 3.12 - note that this is x - your desired value for interpolation. Depending on the value required for interpolation choose which equation to use Q0 or Q1 according to the range of x: 0.34 is obviously between x1 and x2.