3 ms·
Inre the first blog post link, the barycentric interpolation formula is a pretty awesome way to efficiently evaluate polynomial interpolants, https://people.mat
by jacobolus 11y ago
Inre the first blog post link, the barycentric interpolation formula is a pretty awesome way to efficiently evaluate polynomial interpolants, https://people.maths.ox.ac.uk/trefethen/publication/PDF/2004_106.pdf https://people.maths.ox.ac.uk/trefethen/publication/PDF/2004...
The standard Lagrange interpolation formula implemented in that blog post works too, but is O(n^2) vs. O(n) for each evaluation, and not numerically stable.
Also see http://www.maths.manchester.ac.uk/~higham/narep/narep440.pdf http://www.maths.manchester.ac.uk/~higham/narep/narep440.pdf https://people.maths.ox.ac.uk/trefethen/publication/PDF/2011_143.pdf https://people.maths.ox.ac.uk/trefethen/publication/PDF/2011...
Inre the second blog post link, it’s generally a bad idea to evaluate polynomials on an interval in terms of the monomial basis.
But anyhow, on the subject of the Remez algorithm, see http://www.chebfun.org/publications/remez.pdf http://www.chebfun.org/publications/remez.pdf http://www.chebfun.org/examples/approx/BestApprox.html http://www.chebfun.org/examples/approx/BestApprox.html
Note that while a standard Chebyshev polynomial approximant isn’t quite “optimal” for any particular function, in an L∞ norm minimax sense, it’s much easier to find, and often better for most values of x. See Trefethen’s book for details, and also the Chebfun guide, http://www.chebfun.org/docs/guide/guide04.html http://www.chebfun.org/docs/guide/guide04.html or this paper has a nice example picture under “myth 3” https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf
- JacobiX 11y agoThe paper on Barycentric Lagrange Interpolation did a pretty good job at explaining clearly how to evaluate efficiently the polynomial.