Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 62 (Approximation Theory)

The Bernstein polynomial isIt has degree at most $n$, since cancellation can lower the degree. For $0\le x\le 1$, the Bernstein basis weights are nonnegative and their sum is $(x+(1-x){)}^n=1$ by the binomial theorem. ConsequentlyThus the Bernstein polynomial defines a positive linear operator on continuous functions satisfying $\Vert B_{n}f{\Vert }_{\infty }\le \Vert f{\Vert }_{\infty }$. Since $B_{n}1=1$, its operator norm in the supremum norm is exactly one.

Write $j^{\underline{m}}=j(j-1)\cdots (j-m+1)$ for the falling factorial. At the sampling points, $f_{nm}(j/n)=n^{-m}{j}^{\underline{m}}$, which vanishes for $j<m$. For $j\ge m$, cancellation of the factorials givesInsert this into the Bernstein polynomial and set $\ell =j-m$:The binomial theorem evaluates the remaining sum. For $m=0$, both sides equal one. This proves the Bernstein falling-factorial identity $B_n(f_{nm},x)=f_{nm}(1)x^m$.

Fix $m$ and take $n\ge m$. On $[0,1]$, every factor $x-r/n$ and every factor $x$ has absolute value at most one. Replacing the factors successively and applying the triangle inequality givesUsing the supremum norm contraction in (a) and the Bernstein falling-factorial identity in (b),For $m=0,1$, the monomials are reproduced exactly. For every fixed $m$, $B_n(x^m)\to x^m$ uniformly on $[0,1]$.

The Weierstrass approximation theorem states that the polynomials are a dense subspace of $C[0,1]$ in the supremum norm. By linearity and (c), $B_{n}p\to p$ uniformly for every polynomial $p$. Given $f\in C[0,1]$ and $\epsilon >0$, choose a polynomial $p$ with $\Vert f-p{\Vert }_{\infty }<\epsilon$. The operator norm estimate in (a) givesFirst let $n\to \infty$, then $\epsilon \downarrow 0$. Hence $\Vert B_{n}f-f{\Vert }_{\infty }\to 0$ for every continuous $f$. This is an instance of extension of approximation operators from a dense subspace.

Use the centered second modulus of smoothnessThe relevant modulus properties are ${\omega }_2(f,t)\le (1+t/\delta {)}^2{\omega }_2(f,\delta )$ for $t\ge 0$, $\delta >0$, and ${\omega }_2(f,\delta )\le {\delta }^2\Vert f^{\prime \prime }{\Vert }_{\infty }$ when $f^{\prime \prime }$ is continuous. The latter follows from the second-difference integral formulaThe Fejér kernel is even, nonnegative and has integral one. Averaging the convolution at $t$ and $-t$ therefore givesApply the second modulus of smoothness bound and $(1+s{)}^2\le 2(1+s^2)$:For $|t|\le \pi$, $\sin (|t|/2)\ge |t|/\pi$, while ${\sin }^2(nt/2)\le 1$. ThusThe removable value at $t=0$ causes no problem. With $\delta =n^{-1/2}$, the Fejér second-modulus approximation bound isIf $f^{\prime \prime }$ is continuous, this also yields $\Vert {\sigma }_{n}f-f{\Vert }_{\infty }\le (1+{\pi }^2)\Vert f^{\prime \prime }{\Vert }_{\infty }/n=O(n^{-1})$.

Squaring the finite geometric sum in the Fejér kernel gives its Fourier seriesFor a fixed positive integer $k$ and $n>k$, convolution therefore gives ${\sigma }_n(e^{ikx})=(1-k/n)e^{ikx}$. Taking the real part,The ratio to $1/n$ is the nonzero constant $k$, even though the function is infinitely differentiable. This Fejér saturation on a Fourier mode disproves an $o(n^{-1})$ estimate for all $C^2$ periodic functions.

For $x=\cos \theta$ with $0<\theta <\pi$, differentiation of the Chebyshev polynomial givesBoth sides are polynomials in $x$, so the identity holds at the endpoints and, in fact, for every real $x$.

Order the roots of a polynomial here as $x_j=\cos {\theta }_j$, ${\theta }_j=(2j-1)\pi /(2n)$, so $x_1>\cdots >x_n$. At these simple roots,For a polynomial $q$ of degree at most $n-1$, the Lagrange interpolation polynomial isFor $x>x_1$, the Chebyshev polynomial is positive: all its roots are at most $x_1$ and its leading coefficient is positive. Hence ${\ell }_j(x)T_n^{\prime }(x_j)=T_n(x)/(x-x_j)>0$. The assumed nodal bounds and interpolation of the degree-$n-1$ polynomial $T_n^{\prime }$ now giveContinuity includes $x=x_1$. Apply this argument to $q(-x)$ and use the parity of the Chebyshev polynomial to obtain the negative side. Thus the Chebyshev nodal derivative comparison proves

