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

For positive linear operators on continuous functions, a general Korovkin theorem, in its compact Korovkin test space form, can be stated using a test space $H\subset C(K,\mathbb{R})$, where $K$ is a compact Hausdorff space. Assume $H$ contains a strictly positive function $h_0$. Require that, for every $x\in K$, the only positive linear functional $L$ on $C(K)$ with $L(h)=h(x)$ for all $h\in H$ is evaluation at $x$. Then convergence on the test space implies convergence on every continuous function:By the Riesz-Markov-Kakutani representation theorem, the functional condition equivalently says that a positive measure with these test moments must be ${\delta }_x$. This permits arbitrary test families, not just the interval tests $1,x,x^2$.

For completeness, let $c={\min }_K{h}_0>0$. Positivity gives $U_{n}1\le c^{-1}{U}_n{h}_0$, so the operator norms are uniformly bounded. If the conclusion failed for some $f$, choose $x_n$ where its error is bounded away from zero. The evaluation functionals $L_n(g)=U_{n}g(x_n)$ have uniformly bounded norm. Compactness of $K$ and the Banach-Alaoglu theorem give a subnet on which $x_n\to x$ and $L_n$ converges in the weak-star topology to a positive $L$. For every $h\in H$, uniform test convergence gives $L(h)=h(x)$. The hypothesis forces $L(f)=f(x)$, contradicting the chosen errors. Complex-valued functions follow by applying the real result to their real and imaginary parts.

A useful concrete sufficient condition is that $1\in H$ and for each $x$ there is $g_x\in H$ with $g_x\ge 0$ and zero set exactly $\{x\}$. Its zero moment forces the representing measure to be supported at $x$, while the constant moment fixes its mass.

For the circle, take $H=\mathrm{span}\{1,\sin t,\cos t\}$. The nonnegative function $g_x(t)=1-\cos (t-x)$ belongs to $H$ and vanishes only at $x$ on the circle. Thus the periodic Korovkin test set isUniform convergence on these three functions is sufficient for uniform convergence on $C(\mathbb{T})$.

Averaging the given Dirichlet kernels gives the normalized Fejér kernelThe geometric-series identity, or summing the sine terms, proves the second equality. At multiples of $2\pi$ use its removable value $n/(2\pi )$. Therefore $K_n\ge 0$, andis a positive linear operator on continuous functions. The Fourier partial sums, viewed as orthogonal projections, fix $1$, so ${\sigma }_{n}1=1$ and $\int K_n=1$. They also fix $\sin x$ and $\cos x$ for degrees at least one, whereas $s_0$ annihilates them. ConsequentlyAll three periodic Korovkin theorem tests converge uniformly. Hence Fejér sums converge uniformly for every continuous periodic function:

Apply the periodic Korovkin theorem to the constant sequence $U_n=U$. Since it fixes the three test functions, the theorem gives $Uf=f$ for every $f$.

One can also see the rigidity directly. For fixed $x$, the positive linear functional $L_x(f)=(Uf)(x)$ has $L_x(1)=1$ and is represented by a probability measure. The fixed sine and cosine imply $L_x(1-\cos (t-x))=0$. The integrand is nonnegative with unique zero $x$ on the circle, so the measure is ${\delta }_x$. Thus $(Uf)(x)=f(x)$ at every point. The operator is uniquely the identity: $\boxed{U=I}$.

An orthonormal multiresolution analysis consists of closed subspaces $(V_j{)}_{j\in \mathbb{Z}}$ of the L2 space $L^2(\mathbb{R})$ with $V_j\subset V_{j+1}$, dense union, intersection $\{0\}$, and the dilation rule $f\in V_j⟺f(2\cdot )\in V_{j+1}$. A scaling function $\varphi$ has integer translates forming an orthonormal basis of $V_0$. Equivalently,form an orthonormal basis of $V_j$. Let $W_j=V_{j+1}\ominus V_j$. Density and the trivial intersection imply $L^2(\mathbb{R})={⨁}_{j\in \mathbb{Z}}{W}_j$.

