Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 69 (Approximation Theory)

Use the modulus of continuity on the circle, $\omega (f,\delta )={\sup }_{|h|\le \delta }\Vert f(\cdot +h)-f{\Vert }_{\infty }$. Splitting a displacement into steps of length at most $\delta$ and applying the triangle inequality givesThe Fejér kernel is nonnegative and has integral one, soWe therefore need its first absolute moment. The inequalities $|\sin (nt/2)|\le n|\sin (t/2)|$ and $\sin (|t|/2)\ge |t|/\pi$ on $[-\pi ,\pi ]$ implySplitting at $1/n$ givesTaking $\delta ={\delta }_n=(\ln n)/n$ in the preceding error bound proves the Fejér first-moment approximation bound:The constants do not depend on $f$ or $n$. By the Heine-Cantor theorem, a continuous function on the compact circle is uniformly continuous, hence $\omega (f,{\delta }_n)\to 0$ as ${\delta }_n\to 0$. Thus the Fejér sums converge uniformly to $f$. The index restriction is necessary: at $n=1$ the printed scale is zero, while ${\sigma }_{1}f$ is the mean of $f$ and generally differs from it.

Write the Bernstein basis as $p_{n,j}(x)=\left(\genfrac{}{}{0ex}{}{n}{j}\right)x^j(1-x{)}^{n-j}$, with $p_{n,j}=0$ for out-of-range indices. The Bernstein polynomial isDifferentiation and the identities $j\left(\genfrac{}{}{0ex}{}{n}{j}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{j-1}\right)$ and $(n-j)\left(\genfrac{}{}{0ex}{}{n}{j}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{j}\right)$ give $p_{n,j}^{\prime }=n(p_{n-1,j-1}-p_{n-1,j})$. Shifting the first sum's index therefore yieldsRepeating this calculation takes another forward finite difference of the coefficients and lowers the degree by one. Induction proves the derivatives of Bernstein polynomials formulaFor $n>r$, define a continuous function on $[0,1]$ byAll sampled arguments lie in $[0,1]$, since the largest is $(n-r)t/n+r/n\le 1$. At the degree-$(n-r)$ sampling point $t=j/(n-r)$, this gives exactly the coefficient $(n{)}_r{\Delta }_{1/n}^{r}f(j/n)$, and hence $\boxed{B_n^{(r)}f=B_{n-r}{g}_{n,r}}$. The rescaling is essential: the sampling meshes are $1/n$ and $1/(n-r)$, and the function $g_{n,r}$ depends on $n$. For $n=r$, the derivative is the constant $n!{\Delta }_{1/n}^{n}f(0)$, interpreted as a degree-zero Bernstein polynomial.

Now fix $r$ and assume $f\in C^r[0,1]$. The supplied uniform limit of normalized finite differences, together with $(n{)}_r/n^r\to 1$ and uniform continuity of $f^{(r)}$, shows thatPositivity and ${\sum }_j{p}_{m,j}=1$ imply $\Vert B_{m}h{\Vert }_{\infty }\le \Vert h{\Vert }_{\infty }$. For completeness, if $X\sim \mathrm{Bin}(m,x)$ then $B_m(h,x)=\mathbb{E}[h(X/m)]$, and $\mathrm{Var}(X/m)=x(1-x)/m\le 1/(4m)$. Splitting according to whether $|X/m-x|\le \delta$ and using Chebyshev's inequality givesFirst let $m\to \infty$ and then $\delta \to 0$; this proves uniform convergence for each continuous $h$. Finally,Thus Bernstein polynomial derivatives converge uniformly to the corresponding derivatives of $f$, for each fixed $r$ with $f\in C^r[0,1]$. Continuity of $f$ alone is sufficient for the definition of $B_n$, but not for this derivative conclusion.

