Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 70 (Approximation Theory)

Write ${\Delta }_t^{2}f(x)=f(x+t)-2f(x)+f(x-t)$, and use the second modulus of smoothness ${\omega }_2(f,h)={\sup }_{|t|\le h}\Vert {\Delta }_t^{2}f{\Vert }_{\infty }$. The Jackson kernel is even, nonnegative and has unit integral. Pairing the two halves of its convolution therefore givesWe need a weighted moment estimate rather than just concentration of the Jackson kernel. For $|t|\le \pi$, the bounds $|\sin (t/2)|\ge |t|/\pi$ and $|\sin (nt/2)|\le \min (n|\sin (t/2)|,1)$ implyConsequently, splitting the integral at $1/n$ givesThe second modulus of smoothness satisfies ${\omega }_2(f,t)\le (1+t/h{)}^2{\omega }_2(f,h)$ for $t\ge 0$. To see this, choose $q=\lceil t/h\rceil$ when $t>0$, put $u=t/q$, and factor the function translation difference $T_t-I=(T_u-I){\sum }_{r=0}^{q-1}{T}_u^r$. Squaring gives at most $q^2$ translated second differences of step $u$. Each function translation is an isometry in the supremum norm, and centered and forward second differences have the same supremum norm. This proves the stated scaling bound.

Taking $h=1/n$, using $(1+n|t|{)}^2\le 2+2n^2{t}^2$, and integrating against the Jackson kernel now provesThus the Jackson operator estimate is uniform in both $f$ and $n$.

For the requested degree-$n$ best uniform approximation, note that the Jackson kernel, and hence $j_{m}f$, has trigonometric polynomial degree at most $2(m-1)$. Indeed the fourth power in the Jackson kernel is the squared modulus of a squared sum of $m$ consecutive complex exponentials. Choose $m=\lfloor n/2\rfloor +1$, so $2(m-1)\le n$ and $m\ge n/2$. The second-difference integral formula givesApplying the Jackson operator estimate with this $m$ yields the concise answerThe change of index is essential: $j_{n}f$ itself generally has degree $2n-2$, exceeding the permitted degree.

The Bernstein polynomial is the positive weighted averageFor $0\le x\le 1$, the Bernstein basis weights are nonnegative and the binomial theorem gives ${\sum }_{k=0}^n{b}_{n,k}(x)=1$. Hence $|B_n(f,x)|\le {\sum }_k\Vert f{\Vert }_{\infty }{b}_{n,k}(x)=\Vert f{\Vert }_{\infty }$. In particular,This is the contraction property of the positive linear operator on continuous functions defined by the Bernstein polynomial.

The integer endpoint hypothesis is important. Let $r_{n,k}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k/n)-\lfloor \left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k/n)\rfloor$. The floor function gives $0\le r_{n,k}<1$, while $r_{n,0}=r_{n,n}=0$ because $f(0)$ and $f(1)$ are integers. Therefore the rounded Bernstein polynomial satisfiesFor $0\le x\le 1/4$, the successive terms have ratio $x/(1-x)\le 1/3$, so the geometric series estimate givesThe last inequality follows by maximizing $x(1-x{)}^{n-1}$ at $x=1/n$. The same bound holds on $[3/4,1]$ by reflection. On $[1/4,3/4]$, each factor $x$ and $1-x$ is at most $3/4$, giving $S_n(x)\le (n-1)(3/4{)}^n$. ThusHere $n\ge 2$; for $n=1$ the difference vanishes. Without the integer endpoint hypothesis the claim would fail: at $x=0$ the error is $f(0)-\lfloor f(0)\rfloor$, independently of $n$.

First prove necessity. If polynomials with integer coefficients converge to $f$ in the supremum norm, their values at $0$ and $1$ are convergent sequences of integers. Each such sequence is eventually constant, since a convergent sequence is Cauchy and two distinct integers are at distance at least one. Its limit is an integer. Thus $f(0),f(1)\in \mathbb{Z}$.

For sufficiency we also need uniform convergence of the Bernstein polynomial to $f$. Here is a direct argument. For $X\sim \mathrm{Bin}(n,x)$, write $B_n(f,x)=\mathbb{E}f(X/n)$. The binomial distribution has $\mathbb{E}(X/n)=x$ and $\mathrm{Var}(X/n)=x(1-x)/n\le 1/(4n)$. For every $\delta >0$, uniform continuity of $f$ and the Chebyshev inequality giveFirst make $\delta$ small and then $n$ large; the bound is uniform in $x$. Hence $\Vert B_n(f)-f{\Vert }_{\infty }\to 0$.