Assume $n\ge 1$ and $\Vert p{\Vert }_{[-1,1]}\le 1$. The given Bernstein inequality for algebraic polynomials shows that $q=p^{\prime }$ satisfies the nodal hypotheses of (a). Consequently, in the two endpoint regions $\cos (\pi /(2n))\le |x|\le 1$, $|p^{\prime }(x)|\le |T_n^{\prime }(x)|$.

For $0<\theta <\pi$, the finite geometric identitybounds its absolute value by $n$. It follows that $|T_n^{\prime }(\cos \theta )|\le n^2$, and the endpoint limit gives $T_n^{\prime }(1)=n^2$. In the central interval, the Bernstein inequality for algebraic polynomials givessince $\sin t\ge 2t/\pi$ on $[0,\pi /2]$. Combining the regions and rescaling proves the Markov inequality for polynomial derivatives:The Chebyshev polynomial itself attains equality, so this constant is sharp. Constant polynomials have zero derivative.

Put $s_j=t_{i+j}$ for $0\le j\le k$, with the knots in increasing order. The explicit formula for a divided difference at distinct nodes givesEach truncated power function is a piecewise polynomial function of degree $k-1$ and is $C^{k-2}$ for $k\ge 2$. Therefore their sum has the same global smoothness. The jump in the $(k-1)$st derivative at $s_j$ equalswhich is nonzero. Thus each $s_j$ really is a knot, and generally there is no additional smoothness.

If $t<s_0$, the values being differenced are the values of the degree-$k-1$ polynomial $(s-t{)}^{k-1}$, so their $k$th divided difference vanishes. If $t>s_k$, every sampled truncated power function is zero. To check that both support endpoints occur, for $s_0<t<s_1$ subtract the vanished full polynomial divided difference to obtainFor $s_{k-1}<t<s_k$, only the last term survives and is positive. The nonnegativity from the recurrence in (b) actually gives positivity throughout the interior: for each $s_0<t<s_k$, at least one lower-order B-spline covering $t$ has a positive recurrence coefficient, and induction starts with positive order-one indicators. Hence $\mathrm{supp}{M}_i=[t_i,t_{i+k}]$ and $M_i\in C^{k-2}$ for $k\ge 2$, with degree $k-1$ on its knot intervals. For $k=1$, the B-spline is the step function $1_{[s_0,s_1)}(t)/(s_1-s_0)$, so no continuity is asserted.

The unit-integral normalization of a B-spline also follows directly: integrating $k(s_j-t{)}_{+}^{k-1}$ over $s_0\le t\le s_k$ gives $(s_j-s_0{)}^k$. The $k$th divided difference of this monic degree-$k$ polynomial is one. Thus $\int M_i(t)dt=1$, explaining its normalization.

Use $s_j=t_{i+j}$ again and take $k\ge 2$. Set $g(s)=(s-t{)}_{+}^{k-2}$, so $(s-t)g(s)=(s-t{)}_{+}^{k-1}$. LetThe Leibniz rule for divided differences, applied to the linear factor $s-t$, readsMultiply by $s_k-s_0$ and substitute $G$ to get $(t-s_0)H+(s_k-t)K$. Converting $H$ and $K$ to the lower-order normalized B-splines proves the Cox-de Boor recurrence:It starts with $N_{i,1}=1_{[t_i,t_{i+1})}$. The coefficients are nonnegative wherever the corresponding lower-order B-spline is nonzero, so induction proves nonnegativity.

For later use, extend the finite knot sequence to a strictly increasing sequence in both directions. The full order-one sum is one. When the Cox-de Boor recurrence is summed, the two coefficients of each fixed lower-order B-spline add to one. Induction therefore gives a full partition of unity. Removing terms proves the subpartition of unity for B-splines, ${\sum }_{i=1}^n{N}_{i,k}(t)\le 1$. For repeated knots, the same statement follows by a limit of strictly increasing knot sequences, with the usual convention that a recurrence term with zero denominator is zero; the bound holds on each open knot interval and for the standard one-sided endpoint values. The terminology “$L_{\infty }$-normalized” refers to this standard basis normalization; it does not claim that each individual B-spline has supremum norm exactly one.

For the usual spline interpolation problem the sites are distinct and ordered; the Schoenberg–Whitney theorem then makes $A_x$ invertible under the stated support positivity. More generally, the following argument applies whenever the interpolation map in the question is well defined and $A_x$ is invertible.

Factor the spline interpolation operator as $P_x=B{A}_x^{-1}R$, whereSampling has operator norm at most one from the supremum norm to ${\ell }_{\infty }$. Nonnegativity and the subpartition of unity for B-splines giveConsequently $\Vert P_x\Vert \le \Vert A_x^{-1}{\Vert }_{{\ell }_{\infty }}$.

