Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 67 (Approximation Theory)

For $n\ge 1$, the Bernstein polynomial isThe weights sum to one by the binomial theorem. Equivalently, if $K$ has the binomial distribution with parameters $n,x$, then $B_n(f;x)=\mathbb{E}f(K/n)$. This interpretation makes the cancellation of apparent high-degree terms transparent.

For the falling factorial $u^{\underline{r}}=u(u-1)\cdots (u-r+1)$, with $u^{\underline{0}}=1$, direct cancellation in the binomial weights givesThe polynomials $u^{\underline{0}},\dots ,u^{\underline{m}}$ form a monic triangular basis of the degree-at-most-$m$ polynomials. Hence $u^m=u^{\underline{m}}+{\sum }_{r<m}{c}_r{u}^{\underline{r}}$, andFor $m\le n$, its leading coefficient is $n^{\underline{m}}/n^m\ne 0$. If $p$ has actual degree $m$ and leading coefficient $a_m\ne 0$, linearity shows that the leading coefficient of $B_{n}p$ is $a_m{n}^{\underline{m}}/n^m$; lower-degree terms cannot cancel it. Thus the Bernstein polynomial degree preservation property givesThis includes the requested $m<n$, and also explains why the property cannot simply be extended to $m>n$.

The same moments give $\mathbb{E}K=nx$ and $\mathbb{E}{K}^2=n(n-1)x^2+nx$. ThereforeThe first two approximation errors vanish identically, whileAll three convergences are consequently uniform convergence on $[0,1]$.

For a continuous $2\pi$-periodic function, define the Fourier coefficients and Fourier partial sum byThe Fejér sum is the arithmetic average of the first $n$ Fourier partial sums:Thus $s_n$ has degree at most $n$, whereas ${\sigma }_n$ has degree at most $n-1$. These indexing conventions matter in the identity in (b). Throughout, $m$ is a positive integer; when $n=0$, any term $n{\sigma }_n$ is interpreted as zero without introducing ${\sigma }_0$.

For later estimates, the Fejér kernel in the PDF's normalization isThe apparent singularities are removable. The squared modulus makes $F_n$ nonnegative, and integrating its finite exponential expansion leaves only the $n$ diagonal terms, so ${\pi }^{-1}\int F_n=1$. In particular Fejér summation is a uniform-norm contraction:

A trigonometric polynomial $t_n$ of degree at most $n$ has zero Fourier coefficients outside $[-n,n]$. Its Fourier partial sum $s_j(t_n)$ therefore equals $t_n$ for every $j\ge n$. Averaging the sums with $j=n,\dots ,n+m-1$ givesThus the de la Vallée Poussin sum reproduces the entire degree-at-most-$n$ approximation space, including when the actual degree is smaller.

The difference between the two cumulative sums of Fourier partial sums isHence the de la Vallée Poussin sum satisfiesUsing the uniform-norm contraction of Fejér summation on each term and the triangle inequality in the supremum norm,This proves the requested operator norm bound. When $n=0$ the identity reduces to $v_{0,m}={\sigma }_m$ and the bound is one.

Take any trigonometric polynomial $t\in {\mathcal{T}}_n$. The reproduction property in (a) givesBy (b),Taking the infimum over $t\in {\mathcal{T}}_n$ yields the polynomial reproduction error bound for this operator. With $E_n(f)={\inf }_{t\in {\mathcal{T}}_n}\Vert f-t{\Vert }_{\infty }$ and $n/m\le M$, it becomesThis is a near-best uniform approximation estimate; it follows from reproduction and boundedness without requiring the de la Vallée Poussin sum itself to be a best approximant.

Use the periodic modulus of continuitySubdividing a displacement $t$ into at most $\lceil |t|/\delta \rceil$ steps of size at most $\delta$ proves the chaining inequalityFor $|t|\le \delta$, the sharper bound $\omega (f,\delta )$ holds directly.

Set $\delta =n^{-\alpha }$, where $0<\alpha <1$ and $n\ge 1$. Positivity and unit normalized mass of the Fejér kernel giveThe portion $|t|\le \delta$ is at most $\omega (f,\delta )$. For $0<|t|\le \pi$, $\sin (|t|/2)\ge |t|/\pi$ and $|\sin (nt/2)|\le 1$, soApply this bound and the chaining inequality to the two tails:Let $\beta =1-\alpha >0$. Calculus gives ${\sup }_{u\ge 1}{u}^{-\beta }\log u=1/(e\beta )$, attained at $u=e^{1/\beta }$, and $u^{-\beta }\le 1$. Thus a possible explicit constant for the fractional-scale Fejér approximation bound isThe constant depends only on $\alpha$, not on $f$ or $n$. Since a continuous periodic function is uniformly continuous, the right-hand side tends to zero. The logarithmic tail estimate is what permits every $\alpha <1$; a crude global-oscillation bound would not prove the whole requested range.