If the endpoints are integers, part (b) gives $\Vert B_n^{\ast }(f)-B_n(f){\Vert }_{\infty }\to 0$. Each coefficient multiplying $x^k(1-x{)}^{n-k}$ in $B_n^{\ast }$ is an integer. Expanding $(1-x{)}^{n-k}$ by the binomial theorem therefore gives integer coefficients in the ordinary monomial basis. The triangle inequality proves $\Vert B_n^{\ast }(f)-f{\Vert }_{\infty }\to 0$. Thus the integer endpoint condition is necessary and sufficient for integer-coefficient polynomial approximation.

Use real-valued continuous functions and real trigonometric polynomials. The trigonometric Chebyshev alternation theorem says that $p\in {\mathcal{T}}_n$ is the unique best uniform approximation to $f$ if and only if there are distinct points, ordered within one period,Thus the required number of alternating extrema is $2n+2$. When the error is zero, the assertion is interpreted trivially and $p=f$ is unique. The count reflects $\dim {\mathcal{T}}_n=2n+1$ and the fact that a nonzero degree-$n$ trigonometric polynomial has at most $2n$ zeros in one period. In particular a strictly better candidate would force its difference from $p$ to have alternating signs at these points and hence at least $2n+2$ zeros, counting the closing interval around the circle. The trigonometric Chebyshev alternation theorem also gives necessity and uniqueness.

The Weierstrass M-test gives uniform convergence and continuity of the series. For the proposed trigonometric polynomial, set $q=5^{m+1}$ and $A={\sum }_{k=m+1}^{\infty }{a}_k$. The tail satisfiesAt $x_j=j\pi /q$, for $j=0,\dots ,2q-1$, the integer $5^k/q$ is odd for every omitted frequency. Thus $\cos (5^k{x}_j)=(-1{)}^j$ and $r(x_j)=(-1{)}^{j}A$. In particular $\Vert r{\Vert }_{\infty }=A$.

Since $n<q$, these $2q$ points include at least $2n+2$ consecutive alternating extrema in a single period. Also $5^m\le n$, so $t_n\in {\mathcal{T}}_n$. The trigonometric Chebyshev alternation theorem proves that the proposed partial sum is the unique best approximant, withThis is an instance of positive lacunary trigonometric series: all omitted odd frequency ratios align their extrema.

The geometric series formula and part (b) givePut $\alpha =\log 3/\log 5$. Then $5^{\alpha }=3$, so $n^{\alpha }<3^{m+1}$ andThis is the largest possible decay exponent: at $n=5^m$, an estimate with exponent $\beta >\alpha$ would require $\frac{1}{2}\le c(3/5^{\beta }{)}^m$, whose right side tends to zero. Any smaller exponent also gives a valid weaker estimate. In fact $\frac{1}{2}{n}^{-\alpha }\le E_n(f)<\frac{3}{2}{n}^{-\alpha }$ for every $n\ge 1$.

Use the usual strictly increasing spline knot sequence, and initially assume $k\ge 2$. The explicit formula for the order-$k$ divided difference givesEach summand is a truncated power function in $t$, with its junction at $t_j$. It is a piecewise polynomial function of degree at most $k-1$ and has $k-2$ continuous derivatives. Finite summation preserves these properties.

For $t\ge t_{i+k}$ all summands vanish. For $t\le t_i$, all spline knot data come from the polynomial $u\mapsto (u-t{)}^{k-1}$. An order-$k$ divided difference annihilates a polynomial of smaller degree, so $M_i(t)=0$ there too. Thus the support is contained in $[t_i,t_{i+k}]$.

On the last open spline knot interval only the $j=i+k$ term survives; it is a nonzero multiple of $(t_{i+k}-t{)}^{k-1}$. On the first open spline knot interval, compare the truncated spline knot data with the untruncated polynomial data: only the $j=i$ value differs. Since the untruncated divided difference is zero, the result is a nonzero multiple of $(t_i-t{)}^{k-1}$. Consequently both outer pieces are nonzero, giving exact closed support. The Cox-de Boor recurrence used below also proves positivity throughout the open support. ThereforeThis is simple-knot B-spline regularity. For $k=1$ the B-splines are interval indicators; they are piecewise constant and need not be continuous. The notation $C^{k-2}$ should then be read as no continuity requirement, not as a classical negative-order differentiability space.

The divided difference is a finite linear combination of spline knot values, so it commutes with the finite integral. For every spline knot $t_j$ in the defining interval,It follows thatbecause the order-$k$ divided difference of a monic degree-$k$ polynomial is its leading coefficient. This proves the unit-integral normalization of a B-spline.

For the partition of unity, let $N_{i,r}$ denote the partition-normalized order-$r$ B-spline. The Cox-de Boor recurrence isIt follows by substituting the explicit divided difference formula into both sides and collecting each truncated power function. The starting case is $N_{i,1}=1_{[t_i,t_{i+1})}$, with endpoint conventions irrelevant when $r\ge 2$. The two weights are nonnegative wherever their respective lower-order B-splines are nonzero. Induction therefore gives $N_{i,r}\ge 0$ and strict positivity in its open support.

