Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 318 (Approximation Theory)

Averaging the integral representations of the Fourier partial sums givesThe finite trigonometric sum isSince $D_k(u)=\sin ((k+1/2)u)/(2\sin (u/2))$, the Fejér kernel is thereforeand

The displayed square shows that $F_n\ge 0$. Every Fourier partial sum preserves the constant function, so ${\sigma }_n(1)=1$. Substituting $f=1$ in the integral formula givesNonnegativity then yields

Because the Fejér kernel has normalized integral one,For $f\in \mathrm{Lip}\alpha$ this impliesOn $0\le t\le \pi$, the inequalities $\sin (t/2)\ge t/\pi$ and $|\sin (nt/2)|\le n|\sin (t/2)|$ giveSplitting the integral at $1/n$ givesFor $0<\alpha <1$, both terms are $O(n^{-\alpha })$. For $\alpha =1$, the second is $O((\log n)/n)$. Uniformly in $x$,where the constants absorb the Lipschitz continuity constant $M$.

At the cusp of $f_0(t)=|t|$, positivity and evenness of the Fejér kernel giveSince $\sin (t/2)\le t/2$,Summing the supplied lower bound over $I_k$, $1\le k\le n^{\prime }=\lfloor n/2\rfloor$, yieldsThe harmonic series satisfies ${\sum }_{k=1}^{n^{\prime }}{k}^{-1}\ge c^{\prime }\log n$, so

The modulus of continuity of the periodic function $f_0$ obeys $\omega (f_0,1/n)=1/n$. If a universal Jackson-type estimateheld for all continuous periodic $f$, it would give $O(1/n)$ for $f_0$, contradicting the lower bound. Thus

The Chebyshev alternation theorem says that $p^{\ast }\in {\mathcal{P}}_n$ is the unique best uniform approximation to $f\in C[-1,1]$ if and only if there are at least $n+2$ ordered pointsand a sign $\epsilon \in \{-1,1\}$ such thatThus the extremal error has common magnitude and alternating sign at $n+2$ points.

Suppose for contradiction that some $q\in {\mathcal{P}}_n$ satisfiesAt $t_i$,Because $|f(t_i)-q(t_i)|<a_i$, the values $p(t_i)-q(t_i)$ have strictly alternating signs. The intermediate value theorem therefore gives at least one root of $p-q$ in each of the $n+1$ intervals $(t_i,t_{i+1})$. A nonzero polynomial of degree at most $n$ cannot have $n+1$ distinct roots. If $p-q$ were identically zero, its error at $t_i$ would be $a_i\ge a_{\ast }$, also a contradiction. Hence

For any $n\ge 0$, take $f_n=T_{n+1}$, the Chebyshev polynomial of degree $n+1$. It has $n+2$ alternating extrema of magnitude one on $[-1,1]$. The Chebyshev alternation theorem shows that the zero polynomial is best from ${\mathcal{P}}_n$, with error one. Since it also lies in ${\mathcal{P}}_{n-1}$ when $n\ge 1$,

Now suppose $f^{(n)}(x)>0$ throughout $[-1,1]$ and, contrary to the claim, $E_{n-1}(f)=E_n(f)$. A best $p\in {\mathcal{P}}_{n-1}$ would then also be best in ${\mathcal{P}}_n$. Its error $e=f-p$ would have $n+2$ alternating extrema by the alternation theorem, hence at least $n+1$ distinct zeros. Applying the Rolle theorem $n$ times gives a zero ofcontradicting positivity. Therefore

For $n\ge 1$, choose the integer $m$ withand define the partial sumIt belongs to ${\mathcal{P}}_n$, and the triangle inequality givesAt the $3^{m+1}+1$ pointsevery tail term has the same alternating sign becauseThusThere are at least $n+2$ such points because $n<3^{m+1}$. The Chebyshev alternation theorem provesFor $n=0$, the partial sum is empty and the same argument at $x=\pm 1$ gives $p_0=0$ and $E_0(f_0)={\sum }_{k=0}^{\infty }{a}_k$.

A B-spline $N_j$ is positive exactly in the interior of its support $(t_j,t_{j+k})$. If the B-spline collocation matrix $A_{\mathbf{x}}$ is invertible, its determinant contains a nonzero permutation term. Hence there is a permutation $\pi$ such that

If $x_i\le t_i$, then every one of the first $i$ points satisfies $x_r<t_i$. Any support containing such a point must have left endpoint $t_j<x_r$, hence $j<i$. Only $i-1$ B-splines are available to match these $i$ rows, contradicting that $\pi$ is a permutation. Thus $x_i>t_i$. Similarly, if $x_i\ge t_{i+k}$, each of the last $n-i+1$ points can only be matched to an index $j>i$, but only $n-i$ such indices exist. Therefore $x_i<t_{i+k}$. We have proved

