Past exam of the mathematics course of the University of Cambridge / 2011 / ii / Paper 3 / 12F (Topics in Analysis)

Let $E=\Vert f-p{\Vert }_{\infty }$. If $E=0$, minimality is immediate. Otherwise suppose a polynomial $q$ of degree at most $n$ has strictly smaller error. At each alternation point,Thus $q-p$ changes sign between every pair of consecutive $x_j$. By the intermediate value theorem it has at least $n+1$ distinct roots of a polynomial, contradicting its degree bound. ThereforeThis is the sufficiency direction of the Chebyshev alternation theorem.

Let $E_{\ast }={\inf }_{\mathrm{deg}q\le n}\Vert f-q{\Vert }_{\infty }$, and choose a minimizing sequence $p_m$ with $\Vert f-p_m{\Vert }_{\infty }\to E_{\ast }$. Since $E_{\ast }\le \Vert f{\Vert }_{\infty }$, discarding finitely many terms ensures $\Vert p_m{\Vert }_{\infty }\le 2\Vert f{\Vert }_{\infty }+1$.

Fix $n+1$ distinct nodes $a_0,\dots ,a_n$. The Lagrange interpolation formula expressesThe vector of node values is bounded in ${\mathbb{R}}^{n+1}$, so the Bolzano-Weierstrass theorem supplies a subsequence converging to $(v_0,\dots ,v_n)$. Put $p=\sum v_j{\ell }_j$, of degree at most $n$. Because the ${\ell }_j$ are fixed bounded functions,along that subsequence. The reverse triangle inequality implies $\Vert f-p{\Vert }_{\infty }=E_{\ast }$. Thus a best uniform approximation exists, with no appeal to an unproved abstract existence result.

Here ${\mathcal{P}}_n$ is the vector space of real polynomials of degree at most $n$.

Enumerate the finite set increasingly, $y_1<\cdots <y_{n+2}$, so alternating signs refer to spatial order. This is the enumeration needed for the interpolation construction below. The Lagrange cardinal polynomials satisfy $r_j(y_k)={\delta }_{jk}$ and have degree $n+1$.

If the printed indexing were interpreted as an arbitrary fixed permutation, the assertion in (a) would need this qualification. For example with $n=2$, $(y_1,y_2,y_3,y_4)=(0,1/3,1,2/3)$ gives $r(x)=-1+9x(1-x)$ of degree two; for $f=0$ every $\lambda$ works. Ordering the nodes resolves the issue and yields the requested minimizer for every set $Y$.

The coefficient of $x^{n+1}$ in $r_j$ isWith the increasing enumeration, its sign is $(-1{)}^{n+2-j}$. Therefore all terms $(-1{)}^j{c}_j$ have the same sign $(-1{)}^{n+2}$, and $R:={\sum }_j(-1{)}^j{c}_j\ne 0$. The leading coefficient of $t$ is $T:={\sum }_{j}f(y_j)c_j$. Canceling the coefficient of $x^{n+1}$ gives the unique valueBoth interpolants have degree at most $n+1$, so this single cancellation is equivalent to $\mathrm{deg}(t-\lambda r)\le n$.

Set $p=t-\lambda r$ using part (a). At every node,If $\lambda =0$, the error vanishes. Otherwise any degree-at-most-$n$ polynomial $q$ with strictly smaller error would make $q-p$ have alternating nonzero signs at the increasingly ordered nodes (reversed globally if $\lambda <0$). It would then have at least $n+1$ distinct roots by the intermediate value theorem, impossible. Hence