NLA MT25, Chebyshev polynomials
Flashcards
@Define the Chebyshev polynomials $T _ k(x)$ in terms of trigonometric functions and derive a three term recurrence.
Let $z = \exp(i\theta)$ and set $x = \frac 1 2(z + z^{-1}) = \cos \theta$. Then
\[T _ k(x) = \frac 1 2(z^k + z^{-k}) = \cos(k\theta)\]Then we have
\[\underbrace{\frac 1 2 (z + z^{-1})(z^k + z^{-k})} _ {=\, 2x\, T _ k(x)} = \underbrace{\frac 1 2 (z^{k+1} + z^{-(k+1)}) + \frac 1 2 (z^{k-1} + z^{-(k-1)})} _ {=\, T _ {k+1}(x) \,+\, T _ {k-1}(x)}\](the brace values use $x = \frac 1 2(z + z^{-1})$ and $T _ j(x) = \frac 1 2(z^j + z^{-j})$). Hence
\[2x T _ k(x) = T _ {k+1}(x) + T _ {k-1}(x)\]Base cases $T _ 0(x) = 1$, $T _ 1(x) = x$; the recurrence then shows each $T _ k$ is a degree-$k$ polynomial in $x$.
@State a result about the behaviour of Chebyshev polynomials inside and outside $[-1, 1]$.
Inside $[-1, 1]$:
For all $x \in [-1, 1]$,
\[ \vert T _ k(x) \vert \le 1\]Outside $[-1, 1]$:
\[ \vert T _ k(x) \vert \gg 1\]grows rapidly with $ \vert x \vert $ and $k$, and has the fastest growth among $p \in \mathcal P _ k$, with $ \vert p(x) \vert \le 1$ on $x \in [-1, 1]$.
@State a result about the symmetry of Chebyshev polynomials.
for all $x \in \mathbb R$.
Bite-sized
The shifted-and-scaled Chebyshev polynomial on $[a, b]$ that satisfies $p(0) = 1$ is $p(x) = c _ k T _ k\!\left(\tfrac{2x - b - a}{b - a}\right)$ with $c _ k = $ $1 / T _ k\!\left(\tfrac{-(b + a)}{b - a}\right)$.
For the shifted-and-scaled Chebyshev polynomial $p$ with $p(0) = 1$ on $[a, b]$ ($0 < a \le b$, $\kappa = b / a$), the resulting minimax bound is $ \vert p(x) \vert \le <span class="cloze" tabindex="0">1/T _ k\!\left(\tfrac{b + a}{b - a}\right)</span> \le <span class="cloze" tabindex="0">2\left(\tfrac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\right)^k</span>$ for all $x \in [a, b]$.
Why are Chebyshev polynomials the right choice for the CG-convergence analysis?
For any $ \vert M \vert > 1$, $T _ k$ minimises $\max _ {z \in [-1, 1]} \vert p(z) / p(M) \vert $ over all $p \in \mathcal P _ k$ — equivalently, it is the polynomial that takes the smallest values inside $[-1, 1]$ relative to a fixed value at $M$ outside. Shifting and scaling onto $[\lambda _ \min, \lambda _ \max]$ with $M$ mapped to $0$ gives the tightest possible upper bound on $\max _ j \vert p(\lambda _ j) \vert $ subject to $p(0) = 1$, which is exactly the optimisation CG performs implicitly.
Note: the $\sqrt\kappa$ (not $\kappa$) in the CG rate $\frac{\sqrt\kappa - 1}{\sqrt\kappa + 1}$ comes from the change of variables $\frac{1}{2}(z + z^{-1}) = \frac{b + a}{b - a}$, which gives $z = $ $\frac{\sqrt{b/a} + 1}{\sqrt{b/a} - 1}$. Since $T _ k(z) \sim \frac{1}{2} z^k$ for $ \vert z \vert > 1$, the asymptotic decay rate is $1/z$.