Nesting gives the scaling refinement equation $\varphi (x)={\sum }_n{a}_n\varphi (2x-n)$, with $h_n=a_n/\sqrt{2}$ the coefficients in the normalized finer-scale basis. Orthogonality of the translates gives ${\sum }_n{a}_n\overline{a_{n-2r}}=2{\delta }_{r0}$. Its Fourier form is the quadrature mirror filter identity $|m(t){|}^2+|m(t+\pi ){|}^2=1$, where $m(t)=\frac{1}{2}{\sum }_n{a}_n{e}^{-int}$.

Set $b_n=(-1{)}^n\overline{a_{1-n}}$ and define $\psi (x)={\sum }_n{b}_n\varphi (2x-n)$ in $L^2$. Its high-pass symbol is $q(t)=-e^{-it}\overline{m(t+\pi )}$. The matrixis unitary almost everywhere. Under the identification of $V_1$ with its finer-scale coefficient space, this two-channel unitary transform splits that space into the translates of $\varphi$ and the translates of $\psi$. The latter are therefore an orthonormal basis of $W_0$. Dilating gives an orthonormal wavelet basisThis wavelet completion of a multiresolution filter explains how the multiresolution analysis supplies a single orthonormal wavelet. The argument uses coefficient-space completeness, not just pairwise orthogonality.

Use the unnormalized Fourier transform in the question and the Plancherel theorem, with inverse factor $1/(2\pi )$. For a general $L^2$ scaling function, the transform is interpreted in the $L^2$ sense; the printed integral need not be absolutely convergent. All frequency identities are almost-everywhere statements.

Changing variables in the Fourier transform givesThus taking the transform of the scaling refinement equation gives $f(\xi )=m(\xi /2)f(\xi /2)$, orConversely the same calculation and injectivity of the Fourier transform recover refinement, with convergence understood in $L^2$.

To justify both the orthogonality assertion and this convergence precisely, put $P(t)={\sum }_{k\in \mathbb{Z}}|f(t+2\pi k){|}^2$. It belongs to $L^1[-\pi ,\pi ]$ by monotone integration. The Plancherel theorem givesHence orthonormality of all integer translates is equivalent, by uniqueness of Fourier coefficients in L1, to the periodized-energy conditionWhen this holds, the squared norm of ${\sum }_n{a}_n\varphi (2\cdot -n)$ is $\frac{1}{2}{\sum }_n|a_n{|}^2$, so square-summable coefficient series converge in $L^2$. In the converse direction the refinement identity and $P=1$ give, by splitting the periodization of $|f(2t){|}^2$ into even and odd translates,Thus $m$ is bounded and its Fourier coefficients $a_n/2$ are square summable. If $m_N$ are its Fourier partial sum, thenThis verifies the transformed refinement series converges to $f$, completing the equivalence of the two pairs of conditions without imposing an unnecessary $L^1$ assumption on $\varphi$.

The half-open intervals $[-\pi +2\pi k,\pi +2\pi k)$ tile the line, so exactly one term contributes to ${\sum }_k|f(t+2\pi k){|}^2$. It equals one almost everywhere.

Choose the Shannon scaling mask, a $2\pi$-periodic low-pass filter of a multiresolution analysis which equals one on $[-\pi /2,\pi /2)$ and zero on the rest of $[-\pi ,\pi )$. On the support of $f$ its product with $f(t)$ equals $f(2t)$; outside that support both sides vanish. Its Fourier coefficients giveso it also has the required symbol representation. The inverse Fourier transform gives the Shannon scaling functionThis sinc function has $L^2$ norm one. It illustrates why the Fourier transform convention in part B must allow $L^2$ transforms: the Shannon scaling function is not absolutely integrable on the line.

Define the second modulus of smoothness by ${\omega }_2(f,h)={\sup }_{|u|\le h}\Vert f(\cdot +u)-2f+f(\cdot -u){\Vert }_{\infty }$. The Jackson kernel is even, nonnegative and has integral one. Symmetrizing its convolution therefore givesWe first establish the needed scaling rule. For the translation operator $T_u$, $(T_u^m-I)=(I+T_u+\cdots +T_u^{m-1})(T_u-I)$. Squaring gives $\Vert (T_u^m-I{)}^{2}f\Vert \le m^2\Vert (T_u-I{)}^{2}f\Vert$. Central and forward second differences have the same norm. For every $|v|\le |t|$, take $m=\lceil |v|/h\rceil$ and $u=v/m$. Taking the supremum over these $v$ provesThe zero-step case is immediate.

