Cubic spline interpolation
eli.thegreenplace.net
Cubic spline interpolation
1–10 of 29 posts
Re: Cubic spline interpolation
#2You don't need to use O(n^3) Gaussian elimination to find natural cubic splines: you can write the system of equations as a tridiagonal matrix, which can be solved in linear time.
https://splines.readthedocs.io/en/latest/euclidean/natural-u...
Re: Cubic spline interpolation
#3Would split-tweak (chaikins, jareks...) be applicable here? It's easy.
(It's weirdly difficult to find an example to link)
Here's chaikins
Re: Cubic spline interpolation
#4Spline interpolation is a rich and extensively studied field, dating back to at least the 1940s. Here are a few comments about related work. The interpolation algorithm itself can be adjusted in numerous ways. One effective algorithm for reducing overshooting artifacts is Akima spline interpolation, but there are many others. Cubic splines have noteworthy theoretical properties; you can search for "energy minimizer cubic spline" to find out more. As already mentioned in @creata's comment, instead of using Gaussian elimination, you can take advantage of the fact that the matrix is banded and solve it using a banded solve algorithm (search for DGBSV in LAPACK). There is also research that explores the relationship between shift-invariant spaces and functions that can be expressed as a linear combination of splines. Finally, multivariate interpolation is an extension of the 1-d theory to n-d. This is used in image and surface interpolation, for example.
Re: Cubic spline interpolation
#5Coincidentally, I recently put up a profile coffee roasting planner built on cubic splines. The constraints of the cubic spline match up nicely with the behavior of coffee in a roasting machine so doing it this way gets you plans that are easy to follow and fast to put together or edit. This one is just done as a web site, but prior to that I'd been using a prototype in C++ (unreleased because no UI) for several years. Try not to look at the code too closely, not a web dev. https://crucs.net.
Re: Cubic spline interpolation
#6Best resource on this topic:
Re: Cubic spline interpolation
#7Did you know you can do spline interpolation on a piece of paper with the ruler and pencil? It's a nice demonstration that you can do to high school students, and maybe even to middle schoolers.
Here's an example, with fairly round numbers, because we need to use text instead of paper.
Let's say you have a function f, and its values at 1,2 and 3. f(1) = 1, f(2) = 3, f(3) = 2. We plot these 3 points, we call them A,B,C. What is the spline interpolation value at 1.5 ?
You start with the linear interpolation between A (the point (1,1)) and B (the point (2,3)). You get the value 2. Let's call the point (1.5, 2) as M.
Then you do the linear extrapolation of the segment BC. The new point is N with coordinates (1.5, 3.5).
Now move M horizontally until it hits the vertical line y=1, call that point M' (it has coordinates (1,2)). Move N to the vertical line y=3, it has coordinates (3,3.5). Draw the line M'N'. Where it intersects the vertical line y=1.5, that's where the spline interpolation is. It is the point (1.5, 2.375).
Of course, this is not only useful for paper and pencil stuff. That's how splines are actually implemented in lots of packages. You can easily implement it in Excel, if you need to, all with only cell formulas.
Re: Cubic spline interpolation
#8You don't need to use O(n^3) Gaussian elimination to find natural cubic splines: you can write the system of equations as a tridiagonal matrix, which can be solved in linear time. https://splines.readthedocs.io/en/latest/euclidean/natural-u...
You don’t need to solve a system of equations at all, and it’s unusual to do so unless you have very specific requirements, right? All of the reasons the article used to justify going that direction can be met (more or less, depending on more nuance than the article used) with existing spline types. Plus you can trade some of the overshoot properties of the article’s solution for just a little bit of extra curvature, with a Catmull-Rom spline for example, which might be preferable for many people for multiple reasons.
Re: Cubic spline interpolation
#9Would split-tweak (chaikins, jareks...) be applicable here? It's easy. (It's weirdly difficult to find an example to link) Here's chaikins https://sighack.com/post/chaikin-curves
The Chaikin curve is a quadratic B-spline, which is an approximating spline rather than an interpolating spline. Chaikin is very useful for lots of applications, but the reason it doesn’t fit the stated constraints in the article is because it doesn’t interpolate the control points, and doesn’t “naturally” stop at the endpoints of the curve either (though it’s obviously very easy to make your Chaikin curve hit endpoints if you want to). Playing with interpolating quadratic splines is a fun exercise!
Re: Cubic spline interpolation
#10Polynomials, sampling theory, signal processing, Fourier series, etc. are all so closely related that learning even a little bit of one of these things opens up such a wealth of other things to think about and explore. Splines like this basically answer the question "what polynomial fits these points the best?" which, it turns out, is the same question you need to pose to begin formulating gaussian quadrature. And gaussian quadrature is super cool because it approximates integrals about a billion times better than riemann summation[1] for the same amount of computational effort.