For the reverse bound, select a row $r$ of $A_x^{-1}$ with maximal absolute row sum, and choose $y_j=\mathrm{sgn}((A_x^{-1}{)}_{rj})$, assigning any value of modulus at most one when the entry is zero. Then $\Vert y{\Vert }_{{\ell }_{\infty }}=1$ andAt distinct sites there is a continuous piecewise linear function $f$ with $f(x_j)=y_j$ and $\Vert f{\Vert }_{\infty }=1$: interpolate linearly between the ordered sites and extend constantly to the endpoints. The given uniform-norm stability of a B-spline basis therefore impliesThus the B-spline interpolation operator norm satisfiesPositivity $N_i(x_i)>0$ alone, without the usual distinct-site convention, is insufficient to define an interpolation operator. For example, take order-two B-splines with knots $0,1,2,3$ and $x_1=x_2=3/2$. Both diagonal values are $1/2$, but the B-spline collocation matrix has identical rows $(1/2,1/2)$ and is singular. The displayed proof uses the well-defined interpolation map posited in the question; ordered distinct sites supply its standard existence guarantee.

For unit-spaced knots, the quadratic cardinal B-spline with support $[i,i+3]$ is $N_i(t)=B(t-i)$, where the Cox-de Boor recurrence givesIn particular $B(1)=B(2)=1/2$ and $B(0)=B(3)=0$. At $x_i=i+2$, the only nonzero entries in row $i$ are $A_{ii}=1/2$ and, if $i<n$, $A_{i,i+1}=1/2$. Write $U$ for the upper shift matrix, with ones immediately above its diagonal. Thensince $U^n=0$. Thus $(A_x^{-1}{)}_{ij}=2(-1{)}^{j-i}$ for $j\ge i$, and zero otherwise. The largest absolute row sum is the first, giving $\Vert A_x^{-1}{\Vert }_{{\ell }_{\infty }}=2n$.

Using (1) and the permitted $d_3=3$ proves the stronger linear growth of shifted quadratic spline interpolation estimateTherefore $\Vert P_x\Vert =\Theta (n)$ and is not uniformly bounded. An $O(n)$ upper bound alone would not imply unboundedness; the lower bound is essential.

An orthonormal multiresolution analysis consists of closed subspaces $V_j\subset L_2(\mathbb{R})$, $j\in \mathbb{Z}$, with $V_j\subset V_{j+1}$, $\overline{{\bigcup }_j{V}_j}=L_2(\mathbb{R})$, ${\bigcap }_j{V}_j=\{0\}$, and the dilation equivalence $h\in V_j⟺h(2\cdot )\in V_{j+1}$. A scaling function $\varphi$ has integer translates forming an orthonormal basis of $V_0$. Henceis an orthonormal basis of $V_j$. Set $W_j=V_{j+1}\ominus V_j$, the orthogonal complement of $V_j$ inside $V_{j+1}$. A function $\psi$ whose integer translates form an orthonormal basis of $W_0$ produces a complete orthonormal wavelet system $\{2^{j/2}\psi (2^j\cdot -k):j,k\in \mathbb{Z}\}$: different $W_j$ are orthogonal, their sum contains every difference $V_b\ominus V_a$, and density together with the zero intersection exhausts $L_2(\mathbb{R})$.

Here is the filter construction that guarantees such a wavelet. Nesting puts $\varphi$ in $V_1$, so expansion in its orthonormal basis gives the scaling refinement equation $\varphi ={\sum }_n{a}_n\varphi (2\cdot -n)$, with $a\in {\ell }_2$. Define the MRA low-pass filter and its complementary quadrature mirror filter bySplitting the orthonormal translates and Fourier periodization identity at $2t$, as in part (b), gives $|m(t){|}^2+|m(t+\pi ){|}^2=1$ almost everywhere. Consequently the rows ofhave length one and are orthogonal; the matrix is unitary. Put $b_n=(-1{)}^n\overline{a_{1-n}}$ and $\psi ={\sum }_n{b}_n\varphi (2\cdot -n)$, so $q(t)=\frac{1}{2}{\sum }_n{b}_n{e}^{-int}$.

To see completeness as well as orthogonality, identify $V_1$ with its fine-scale coefficient sequences and take their Fourier series. Group the frequencies $t$ and $t+\pi$ over a half-period. The two rows of the displayed matrix are the normalized coarse and complementary channels; their unitarity is exactly an onto isometry from these two channels to the fine-scale coefficient space. Translates of $\varphi$ and $\psi$ correspond to the Fourier basis in the respective channels. They therefore jointly form an orthonormal basis of $V_1$. The orthogonal complement channel gives the wavelet completion of a multiresolution filter, namely the integer translates of $\psi$ span $W_0$. This proves the asserted relation with an orthonormal wavelet.