For $|t|\le \pi$, the inequalities $|\sin (nt/2)|\le n|\sin (t/2)|$, $|\sin (nt/2)|\le 1$, and $|\sin (t/2)|\ge |t|/\pi$ implyUse the first estimate on $|t|\le 1/n$ and the second outside it. ThenAll constants are independent of $n$ and $f$. Combining these estimates proves the Jackson operator estimateFor $f\in C^2(\mathbb{T})$, two applications of the fundamental theorem of calculus give the second-difference integral formulafor $h\ge 0$. Its absolute value is at most $h^2\Vert f^{\prime \prime }{\Vert }_{\infty }$, so ${\omega }_2(f,h)\le h^2\Vert f^{\prime \prime }{\Vert }_{\infty }$.

Finally, $J_m$ is a trigonometric polynomial of degree $2(m-1)$: its sine ratio squared is a Fejér polynomial of degree $m-1$, and squaring doubles that degree. Thus $j_m(f)$ has degree at most $2(m-1)$. To bound degree-$n$ best approximation, choose $m=\lfloor n/2\rfloor +1$, rather than using $j_n$ directly. Since $m\ge n/2$ for $n\ge 1$, the smooth-function approximation rate is

Let $u^{\ast }\in \mathcal{U}$, $e=f-u^{\ast }$, $d=\Vert e{\Vert }_{\infty }$, and $E=\{x:|e(x)|=d\}$. The real Kolmogorov criterion for uniform approximation says $u^{\ast }$ is best if and only ifEquivalently, no direction $v$ has the error's sign strictly at every extremal point. If $d=0$, the criterion is automatic.

For sufficiency, a point with $e(x)v(x)\le 0$ gives $|e(x)-v(x)|\ge d$, so $u^{\ast }+v$ cannot improve the norm. For necessity, suppose $e(x)v(x)>0$ on $E$. Compactness gives a positive lower bound there and on a neighbourhood of $E$. On that neighbourhood, $(e-\tau v{)}^2=e^2-2\tau ev+{\tau }^2{v}^2<d^2$ for sufficiently small positive $\tau$. Off the neighbourhood, $|e|$ has a strict gap below $d$, and small $\tau$ preserves that gap. Thus $u^{\ast }+\tau v$ has smaller error, a contradiction. This also explains why the criterion involves all active extrema.

Let $p\in {\mathcal{P}}_n$ and $e=f-p$, with $d=\Vert e{\Vert }_{\infty }>0$. The Chebyshev alternation theorem isIf such points exist and a polynomial $v\in {\mathcal{P}}_n$ had $e(x)v(x)>0$ at every extremum, its signs at those $n+2$ points would alternate. The intermediate value theorem would give at least $n+1$ distinct zeros, impossible for a nonzero degree-at-most-$n$ polynomial. The Kolmogorov criterion for uniform approximation therefore proves sufficiency.

For necessity, let $E_{+}=\{e=d\}$ and $E_{-}=\{e=-d\}$. They are disjoint compact sets. If one set is empty there is just one sign block. Otherwise their positive separation implies that, reading the extremal set from left to right, its signs form finitely many alternating blocks. If there are fewer than $n+2$ alternating extrema, there are at most $n+1$ blocks. Place one point ${\xi }_j$ in each extremum-free gap between consecutive blocks. A scalar multiple of $v(x)={\prod }_j(x-{\xi }_j)$ can be chosen to have exactly the sign of $e$ on every block. Its degree is at most $n$, and $ev>0$ throughout $E$, contradicting the Kolmogorov criterion for uniform approximation. Thus there must be at least $n+2$ alternating extrema. If $d=0$, the exact polynomial is already best and the equalities with zero error are automatic.

Fix the degree bound $n$. Existence can be proved without a general uniqueness theorem: a minimizing sequence in ${\mathcal{P}}_n$ is uniformly bounded because its distances from $f$ are bounded. Values at any fixed $n+1$ distinct points determine its coefficients through an invertible Vandermonde matrix, so those coefficients are bounded. A convergent subsequence supplies a polynomial attaining the minimum.

