The Chebyshev polynomials (of the first kind) are a sequence of polynomials defined recursively by
$$
\begin{cases}
T_{0}(x) = 1 \\
T_{1}(x) = x \\
T_{n}(x) = 2xT_{n-1}(x) – T_{n-2}(x)
\end{cases}
$$
I'll refer to Mathematica for all other properties, which I haven't needed so far.
Using this recurrence relation, it is easy to expand given lineair combinations of Chebyshev polynomials as linear combinations of powers of $x$. What I do in Matlab, is I choose an upper bound $n$ for the degree of polynomials I'll be working with and then write the conversion out explicitly in matrix form. For example, if $n = 4$, I'd have:
$$
A = \begin{bmatrix}
1& 0& -1& 0& 1 \\
0& 1& 0& -3& 0 \\
0& 0& 2& 0& -8 \\
0& 0& 0& 4& 0 \\
0& 0& 0& 0& 8
\end{bmatrix}
$$
where the columns are constructed from left to right using the recurrence relation.
If $c$ is a vector of coefficients of a polynomial (of degree $\leq 4$) with respect to the Chebyshev basis, then its coefficients with respect to the monomial basis are simply given as $A \cdot c$.
If I want to go the other way around, that is, rewriting a linear combination of powers of x as a linear combination of Chebyshev polynomials, I can just invert this matrix. Needless to say, this fails numerically as soon as $n$ gets large enough (the elements on the main diagonal of $A$ are powers of 2). I was wondering if there is a better way to obtain this inverse matrix, perhaps by using some inverse recurrence formula?
Kind regards
Nicolas
Best Answer
We may think to this problem in these terms: to write $T_n(x)$ as a linear combination of monomials is the same as expressing $\cos(nx)$ in terms of $\cos(x),\cos^2(x),\ldots$ On the other hand, to express $x^n$ in terms of $T_0(x),\ldots,T_n(x)$ is the same as expressing $\cos(x)^n$ in terms of $1,\cos(x),\cos(2x),\ldots$, i.e. to compute the Fourier cosine series of $\cos(x)^n$. That is an easy task through the binomial theorem, since:
$$ \cos^n(x) = \left(\frac{e^{ix}+e^{-ix}}{2}\right)^n = \frac{1}{2^n}\sum_{j=0}^{n}\binom{n}{j}e^{(n-2j)ix}\tag{1}$$ gives: $$ \cos^{2n}(x)=\frac{1}{4^n}\binom{2n}{n}+\frac{2}{4^n}\sum_{j=1}^{n}\binom{2n}{n+j}\cos(2jx)\tag{2}$$ so: $$ x^{2n} = \frac{1}{4^n}\binom{2n}{n}+\frac{2}{4^n}\sum_{j=1}^{n}\binom{2n}{n+j} T_{2j}(x).\tag{3}$$ The odd case is similar.
The solution to the inverse problem is given by the formula $(15)$ here: it can be achieved through the binomial theorem, too. This sheds some light on the relation between the Lagrange inversion formula and the inversion of structured matrices (Toeplitz matrices, in this case) through Cramer's rule or Gaussian elimination.