3 ms·

> 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

by rnburn 3y ago

> 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 problematic if you use equispaced points. If you use Chebyshev points, they are highly accurate and in general perform much better than cubic splines. See myth 1 from Lloyd Trefethen's paper: https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf

creata 3y ago
> in general perform much better than cubic splines Source? (I couldn't find that in the paper you linked.)
- rnburn 3y ago
  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/publication/243095286_On_the_Order_of_Convergence_of_Natural_Cubic_Spline_Interpolation https://www.researchgate.net/publication/243095286_On_the_Or... This is further explained in Trefethen's book https://www.amazon.com/Approximation-Theory-Practice-Applied-Mathematics/dp/1611972396 https://www.amazon.com/Approximation-Theory-Practice-Applied... Quoting from Ch 14 > In fact, polynomial interpolants in Chebyshev points are problem-free when evaluated by the barycentric interpolation formula. They have the same behavior as discrete Fourier series for period functions, whose reliability nobody worries about. The introduction of splines is a red herring: the true advantage of splines is not that they converge where polynomials fail to do so, but that they are more easility adapted to irregular point distributions and more localized. You can see also the software package https://www.chebfun.org/ https://www.chebfun.org/ for Chebyshev interpolations with Matlab and https://github.com/rnburn/bbai https://github.com/rnburn/bbai for Chebyshev interpolation of arbitrary dimension functions with sparse grids for Python. And here is a quick notebook for an experiment you can run that will compare Chebyshev interpolants to cubic splines: https://github.com/rnburn/bbai/blob/master/example/13-sparse-grid.ipynb https://github.com/rnburn/bbai/blob/master/example/13-sparse...
  - creata 3y ago
    Thank you!
  - jacobolus 3y ago
    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 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 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.
CamperBob2 3y ago
That's a great paper, thanks for the pointer.
Someone 3y ago
> 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”.

by rnburn 3y ago

creata 3y ago

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

rnburn 3y ago
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/publication/243095286_On_the_Order_of_Convergence_of_Natural_Cubic_Spline_Interpolation https://www.researchgate.net/publication/243095286_On_the_Or... This is further explained in Trefethen's book https://www.amazon.com/Approximation-Theory-Practice-Applied-Mathematics/dp/1611972396 https://www.amazon.com/Approximation-Theory-Practice-Applied... Quoting from Ch 14 > In fact, polynomial interpolants in Chebyshev points are problem-free when evaluated by the barycentric interpolation formula. They have the same behavior as discrete Fourier series for period functions, whose reliability nobody worries about. The introduction of splines is a red herring: the true advantage of splines is not that they converge where polynomials fail to do so, but that they are more easility adapted to irregular point distributions and more localized. You can see also the software package https://www.chebfun.org/ https://www.chebfun.org/ for Chebyshev interpolations with Matlab and https://github.com/rnburn/bbai https://github.com/rnburn/bbai for Chebyshev interpolation of arbitrary dimension functions with sparse grids for Python. And here is a quick notebook for an experiment you can run that will compare Chebyshev interpolants to cubic splines: https://github.com/rnburn/bbai/blob/master/example/13-sparse-grid.ipynb https://github.com/rnburn/bbai/blob/master/example/13-sparse...
- creata 3y ago
  Thank you!
- jacobolus 3y ago
  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 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 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.

CamperBob2 3y ago

That's a great paper, thanks for the pointer.

Someone 3y ago

> 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”.