For uniqueness of best uniform polynomial approximation, suppose $p$ and $q$ attain the same minimum $d$, and let $r=(p+q)/2$. The triangle inequality makes $r$ another minimizer. If $d=0$, both polynomials equal $f$, so assume $d>0$. Put $e=f-r$ and $E=\{|e|=d\}$. At each $x\in E$, the two real errors $f-p$ and $f-q$ lie in $[-d,d]$ and their average equals an endpoint. Hence they are equal there, and $p(x)=q(x)$.

The set $E$ must contain at least $n+2$ points. Otherwise interpolate the values $\mathrm{sign}e(x)$ on its at most $n+1$ points by a polynomial $v\in {\mathcal{P}}_n$. Then $ev>0$ on $E$. Continuity gives this positivity on a neighbourhood of $E$, while the error has a strict gap below $d$ on the compact complement. A sufficiently small positive multiple of $v$ decreases the maximum error, contradicting optimality of $r$. This is an elementary perturbation argument, not an appeal to Haar's theorem.

Thus $p-q$ has at least $n+2$ distinct zeros. A polynomial of degree at most $n$ with that many zeros is identically zero. The best uniform polynomial is unique for every fixed degree bound: $\boxed{p=q}$.

Write $g_t(y)=(y-t{)}_{+}^{k-1}$. Begin with distinct increasing knots so ordinary polynomial interpolation is unambiguous. The two interpolants agree at the $k-1$ common knots $t_{i+1},\dots ,t_{i+k-1}$. Their difference is consequently a scalar multiple of the monic polynomial ${\omega }_i$ of degree $k-1$.

The leading coefficient of an interpolant is its highest divided difference. Thus this scalar isThe equality is precisely the divided-difference recurrence. This proves the Lee interpolation identity:For $k=1$ the common-knot product is empty; the same argument is a difference of constants. Interpret $(y-t{)}_{+}^0$ as $1_{y>t}$ to obtain the usual half-open order-one B-splines. Repeated knots use the standard confluent or limiting interpretation, where the interpolation data are defined.

Sum over $i=1,\dots ,n$. The right side telescopes to ${\ell }_{n+1}(x,t)-{\ell }_1(x,t)$. When $t_k<t<t_{n+1}$, the first interpolation nodes all lie below $t$, so ${\ell }_1=0$. The last interpolation nodes all lie above $t$, so ${\ell }_{n+1}$ interpolates the polynomial $(x-t{)}^{k-1}$ of degree $k-1$ and equals it identically. Hence the Marsden identity follows:

Set $d=k-1$ and let $e_m(t_{i+1},\dots ,t_{i+d})$ be the elementary symmetric polynomial of degree $m$ in the interior knots, with $e_0=1$. Expand the Marsden identity in powers of $x$. The coefficient of $x^{d-m}$ on the left is $(-1{)}^m(\genfrac{}{}{0ex}{}{d}{m})t^m$; that coefficient in ${\omega }_i(x)$ is $(-1{)}^m{e}_m(t_{i+1},\dots ,t_{i+d})$. Comparing and cancelling the sign proves the monomial B-spline coefficients:For $m=0$ this gives partition of unity on the basic interval. For $m=1$ it gives the Greville abscissae, the arithmetic means of the $k-1$ interior knots. For the top degree it gives their product. When $k=1$, only $m=0$ occurs and the empty symmetric polynomial is one.

Put $e=x-u^{\ast }$. If $u^{\ast }$ minimizes distance, then for every $v\in {\mathcal{U}}_n$ and every real $t$,Both signs of arbitrarily small $t$ force $\mathrm{Re}(e,v)=0$. In a complex inner product space, apply the same argument to $iv$ to obtain the imaginary part too. Conversely, if $e$ is orthogonal to the subspace, the Pythagorean theorem for inner product spaces givesThus orthogonality characterizes the unique best approximation:Finite dimension also guarantees existence by solving the invertible Gram matrix normal equations; completeness of the ambient inner product space is unnecessary.

