Chebyshev approximation and how it can help (2012)

A great book on this subject is Approximation Theory and Approximation Practice:

https://people.maths.ox.ac.uk/trefethen/ATAP/

Also chebfun!

https://www.chebfun.org/

2012

Related:

Chebyshev Approximation - https://news.ycombinator.com/item?id=10115336 - Aug 2015 (60 comments)

chebyshev approximations are fucking awesome, but this article gives too short shrift to table lookup; it does go a bit beyond nearest-neighbor interpolation to linear interpolation, and correctly points out that this gives you error that is quadratic in the distance from the x-coordinate of the nearest table entry (and therefore worst-case error quadratic in your point spacing), and that this gives you half the error of the fifth-order chebyshev approximation. it says that this is a 'rare case', but in fact you will always get a lower error from table lookup if you use enough points. it's just that with only linear interpolation, the number of points rapidly becomes impractical

as i understand it, other commonly-used strategies include spline interpolation (using second-, third-, or even fourth-order interpolation, requiring respectively three, four, and five multiplications, which can be done concurrently) and, in suitable cases like this example, newton iteration from an initial table-lookup guess

unlike the piecewise-taylor approach outlined early in the article, spline interpolation only requires storing a tiny amount more data than simple nearest-neighbor table lookup (potentially three more points for fourth-order interpolation, so a 256-entry table becomes 259 entries)

on a different topic, i think it's easy to find embedded dsp applications where the easiest solution uses fourier transforms, which usually do require high-precision floating point. machine vision, radio communication, musical applications, etc.

incidentally, if you find yourself in a situation where you actually need the taylor expansion of √(1+x) or √(½+x) or something, and you don't want to do a bunch of pencil-and-paper algebra (or don't trust yourself), pari/gp has your back:

    ? sqrt(1+x) + O(x^5)
    %5 = 1 + 1/2*x - 1/8*x^2 + 1/16*x^3 - 5/128*x^4 + O(x^5)
    ? sqrt(1+x) + O(x^7)
    %7 = 1 + 1/2*x - 1/8*x^2 + 1/16*x^3 - 5/128*x^4 + 7/256*x^5 - 21/1024*x^6 + O(x^7)
    ? sqrt(1/2+x) + O(x^5)
    %6 = 0.70710678118654752440084436210484903928 + 0.70710678118654752440084436210484903928*x - 0.35355339059327376220042218105242451964*x^2 + 0.35355339059327376220042218105242451964*x^3 - 0.44194173824159220275052772631553064955*x^4 + O(x^5)

As Boyd says in his book on Chebyshev Methods: when in doubt use Chebyshev polynomials.

I use Chebyshev polynomials extensively in finance and have tried problems like MNIST with Chebyshev and they get close to CNNs in accuracy.

ApproxFun Julia package pretty cool for Chebyshev work:

https://juliaapproximation.github.io/ApproxFun.jl/latest/