Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 69 / 3

Let $p\in A$, $r=f-p$, $E=\Vert r{\Vert }_{\infty }$ and $M=\{x\in [0,1]:|r(x)|=E\}$. The Kolmogorov criterion for uniform approximation saysIf $E=0$, $p=f$ is already best and the criterion holds. Suppose $E>0$. If $q=p+h$ were strictly better, then $|r(x)-h(x)|<|r(x)|=E$ on $M$, which forces $r(x)h(x)>0$ there. Conversely, if a direction $h$ has $rh>0$ everywhere on $M$, compactness gives a positive lower bound on this product. On a sufficiently small neighborhood of $M$, $r$ and $h$ therefore have matching signs with $|h|$ bounded away from zero and $|r|$ bounded away from zero. On its compact complement, $|r|\le E-\delta$ for some $\delta >0$. Choose $\epsilon >0$ so small that $\epsilon \Vert h{\Vert }_{\infty }<\delta$ and that subtracting $\epsilon h$ does not cross zero on that neighborhood. Then $\Vert r-\epsilon h{\Vert }_{\infty }<E$, so $p$ is not a best uniform approximation. This proves both directions.

The Chebyshev alternation theorem states that $p\in {\mathcal{P}}_n$ is a best uniform approximation to real $f$ precisely when there are $n+2$ increasingly ordered points $x_0<\cdots <x_{n+1}$ withFor sufficiency, an improving polynomial direction $h$ would have to share these alternating signs, by the Kolmogorov criterion for uniform approximation. The intermediate value theorem would give at least $n+1$ distinct roots of a polynomial between consecutive points. A nonzero polynomial of degree at most $n$ cannot do that. If $E=0$, no improvement is possible anyway.

For necessity, suppose $E>0$ and the active set $M$ has no alternating sequence of length $n+2$. Its positive-error and negative-error subsets are disjoint compact sets, hence separated by a positive distance. Reading them from left to right splits $M$ into finitely many consecutive sign blocks. If there are $L$ blocks, choosing one point per block gives an alternating sequence, so $L\le n+1$. Choose $z_j$ in the gap between each consecutive pair of blocks. The polynomial $h(x)=C{\prod }_{j=1}^{L-1}(x-z_j)$ has degree at most $n$; choose the sign of $C$ to match the error on the first block. Its sign then matches the error on every block, and it is nonzero throughout $M$. Thus $rh>0$ on $M$, contradicting the Kolmogorov criterion for uniform approximation. There must therefore be $n+2$ alternating extrema.

Choose a best uniform approximation $p_n\in {\mathcal{P}}_n$. It exists because this vector subspace is a finite-dimensional vector space and a minimizing sequence $q_j$ is bounded: $\Vert q_j{\Vert }_{\infty }\le \Vert f{\Vert }_{\infty }+\Vert f-q_j{\Vert }_{\infty }$. Finite-dimensional equivalence of norms then supplies a convergent subsequence of coefficients. If $E_n(f)>0$, the Chebyshev alternation theorem gives $n+2$ alternating error extrema. The intermediate value theorem supplies a zero $x_{n,k}$ of $f-p_n$ in each of the $n+1$ intervening open intervals. These interpolation nodes are distinct, and uniqueness of polynomial interpolation givesThe convergence follows from the Weierstrass approximation theorem. If $E_n(f)=0$, choose any $n+1$ distinct nodes: the polynomial interpolant is still $f=p_n$. This constructs interpolation nodes from best uniform approximation; the nodes depend on $f$, and no universal node system for all continuous functions is asserted.