Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 61 (Approximation Theory)

Take $n\ge 1$. In the normalization used here, the Dirichlet kernel has the finite expansionAveraging a finite number of the integral formulas for the Fourier partial sums is legitimate by linearity of the integral. Hence the Fejér sum is convolution withTo obtain the nonnegative form of the Fejér kernel, expand a squared geometric sum:The coefficient $n-r$ counts pairs of indices whose difference is $r$. Dividing by $2n$ and summing the geometric progression givesAt $u\in 2\pi \mathbb{Z}$ the ratio has its continuous limiting value $F_n(u)=n/2$. Thus this is a continuous, nonnegative trigonometric polynomial, not a kernel with genuine singularities.

Integration over a full period kills every nonconstant cosine term, soTranslation invariance of integration over the circle consequently gives, for every $x$,The first step is the integral triangle inequality, the second uses nonnegativity, and the last uses the mass just computed. Taking the supremum norm provesIn particular, Fejér summation is a uniform-norm contraction. The factor $\pi$, rather than $2\pi$, is essential for the half-normalized Dirichlet kernel and Fejér kernel in this problem.

Let $m$ be a positive integer and let the trigonometric polynomial $t_n$ have frequencies only in $[-n,n]$. For every $j\ge n$, its Fourier partial sum is the polynomial itself: $s_j(t_n)=t_n$. Every term in the defining average of the de la Vallée Poussin sum therefore equals $t_n$, givingThis is exact reproduction of the degree-at-most-$n$ trigonometric polynomials, irrespective of the positive averaging length $m$.

The indexing of the Fejér sums givesSubtracting removes precisely the initial $n$ Fourier partial sums. ThusFor $n=0$, omit the second term, so that no undefined ${\sigma }_0$ is needed. Apply the triangle inequality and the uniform-norm contraction of Fejér summation estimate to getHence the operator norm of the de la Vallée Poussin sum is at most $1+2n/m$.

For any degree-at-most-$n$ trigonometric polynomial $t_n$, linearity and reproduction giveThe operator norm bound in the preceding part yieldsTake the infimum over all such trigonometric polynomials. By the definition of best uniform approximation,No choice of a minimizer is needed for this argument. It is an instance of the polynomial reproduction error bound: a bounded linear reproducing operator has error at most $1+\Vert P\Vert$ times the optimal error.

Put $r=k-1$. The linear-reproduction request requires $k\ge 2$, which we use for that final step. Since ${\psi }_i={\omega }_i/r!$, the useful normalized Marsden dual functional isThere is no further factor $1/r!$ outside this sum: it has already been included in ${\psi }_i$.

To derive the formula directly from Marsden's identity, Taylor's theorem for the polynomial $p$ around the arbitrary point $x$ givesOn the other hand,Differentiate Marsden's identity $r-j$ times in $x$, multiply by $(-1{)}^j{p}^{(j)}(x)/r!$, and sum over $j$. The left side becomes $p(t)$, while the right side becomesOnly finite sums and derivatives of polynomials are involved.

Independence of the auxiliary point does not require an assumption about uniqueness of an expansion. Differentiate the formula for ${\lambda }_i$ itself:The first summand at $j=r$ and the second at $j=0$ vanish because both polynomials have degree at most $r$. All remaining terms cancel after shifting the index by one. Therefore ${\lambda }_i(p)$ is a constant in $x$, and it is visibly a linear functional of $p$.

For $p(t)=a+bt$, only $j=0,1$ remain. The leading two coefficients of the monic knot polynomial giveIt follows thatSubstituting into the expansion proveson the basic knot interval. Thus the Greville abscissae are exactly the sampling coefficients that reproduce linear polynomials; the constant case also gives the subpartition of unity for B-splines with equality on this interval.

Write the strictly increasing local spline knots as $u_j=t_{i+j}$, $0\le j\le k$. The explicit formula for a divided difference givesEach summand is a truncated power function of $t$: it is a polynomial on either side of its knot $u_j$, and for $k\ge 2$ is globally $C^{k-2}$. Hence $M_i$ is a piecewise polynomial function of degree at most $k-1$, with these spline knots and at least this global smoothness.

For $t\ge u_k$, all summands vanish. For $t<u_0$, all knot values agree with those of the ordinary polynomial $(s-t{)}^{k-1}$ in the divided-difference variable $s$. Its order-$k$ divided difference is zero, because its degree is less than $k$. Thus $M_i$ also vanishes to the left of $u_0$.

The closed support is exactly the indicated interval, rather than merely contained in it. For $u_0<t<u_1$, subtracting the omitted $j=0$ term from the zero divided difference of $(s-t{)}^{k-1}$ givesFor $u_{k-1}<t<u_k$, only the last truncated-power term survives, givingThere are therefore nonzero values arbitrarily close to either endpoint, provingAt each simple knot, the $(k-1)$st derivative has a nonzero jump from exactly one truncated-power summand, so this is also the exact global smoothness. For order $k=1$, the function is instead the normalized interval indicator; there is no assertion of classical continuity, and the notation $C^{k-2}$ is only the customary formal spline smoothness notation. This distinction is part of simple-knot B-spline regularity.