The Schoenberg–Whitney theorem states, for strictly increasing knots and interpolation sites, thatIndeed its determinant is positive under these inequalities.

Write the interpolating spline asThe interpolation equations are $A_{\mathbf{x}}c=f_{\mathbf{x}}$, where $(f_{\mathbf{x}}{)}_i=f(x_i)$, soThe B-splines are nonnegative and form a partition of unity on the spline interval. ConsequentlyTaking the supremum over $t$ and then over $\Vert f{\Vert }_{\infty }\le 1$ proves the operator norm bound

For Cardinal cubic B-splines, the values at integer knots areand all other knot values vanish. Since $x_i=t_{i+2}$,This tridiagonal matrix is strictly diagonally dominant. The standard inverse bound for such a matrix givesThe minimum denominator is $4/6-2/6=1/3$, soPart (b) then yields

Put $m=k-1$, so the Marsden identity isDifferentiating $m-j$ times with respect to $x$ givesThe exact Taylor formula for a polynomial isSubstitution of the differentiated Marsden identities yieldswhere

Differentiating this expression for ${\lambda }_i$ produces two sums whose adjacent terms cancel. The uncancelled endpoints contain ${\psi }_i^{(k)}$ and $p^{(k)}$, both zero because the two functions have degree at most $k-1$. Thusso the Marsden dual functional ${\lambda }_i(p)$ is independent of the auxiliary point $x$.

Fix ${\xi }_i\in [t_i,t_{i+k}]$ and choose a knot interval $I=(t_{\ell },t_{\ell +1})$ adjacent to it on which $N_i$ is active. Exactly $k$ B-splines are nonzero on $I$, and their polynomial restrictions form a basis of ${\mathcal{P}}_{k-1}$. Applying the expansion from part (a) to the polynomial piece $N_j{|}_I$ givesUniqueness of coordinates in this local basis forceswhen $N_j$ is active. If $N_j$ vanishes on $I$, all of its local polynomial derivatives vanish and the same equality holds with value zero. At a knot, use either adjacent polynomial piece; the $x$-independence proved in part (a) gives the same coefficient. Henceso the ${\lambda }_i$ form the dual basis to the B-spline basis.

Suppose first that $f-u^{\ast }$ is orthogonal to ${\mathcal{U}}_n$. Every $u\in {\mathcal{U}}_n$ can be written $u=u^{\ast }+v$ with $v\in {\mathcal{U}}_n$. The Pythagorean theorem in an inner-product space givesThus $u^{\ast }$ is a best approximation.

Conversely, if $u^{\ast }$ minimizes the distance, then for every $v\in {\mathcal{U}}_n$ the quadratichas its minimum at $t=0$. Differentiating there gives $q^{\prime }(0)=-2(f-u^{\ast },v)=0$ in the real case; varying real and imaginary parts gives the complex case. Therefore

The defining relation for $P_{\mathcal{U}}$ givesPart (a) therefore shows that $P_{\mathcal{U}}f$ is the best approximation. Moreover, $P_{\mathcal{U}}f$ and $f-P_{\mathcal{U}}f$ are orthogonal, soThus orthogonal projection is a contraction:

The integral form of the Taylor theorem about the left endpoint iswhere $q_{k-1}\in {\mathcal{P}}_{k-1}$. Apply the order-$k$ divided difference at $x_i,\dots ,x_{i+k}$. The polynomial term vanishes, and linearity permits interchange with the integral:By the definition $M_i(t)=k[x_i,\dots ,x_{i+k}](\cdot -t{)}_{+}^{k-1}$,This is the Peano kernel theorem for the divided-difference functional.

Substitute the B-spline expansion $s={\sum }_{j=1}^n{a}_j{M}_j$ into $(M_i,s)=k!{\gamma }_i$. The coefficients solvewith the Gram matrix and right-hand sideThe linearly independent B-splines have a positive-definite Gram matrix, so this system has a unique coefficient vector.

For any admissible $f$, part (a) rewrites the constraints asHence $f^{(k)}-s$ is orthogonal to every $M_i$ and therefore to their span, which contains $s$. The Pythagorean theorem in an inner-product space givesChoose any $k$-fold antiderivative $\sigma$ of $s$. The identity from part (a) and $(M_i,s)=k!{\gamma }_i$ show that $\sigma$ satisfies all prescribed divided differences, and equality holds in the norm bound. Thereforecharacterizes the minimizers. They are unique up to addition of an arbitrary polynomial in ${\mathcal{P}}_{k-1}$, which changes neither the order-$k$ divided differences nor the $k$th derivative.