4 ms·
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 bou
by 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 agoThank you!
- jacobolus 3y agoHowever, 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.