We derive the Cox-de Boor recurrence from the Leibniz rule for divided differences. Fix $t$, let $u_j=t_{i+j}$, and setAway from the spline knots, $h(s)=(s-t{)}_{+}^{k-1}$. IntroduceThe defining divided-difference recurrence says $(u_k-u_0)D=R-L$. Since $s-t=(s-u_0)+(u_0-t)$ and the first factor is linear, the Leibniz rule for divided differences givesMultiplication by $u_k-u_0$ consequently yieldsReplace $L$ and $R$ by the corresponding lower-order B-splines divided by their support widths. This provesThe denominators are positive for the distinct spline knots of this question. The recursion starts with $N_{i,1}$, the interval indicator on $[t_i,t_{i+1})$. For $k\ge 2$, values at the spline knots follow by the continuous extension of the left side; the usual half-open convention for the order-one factors gives the same result. This proves the recurrence rather than assuming it as a definition.

For a periodic function use the modulus of continuityOn the interval, take the supremum over pairs of points whose distance is at most $\delta$. The mean value theorem applied to cosine, whose derivative has absolute value at most one, givesBoth cosine values lie in $[-1,1]$, so for $|h|\le \delta$,Taking the supremum provesThe cosine substitution for polynomial approximation is also a linear isometry in the supremum norm, since cosine maps a full period onto $[-1,1]$; its image consists of even continuous periodic functions.

The first Jackson theorem for periodic approximation asserts that a universal constant $C$ satisfiesfor every continuous $2\pi$-periodic function $g$, where the infimum is over degree-at-most-$n$ trigonometric polynomials.

Apply it to the even function $g(\theta )=f(\cos \theta )$. If $q_n$ is a trigonometric polynomial approximating $g$, its even parthas no larger error, because $g(-\theta )=g(\theta )$ and the triangle inequality bounds each averaged error by $\Vert g-q_n{\Vert }_{\infty }$. Every even trigonometric polynomial has the formHere the Chebyshev polynomials $T_j$ have algebraic degree $j$, so $p_n$ has degree at most $n$. Surjectivity of cosine givesConversely, every algebraic polynomial of degree at most $n$ yields such an even trigonometric polynomial. Taking infima therefore proves the exact identity $E_n^{\mathrm{alg}}(f)=E_n^{\mathrm{trig}}(\tilde{f})$, not merely an inequality. Combine this with the periodic theorem and the preceding modulus of continuity estimate:Symmetrization, the degree correspondence and the equality of norms justify every step in transferring the Jackson-type estimate.

For the indicated function the cosine substitution givesThe absolute-value function is Lipschitz continuous with constant one, and so is sine. Their composition therefore satisfiesUse the sharper intermediate estimate from the preceding part, rather than the ordinary interval modulus of continuity:

The usual inverse theorem for trigonometric approximation cannot hold verbatim with the ordinary interval modulus of continuity. It would implyBut comparison with the endpoint $1$ giveswhich is of order $n^{-1/2}$ and contradicts that bound as $n\to \infty$. This is an endpoint obstruction to an algebraic inverse approximation theorem. The algebraic approximation rate measures smoothness after cosine substitution; cosine compresses distances quadratically near the endpoints. A valid algebraic inverse theorem must account for that endpoint geometry rather than using the unchanged periodic formulation.

Write $Ba={\sum }_{j=1}^n{a}_j{N}_j$, and let $Rf=(f(x_1),\dots ,f(x_n){)}^T$. We use the standard interpolation convention of distinct ordered sites $x_1<\cdots <x_n$. Together with $N_i(x_i)>0$, the Schoenberg–Whitney theorem makes the B-spline collocation matrix $A$ invertible. Equivalently, its invertibility is implicit in the existence of the interpolation operator for every data vector.

If distinctness is not understood, the printed positivity condition alone is insufficient. For the order-two basis on spline knots $1,2,3,4$, take $x_1=x_2=5/2$. Both diagonal B-spline values are $1/2>0$, but the two rows of $A$ coincide. Arbitrary data cannot then be interpolated uniquely. The norm statement below concerns the intended well-defined interpolation operator.

Spline interpolation determines the coefficient vector by $Aa=Rf$, and henceNonnegativity and the subpartition of unity for B-splines giveFor completeness, extend the finite spline knot sequence beyond both ends. For the full sequence the order-one interval indicators sum to one. Summing the Cox-de Boor recurrence and shifting the index in its second term combines the two coefficients of each lower-order B-spline to one, so induction gives partition of unity at every order. Our finite collection is a subset of that nonnegative collection, and thus has sum at most one. Repeated spline knots are handled by the standard zero-term convention or a knot limit. This argument controls the entire interval, not only the basic knot interval.

