Chebyshev iteration

Remarks

Since $A$ is symmetric, $\norm{p_k(A)}_2 = \max_\lambda \abs{p_k(\lambda)}$ over its eigenvalues, and on $[\alpha, \beta]$ the numerator of $p_k$ is at most $1$ in absolute value. The bound $T_k(\theta) \ge \frac12 \sigma^{-k}$ with $\sigma = (\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1)$ follows from $T_k(x) = \frac12 \big( (x + \sqrt{x^2 - 1})^k + (x - \sqrt{x^2 - 1})^k \big)$ for $x \ge 1$. Among all polynomials of degree $k$ with value $1$ at $0$, the scaled Chebyshev polynomial $p_k$ has the least maximum on $[\alpha, \beta]$. So no method of the form $e_k = q(A) e_0$ with such $q$ can do better in the worst case over matrices with spectrum in $[\alpha, \beta]$. For comparison, the optimal Richardson iteration contracts by $(\kappa - 1)/(\kappa + 1)$ per step. Example: for $\kappa = 100$ the Chebyshev factor is $9/11 \approx 0.82$, while the Richardson factor is $99/101 \approx 0.98$. If the interval does not contain the whole spectrum, the bound fails and the method can diverge.

Going deeper

For a student

The error factor depends on $\sqrt{\kappa}$ instead of $\kappa$, like the conjugate gradient method, where $\kappa$ is the condition number. Unlike conjugate gradients it needs no inner products, which helps on parallel machines where global sums are costly. Its iterates lie in the Krylov subspace shifted by $x^{(0)}$, and the conjugate gradient method finds an iterate there that is at least as good in the energy norm. Chebyshev polynomials are also used as smoothers in multigrid and as polynomial preconditioners.