Extend the finite spline knot sequence strictly in both directions, with no finite accumulation. At each point only finitely many B-splines are nonzero. For the full extended family the sum is one for order one. Summing the Cox-de Boor recurrence, the combined coefficient of $N_{j,r-1}$ isInduction gives a full partition of unity at every order. On $t_k<t<t_{n+1}$, all extended order-$k$ functions with index $i\le 0$ or $i\ge n+1$ vanish by their supports. HenceThe same argument gives the useful global subpartition of unity for B-splines, $0\le {\sum }_{i=1}^n{N}_i(t)\le 1$, including outside the basic spline knot interval.

The orthogonal projection has range $\mathcal{S}$, not all of $C[0,1]$: the latter is an infinite-dimensional vector space whereas $\mathcal{S}$ is a finite-dimensional vector space. For a concrete counterexample, $e^x$ cannot belong to any finite-degree piecewise polynomial space, since all its derivatives are nonzero on every open interval. For $k\ge 2$, the B-splines are continuous, so the orthogonal projection is a map $C[0,1]\to \mathcal{S}\subset C[0,1]$. For order one it instead has a generally discontinuous piecewise constant range. For example, a single interval indicator on $[1/4,3/4)$ is the projection of the constant function one onto its span, and is not continuous.

Write $s^{\ast }={\sum }_j{a}_j{N}_j$. Since $M_i$ is a positive scalar multiple of $N_i$, the operator normal equations $⟨f-s^{\ast },N_i⟩=0$ are equivalent toThe mixed-normalization spline Gram matrix is invertible: $G=DH$ where $D_{ii}=k/(t_{i+k}-t_i)>0$ and $H_{ij}=⟨N_i,N_j⟩$ is the ordinary positive-definite matrix of inner products of a linearly independent basis. The positivity and unit-integral normalization of a B-spline give $|b_i|\le \Vert f{\Vert }_{\infty }$. The subpartition of unity for B-splines givesHere the operator norm of a matrix on ${\ell }^{\infty }$ is its maximum absolute row sum. Consequently,This proves the maximum-norm bound for spline projection.

For $k=2$ on an equidistant spline knot sequence, $N_i$ is the triangular hat with value one at $t_{i+1}$ and support $[t_i,t_{i+2}]$. Its slopes on the two pieces are $1/h$ and $-1/h$, and $M_i=N_i/h$. Direct integration givesNonadjacent hats have disjoint interiors of their supports, so their inner product vanishes. Dividing by $h$ therefore givesThis linear-spline mixed Gram matrix is tridiagonal. Every diagonal entry is $2/3$, including the first and last: the distinct-knot hats have their full supports inside $[0,1]$. End rows simply lack one off-diagonal neighbor; there are no repeated endpoint spline knots here.

A strict diagonal dominance argument proves the estimate even on a nonuniform strictly increasing spline knot sequence. Put $h_i=t_{i+1}-t_i>0$. Then $N_i$ has a rising piece of length $h_i$ and a falling piece of length $h_{i+1}$, while $M_i=2N_i/(h_i+h_{i+1})$. The same integrations as in part (b) give the linear-spline mixed Gram matrixOnly entries with indices in $1,\dots ,n$ are present. Thus ${\sum }_{j\ne i}|g_{ij}|\le 1/3$ in every row.

For $Ga=b$, choose an index $i$ with $|a_i|=\Vert a{\Vert }_{{\ell }^{\infty }}$. The reverse triangle inequality then yieldsHence $\Vert a{\Vert }_{{\ell }^{\infty }}\le 3\Vert b{\Vert }_{{\ell }^{\infty }}$. Applying this to every $b$ provesThis is the inverse infinity-norm bound from diagonal dominance; no total positivity theorem is needed. The proof also gives invertibility directly by taking $b=0$.

An orthonormal multiresolution analysis consists of closed subspaces of a Hilbert space $(V_j{)}_{j\in \mathbb{Z}}$ of the Hilbert space $L^2(\mathbb{R})$ such thatThere is a scaling function $\varphi$ whose integer function translations form an orthonormal basis of $V_0$. Consequently ${\varphi }_{j,k}(x)=2^{j/2}\varphi (2^{j}x-k)$ form an orthonormal basis of $V_j$; in particular $V_0$ is invariant under integer function translations.

Let $W_j=V_{j+1}\ominus V_j$ be the orthogonal complement of $V_j$ in $V_{j+1}$. Nesting, density and the trivial intersection imply the orthogonal direct sumFor example, telescoping $V_{J+1}=V_L\oplus {⨁}_{j=L}^J{W}_j$ and letting $L\to -\infty$, $J\to \infty$ gives this decomposition; the corresponding orthogonal projections converge strongly to zero and the identity by the intersection and density properties.