Use the standard partition normalization of the B-splines, so $N_j\ge 0$ and the subpartition of unity for B-splines gives ${\sum }_{j=1}^n{N}_j(t)\le 1$. Write the interpolating spline as $P_{x}f={\sum }_j{c}_j{N}_j$ and the sampled values as $y_i=f(x_i)$. The interpolation equations are $A_{x}c=y$, hence $c=A_x^{-1}y$ whenever the stated interpolation map is well defined. For every $t$,The sampling map also satisfies $\Vert y{\Vert }_{{\ell }^{\infty }}\le \Vert f{\Vert }_{\infty }$. Taking supremum norms and then the operator norm therefore provesThis is the B-spline interpolation operator norm bound, and it applies on any interval containing the sampling sites on which these normalized B-splines are used.

There is a small qualification to the printed hypotheses: diagonal positivity alone does not ensure uniqueness unless the usual site assumptions are supplied. For example, with two quadratic B-splines on knots $1,2,3,4,5$ and $x_1=x_2=3$, both diagonal values equal $1/2$, but $A_x$ has two identical rows and is singular. The intended increasing sites $x_1<\cdots <x_n$ with $N_i(x_i)>0$ satisfy the Schoenberg–Whitney theorem, making $A_x$ invertible; alternatively invertibility is implicit in the premise that $P_x$ is the unique interpolation map. The displayed bound is proved under that premise, rather than inferring invertibility from diagonal positivity alone.

For unit-spaced knots, the quadratic cardinal B-spline is a translate ofFor example, the Cox-de Boor recurrence gives $N_{j,3}(t)=(t-j)N_{j,2}(t)/2+(j+3-t)N_{j+1,2}(t)/2$ from the two linear hats. Substituting their linear pieces gives the three expressions above. At $x_i=i+3/2$, only the B-splines with indices $j=i-1,i,i+1$ have nonzero values, and their values are respectivelyOnly indices $1\le j\le n$ belong to the given basis, so entries outside that range are omitted at the boundary.

The midpoint quadratic spline collocation matrix isIts strict diagonal dominance margin is at least $3/4-2/8=1/2$. The inverse infinity-norm bound from diagonal dominance thus already proves $\Vert A_x^{-1}{\Vert }_{\infty }\le 2$: choosing an index where a vector $c$ attains its maximum absolute entry gives $\Vert A_{x}c{\Vert }_{\infty }\ge \frac{1}{2}\Vert c{\Vert }_{\infty }$, which also proves invertibility.

To evaluate the finite-dimensional norm exactly, set $D_{ii}=(-1{)}^i$ and $B=D{A}_{x}D$. If $T$ is the matrix with ones on its two adjacent diagonals and zeros elsewhere, then $B=(3/4)(I-T/6)$. Since $\Vert T/6{\Vert }_{\infty }\le 1/3$, the Neumann serieshas nonnegative entries. Thus $A_x^{-1}=D{B}^{-1}D$ has absolute entry values equal to those of $B^{-1}$. Its absolute row-sum vector is $v=B^{-1}1$, characterized byThe homogeneous roots are $3\pm 2\sqrt{2}$, and the constant particular solution is $v_i=2$. Writing $q=3-2\sqrt{2}\in (0,1)$ and imposing the two boundary values givesThis is largest at the middle row or rows. Therefore, with $i_{\ast }=\lfloor (n+1)/2\rfloor$, the exact norm isFor example, it is $4/3$ for $n=1$ and $8/5$ for $n=2$, and it increases towards two as the system grows. Thus two is a uniform bound, rather than the exact finite-$n$ inverse norm.

Combine the B-spline interpolation operator norm estimate from part 1 with the inverse operator norm computed in part 2(b):so in particular $\Vert P_x{\Vert }_{L^{\infty }}\le 2$, uniformly in $n$. The subpartition of unity for B-splines is important at the outer boundary: the finite basis may sum to less than one there, but that only strengthens the estimate.