For real-valued $f\in C[-1,1]$, there is a unique best uniform approximation $p_{\ast }\in {\mathcal{P}}_n$, where ${\mathcal{P}}_n$ means degree at most $n$. If $E=\Vert f-p_{\ast }{\Vert }_{\infty }>0$, the Chebyshev alternation theorem characterizes it by the existence of $n+2$ ordered pointsand a sign $\epsilon \in \{-1,1\}$ such thatConversely, a polynomial in ${\mathcal{P}}_n$ whose error has this alternation is the best one. If the best error is zero, $f$ itself is the exact polynomial approximant. The real-valued qualification matters: this sign-alternation formulation is not the corresponding criterion for arbitrary complex-valued approximation.

The obstruction to a strict improvement is concrete. If $q$ had smaller error at every alternation point, $q-p_{\ast }$ would have alternating strict signs there. The intermediate value theorem would give at least $n+1$ distinct zeros, impossible for a nonzero polynomial of degree at most $n$.

Since $|T_j(x)|\le 1$ on $[-1,1]$ and the coefficients are summable, the Weierstrass M-test gives uniform convergence of this positive lacunary Chebyshev series and makes its sum continuous.

Let $r$ be the largest integer with $3^r\le n$, and set $r=-1$ when $n=0$. The candidate and its tail size areThe empty sum for $n=0$ is zero. The candidate has degree at most $n$. The triangle inequality bounds its error by the proposed tail sum, and equality holds at $x=1$, since every Chebyshev polynomial has $T_j(1)=1$ and all tail coefficients are positive. It remains to prove that another polynomial cannot improve this error.

Put $L=3^{r+1}$, the first omitted degree, so $L>n$. At the points $y_j=\cos (j\pi /L)$ for $j=0,\dots ,L$, every omitted term hasbecause $3^{k-r-1}$ is odd. Uniform convergence therefore givesThese $L+1$ distinct points run in decreasing order; reversing their order still gives alternating signs. Since $L+1\ge n+2$, select $n+2$ consecutive ones and apply the Chebyshev alternation theorem. It proves both optimality and uniqueness of the displayed candidate. Thus the best polynomial and the error stay unchanged between successive powers of three; this exact truncation property depends on the synchronized tail signs, not on a general rule that truncating a Chebyshev expansion is optimal.

This addresses the general interpolation bound in part (I); the subsequent (a)–(c) address the cubic case in part (II). Write the interpolant in the B-spline basis asThe stipulated uniquely defined spline interpolation operator presupposes invertibility of the B-spline collocation matrix. For the standard increasing distinct sites, the conditions $N_i(x_i)>0$ give it by the Schoenberg–Whitney theorem. Thus $c=A_{\mathbf{x}}^{-1}Rf$.

Use the standard partition-normalized B-splines of the question: they are nonnegative and satisfy the subpartition of unity for B-splines, ${\sum }_j{N}_j(t)\le 1$. This also holds outside the basic knot interval; one may extend the knots and regard the finite family as a subfamily of a full partition of unity. The recurrence proof of the full partition is given in Question 6(c). Repeated knots retain the same nonnegativity and subpartition properties, with zero-denominator recurrence terms interpreted as zero or by knot limits. ConsequentlySampling has norm at most one, $\Vert Rf{\Vert }_{{\ell }^{\infty }}\le \Vert f{\Vert }_{\infty }$, and soHere the induced matrix norm is the maximum absolute row sum. The label $L^{\infty }$-normalized means the usual partition normalization, not rescaling each spline to have maximum value one. Such a rescaling would invalidate the specific coefficient bound and the cardinal values used below.

Let $C_k(u)$ be the order-$k$ Cardinal B-spline supported on $[0,k]$. The Cox-de Boor recurrence on unit-spaced knots readsStart with $C_1=1_{[0,1)}$. The order-two hat satisfies $C_2(1)=1$ and vanishes at its support endpoints. Substituting these values into the recurrence gives $C_3(1)=C_3(2)=1/2$ and thenThe continuous cubic spline is zero at $0,4$ and outside its support. Since $N_j(t)=C_4(t-j)$ and $x_i=i+2$, this yields the midpoint cubic spline collocation valuesOnly indices $1\le j\le n$ are retained. In particular no nonexistent spline is added to an endpoint row.

The B-spline collocation matrix in the cubic case is the finite tridiagonal matrixFor $n=1$, this is simply the one-entry matrix $(2/3)$.

To evaluate the inverse norm exactly, let $D=\mathrm{diag}((-1{)}^1,\dots ,(-1{)}^n)$. Then $B_n=D{A}_{n}D=(4I-C)/6$, where $C$ has ones immediately above and below the diagonal and zeros elsewhere. Since $\Vert C/4{\Vert }_{{\ell }^{\infty }}\le 1/2$, the convergent Neumann serieshas nonnegative entries and proves invertibility. Since $A_n^{-1}=D{B}_n^{-1}D$, its absolute entries equal those of $B_n^{-1}$. The absolute row sums are therefore the entries of $u=B_n^{-1}1$.

