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

Let $u\in \mathcal{U}$, $r=f-u$, $M=\Vert r{\Vert }_{\infty }$, and $E=\{x\in [0,1]:|r(x)|=M\}$. The Kolmogorov criterion for uniform approximation saysEquivalently, no available perturbation $v$ has strictly the same sign as the nonzero residual at every extremal point. This statement concerns a candidate $u$ in the linear subspace; it does not assume every subspace has an attained best approximation. If $M=0$, $u=f$ is already exact and the criterion is automatic.

To see sufficiency, for any competitor $u+v$, the criterion supplies an $x\in E$ with $r(x)v(x)\le 0$. Then $|f(x)-u(x)-v(x)|\ge |r(x)|=M$, so the competitor cannot have smaller supremum norm error.

For necessity, suppose $M>0$ and some $v\in \mathcal{U}$ has $r(x)v(x)>0$ on $E$. Since $E$ is compact, this product has a positive minimum there. By continuity, a neighborhood $O$ of $E$ has $rv\ge \eta >0$. For sufficiently small $\epsilon >0$,On the compact complement of $O$, $|r|$ has a strict gap below $M$, and taking $\epsilon \Vert v{\Vert }_{\infty }$ smaller than this gap preserves it. Hence $u+\epsilon v$ improves the uniform error everywhere, contradicting best uniform approximation.

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.