Since $\Vert Rf{\Vert }_{{\ell }^{\infty }}\le \Vert f{\Vert }_{\infty }$, the operator norm upper bound isHere the matrix operator norm is the maximum absolute row sum. For the lower bound, choose a row of $A^{-1}$ with maximum absolute row sum and a data vector $y$ whose components are the signs of that row's entries. Then $\Vert y{\Vert }_{{\ell }^{\infty }}=1$ andA continuous piecewise-linear function taking these values at the distinct ordered sites, and constant outside their range, has supremum norm one. Apply the given uniform-norm stability of a B-spline basis to its coefficient vector:ThereforeThe construction of the bounded continuous data extension is what permits the matrix norm to give a lower bound for a function-space operator norm.

For the uniform spline knots, translation reduces every degree-two basis function to a quadratic cardinal B-spline. From the Cox-de Boor recurrence, an order-three function takes the valuesAt the prescribed site $x_i=i+2$, only $N_i$ and, when $i<n$, $N_{i+1}$ have nonzero values. Hence the B-spline collocation matrix isThe shift satisfies $S^n=0$. A finite geometric expansion gives the exact inverseIts $i$th absolute row sum is $2(n-i+1)$, so $\Vert A^{-1}{\Vert }_{{\ell }^{\infty }}=2n$. Use the preceding bounds and the supplied stability constant $d_3=3$:Thus the linear growth of shifted quadratic spline interpolation is $\Theta (n)$, which in particular is $O(n)$. The lower bound, rather than the $O(n)$ upper bound alone, proves that these spline interpolation operators are not uniformly bounded.

We work in the usual real-valued setting of the Chebyshev alternation theorem. For $f\in C[-1,1]$ and an algebraic polynomial $p$ of degree at most $n$, the theorem says that $p$ is a best uniform approximation if and only if its error has $n+2$ ordered points with alternating maximal values:If $f=p$, the zero-error case is included directly.

Existence follows, for example, by taking a minimizing sequence: its supremum norms are bounded, all norms on the finite-dimensional polynomial space are equivalent, and a convergent coefficient subsequence attains the infimum. To prove uniqueness of best uniform polynomial approximation, let $p,q$ both attain the minimum error $E$. Their average $r=(p+q)/2$ has error at most $E$ by the triangle inequality and therefore exactly $E$ by minimality.

If $E=0$, both polynomials equal $f$ and are equal. Otherwise apply the Chebyshev alternation theorem to $r$. At every alternating extremal point, $f-r$ is either $E$ or $-E$. But it is the average of $f-p$ and $f-q$, each lying in $[-E,E]$. An average attains an endpoint of this interval only when both entries equal that endpoint. Hence $p(x_j)=q(x_j)$ at all $n+2$ points. The difference is a degree-at-most-$n$ polynomial with more than $n$ distinct zeros, so it is identically zero. The best approximating polynomial is unique.

The original PDF has indices $3^k$; the exponent is lost in the TeX transcription. This lacunary indexing is essential to the positive lacunary Chebyshev series argument below.

Let $K$ be the least nonnegative integer with $3^K>n$, so $K=0$ for $n=0$. DefineFor $K=0$ the sum is empty and means the zero polynomial. Each included Chebyshev polynomial has degree at most $n$. Also $|T_j(x)|\le 1$ on the interval, so summability of the positive coefficients gives uniform convergence by the Weierstrass M-test, andChoose $L=3^K$ and the $L+1$ points $x_j=\cos (j\pi /L)$, $0\le j\le L$. For every omitted index $k\ge K$, the integer $3^{k-K}$ is odd. Consequently,Every term of the tail has the same sign at a given point, and thereforeThis shows both that the error norm is exactly $A_K$ and that it alternates at $L+1\ge n+2$ distinct points. The points are in decreasing order; reversing their order still gives alternation. The Chebyshev alternation theorem proves that this partial sum is the unique best uniform approximation. HenceIn particular, $p_0=0$ and $E_0(f_0)={\sum }_{k=0}^{\infty }{a}_k$. The equal signs of all tail terms at the same extrema are the reason positivity and the odd integer frequency ratios are useful.

An explicit construction gives Bernstein's lethargy theorem in the requested inequality form. SetStrict decrease makes every coefficient positive. Telescoping and the limit assumption giveThusdefines a continuous function by the Weierstrass M-test and the uniform limit theorem. Apply the positive lacunary Chebyshev series calculation. At $n=0$,For $n\ge 1$, choose $K\ge 1$ so that $3^{K-1}\le n<3^K$. Its error isTherefore the function satisfiesThis explicit Chebyshev construction for Bernstein lethargy also has $E_n(f_{ϵ})\to 0$. It shows that continuity imposes no universal speed of convergence of best polynomial approximation, even though convergence itself follows from the Weierstrass approximation theorem.