Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 75 / 3

For a real continuous function on $[-1,1]$, the Chebyshev alternation theorem gives a unique best uniform approximation $p_n^{\ast }$ from the space of polynomials of degree at most $n$. If $f$ is not already in that space, a candidate $p$ is best if and only if there exist ordered points $x_0<\cdots <x_{n+1}$ and a sign $\sigma \in \{1,-1\}$ withThus a nonzero best error has at least $n+2$ alternating extrema of equal magnitude. If $f$ is already a polynomial of degree at most $n$, the unique best approximant is $f$ itself with zero error.

Existence does not require assuming that the infimum is attained: a minimizing sequence has uniformly bounded polynomial norms, and evaluation at $n+1$ fixed distinct nodes bounds its coefficients through an invertible interpolation matrix. A convergent coefficient subsequence then attains the infimum. The alternation criterion characterizes that minimum and gives uniqueness. In the following parts, $n\ge 1$ whenever $E_{n-1}$ occurs.

A nontrivial example is $f_n=T_{n+1}$, the Chebyshev polynomial characterized by $T_{n+1}(\cos \theta )=\cos ((n+1)\theta )$. Its supremum norm is one. At the $n+2$ points $\cos (j\pi /(n+1))$, $0\le j\le n+1$, its values alternate between $1$ and $-1$; reversing their order gives increasing nodes with the same alternation.

The zero polynomial therefore satisfies the Chebyshev alternation theorem for degree at most $n$, so $E_n(f_n)=1$. Since the smaller polynomial space is contained in the larger one, $E_{n-1}(f_n)\ge 1$; the zero polynomial is feasible in the smaller space as well, giving the reverse inequality. HenceA constant function would also give equality with both errors zero, but this example shows that equality can occur at a positive approximation error.

Let $p$ be the best uniform approximation to the exponential function from the degree-at-most-$n-1$ polynomial space. Suppose that $E_{n-1}(e^x)=E_n(e^x)$. Then the same $p$ is best in the larger space. Its error $g(x)=e^x-p(x)$ is nonzero, since the exponential is not a polynomial. The Chebyshev alternation theorem supplies $n+2$ ordered points where $g$ has alternating signs. By the intermediate value theorem, $g$ has at least one zero in each of the $n+1$ intervening intervals, hence at least $n+1$ distinct zeros.

Applying Rolle's theorem successively $n$ times forces a zero of $g^{(n)}$. But $\mathrm{deg}p\le n-1$, soeverywhere. This is a contradiction. Together with the automatic non-increase of best errors, it provesThe argument is an instance of strict polynomial error decrease from nonvanishing derivatives.

For each $n$, choose the best uniform approximation $p_n^{\ast }$. If its error is nonzero, take its $n+2$ alternating extrema. The intermediate value theorem supplies a point $y_j$ strictly between the $j$th and $(j+1)$st extrema such that $f(y_j)=p_n^{\ast }(y_j)$, for $0\le j\le n$. These $n+1$ points are distinct. The polynomial interpolation problem at them has a unique solution of degree at most $n$, so its solution is exactly $p_n^{\ast }$. This constructs the interpolation nodes from best uniform approximation.

If $E_n(f)=0$, then $f$ itself belongs to the polynomial space, and any $n+1$ distinct nodes give the same conclusion. In either case, take $x_{n,j}=y_j$ or the arbitrary nodes just described. ThenThe Weierstrass approximation theorem gives $E_n(f)\to 0$; alternatively, the bound derived in part 4(b), combined with uniform continuity, gives this convergence directly. ThereforeThe nodes may depend on $f$ and on $n$. The conclusion does not assert a universal sequence of interpolation grids working for every continuous target.