Past exam of the approximation theory and finite element methods course of the University of Oxford / 2008 / A / 4

The equioscillation theorem says that a best degree-at-most-$n$ polynomial approximation to a continuous real function on $[a,b]$ has $n+2$ ordered extreme-error points with alternating signs and equal absolute error. Conversely such alternation proves optimality. If the error is zero, the target is already a polynomial of the required degree.

For the single-point exchange in polynomial minimax approximation, start with $n+2$ ordered reference points $t_j$ and solve the linear systemfor the $n+1$ polynomial coefficients and $E$. Locate a point of largest absolute error on the interval. If its magnitude is no larger than $|E|$ within the desired tolerance, alternation certifies the approximation.

Otherwise insert that point and delete one old reference point so that the ordered signs still alternate. If the new point lies between two reference points, delete the neighboring point with the same error sign. If it lies outside the reference range, either replace the adjacent same-sign endpoint or, for opposite sign, insert it and drop the far endpoint. Solve again and repeat. This is the one-point Remez algorithm; a global extreme-error search is required for its stopping certificate, rather than merely checking the old reference points.

A $C^2$ piecewise cubic supported on $[0,ph]$ has the truncated-power representation with indices $0,\dots ,p$. Vanishing for $x\ge ph$ imposesafter expanding its cubic exterior polynomial; powers of $h$ cancel. For $p\le 3$, the Vandermonde matrix columns are independent, forcing every coefficient to be zero. For $p=4$, coefficients proportional to $(1,-4,6,-4,1)$ satisfy these conditions because a fourth finite difference annihilates cubics.

Normalize to get the Cardinal cubic B-splineAt its five support knots its values are $0,1/6,2/3,1/6,0$, so their sum is one. Thus four intervals are necessary and sufficient.

For $h=1/2$, the five translates active in the interior of $[0,1]=[0,2h]$ are indexed $-3,-2,-1,0,1$. Write $s(x)={\sum }_{j=-3}^1{c}_j{N}_j^3(x)$. Nodal interpolation givesAt the left endpoint the first derivatives of the three active functions are $-1/(2h),0,1/(2h)$, and their second derivatives are $1/h^2,-2/h^2,1/h^2$. The two remaining equations areTogether these five equations form the requested system; insert $h=1/2$ if numerical coefficients are desired. The first, fourth and fifth determine the first three coefficients, and the other two then determine $c_0,c_1$, so the system is nonsingular.

The source only assumes $u\in C[0,1]$, which need not have either endpoint derivative. The Hermite conditions require those derivatives to exist, or to be supplied as separate interpolation data. The nodal conditions alone remain meaningful for every continuous $u$.