To construct the orthonormal wavelet, use $\varphi \in V_1$ to write the scaling refinement equation $\varphi ={\sum }_n{a}_n\varphi (2\cdot -n)$, with $a\in {\ell }^2$ and ${\sum }_n|a_n{|}^2=2$. Put $m(t)=\frac{1}{2}{\sum }_n{a}_n{e}^{-int}$. The orthonormal translates and Fourier periodization criterion proved in part (b), applied to the scaling refinement equation, yieldsThis is the quadrature mirror filter identity. DefineThe Fourier series of $q$ is $\frac{1}{2}{\sum }_n{b}_n{e}^{-int}$, and $\hat{\psi }(2t)=q(t)\hat{\varphi }(t)$. The two rows $(m(t),m(t+\pi ))$ and $(q(t),q(t+\pi ))$ form a unitary $2\times 2$ matrix almost everywhere: both have squared norm one and their inner product is zero. This wavelet completion of a multiresolution filter proves not just orthogonality but completeness. Splitting a finer-scale coefficient Fourier series into its values at $t$ and $t+\pi$, this invertible two-channel matrix resolves it into a coarse-scale channel and its complementary channel. Thus the integer function translations of $\psi$ form an orthonormal basis of $W_0$.

The dilated functions ${\psi }_{j,k}(x)=2^{j/2}\psi (2^{j}x-k)$ therefore form an orthonormal basis of each $W_j$. The orthogonal direct sum proves the conclusion: every orthonormal multiresolution analysis produces an orthonormal wavelet basis $\{{\psi }_{j,k}:j,k\in \mathbb{Z}\}$ of $L^2(\mathbb{R})$.

Use the printed Fourier transform convention $\hat{\varphi }(t)=\int \varphi (x)e^{-ixt}dx$, interpreted by the Plancherel theorem when $\varphi$ is only square integrable. By the scaling and function translation rules,Taking the Fourier transform of the scaling refinement equation gives $f(t)=m(t/2)f(t/2)$, or equivalentlyConversely this identity, the same scaling rule and injectivity of the Fourier transform recover the scaling refinement equation.

For infinite filters, these statements are equalities in $L^2$, with Fourier series understood in $L^2[0,2\pi ]$. Under the accompanying orthonormality condition, $\{\sqrt{2}\varphi (2\cdot -n)\}$ is an orthonormal sequence, so the refinement series converges in $L^2$ precisely for $a\in {\ell }^2$. Moreover the condition in part (b)(2) makes multiplication by $f$ an isometry from periodic $L^2$ symbols into $L^2(\mathbb{R})$:Applying this to finite filter truncations justifies passage to the limit in both directions. Thus the two paired assertions have a rigorous equivalent interpretation without requiring absolute integrability of $\varphi$.

Let $F(t)={\sum }_{k\in \mathbb{Z}}|f(t+2\pi k){|}^2$. By the Tonelli theorem, $F$ is integrable on $[0,2\pi ]$, since its integral is ${\int }_{\mathbb{R}}|f{|}^2<\infty$. The Plancherel theorem and periodization giveConsequently, if $F=1$ almost everywhere these inner products are ${\delta }_{mn}$, proving orthonormality. Conversely orthonormality says that every Fourier coefficient of $F-1$ is zero. The uniqueness of Fourier coefficients in L1 implies $F-1=0$ almost everywhere. HenceThis proves orthonormal translates and Fourier periodization, including both directions and the normalization constant associated with the printed Fourier transform.

The half-open translates $[-\pi ,\pi )+2\pi k$ partition the real line. Exactly one summand is therefore nonzero in the periodization of $|f{|}^2$, giving ${\sum }_k|f(t+2\pi k){|}^2=1$.

Choose the Shannon scaling mask to be the $2\pi$-periodic extension of $1_{[-\pi /2,\pi /2)}$. On the support of $f$, its product with $f$ is $1_{[-\pi /2,\pi /2)}(t)=f(2t)$; outside that support both sides vanish. Thus the scaling refinement equation holds in frequency. The Fourier coefficients give its precise filter normalization:These coefficients are square summable, so the interpretation in part (b) applies.

The Fourier inversion theorem gives the Shannon scaling functionThis is the normalized sinc function. Its Fourier transform is taken in the Plancherel theorem sense: the Shannon scaling function belongs to $L^2$ but not $L^1$, so its Fourier integral is not absolutely convergent. The inverse integral above is an ordinary integral because the rectangular transform belongs to $L^1$. The resulting refinement spaces are exactly the $L^2$ functions with Fourier transform supported in $[-2^j\pi ,2^j\pi ]$; their union is dense and their intersection is zero. Thus this example also gives a full multiresolution analysis.