Problem Ia is clearly wrong. The solution, with the conditions stated, is that s'' is zero everywhere, resulting in a value of the integral of zero. This is a linear spline, with discontinuous first derivatives. If the condition of continuous first and second derivatives is to be taken as implicit, then there is a unique solution based on that and the end point conditions, and a fixed value for the integral, no minimization possible.
Ib is equally bad. The solution is again a linear interpolation where both the integral and the summation will be zero. Only if one assumes the continuity condition and not the interpolation condition does this become an interesting problem. Even then, the condition of a zero second derivative at the ends should not be imposed, those values should be chosen, like all the others, to minimize the objective function.
For IIa, since you apparently have a square grid, you can apply Mathcad's cspline (much better boundary condition than lspline, which corresponds to what was stated in part I) directly. An explication of cubic splines, including implementations of one and two dimensional splines can be found at http://collab.mathsoft.com/read?79386,11e#79386 . A similar scheme could probably be worked out for three dimensions, although it would be quite messy. The three dimensional spline will have 64 degrees of freedom and will require eight values at each of the eight corners (presumably one value, three second partial derivatives, three fourth partial derivatives, and one sixth partial derivative).
On 10/20/2007 9:56:41 PM, Wave wrote: >if it's wrong, do you have any >idea why the professor gave >out this assignment? everyone >is suffering in this class. ____________________________
Please ignore the comment you read:
Your teacher looks questionable .
Sorry for spanking you in the first place, now here is compassion and collaboration. What you need mostly is understanding the process of deriving the cubic splines [then the Mathcad built-in l, p, csplines]. The all thing starts by reading the several pages collapsed area, i.e: the Matlab introduction, then Mathcad spline(s) implements the tridiagonal matrix and solves for the coefficients .
The attached is in 11.2a, works perfect but it might fail some place in 14 . I don't recall if collabs have checked and re-posted in 14 ?
>>if it's wrong, do you have any idea why the professor gave out this assignment? <<
No idea. Possibly the profesor does not know it's wrong. Perhaps he doesn't even know what is in the homework. It might be canned problems from a text book or old notes from previous professors, grading might be by TAs. Perhaps he makes some implicit assumptions that make it reasonable (I have no idea what those would be -- either what is stated or the most likely conditions don't work).
>>everyone is suffering in this class. <<
That might relate to the answer (or lack thereof) to the previous question.
Does the professor provide the answers to the homework questions? I am real curious as to what he considers a solution to the 3D case. If he uses the same ten intervals as in the first problem on each of the three independent variables there are a thousand cubes to be fit. Does he really want sixty four coefficients for each of the thousand cubes? Or even some other set of sixty four parameters for each cube? Or is he just looking for an algorith that will do the spline?
That is fairly easy, albeit a bit slow. You just pick one of the dimensions and do 121 splines along that dimension. Then you pick a second dimension and do 11 splines along that dimension. Finally you do one spline along the remaining dimension. It turns out that it doesn't matter what order you take the dimensions in -- the result is the same.
Thanks jmG. No need to sorry, life is hard in engineering. Sad. I have no choice but to take this class as I double major in aeronautical and mechanical engineering (the aero major needs this class the most as this professor will teach Theoretical and Computational Aerodynamics in the spring).
The TAs are actually doing the grading and are in charge of assigning these projects. I'm not sure who write these projects.
After looking at that my first impression is: better you than me.
So you're not allowed to use something like Matlab's matrix inverse. But you can use the plot and the contour functions. Somebody really ought to provide some informative guidelines on what is and what is not allowable. If anything is a Matlab trick, a black box, it is the contour routine. Clearly some black boxes are allowed and some are not.
I can see where you should learn how matrix inversion and linear solutions are done. But having learned that I see absolutely no point in not using the Matlab functions. You learn absolutely nothing more by using the routines you've coded, and they won't work anywhere near as fast or reliably as Matlab's -- general routines need to do pivoting, which does not even seem to be mentioned.
Not much is clarified. The 1D spline still does not specify the exact conditions imposed. It does refer to a handout, but does that actually have the information? My original comments stand -- if you want an interpolation spline and the only condition is the minimization of the second derivatives you get the linear spline, if you require three orders of continuity and interpolation you have only two degrees of freedom (at the end points) and since those were specified the curve is fixed without minimizing anything, and if you don't make interpolation as a condition you have no tie to the data at all. I suppose you could require two orders of continuity and then minimize the second derivatives. That would work, but it seems a bit odd. And it's certainly not stated in anything you've posted so far.
The 2D spline seems similar in basis to mine, except that it is based on first derivatives rather than second derivatives. The matrix form for the evaluation is interesting (I don't have time to study it right now) -- matrix operations are often optimized, even at the hardware level (various forms of vector (or SIMO) operations). I just took the easy way out and did multiple 1D calculations, but if the calculation based on second derivatives could be put in matrix form that would be of interest.
No mention of the 3D spline. I suppose the equivalent would be third order tensors with tensor products. Still writing out a 64 element tensor (the way the 16 element matrix was written out element by element) is not my idea of fun.
for problem 3a, do you get the same answers using Doolittle method and Cholesky method?
I'm sure both answers should be the same, but for some reason I keep getting different answers for n is small (nxn matrix system). If n is very large, like n=1000 the answers are the same but somewhere between x1 to x10 the answers are off probably around less than 5%. I've spent 2 hours trying to debug this.
Using Doolittle method, Ax=d where A=LU and letting Ly=d and Ux=y I found y then x. This is what I got for n=20: 0 -1.517735393616925 -3.653773224327163 -4.569071831009250 -6.190260105073422 -7.244882273471898 -8.298864234587702 -9.054028045364612 -9.591506712436077 -9.857746893059050 -9.858541543185039 -9.589348437910154 -9.058979367052205 -8.281232983948808 -7.278256477569006 -6.074395516584855 -4.713588991428128 -3.191569222605806 -1.704298846468576 0.284049807744763
Using Cholesky method, A=L*L^T and letting Ly=d and (L^T)x=y I found y then x. This is what I got for n=10: 0 -1.628187920134536 -3.211963118256717 -4.708124335156493 -6.075860194554889 -7.277862421960706 -8.281343551151007 -9.058931153851592 -9.589414961924856 -9.858323660326974 -9.858326224624562 -9.589407269032089 -9.058959361124952 -8.281238414950678 -7.278254759488768 -6.074395980642880 -4.713588853276268 -3.191569259688847 -1.704298836288270 0.284049806048045
You can see that the solutions are closer and closer as n gets larger.
Yes, you should get (to within rounding errors) the same result no matter how you solve the system. I get no result at all, since I don't understand the problem (I don't know what g is supposed to be, I don't know what sort of spline is being looked for), nor do I know what the data is. I don't know what n is supposed to be in your posted results, there seem to be 20 results in each.
I would say that both results are incorrect on their face, since on thing I can make out from the problem statement is that g should be zero for the first and last element.
Do note that in the sheet the Doolittle and Chomskey methods are applied to different matrices. I suggest that you check your work by seeing if your decomposition is correct -- multiply out and compare to the original matrix.
>Thanks jmG. No need to sorry, life is hard in engineering.<<br> ___________________
Yes, life is hard in Engineering.
The link you provided, I visited quick and they insist on the tridiagonal solver. In fact the cubic splines [l, p, c] ... their coefficients do result from solving the tridiagonal, that you have seen in the work sheet. Arriving at the tridiagonal is in the collapsed area (7 pages from recollection). The other large category of splines are NURBS, searching that in the collab, you will find another pile of that stuff. NURBS = Non-Uniform Rtional B_Splines but it is basically defined by others as "Non-Uniform Rational B�zier Splines", the latest is more true in the sense that those splines work on the principle of control points.
Reading the project *.DOC, I got struck twice:
1. the from of the exercise is given in the "Hamming" book style and as well as "Hildebrand".
2. The integral they talk about makes me understand they want to arrive at the "spline smoothing" equivalent to the Matlab . That spline smoothing, I tried in the past but not to avail. I asked the Advisor for it ... no reply. And passed in the collab... no reply except from collab "Yuk" that provided the gorgeous "Catmull-Clark" 3D.
All that spline monkey business started with Hermite 2 centuries ago and the modern NURBS are very recent from B�zier and De Casteljau both ignoring each other and doing same for two different car manufacturers. B�zier dates early 1980's ! and is the basis for font smoothing and PDF construct... CAD's ...etc.
I will be absent of the collab from Nov. 15 till Jan. 10, visiting my two moskitos in England.
BTW: the Paint curve tool is the 4 points B�zier, i.e: the two first clicks are the end points that is draws as a line and the last two clicks are the two control points.
Good Engineers are suffering beast. There are plenty in this collab !
On 10/22/2007 2:12:58 AM, Wave wrote: >Thanks jmG. No need to sorry, life is hard in engineering. Sad. I have no choice but to take this class as I double major in aeronautical and mechanical engineering (the aero major needs this class the most as this professor will teach Theoretical and Computational Aerodynamics in the spring).
The TAs are actually doing the grading and are in charge of assigning these projects. I'm not sure who write these projects.
All in all it is a Matlab task or project about splines. The tridiagonal solver is very important, the form for the l, p, c splines is universal and as given in the Mathcad sheet you had. The first and last elements vary for the 3 types, but it is not rigid as suggested . In Mathcad, you can extract the spline coefficients and modify the first and last ones for other kind of extra-fit (extrapolation sometimes needed). Same thing applies to Hermite cubic and quadratic.
Now, about the Dolittle-Cholesky comparison, who cares ? unless one is recognized better/faster than the other one. On that, trust Mathsoft .
His suggestion about simply linear or quadratic for the first derivative (the one at the extreme right) ... I disagree on the two principles as suggested. It may become a very delicate task for the Engineer to fit real life problem .
You project is more a Matlab one than Mathcad.
Extract from project 2:
Linear spline: Plot straight lines from point to point. You don't need additional points between the given points, but it's a good idea to test your code by finding them, and then to extend the code to quadratic and cubic splines.
Quadratic spline: Quadratic polynomial is y=ai+bi(x-xi)+ci(x-xi)2. Where, bi=bi-1+2ci-1(xi-xi-1). To find the coefficient b for the current segment (i) you need to know b and c from the previous segment (i-1). The (i-1) segment does not exist for the first segment. Therefore, you have to find the coefficients of the quadratic polynomial for the first segment by some other way. Find them by fitting a parabola to the first three points. Having the coefficients of the polynomial for each segment you can plot a line between each pair of the given points. The line will look differently if you go forward from the first point or go backward from the last point. Find two lines: the "forward" line and the "backward" one. Then, average them. To program the backward way is tricky. Here is a nice and simple "cheat": flip the data and run your forward subroutine again.
Cubic spline: y=ai+bi(x-xi)+ci(x-xi)2+di(x-xi)3. Here you use the tridiagonal solver to find the coefficients bi. First, make sure that your tridiagonal solver works. Known b, the coefficients c and d can be found solving a system of two equations:
It's actually for any program that has programming capability such as fortran, java, matlab, C/C++, etc. But I need to transfer the script into matlab anyway so I might as well use matlab. I can get help if i use matlab as the TAs probably don't know about other programs.
On 10/22/2007 11:07:03 PM, Wave wrote: >>>You project is more a Matlab one than Mathcad. > >It's actually for any program >that has programming >capability such as fortran, >java, matlab, C/C++, etc. But >I need to transfer the script >into matlab anyway so I might >as well use matlab. I can get >help if i use matlab as the >TAs probably don't know about >other programs. > >Tomorrow. ____________________
OK ! but Mathacd has none of these programming capability directly. Very confusing as you had first technical question about splines and now you only need to convert your TA personal programming language into Matlab.
>> the form for the l, p, c splines is universal and as given in the Mathcad sheet you had. The first and last elements vary for the 3 types,<< [jmG]
No, all the elements differ for the 3 types. The difference is largest at the ends, and decays as you move away from them, but it affects, to some degree, all the elements. [Tom]
____________ "No, all the elements differ for the 3 types"
NOT TRUE: the "cubic spline" tridiagonal is fixed and based on the lspline, only subsequently the highlighted yellow are modified as per the two other types pspline/cspline. But obviously the final 's' spline coefficients are not at all the same for either of the 3 types. ___________
>>In Mathcad, you can extract the spline coefficients and modify the first and last ones<<
You can. But you will no longer have a proper cubic spline. You will introduce some discontinuities in the first derivatives if you change some elements.
...... ...... ...... I will not argue your 2nd point as I was talking about the "best end points fit", which is the first objective generally attempted from a fitting session.
Thanks for collaboration hoping it's clear for all collabs. Set the work sheet in "backward compatibility".
>>NOT TRUE: the "cubic spline" tridiagonal is fixed and based on the lspline, only subsequently the highlighted yellow are modified as per the two other types pspline/cspline. But obviously the final 's' spline coefficients are not at all the same for either of the 3 types.<<
NOT NOT TRUE. The cubic spline tridiagonal is fixed, except for the first and last rows. These depend on the boundary conditions imposed (see my cubic spline sheet for five different boundary conditions, and the associated equations). Changing even one equation is a set of equations can change the values of all the unknowns, not just one of them.
I have seen your sheets modifying the spline coefficients before. It just never seemed worth correcting. I correct it now because Wave is rather new at this, and might not otherwise recognize the error -- I would assume that anybody knowledgeable about cubic splines would already know that. The correct way to adjust the endpoint fits is to adjust the boundary conditions. This can be done with Sspline (from my sheet), where you can specify the slopes at the end points. Particularly useful for splining numerical solutions to ODEs, as the actual derivatives at the end points are known from the differential equations.
I may be wrong, but I think the misunderstanding might be about the returned mathcad vector of coefficients, which does vary according to the chioce of spline. If memory serves, there is a matrix based system setting up the spline fit which is tri diagonal, and it only has the end point region as different between types. But the solution (inverting the set-up) then has the variation across the whole matrix.
>>I may be wrong, but I think the misunderstanding might be about the returned mathcad vector of coefficients, which does vary according to the chioce of spline.<<
There is no misunderstanding. jmG has a longstanding sheet where he modifies the first and last parameter returned by the spline routine (cspline, pspline, or lspline). The result is no longer a proper spline.
On 10/24/2007 2:50:20 AM, Tom_Gutman wrote: >>>Can you explain in real words what you mean "proper spline" ?<< > >For a cubic spline, one where >the first and second >derivatives are continuous. >That will not be the case once >the two end parameters from >the spline routine are >changed. > > Tom Gutman _________________________
I understand your point, but constraining is applicable only to the lspline. It does nor affect the 1rst derivative and nicely it will vary the slope of the 2nd derivative. If the project consists in extracting the 2nd derivative from a data set, then the lspline is the spline and as such, if constrained the "constrain" is suitable at will or for else purpose.
Same work sheet but the 2nd derivative added. Saved 2001i, note the backward compatibility.
>>I understand your point, but constraining is applicable only to the lspline.<<
Not so. All forms of cubic splines impose constraints. Most of the degrees of freedom are provided for with the common constraints of interpolation and continuity of first and second derivatives. But those constraints still leave two degrees of freedom and so two more constraints are imposed. lspline, pspline, and cspline all impose one constraint at each of the two endpoints. They differ only as to what that constraint is. lspline imposes the (rather unnatural) condition that the curve have a point of inflection at each end. But the effects of that constraint propogate throughout the spline, so that the three forms produce different values for all the coefficients (although with long splines the difference in the middle might not be noticeable).
>>It does nor affect the 1rst derivative<<
It does affect the first derivative. Indeed, all but the first and last rows of the tridiagonal system are based on equating the first derivatives as functions of the values and second derivatives (which are the values to be found). Change some of the second derivatives arbitrarily, without getting a new solution of the tridiagonal system, and the new values will not be a solution of the tridiagonal system and will not have continuous first derivatives.
On 10/23/2007 6:17:40 PM, philipoakley wrote: >I may be wrong, but I think the misunderstanding might be about the returned mathcad vector of coefficients, which does vary according to the choice of spline. If memory serves, there is a matrix based system setting up the spline fit which is tri diagonal, and it only has the end point region as different between types. ...
Philip Oakley >____________________
No, you are not wrong ! we are talking about the splines from Numerical Recipes as implemented in Mathcad, Matlab, Mathematica ... surely Maple too ! Which splines are derived from the A... Z analysis all exposed in the sheet "MCD for Eng's_Splines" and this tridiagonal matrix is the one implemented in Mathcad . The only thing that varies are two elements ... as explicited again in the attached . There are so many splines that at this point is useless introducing the all bible of them . The collab had a question about the basic splines we are talking here .
The magic spline and the ODE is as endless as arguing that numerical solver are not exact anyway. The tridiagonal attached is not my invention, rather it comes from Mathsoft years ago and at the very beginning of Mathcad and has not changed, because there is nothing to change in there vis l, p, c splines.
Read carefully the note about constraining the end point and experiment as I have lavishly exposed and exploded those splines of concern.
On 10/23/2007 2:47:17 AM, Tom_Gutman wrote: >>>In Mathcad, you can extract the spline coefficients and modify the first and last ones<< > [jmG}
>You can. But you will no >longer have a proper cubic >spline. You will introduce >some discontinuities in the >first derivatives if you >change some elements. > >� � � � Tom Gutman ___________________
For those confused, here is my point below marlett. Try the 3 types, then enable/disable at the blue arrow. Like said above, I don't argue that point, just get the best end points fit.
Reply to post #12. I actually didn't see this. The numbering system is weird.
On 10/22/2007 8:07:02 PM, Tom_Gutman wrote: >Yes, you should get (to within >rounding errors) the same >result no matter how you solve >the system. I get no result at >all, since I don't understand >the problem (I don't know what >g is supposed to be, I don't >know what sort of spline is >being looked for), nor do I >know what the data is. I don't >know what n is supposed to be >in your posted results, there >seem to be 20 results in each. > >I would say that both results >are incorrect on their face, >since on thing I can make out >from the problem statement is >that g should be zero for the >first and last element. >Do note that in the sheet the >Doolittle and Chomskey methods >are applied to different >matrices. I suggest that you >check your work by seeing if >your decomposition is correct >-- multiply out and compare to >the original matrix. > > Tom Gutman
g is the second derivative of the function. I attached the cubic spline from my TA so that you can understand what sort of spline we are doing. Some more attachments will be available when my scanner is up. My biggest problem is finding the constants a,b,c, and d in the cubic spline. Actually I can't even find the constants for the quadratic spline. I don't quite get what the TA meant by finding the points using forward difference, backward difference, and central difference on the website.
The solutions were off because my indices were set up incorrectly in the script.
The handout (to be posted after i set up my scanner) includes the formula for the spline s(x). It was used to do project 3 problem 1a. The exact derivation of this equation is still mysterious to me but all of the projects we are doing require some equations in the handout.
We are finding solutions to functions using iterative methods. Jacobi, Gauss-Siedel, and Successive OVer relaxation method are considered. For finding the roots, various method such as fixed iteration method, newton's method, Halley's method and some others are considered. These methods are interesting but coding them is a pain.
He won the Academic Senate Distinguished Teaching Award so he doesn't look that questionable with that award. But he is unorganized--first day, no syllabus, write everything from memory, no set of instructions to do the project but the project statements. Told people to drop the class if they don't have at least 20 hours a week to do each project. did people drop? I think 13 people got scared and dropped the class.
>He won the Academic Senate Distinguished Teaching Award so he doesn't look that questionable with that award.<<br> =>=> that means just a "lecturer" Maths is not a matter to teach or lecture, maths is a matter you transfer.
>My biggest problem is finding the constants a,b,c, and d in the cubic spline. Actually I can't even find the constants for the quadratic spline.<<br> =>=> Did you open my last work sheet ? It does demonstrate the construct of the base spline, i.e: the "linear" cubic spline. And it then does show which elements are modified to accomplish "parabolic" and the common "Cubic". Then how to solve the resultant tridiagonal which solution is the vector of the spline coefficients. Then for your a, b, c, d ... the canonical form . From the very last canonical form, it's only to join, that is not shown, but if you insist you will have the little piece of program that does it and then reproduces the Mathcad built-in interp(,,,,).
Now, if you don't have Mathcad installed, all that is for the birds . You mention big name methods, that is another story just concerning solving the tridiagonal . It's like going back to the alphabet before reading a book .
>>Reply to post #12. I actually didn't see this. The numbering system is weird.<<
Actually, a reply to post #18, a posting by jmG. The numbering system is fairly straightforward -- posts are numbered in the order in which they are created. But this is a threaded system, and replies are positioned after the message to which they are a reply. For this to work properly you have to use the reply button in the message (on top) to which you are replying. Don't use the reply button at the bottom of the thread -- that just make a reply to the end of the thread, often to an unrelated branch of the thread (and any long thread will have several distinct branches, which need to be kept straight if they are to make any sense).
To find new posts you should be expanding the thread tree (on the left side of the screen) and looking for the new flag. It's on a black background and hard to miss. You can use the position of the new messages as a guide and scroll the complete message list looking for the new flag there (that's what I usually do, so as to have the context at hand) or you can click on the specific message, or a close ancestor, and see a reduced set of messages. Alternatively you can choose, at the top of the index pane, to view just new messages. You can alway use the show entire topic button to see the complete context, if you are viewing a subset of the thread.
>>g is the second derivative of the function.<<
OK. That is the second derivative of the spline function, not the underlying function being approximated (although they should be close). That is the standard spline procedure. Looking at the attachment it is the standard exposition (same as in my sheet) based purely on continuity conditions. No minimization involved.
Given the values of the cubic and its second derivative at the two end points the coefficients are easy to calculate. The equations for that are in the theory section of my spline sheet. But those coefficients are neither used nor calculated in the actual implementation of a cubic spline. Rather the equations are worked out that calculate the value of the spline at any x using just the values of the function and the second derivative at the end points.
>>The solutions were off because my indices were set up incorrectly in the script.<<
I take it then that you have been able to get the correct answers. You can use Mathcad to check your work, as the results of lspline (excluding the first three elements, which are a header) are the second derivatives of the spline function. lspline corresponds to your given conditions, with the unnatural boundary condition of forcing a point of inflection (zero second derivative) at the end points.
Come to think of it, my sheet may have the coefficients for a somewhat different form, a cubic in x rather than in x-xi. Easy enough to redo for that form. And I probably used "a" for the leading term, not the constant term. Again, just a matter of nomenclature.