Chebyshev Approximation
Folks interested in this topic should look at Chebfun, <a href="http://www.chebfun.org" rel="nofollow">http://www.chebfun.org</a><p>Also at Lloyd Trefethen’s book Approximation Theory and Approximation Practice, of which the first 6 chapters are available online, <a href="http://www.chebfun.org/ATAP/" rel="nofollow">http://www.chebfun.org/ATAP/</a><p>The author of this blog post might as well have used Clenshaw’s algorithm as he mentioned was suggested by Numerical Recipes. It’s like 4–5 lines of code, fast, and has been proven numerically stable.<p>If bk1, and bk2 are the previous two terms of the recurrence, and c the coefficient array, code to find y = f(x) for x in [-1, 1] looks like:<p><pre><code>  x2 = 2*x
  bk2 = bk1 = 0
  for ck in c[:0:-1]:
      bk2, bk1 = bk1, ck + x2*bk1 - bk2
  y = c[0] + x * bk1 - bk2
</code></pre>
(Note: There might be some typos there, I didn’t try running that. Here’s a vectorized Matlab version <a href="https://github.com/chebfun/chebfun/blob/development/%40chebtech/clenshaw.m" rel="nofollow">https://github.com/chebfun/chebfun/blob/development/%40chebt...</a> with coefficients in that version ordered from highest to lowest)<p>Or if he wanted an easy Python tool, just used this (partial) python port of Chebfun (though I guess it dates from around the same time as his post), <a href="https://github.com/olivierverdier/pychebfun" rel="nofollow">https://github.com/olivierverdier/pychebfun</a><p>I’m not convinced about his measurements on an arbitrary grid -> chebyshev coefficients via weighted least squares method. If his measurement points are reasonably clustered near the endpoints of his interval, he could just use an exactly interpolating polynomial and use the barycentric interpolation formula to get the values at the chebyshev points (see Trefethen’s book). His approach might also be fine, I haven’t thought deeply about it. Also see <a href="http://www.chebfun.org/examples/approx/RationalInterp.html" rel="nofollow">http://www.chebfun.org/examples/approx/RationalInterp.html</a> <a href="http://www.chebfun.org/examples/approx/EquispacedData.html" rel="nofollow">http://www.chebfun.org/examples/approx/EquispacedData.html</a> <a href="http://www.chebfun.org/examples/approx/BestL2Approximation.html" rel="nofollow">http://www.chebfun.org/examples/approx/BestL2Approximation.h...</a><p>The neat thing about Chebyshev polynomials is that it’s possible to convert from values at the Chebyshev points (either extrema or roots of the Chebyshev polynomial) to Chebyshev coefficients by using an FFT, which takes O(n log n) time. Along with various other efficient algorithms for differentiation, integration, root finding, solving differential equations, etc., Chebfun makes it practical to deal with polynomials of very high degree, and do lots of neat stuff with them.<p>This blog post’s statement that “higher degree polynomials can have problems with numerical accuracy” turns out to be a myth: <a href="https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf" rel="nofollow">https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf</a>