Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 69 / 4 / b / Solution

For a real continuous function $f$, the Chebyshev alternation theorem asserts that a polynomial $p\in {\mathcal{P}}_n$ is a best uniform approximation exactly when either it is exact or its residual $r=f-p$ has $n+2$ ordered alternating extrema:Here ${\mathcal{P}}_n$ means degree at most $n$, as required for a linear subspace.

For sufficiency, if a polynomial perturbation $v\in {\mathcal{P}}_n$ violated the Kolmogorov criterion for uniform approximation, then $r(x_j)v(x_j)>0$ at every displayed point. Thus $v(x_j)$ would alternate signs, forcing a distinct zero in each of the $n+1$ intervals $(x_j,x_{j+1})$ by the intermediate value theorem. A nonzero polynomial of degree at most $n$ cannot have that many zeros; the zero polynomial does not violate the criterion either.

For necessity, assume $M=\Vert r{\Vert }_{\infty }>0$ and no such alternating sequence exists. The two compact sets $E_{+}=\{r=M\}$ and $E_{-}=\{r=-M\}$ are disjoint and, when both are nonempty, have positive separation. Hence the extremal set has finitely many successive sign runs: infinitely many alternations would contradict that separation on the bounded interval. If there are $m$ changes of sign between those runs, then selecting one point from each run gives an alternating sequence of length $m+1$, so $m\le n$. Choose a point $z_j$ in the gap between each pair of consecutive opposite-sign runs, and setChoose the sign of $C$ so that $v$ agrees with $r$ on the first run. The roots lie outside the extremal set and each changes the sign, so $rv>0$ at every extremal point. Since $\mathrm{deg}v=m\le n$, this contradicts the Kolmogorov criterion for uniform approximation. Therefore a best polynomial must have the required alternation.

Existence also holds: a minimizing sequence has bounded supremum norms, hence bounded coefficients by evaluating at $n+1$ fixed distinct points and inverting the resulting Vandermonde matrix. A convergent subsequence of coefficients yields a minimizer. Finally, if $p$ and $q$ are both best, their average is best; at its alternating extrema both individual residuals must equal the same extremal value. Consequently $p-q$ has at least $n+2$ zeros and is identically zero. The best polynomial exists, is unique, and is characterized by alternation.