Let $u\in \mathcal{U}$, $r=f-u$, $M=\Vert r{\Vert }_{\infty }$, and $E=\{x\in [0,1]:|r(x)|=M\}$. The Kolmogorov criterion for uniform approximation saysEquivalently, no available perturbation $v$ has strictly the same sign as the nonzero residual at every extremal point. This statement concerns a candidate $u$ in the linear subspace; it does not assume every subspace has an attained best approximation. If $M=0$, $u=f$ is already exact and the criterion is automatic.

To see sufficiency, for any competitor $u+v$, the criterion supplies an $x\in E$ with $r(x)v(x)\le 0$. Then $|f(x)-u(x)-v(x)|\ge |r(x)|=M$, so the competitor cannot have smaller supremum norm error.

For necessity, suppose $M>0$ and some $v\in \mathcal{U}$ has $r(x)v(x)>0$ on $E$. Since $E$ is compact, this product has a positive minimum there. By continuity, a neighborhood $O$ of $E$ has $rv\ge \eta >0$. For sufficiently small $\epsilon >0$,On the compact complement of $O$, $|r|$ has a strict gap below $M$, and taking $\epsilon \Vert v{\Vert }_{\infty }$ smaller than this gap preserves it. Hence $u+\epsilon v$ improves the uniform error everywhere, contradicting best uniform approximation.

For a real continuous function $f$, the Chebyshev alternation theorem asserts that a polynomial $p\in {\mathcal{P}}_n$ is a best uniform approximation exactly when either it is exact or its residual $r=f-p$ has $n+2$ ordered alternating extrema:Here ${\mathcal{P}}_n$ means degree at most $n$, as required for a linear subspace.

For sufficiency, if a polynomial perturbation $v\in {\mathcal{P}}_n$ violated the Kolmogorov criterion for uniform approximation, then $r(x_j)v(x_j)>0$ at every displayed point. Thus $v(x_j)$ would alternate signs, forcing a distinct zero in each of the $n+1$ intervals $(x_j,x_{j+1})$ by the intermediate value theorem. A nonzero polynomial of degree at most $n$ cannot have that many zeros; the zero polynomial does not violate the criterion either.

For necessity, assume $M=\Vert r{\Vert }_{\infty }>0$ and no such alternating sequence exists. The two compact sets $E_{+}=\{r=M\}$ and $E_{-}=\{r=-M\}$ are disjoint and, when both are nonempty, have positive separation. Hence the extremal set has finitely many successive sign runs: infinitely many alternations would contradict that separation on the bounded interval. If there are $m$ changes of sign between those runs, then selecting one point from each run gives an alternating sequence of length $m+1$, so $m\le n$. Choose a point $z_j$ in the gap between each pair of consecutive opposite-sign runs, and setChoose the sign of $C$ so that $v$ agrees with $r$ on the first run. The roots lie outside the extremal set and each changes the sign, so $rv>0$ at every extremal point. Since $\mathrm{deg}v=m\le n$, this contradicts the Kolmogorov criterion for uniform approximation. Therefore a best polynomial must have the required alternation.

Existence also holds: a minimizing sequence has bounded supremum norms, hence bounded coefficients by evaluating at $n+1$ fixed distinct points and inverting the resulting Vandermonde matrix. A convergent subsequence of coefficients yields a minimizer. Finally, if $p$ and $q$ are both best, their average is best; at its alternating extrema both individual residuals must equal the same extremal value. Consequently $p-q$ has at least $n+2$ zeros and is identically zero. The best polynomial exists, is unique, and is characterized by alternation.

