Chebyshev coefficients from a polynomial

Question

Is there an efficient algorithm for finding the coefficients in a Chebyshev basis of a polynomial? That is, given the set of $a_k$ such that:

$p_n(x) = \sum_{k=0}^N a_k x^k $

Find the set of $c_k$ such that:

$ p_n(x) = \sum_{k=0}^N c_k T_k(x)$

Where $T_k(x)$ is the kth Chebyshev polynomial of the first kind

I've found this link but I think there's some typos in the explanation since the bounds on the sums don't make sense.

Answer 1

Natural way to arrive at the formulas would be to use orthogonality: $$ c_k = \frac{2 - \delta_{k,0}}{\pi} \int_0^\pi \cos(k x) p_n(\cos(x)) \mathrm{d}x = \frac{2 - \delta_{k,0}}{\pi} \sum_{m=0}^n a_m \int_0^\pi \cos(k x) \cos^m(x) \mathrm{d}x $$ Now, using $$ \begin{eqnarray} \cos^m(x) &=& \Re\left( \left( \frac{1}{2} \left(\mathrm{e}^{i x} + \mathrm{e}^{-i x} \right) \right)^m \right) = \Re\left(\frac{1}{2^m} \sum_{r=0}^m \binom{m}{r} \mathrm{e}^{i (r x - x (m-r) }\right)\\ &=& \frac{1}{2^m} \sum_{r=0}^m \binom{m}{r} \cos((2r-m)x) \end{eqnarray}$$ we have $$\begin{eqnarray} c_k &=& \frac{2 - \delta_{k,0}}{\pi} \sum_{m=0}^n \frac{a_m}{2^m} \frac{\pi}{2-\delta_{k,0}} \sum_{r=0}^m \binom{m}{r} \delta_{k, | 2r-m |} \\ &=& \sum_{m=0}^{n} \frac{a_m}{2^m} \left[ m + k \equiv 0 \mod 2 \right] \frac{1}{1+\delta_{k,0}}\left( \binom{m}{\frac{m+k}{2}} + \binom{m}{\frac{m-k}{2}} \right) \end{eqnarray}$$

Here is a confirmation in Mathematica:

In[21]:= c[k_Integer] := 
  Sum[1/2^m a[m] 1/(
    1 + KroneckerDelta[k, 0]) (Binomial[m, (k + m)/2] + 
      Binomial[m, (-k + m)/2]), {m, Mod[k, 2], n, 2}];

In[22]:= Table[
  Sum[c[k] ChebyshevT[k, x], {k, 0, n}], {n, 0, 4}] // Expand

Out[22]= {a[0], a[0] + x a[1], a[0] + x a[1] + x^2 a[2], 
 a[0] + x a[1] + x^2 a[2] + x^3 a[3], 
 a[0] + x a[1] + x^2 a[2] + x^3 a[3] + x^4 a[4]}

In[23]:= Table[Sum[a[m] x^m, {m, 0, n}], {n, 0, 4}] == %

Out[23]= True