Past exam of the approximation theory and finite element methods course of the University of Oxford / 2009 / A / 3

By definition, a best uniform approximation $p^{\ast }\in P_n$ minimizes $\Vert u-p{\Vert }_{\infty }$ over $p\in P_n$. Write $E=\Vert u-p^{\ast }{\Vert }_{\infty }$. The equioscillation theorem says that, if $E>0$, optimality is equivalent to the existence of $n+2$ ordered points with signed errorsThe absolute-value bars on the left of the printed formula must be omitted for this alternating-sign statement. A nonnegative absolute value cannot equal a negative $-E$.

For sufficiency, suppose a polynomial $p$ had strictly smaller error. At the alternating points, $p-p^{\ast }$ must have the same sign as $u-p^{\ast }$, since otherwise the new error would have magnitude at least $E$. The difference polynomial therefore changes sign in all $n+1$ successive gaps and has at least $n+1$ distinct roots, impossible for a nonzero element of $P_n$.

For necessity, suppose that no $n+2$ alternating extremal points exist. On the compact extremal set $K=\{x:|u(x)-p^{\ast }(x)|=E\}$, group the signs of the error into consecutive blocks. The positive and negative extremal sets are disjoint compact sets, so sign changes are separated by positive distances; the number of blocks is finite. The absence of an $n+2$ alternating selection means there are at most $n+1$ blocks. Place a root in each gap between successive blocks and choose the overall sign of their product $q$ to agree with the error on $K$. Then $\mathrm{deg}q\le n$ and $q$ is nonzero throughout $K$.

By compactness and continuity, on a neighborhood of $K$ the signs still agree and $|q|$ is bounded below. A sufficiently small positive $\eta$ reduces the error there when $p^{\ast }$ is replaced by $p^{\ast }+\eta q$. On the compact complement of this neighborhood the old error is below $E$ by a fixed positive margin, and choosing $\eta$ smaller preserves that margin. This gives a strictly better approximation, a contradiction. If $E=0$, the target already lies in $P_n$ and optimality is immediate.

For $u(x)=x^{1/3}$, the chord is $x$. Concavity gives $x^{1/3}-x\ge 0$, with maximum at $x_{\ast }=1/(3\sqrt{3})$ and maximum value $2/(3\sqrt{3})$. Shift the chord up by half that amount. The errors at $0,x_{\ast },1$ are respectively $-E,+E,-E$, so

Use the standard meaning of a cubic spline: a $C^2$ function that is cubic on each unit interval. If it vanishes on both exterior intervals, continuity of the function and its first two derivatives gives zero endpoint jets at zero and at $k$.

Such a spline can be represented through its third-derivative jumps asFor $x\ge k$, this must be the zero polynomial. Expanding in powers of $x$ yields the four moment conditionsIf $k\le 3$, the columns of this Vandermonde system are linearly independent, so every $c_j=0$. No nonzero spline has such short support.

For $k=4$, a nonzero null vector is $(1,-4,6,-4,1)$, since the fourth finite difference annihilates every cubic. Thus the Cardinal cubic B-spline isIts knot values at $0,1,2,3,4$ are $0,1/6,2/3,1/6,0$, whose sum is one. It is nonzero and supported on $[0,4]$, proving the minimal value $k=4$. Equivalently, on $[0,1]$ it is $x^3/6$, on $[1,2]$ it is $[-3x^3+12x^2-12x+4]/6$, and the other half follows by symmetry $\varphi (4-x)=\varphi (x)$.