Fix $t$ and let $F_t(u)=(u-t{)}_{+}^{k-1}$. Initially assume distinct spline knots, so the ordinary polynomial interpolation definitions are unambiguous. The two interpolants ${\ell }_i(\cdot ,t)$ and ${\ell }_{i+1}(\cdot ,t)$ agree with $F_t$ at their $k-1$ shared nodes $t_{i+1},\dots ,t_{i+k-1}$. Their difference has degree at most $k-1$ and all these roots, henceFor $k=1$ the product is empty and the same statement concerns constants. The leading coefficient of an interpolating polynomial is its highest-order divided difference, so the divided difference recurrence givesThis proves Lee's formula:Summing over $i$ telescopes to ${\ell }_{n+1}(x,t)-{\ell }_1(x,t)$. If $t_k<t<t_{n+1}$, the first interpolation nodes $t_1,\dots ,t_k$ are all smaller than $t$, so their truncated-power data vanish and ${\ell }_1=0$. The last nodes $t_{n+1},\dots ,t_{n+k}$ are larger than $t$, so their data are values of the polynomial $(u-t{)}^{k-1}$ and uniqueness gives ${\ell }_{n+1}(x,t)=(x-t{)}^{k-1}$. Thus the telescoped identity isthe Marsden identity, valid for every real $x$.

If repeated spline knots are allowed, ordinary value interpolation at repeated nodes does not specify ${\ell }_i$ uniquely. The standard extension uses confluent divided differences and Hermite interpolation, or limits of distinct knots: the same polynomial identity then persists wherever these quantities are defined. At a maximally repeated knot where the truncated power lacks the required derivative, the appropriate one-sided spline convention must be fixed; an unspecified classical derivative is not part of the proof. For distinct knots, the printed identity requires no such qualification.

Put $d=k-1$ and let $e_m$ be the elementary symmetric polynomial of degree $m$ in the $d$ interior spline knots $t_{i+1},\dots ,t_{i+d}$, with $e_0=1$. Expanding the knot polynomial givesCompare the coefficient of $x^{d-m}$ in the Marsden identity. The left coefficient is $(-1{)}^m(\genfrac{}{}{0ex}{}{d}{m})t^m$; the right coefficient is $(-1{)}^m{\sum }_i{e}_m(t_{i+1},\dots ,t_{i+d})N_i(t)$. Cancelling the common sign therefore gives the monomial B-spline coefficients:Equivalently, for $m\ge 1$ the numerator is ${\sum }_{1\le r_1<\cdots <r_m\le k-1}{t}_{i+r_1}\cdots t_{i+r_m}$. In particular $a_i^{(0)}=1$, so the order-zero case reproduces constants, and for $k\ge 2$ the linear coefficients are $a_i^{(1)}=(t_{i+1}+\cdots +t_{i+k-1})/(k-1)$, the Greville abscissae. At $m=k-1$, the coefficient is the product of all interior knots. Each formula holds on the basic knot interval used in the Marsden identity.

For $f\in C(\mathbb{T})$, define $E_j(f)={\inf }_{T\in {\mathcal{T}}_j}\Vert f-T{\Vert }_{\infty }$, where ${\mathcal{T}}_j$ is the space of degree-at-most-$j$ trigonometric polynomials. The first inverse theorem for trigonometric approximation states that a universal constant $C$ satisfiesFor perspective, take best approximants at dyadic degrees and telescope their differences. Each difference between consecutive approximants has supremum norm at most twice the earlier error, and the Bernstein inequality for trigonometric polynomials multiplies that bound by its degree when differentiating. The resulting dyadic sum is bounded by the displayed sum because $E_j$ decreases with $j$; the remaining approximation error is also bounded by an average of earlier errors.

Now suppose $E_j(f)\le K{j}^{-\alpha }$ for large $j$, absorbing finitely many earlier terms into a constant. If $0<\alpha <1$, comparison with an integral gives ${\sum }_{j=1}^n{j}^{-\alpha }=O(n^{1-\alpha })$. If $\alpha =1$, the same comparison gives ${\sum }_{j=1}^n{j}^{-1}=O(1+\ln n)$. Substitution proves the requested two rates:The logarithm is the endpoint contribution of the harmonic sum and cannot generally be removed, as the following Weierstrass function shows.

