3 ms·

If you want a very simple introduction to Chebyshev approximation http://sidewindiegames.com/?p=436 http://sidewindiegames.com/?p=436 I skip many useful details

• deleted 11y ago
  [deleted]
• 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 ago
    The paper on Barycentric Lagrange Interpolation did a pretty good job at explaining clearly how to evaluate efficiently the polynomial.