Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cubic spline interpolation

eli.thegreenplace.net

Post reply on HN
Print view View original

21–29 of 29 posts

Re: Cubic spline interpolation

#21

Post by buzzcut_ »

Rayhem wrote: post #10

Polynomials, 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 ga…

I'm taking a numerical algorithm class and have been learning about gaussian quadrature for the first time. It's super cool stuff. I haven't been able to wrap my head around why it works entirely and have found readings about legendre polynomials really difficult to understand. Do you have any intuition you can share?

Re: Cubic spline interpolation

#22

Post by sltkr »

nurple wrote: post #17

Somewhat related: Something that helped me understand splines more intuitively was to see them animated in a way that they can be played with. https://www.jasondavies.com/animated-bezier/

That's a cool page but it's about Bézier curves, while this article is about cubic splines. They are not the same!

The most notable difference is that a Bézier curve is defined in terms of control points that do not (generally) pass through the curve, while a polynomial spline is defined by the points it passes through; there are no additional control points.

Re: Cubic spline interpolation

#23

Post by jacobolus »

rnburn wrote: post #18
creata wrote: post #12

Earlier quoted context omitted.

> in general perform much better than cubic splines Source? (I couldn't find that in the paper you linked.)

The paper gives the rate of convergence you get with Polynomial interpolants in Chebyshev nodes: > If f has v derivatives, with the vth derivative being of bounded variation V, then ||f - p_n|| = O(V n^{-v}) as n -> ∞ and > If f is analytic, the convergence is geometric, with ||f - p_n|| = O(p^{-n}) for some p > 1 You will not get that good of a rate of convergence with cubic splines. See https://www.researchgate.net…

However, in many circumstances, you have equispaced nodes (not Chebyshev nodes), for which global polynomial interpolation is terrible and it is literally impossible to make a global method which is without pitfalls. Trefethen has some other papers about this, esp. http://people.maths.ox.ac.uk/~trefethen/impossibility.pdf, but also a new paper in 2023 with a different recommended method ("AAA") https://link.springer.com/article/10.1007/s10543-023-00959-x

In some cases cubic splines are a convenient and good enough tool, computationally cheap because the tridiagonal system involved can be solved in linear time.

Re: Cubic spline interpolation

#24

Post by jacobolus »

dahart wrote: post #8
creata wrote: post #2

You 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,…

Here's a write-up I made a couple years ago which I think does a bit better describing the math in question:

https://observablehq.com/@jrus/cubic-spline

Re: Cubic spline interpolation

#26

Post by Someone »

rnburn wrote: post #11

> There are many techniques to interpolate between a given set of points. Polynomial interpolation can perfectly fit N points with an N-1 degree polynomial, but this approach can be problematic for large a N; high-degree polynomials tend to overfit their data, and suffer from other numerical issues like Runge's phenomenon. This is a misconception that's often repeated. High degree polynomial interpolations are proble…

> This is a misconception that's often repeated

I don’t see how “If you use Chebyshev points, polynomial interpolation isn’t problematic” is a refutation of the claim “Polynomial interpolation between a given set of points can be problematic”. That given set isn’t necessarily, and typically isn’t, a set of Chebyshev points.

That’s like saying “Integer factorization isn’t hard. If you pick powers of ten, it’s easy”.

Re: Cubic spline interpolation

#27

Post by algas »

jethkl wrote: post #4

Spline 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 c…

I was hoping someone would mention the variational properties of splines, so I'm glad to see you bring up their energy minimization. In Strang's Intro to Applied Mathematics, he briefly mentions (at the end of the section on splines) that a spline interpolation can be found by minimum principles, since it's essentially passing a beam in bending through the control points. I was curious if anyone has used that practically, eg writing a finite element spline solver?

Re: Cubic spline interpolation

#28

Post by Rayhem »

buzzcut_ wrote: post #21
Rayhem wrote: post #10

Polynomials, 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 ga…

I'm taking a numerical algorithm class and have been learning about gaussian quadrature for the first time. It's super cool stuff. I haven't been able to wrap my head around why it works entirely and have found readings about legendre polynomials really difficult to understand. Do you have any intuition you can share?

It's by no means rigorous, but the gist of it is that

1. You're integrating the polynomial that best approximates the function over the interval. This is why quadrature is exact for polynomials up to some order: the best approximating polynomial is the polynomial itself.

2. Polynomials are good approximations when the function is smooth. Most useful functions are.

3. Because of the smoothness, the behavior in the middle of the interval is largely affected by the behavior at the edges, so you need more densely sample the edges. Think of it like wiggling a string. You're only allowed to wiggle the end, but that very specifically defines the behavior in the middle.

4. There are lots of polynomial sets - Legendre, Chebyshev, Hermite, etc. They're each useful because they're orthogonal to a special weight function, and Legendre polynomials are kind of the default set because they have the simplest weight function: 1.

Re: Cubic spline interpolation

#29

Post by jethkl »

algas wrote: post #27
jethkl wrote: post #4

Spline 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 c…

I was hoping someone would mention the variational properties of splines, so I'm glad to see you bring up their energy minimization. In Strang's Intro to Applied Mathematics, he briefly mentions (at the end of the section on splines) that a spline interpolation can be found by minimum principles, since it's essentially passing a beam in bending through the control points. I was curious if anyone has used that practic…

I am unaware of any effort in that direction, but I did find a 1987 paper by Höllig [1] that seems to do a kind of converse (approximates FEM solutions using splines. I haven't read the paper, but that's my quick take). Recovering splines using a FEM might be an interesting learning exercise, since the analytic solution is known and the model seems simple. The motivating physical model is described by flat splines [2], and Carl de Boor has photographs of physical splines in action [3].

[1] https://www.semanticscholar.org/paper/Finite-element-methods...

[2] https://en.wikipedia.org/wiki/Flat_spline

[3] https://pages.cs.wisc.edu/~deboor/draftspline.html

Post reply on HN