The Weierstrass M-test gives a continuous periodic Weierstrass function, since $\sum a^{-k}<\infty$. For $5^m\le n<5^{m+1}$, the given best approximant leaves the tailIts supremum norm is at most the sum of its coefficients, and at $x=0$ all cosine terms equal one, attaining that bound. ConsequentlyPut $\alpha =\ln a/\ln 5$. Then $a^{-m}=(5^m{)}^{-\alpha }$ and $n/5^m\in [1,5)$, giving $E_n(g)\asymp n^{-\alpha }$, with constants depending only on $a$.

For $1<a<5$, part (a) gives $\omega (g,1/n)\le C_a{n}^{-\alpha }$. The first Jackson theorem for periodic approximation, $E_n(g)\le C\omega (g,1/n)$, supplies the matching lower bound. Hence the modulus of continuity has the precise orderAt $a=5$, the inverse theorem for trigonometric approximation gives the upper bound $C\delta \ln (1/\delta )$, and part (c) proves the matching lower bound. Thus the critical Weierstrass modulus isTo pass from scales $1/n$ to all small $\delta$, use monotonicity of the modulus of continuity and adjacent reciprocals, which are comparable to $\delta$.

Take $a=5$ and $x=\pi /2$. Since $5^k\equiv 1(\mathrm{mod}4)$, every cosine term vanishes at $x$, andSet $h=1/n$ and $m=\lfloor {\log }_{5}n\rfloor$. For $0\le k\le m$, the sine argument lies in $[0,1]$, where $\sin u\ge (\sin 1)u$. The initial part therefore has a common sign and magnitude at least $(m+1)(\sin 1)/n$. The remaining tail has absolute value at mostThe reverse triangle inequality now givesfor sufficiently large $n$, because $m+1>\ln n/\ln 5$. This establishes the sharp logarithmic lower boundThe constant can be reduced to include the finitely many small indices: for $n\ge 5$ the displayed lower bound is positive; for $n=2,3$ the first sine exceeds the tail bound $1/4$, and for $n=4$ the first two sines contribute $\sin (1/4)+\sin (5/4)/5$, exceeding the remaining tail bound $1/20$. At $n=1$ the logarithmic right side is zero.

Here $E_n(g)\asymp 1/n$ but $g$ is not Lipschitz continuous, so a first modulus of continuity bound $O(1/n)$ is sufficient by the first Jackson theorem for periodic approximation but is not necessary. Nor is the weaker necessary bound $O(\ln n/n)$ sufficient: an explicit comparison is the logarithmic cusp with slow trigonometric approximationextended periodically. On $[0,\pi ]$ it is increasing and concave, so its largest increment over distance $\delta$ is from zero, giving $\omega (h,\delta )=\delta \ln (e\pi /\delta )$ for $0<\delta \le \pi$.

For a concrete approximation lower bound, its cosine Fourier coefficients satisfyIndeed, integration by parts once replaces $h$ by $h^{\prime }(x)=\ln (\pi /x)$; integrating that against sine with primitive $(1-\cos jx)/j$ yields the stated positive integral. Its logarithmic growth follows because ${\int }_1^A\cos u/udu$ stays bounded by the Dirichlet test. All $a_j$ are negative and absolutely summable.

Let $V_n=2{\sigma }_{2n}-{\sigma }_n$, a de la Vallée Poussin sum. Its multiplier is one for $j\le n$, $2-j/n$ for $n<j<2n$, and zero for $j\ge 2n$; the Fejér summation is a uniform-norm contraction property gives $\Vert V_n\Vert \le 3$. Thus the functional $L_n(f)=f(0)-V_{n}f(0)$ has norm at most four and vanishes on every degree-at-most-$n$ trigonometric polynomial. Because the remaining multiplier weights are nonnegative and all $a_j<0$,The first Jackson theorem for periodic approximation gives the corresponding upper bound. The same first-modulus order $\delta \ln (1/\delta )$ occurs with both $E_n\asymp 1/n$ and $E_n\asymp \ln n/n$. Therefore first-modulus rates alone do not characterize the endpoint approximation class, unlike the matched direct and inverse rates for $0<\alpha <1$.