Use the Fourier transform convention $f(t)=\hat{\varphi }(t)=\int \varphi (x)e^{-ixt}dx$ and the Plancherel theorem normalization $\Vert \varphi {\Vert }_2^2=(2\pi {)}^{-1}\Vert f{\Vert }_2^2$. For a general $L_2$ scaling function, the transform means its $L_2$ extension; an ordinary absolutely convergent integral is not required.

A change of variables gives $\widehat{\varphi (2\cdot -n)}(t)=\frac{1}{2}{e}^{-int/2}f(t/2)$. Thus the scaling refinement equation transforms to $f(t)=m(t/2)f(t/2)$, or $f(2t)=m(t)f(t)$, with the $2\pi$-periodic MRA low-pass filter $m(t)=\frac{1}{2}{\sum }_n{a}_n{e}^{-int}$. The periodicity is necessary; allowing an arbitrary quotient $f(2t)/f(t)$ would not express refinement by integer translates.

For orthonormality, let $P(t)={\sum }_{k\in \mathbb{Z}}|f(t+2\pi k){|}^2$. This is a $2\pi$-periodic $L_1$ function, since $f\in L_2$. The Plancherel theorem givesThese inner products equal ${\delta }_{j\ell }$ precisely when the Fourier coefficients of $P$ agree with those of one. The uniqueness of Fourier coefficients in L1 proves the equivalenceFor completeness, the converse refinement implication is also valid with the natural $L_2$ series interpretation. Suppose this periodization identity and $f(2t)=m(t)f(t)$ hold for a measurable $2\pi$-periodic $m$. Splitting the periodization at $2t$ into even and odd translates givesHence $m$ is bounded and belongs to $L_2$ of a period. Write $m=\frac{1}{2}{\sum }_n{a}_n{e}^{-int}$ in $L_2$ and let $m_N$ denote the symmetric partial sums. Since $P=1$,After substituting $t/2$, this proves convergence of the transformed refinement sums to $f$ in $L_2$. Inverting the Fourier transform proves $\varphi ={\sum }_n{a}_n\varphi (2\cdot -n)$ in $L_2$. Thus the two spatial conditions and the two Fourier conditions are equivalent, with the periodic mask and convergence conventions made explicit.

First use the usual real-valued, measurable interpretation of the transition data. The complementary squares then imply $|f|\le 1$, and the compact support gives $f\in L_2$. Consider the periodization on $[-\pi ,\pi ]$. For $|t|<2\pi /3$, only $f(t)=1$ contributes. For $2\pi /3\le t\le \pi$, only $f(t)$ and $f(t-2\pi )$ can contribute, and their squares sum to one. For $-\pi \le t\le -2\pi /3$, apply the complementary identity at $t+2\pi$ to obtain $f(t{)}^2+f(t+2\pi {)}^2=1$. Therefore the orthonormal translates and Fourier periodization identity holds almost everywhere.

Define a periodic MRA low-pass filter by prescribing it on $[-\pi ,\pi ]$:In the central band, $f(t)=1$, so $f(2t)=m(t)f(t)$. In the rest of this fundamental interval, both $m(t)$ and $f(2t)$ vanish. If $\pi <|t|<4\pi /3$, reducing $t$ modulo $2\pi$ puts it in an outer band where $m=0$, and again $f(2t)=0$. For $|t|\ge 4\pi /3$, both $f(t)$ and $f(2t)$ vanish. Endpoint choices affect only a null set. Thus the complementary transition bands for a scaling function give both Fourier conditions, with this explicitly constructed periodic mask.

A concrete real-valued choice, illustrating that the transition constraints are consistent, isOn the positive transition band put $u=3t/(2\pi )-1\in [0,1]$. The other translate has parameter $1-u$, so the sum is ${\cos }^2(\pi u/2)+{\sin }^2(\pi u/2)=1$.

There is a genuine qualification in the printed formulation: it uses ordinary squares without explicitly declaring $f$ real-valued. If arbitrary complex values are allowed, the claimed verification is false. Take $f=1$ for $|t|\le 2\pi /3$, $f=0$ for $|t|\ge 4\pi /3$, and setThe printed complementary-square rule holds, including its endpoints: in the interior $i^2+(\sqrt{2}{)}^2=1$, while the endpoints pair one with zero. Nevertheless, for $2\pi /3<t<\pi$,This compactly supported $L_2$ function is the Fourier transform of an $L_2$ function, so it is a counterexample within the natural complex Hilbert space. The verification is valid for real-valued $f$, or with absolute squares in the transition rule; it is not valid for unrestricted complex $f$ with ordinary squares.