The equation $B_{n}u=1$ becomesIts constant particular solution is $3$; the two characteristic roots of the homogeneous recurrence are $\rho =2-\sqrt{3}$ and ${\rho }^{-1}=2+\sqrt{3}$. Imposing the two boundary values givesThis can also be checked by direct substitution, since $\rho +{\rho }^{-1}=4$. The numerator is smallest at the central index or central pair of indices: its successive difference is $(1-\rho )({\rho }^{n-i}-{\rho }^i)$. Thus, with $j=\lfloor (n+1)/2\rfloor$, the exact inverse norm of midpoint cubic spline collocation isEquivalently, if $n=2m-1$ the fraction is $2{\rho }^m/(1+{\rho }^{2m})$, and if $n=2m$ it is $({\rho }^m+{\rho }^{m+1})/(1+{\rho }^{2m+1})$. The finite norm is not exactly three: it equals $3/2$ for $n=1$, two for $n=2$, and tends to three as $n$ grows. Hence three is the sharp dimension-independent bound for these inverse matrix norms.

Apply the general B-spline interpolation operator norm estimate in part (I) to the inverse norm from (b):and hence in particular $\Vert P_{\mathbf{x}}{\Vert }_{L^{\infty }}\le 3$, independently of $n$. The strict finite-dimensional estimate uses the actual finite collocation matrix; it does not require periodic closure, natural boundary conditions or endpoint knot repetitions.

There is also a direct shorter verification of the uniform bound. For an index $i$ maximizing $|z_i|$, the triangle inequality giveswith an even larger margin when a neighbor is missing. This is the inverse infinity-norm bound from diagonal dominance, and again gives $\Vert A_n^{-1}{\Vert }_{{\ell }^{\infty }}\le 3$.

For this part relabel one consecutive block of $k+1$ distinct knots as $t_0,\dots ,t_k$. This is a local reindexing; no extra global knot is being introduced. Let $g_t(u)=(u-t{)}_{+}^{k-1}$. Its Lagrange interpolation polynomial through the knot values isEach quotient $\omega (u)/(u-t_i)$ is monic of degree $k$. Comparing leading coefficients givesThe same leading coefficient is the order-$k$ divided difference $[t_0,\dots ,t_k]g_t$, by the Newton interpolation polynomial representation. Multiplying by $k$ therefore gives the explicit B-spline formulaDistinct knots make every denominator nonzero. For $k=1$ the degree-zero truncated power is interpreted as an interval-indicator convention; values at individual endpoints do not affect its integral.

The order-$k$ divided difference defining $M_i$ is a finite linear combination of values at its knots. Hence integration can be interchanged with it directly. For a knot value $u\in [a,b]$,It follows thatThe final equality holds because the order-$k$ divided difference of a degree-$k$ monic polynomial is its leading coefficient, one. ThusThis proves the unit-integral normalization of a B-spline. Its support is contained in $[t_i,t_{i+k}]$: below all its knots, the sampled truncated power agrees with a degree-$k-1$ polynomial, annihilated by the order-$k$ divided difference; above all its knots, every sample is zero. No mass is omitted by integration over $[a,b]$.

Since $N_i=(t_{i+k}-t_i)M_i/k$, the corresponding partition-normalized B-spline has integral $(t_{i+k}-t_i)/k$. Its normalization is different from that of $M_i$.

We first derive the recurrence needed for the partition of unity. Denote an order-$r$ partition-normalized spline by $N_{i,r}$. For $r\ge 2$, set $h_t(u)=(u-t{)}_{+}^{r-2}$, so $(u-t)h_t(u)=(u-t{)}_{+}^{r-1}$. The elementary product identities for divided differences areThey follow from the Leibniz rule for divided differences because the divided differences of the linear factor vanish above first order. Use the first identity on $t_i,\dots ,t_{i+r-1}$ and the second on $t_{i+1},\dots ,t_{i+r}$. Subtracting cancels the common middle-block term. The defining divided-difference recurrence for $N_{i,r}$ then givesThis is the Cox-de Boor recurrence, derived here from the specified normalization rather than assumed as a partition theorem.

Extend the distinct knot sequence in both directions to a strictly increasing sequence $(t_i{)}_{i\in \mathbb{Z}}$ tending to $\pm \infty$. For order one, $N_{i,1}=1_{[t_i,t_{i+1})}$, so the full sum equals one. All higher-order splines are supported on $[t_i,t_{i+r}]$, making the following sums locally finite. Reindexing the second term of the recurrence yieldsInduction proves that the full sum is one for every order. The same recurrence gives nonnegativity: each coefficient is nonnegative wherever its associated lower-order spline is nonzero. Removing splines therefore gives the subpartition of unity for B-splines on the whole line.

For $t_k<t<t_{n+1}$, a spline with index $i\le 0$ ends no later than $t_k$, and one with $i\ge n+1$ starts no earlier than $t_{n+1}$. They all vanish, leaving exactly the indices $1,\dots ,n$. For $k\ge 2$ the splines are continuous and vanish at their support endpoints, so the equality extends to the closed basic knot interval:If order one is allowed, the standard half-open indicator convention gives equality on $[t_1,t_{n+1})$; to include its final endpoint literally, assign the left-limit value there. This harmless endpoint convention does not change integrals or $L^{\infty }$ norms. For the continuous splines of order at least two no such convention is necessary.