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

Direct evaluation gives $X[1]=X[x]=X[x^2]=0$ and $X[x^3]=-13/16$. Hence the linear functional vanishes on every polynomial of degree at most two and is nonzero on every genuine cubic polynomial.

The Peano kernel theorem with order three gives $X[u]={\int }_{-1}^{1}K(t)u^{\prime \prime \prime }(t)dt$, whereThe first term comes from differentiating $(x-t{)}_{+}^2/2$ at $x=1/4$. On the integration interval this simplifies toIn particular $K\le 0$. Its L1 norm is $-\int K=-X[x^3/6]=13/96$, so the sharp bound isThe printed constant $1/12$ is false for the printed functional. The cubic $u=x^3/6$ has $\Vert u^{\prime \prime \prime }{\Vert }_{\infty }=1$ but $|X[u]|=13/96>1/12$, and it attains the corrected bound. This is an exact Peano kernel norm calculation, not an error from numerical quadrature.

A cubic spline that vanishes for $x\le 0$ and is twice continuously differentiable can be written using truncated power functions as $s(x)={\sum }_{j=0}^k{a}_j(x-jh{)}_{+}^3$. Vanishing for $x\ge kh$ imposes the four moment equations ${\sum }_j{a}_j{j}^r=0$ for $r=0,1,2,3$. Their Vandermonde matrix has rank $\min (4,k+1)$, so a nonzero coefficient vector first exists at $\boxed{k=4}$.

A normalized compact cubic cardinal B-spline isIt has nodal values $0,1/6,2/3,1/6,0$ at $0,h,2h,3h,4h$, so their sum is one. The alternating binomial coefficients meet the four moment equations, and the factor $1/6$ fixes the requested normalization.

For interpolation on $[-1,1]$, centre the translates as ${\beta }_j(x)=B_3(x/h-j+2)$, with $j=-n-1,\dots ,n+1$. Their restrictions form a basis for the cubic $C^2$ spline space on these knots. Write $S={\sum }_j{c}_j{\beta }_j$. The $2n+1$ interpolation equations areThe recurrence determines all remaining coefficients after choosing $c_{-n-1},c_{-n}$, giving exactly two free parameters. The two natural cubic spline conditions becomebecause $S^{\prime \prime }(rh)=h^{-2}(c_{r-1}-2c_r+c_{r+1})$.

For uniqueness, take the difference $s$ of two candidates. It vanishes at every knot and has $s^{\prime \prime }(\pm 1)=0$. Integrating by parts twice on each cubic piece gives ${\int }_{-1}^1(s^{\prime \prime }{)}^2=0$: terms involving $s$ vanish at the knots, and those involving $s^{\prime \prime }{s}^{\prime }$ cancel at internal knots and vanish at the endpoints. Thus $s^{\prime \prime }=0$; the remaining affine function vanishes at both endpoints and is zero. The square linear system for the coefficients is therefore nonsingular, giving existence as well as uniqueness of the natural cubic spline interpolant.

Let $e=u-p$. If $p$ minimizes the squared L2 norm error, then for any $q\in A$ the real quadratic $\Vert e-tq{\Vert }_2^2=\Vert e{\Vert }_2^2-2t(e,q)+t^2\Vert q{\Vert }_2^2$ has its minimum at $t=0$. Its derivative there is zero, giving $(e,q)=0$.

Conversely, if $e$ is orthogonal to $A$, then for every $q\in A$, $p-q\in A$ and the Pythagorean theorem for inner product spaces givesThis proves the equivalence and identifies $p$ as an orthogonal projection. It characterizes a minimizer whenever one exists; a general nonclosed vector subspace need not admit a projection for every $u$.

The orthogonal projection is $p_n={\sum }_{r=0}^n(u,{\varphi }_r){\varphi }_r$. Subtract it from $u$ and use the orthonormal basis relations to obtainThis is the requested Bessel inequality.