Use the convention that the inner product is conjugate-linear in its first argument; the real case is the same without conjugates. Linear independence makes the Gram matrix $G$ positive definite, so $B=G^{-1}$ exists and is Hermitian. Define the Riesz dual basis in an inner product space within ${\mathcal{U}}_n$ byThen $(u_i,{\hat{u}}_k)={\sum }_l{G}_{il}{b}_{lk}={\delta }_{ik}$. Its own Gram entries areHence the inverse Gram matrix is the Gram matrix of the dual vectors:The dual vectors are required to lie in ${\mathcal{U}}_n$; adding arbitrary vectors orthogonal to that subspace would preserve the displayed biorthogonality but would destroy this conclusion.

Use the standard partition normalization of B-splines, not rescaling each spline to have supremum exactly one. Let $h_i=t_{i+k}-t_i>0$. Then $M_i=k{N}_i/h_i$. In the ordinary real inner product, the mixed-normalization spline Gram matrix is $G=D^{-1}H$, where $D=\mathrm{diag}(h_i/k)$ and $H_{ij}=(N_i,N_j)$. Since the $N_i$ form a basis, $H$ is positive definite; $D$ is invertible, so $G$ is invertible. The undeclared upper index $h$ in the printed matrix should be $n$.

We need the standard positivity and normalization properties with their justification. The Cox-de Boor recurrence iswith zero-width terms interpreted as zero. It starts from nonnegative interval indicators. On each lower-order spline's support, its recurrence coefficients are nonnegative, so induction gives $N_i\ge 0$. Extend the finite knots outside their endpoints to a full knot sequence. In the full sum, coefficients of each lower-order spline add to one, so the recurrence preserves partition of unity. Our finite collection is a subset of nonnegative B-splines; therefore ${\sum }_{i=1}^n{N}_i(t)\le 1$ everywhere. The Marsden identity gives equality on the basic knot interval.

The divided-difference definition also gives support in $[t_i,t_{i+k}]$: below the left endpoint the knot-data function is a polynomial of degree $k-1$, whose order-$k$ divided difference vanishes; above the right endpoint the knot data vanish. Choose $a<t_i$ and $b>t_{i+k}$. Integrating in $t$ and then taking the divided difference in its knot variable givesbecause an order-$k$ divided difference of a monic degree-$k$ polynomial is one. The support lies inside $[0,1]$, so ${\int }_0^1{M}_i=1$.

Orthogonality of $f-s^{\ast }$ to the spline space gives $Ga=r$, with $r_i=(M_i,f)$. Since $M_i\ge 0$ and has unit integral, $|r_i|\le \Vert f{\Vert }_{\infty }$. The induced matrix maximum norm is the absolute row-sum norm, soTaking the supremum over nonzero $f$ proves the maximum-norm bound for spline projection:The range is $\mathcal{S}$, so the printed phrase “onto $C[0,1]$” must mean into $C[0,1]$, and onto $\mathcal{S}$. Continuity of the range requires continuous B-splines, for example $k\ge 2$ and internal multiplicities at most $k-1$. For order-one or discontinuous B-splines, the same bound is valid with codomain $L^{\infty }[0,1]$ rather than $C[0,1]$.

Fix $i$. If $t<t_i$, all knot values of the function $x\mapsto (x-t{)}_{+}^{k-1}$ agree with a polynomial of degree $k-1$. Its order-$k$ divided difference vanishes. If $t>t_{i+k}$, all the knot values are zero, so the same divided difference again vanishes. Thus the support is finite:The support and Gram bandwidth of B-splines also holds at repeated knots: the same conclusion follows with the standard limiting convention. If $j\ge i+k$, then $t_j\ge t_{i+k}$, so the two supports have no positive-length overlap. An endpoint intersection contributes zero to the integral defining $G_{ij}$. The case $i\ge j+k$ is identical. HenceFor strictly increasing knots, B-splines whose indices differ by $k-1$ overlap on a positive-length interval and their product is positive there, so this universal bound is sharp. In standard matrix terminology the half-bandwidth is $k-1$ and the full bandwidth is $2k-1$; the paper's integer $d$ is $k$.