5.1. Chebyshev polynomials

5.1.1. Cosines

• We know that

  \[\cos(\alpha + \beta) = \cos\alpha \cos\beta - \sin \alpha \sin\beta\]

• Put \(\alpha = n\theta\) and \(\beta = \theta\)

  \[\cos((n+1)\theta) = \cos n\theta \cos\theta - \sin n\theta \sin \theta\]

• Put \(\alpha = n\theta\) and \(\beta = -\theta\)

  \[\cos((n-1)\theta) = \cos n\theta \cos\theta + \sin n\theta \sin \theta\]

• Adding

  \[ \begin{align}\begin{aligned}\cos((n-1)\theta) + \cos((n+1)\theta) = 2\cos n\theta \cos\theta\\\cos((n+1)\theta) = 2\cos n\theta \cos\theta - \cos((n-1)\theta)\end{aligned}\end{align} \]

• We claim that for each non-negative integer \(n\), there exist integers \(c_i\) s.t.

  \[\cos n\theta = \sum_{i=0}^{n} c_i \cos^i (\theta)\]

5.1.2. Chebyshev polynomials

• Essentially \(\cos n\theta\) is a polynomial in \(\cos \theta\).

• For a fixed \(n\) we define \(n^{th}\) Chebyshev polynomial as:

  \[cos(n\theta) = T_n(cos\theta))\]

• Putting \(x = \cos\theta\), \(T_n(x)\) is a polynomial.

  \[T_n(x) = \cos(n \arccos(x)) \quad \forall x \in [-1,1]\]

• Basic Chebyshev polynomials:

  \[\begin{split}&T_0(x) = \cos 0 \theta = 1 \\ &T_1(x) = \cos 1 \theta = x\end{split}\]

• Recurrence relation:

  \[\begin{split}&T_{n-1}(x) + T_{n+1}(x) = 2 T_1(x) T_n(x) = 2x T_n(x)\\ &T_{n+1}(x) = 2x T_n(x) - T_{n-1}(x)\end{split}\]

  or

  \[x T_n(x) = \frac{T_{n-1}(x) + T_{n+1}(x)}{2}\]

  This has resemblance to space shift operator in algebraic signal processing.

• Recurrence examples:

  \[\begin{split}&T_2(x) = 2x T_1(x) - T_0(x) = 2x^2 - 1\\ &T_3(x) = 2 T_2(x) - T_1(x) = 2x(2x^2 -1) - x = 4x^3 - 3x\end{split}\]

• Chebyshev polynomials upto 7th order

  \[\begin{split}&T_0(x) = 1 \\ &T_1(x) = x \\ &T_2(x) = 2x^2 - 1\\ &T_3(x) = 4x^3 - 3x\\ &T_4(x) = 8x^4 - 8x^2 + 1\\ &T_5(x) = 16x^5 - 20x^3 + 5x\\ &T_6(x) = 32x^6 - 48x^4 + 18x^2 - 1\\ &T_7(x) = 64x^7 - 112x^5 + 56x^3 -7x\end{split}\]

5.1.3. Properties

Maximum value

\[\max_{-1\leq x \leq 1}T_n(x) = 1\]

Composition

\[T_m(T_n(x)) = T_{mn}(x)\]

Proof:

\[\cos(m \arccos(\cos(n \arccos(x)))) = \cos(mn \arccos(x))\]

Zeros

Zeros of \(T_n(x)\) are given by:

\[x_k = \cos (\frac{(2k-1)\pi}{2n})\quad 1 \leq k \leq n\]

• All the roots of \(T_n(x)\) are real and lie in the interval \([-1,1]\).

Recurrence

\[T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x)\]

Thus:

\[T_{n}(x) = 2^{n-1}x^n + \mathbb{O}(x^{n-1})\]

Symmetry

• Lets compute \(T_{-1}(x)\).

  \[\begin{split}&T_1(x) = 2 xT_0(x) - T_{-1}(x) \\ \implies &T_{-1}(x) = 2 xT_0(x) - T_1(x)\\ &= 2x - x = x = T_1(x)\end{split}\]

• It can be shown that:

  \[T_n(x) = T_{-n}(x)\]

  The sequence of Chebyshev polynomials is symmetric.

5.1.4. Power form

• Euler formula:

\[\cos \theta = \frac{e^{j\theta} + e^{-j\theta}}{2}\]

• Define \(u = e^{j\theta}\)

  \[x = \cos \theta = \frac{u^{1} + u^{-1}}{2}\]

• Thus

  \[T_n(x) = \cos n\theta = \frac{u^{n} + u^{-n}}{2}\]

5.1.5. Differential equation

Even/odd polynomials

\[T_n(-x) = (-1)^n T_n(x)\]

• Even degree Chebyshev polynomials are even functions.

• Odd degree Chevyshev polynomials are odd functions.

Differential equation

• It can be shown that:

  \[(1-x^2)T''_n(x) - xT'_n(x) + n^2T_n(x) = 0\]

• Assume that \(y = \sum_{k=0}^{n}t_k x^k\) is a solution to above differential equation. Then:

  \[(n^2 - k^2)t_k + (k+1)(k+2)t_{k+2} = 0\]

• We already know that \(t_n = 2^{n-1}\)

• Solving further we get:

  \[t_{n-2m} = (-1)^m 2^{n - 2m -1} \frac{n}{n - m} {n -m \choose m}\]

5.1.6. Orthogonality

The integral

\[\int_0^{\pi} \cos (m\theta) \cos (n\theta) d\theta\]

is zero unless \(m=n\).

If \(m=n\)

• If \(m=n=0\), integral is \(\pi\).

• Otherwise, integral is \(\pi/2\)

Putting \(x = \cos\theta\)

\[\int_0^{\pi} \cos (m\theta) \cos (n\theta) d\theta = \int_{-1}^{1} T_m(x) T_n(x) \frac{dx}{\sqrt{1-x^2}}\]

• Chebyshev polynomials are orthogonal over \([-1,1]\) w.r.t. weight \((1-x^2)^{-1/2}\)

• The sequence \(\frac{1}{\pi}T_0, \frac{2}{\pi}T_1, \frac{2}{\pi}T_3,\dots\) is an orthonormal system.

Discrete orthogonality condition

• Let \(x_j\) be roots of \(T_N\)

• The sum:

  \[\sum_{k=1}^{N} T(mx_k) T(nx_k)\]

  • Is zero if \(m \neq n\)

  • \(N\) if \(m=n=0\)

  • \(N/2\) otherwise

5.1.7. Chebyshev polynomials of different kinds

• So far we have looked at Chebyshev polynomials of first kind.

• Chebyshev polynomials are generated by the recurrence relation:

  \[C_{n+1}(x) = 2xC_n(x) - C_{n-1}(x)\]

• \(C_0 = 1, C_1 = x\) generates the Chebyshev polynomials of first kind denoted by \(T_n(x)\).

• Chebyshev polynomials of second, third and forth kind are described below.

5.1.8. References

• [CookChebyshevPolynomials]

Change log

Last Modified

$Id: chebyshev.rst 249 2012-08-05 06:17:57Z shailesh $