| Some other useful things about Chebyshev approximations: 1. You can use a Fourier transform to get the coefficients in O(n log n) time. 2. So, multiplying two approximations only takes O(n log n) time. 3. Also, adding, integrating, or taking the derivative only take O(n) time. This is why chebfun/chebpy can run so fast while magically finding roots/derivatives/etc. A couple other interesting facts: 1. Remember the double-angle formula? There's a more general recursion for the Chebyshev polynomials: \[ T_n(x) = 2x T_{n-1}(x) - T_{n-2}. \] So, e.g. \[ T_2(cos(theta)) = cos(2*theta) = 2cos(theta)^2 - 1 = 2cos(theta)T_1(cos(theta))
- T_0(cos(theta)) \] 2. Computers actually use this recursion to calculate sines and cosines! So, it's a little inefficient to code your Chebyshev polynomials using `math.sin`. 3. Using generating functions, you can get a closed form for T_n(x) that only takes O(log n) time to calculate. (Note: assuming you count multiplications as constant. However, you actually need O(log n) bits to accurately represent x, so it's more accurately O((log n)^2 log log n).) |