For the infinite tail, use completeness of the orthonormal polynomial family in the usual weighted L2 space. The relevant density facts are that continuous functions are dense for the finite measure $w(x)dx$, and the Weierstrass approximation theorem makes polynomials uniformly dense in continuous functions on the compact interval. Since $\int w<\infty$, uniform approximation also gives weighted L2 norm approximation. Parseval's identity therefore givesHere finiteness of the weight integral is also necessary for the constant polynomial to belong to the stated Hilbert space. Without completeness of the polynomial family, an additional squared component orthogonal to every polynomial would remain; Bessel inequality alone does not justify equality.

The moments are ${\int }_0^1{x}^{j+2}dx=1/(j+3)$. The Gram-Schmidt process first gives the constant ${\varphi }_0=\sqrt{3}$. Removing the constant component of $x$ gives $r_1=x-3/4$, with squared norm $1/80$, hence ${\varphi }_1=4\sqrt{5}(x-3/4)$.

For the quadratic, imposing orthogonality of $r_2=x^2+ax+b$ to one and $x$ gives $1/5+a/4+b/3=0$ and $1/6+a/5+b/4=0$. Thus $r_2=x^2-4x/3+2/5$, whose squared norm is $1/1575$. Taking positive leading coefficients, the first three orthonormal polynomials are

For $n\ge 1$, ${\varphi }_n$ is orthogonal to every polynomial in $P_{n-1}$, so $(u,{\varphi }_n)=(u-p_{n-1}^{\ast },{\varphi }_n)$. The Cauchy-Schwarz inequality givesUsing the tail identity from part (b) and shifting the index,For the stated power law and $n>1$, the decreasing-function integral test givesConsequentlyThe assumption $a>1$ is sufficient; this summation estimate itself only needs $a>1/2$.

Put $m={\min }_r|u(x_r)-q(x_r)|$ and $M={\max }_r|u(x_r)-q(x_r)|$. If the best uniform approximation had error below $m$, the values of $p_n^{\ast }-q$ would strictly alternate in sign at all $n+2$ reference points. The intermediate value theorem would give at least $n+1$ distinct roots of a polynomial of degree at most $n$, a contradiction. If $m=0$ the lower bound is immediate.

At least one reference point attains the global error maximum of $q$, so $M=\Vert u-q{\Vert }_{\infty }$. Optimality of $p_n^{\ast }$ gives the upper bound, and thereforeThis is the unequal-height version of the alternating-reference error bound.

Here the exchange point lies between adjacent reference points and has the same, positive error sign as the point it replaces. Hence the new set remains spatially ordered, and the old error at its points alternates in sign. Its magnitudes are $|h_0|$ everywhere except at $\eta$, where $M=u(\eta )-q(\eta )>|h_0|$.

Set $w_r={\prod }_{j\ne r}(z_r-z_j{)}^{-1}$. Apply the order-$(n+1)$ divided difference to $q$ and $v$; both vanish because their degrees are at most $n$. In the new alternation equations, all products $(-1{)}^r{w}_r$ have the same sign. Thus the single-point exchange in polynomial minimax approximation givesThe Remez algorithm repeatedly solves for the reference polynomial and common signed height, locates a larger error extreme, and performs an order-preserving exchange. The reference height bounds the optimum from below and the global error maximum bounds it from above. Their gap provides an optimality stopping certificate. A general implementation also needs the endpoint exchange rule when the new extreme lies outside the reference set.

For a line $p(x)=ax+b$, the error $e^x-ax-b$ is strictly convex. Its two endpoint maxima must agree, giving $a=e-1$. Its unique interior minimum is at $c=\log a\in (0,1)$. Equating its magnitude to the endpoint error givesThe errors at $0,c,1$ are respectively $E_1,-E_1,E_1$. The equioscillation theorem therefore certifies this best uniform approximation directly.

For degree above one, subtracting a general polynomial does not preserve convexity of the error. The required $n+2$ alternating extreme points include additional unknown interior points, and their derivative and equal-height equations form a coupled nonlinear problem. The simple endpoint-and-single-minimum calculation therefore does not extend as a direct higher-degree recipe.