Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 71 (Approximation Theory)

Write the Bernstein polynomial in its partition-normalized Bernstein basis:For $0\le x\le 1$, every weight is nonnegative, and the binomial theorem gives their sum as $(x+1-x{)}^n=1$. ConsequentlyTaking the supremum norm proves $\Vert B_n(f){\Vert }_{\infty }\le \Vert f{\Vert }_{\infty }$. The construction yields degree at most $n$, possibly lower for special functions.

For each $k$, let ${\epsilon }_{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 ensures $0\le {\epsilon }_{n,k}<1$, even when the quantity being rounded is negative. The integer endpoint hypothesis gives ${\epsilon }_{n,0}={\epsilon }_{n,n}=0$. Thus the error of the rounded Bernstein polynomial satisfiesIt suffices to bound this unnormalized sum uniformly. If $0\le x\le 1/4$, put $q=x/(1-x)\le 1/3$ and sum a geometric series:The last inequality follows by maximizing $x(1-x{)}^n$, whose maximum occurs at $x=1/(n+1)$ and is at most $1/(n+1)$. Reflection gives the same bound for $3/4\le x\le 1$. In the middle interval both $x$ and $1-x$ are at most $3/4$, so each summand is at most $(3/4{)}^n$. Therefore, for $n\ge 2$,Endpoint integrality matters: at zero or one a noninteger value would leave a fixed nonzero rounding error.

If polynomials with integer monomial coefficients converge uniformly to $f$, their values at zero and one are integers converging to $f(0)$ and $f(1)$. A convergent integer sequence is eventually constant: once all its terms lie in an interval of length less than one they must agree. Hence both endpoint values are integers.

Conversely assume those values are integers. The rounded Bernstein polynomial is an integer-coefficient polynomial, because its displayed scalar coefficients are integers and each $x^k(1-x{)}^{n-k}$ expands with integer coefficients. Part b gives its vanishing distance from $B_{n}f$. For completeness, the remaining uniform convergence $B_{n}f\to f$ follows directly from uniform continuity. Let $X$ have the binomial distribution with parameters $n,x$; then $B_n(f,x)=\mathbb{E}f(X/n)$, $\mathbb{E}(X/n)=x$, and $\mathrm{Var}(X/n)=x(1-x)/n\le 1/(4n)$. Splitting into $|X/n-x|\le \delta$ and its complement, and applying Chebyshev's inequality, giveswhere $\omega$ is the modulus of continuity. First choose $\delta$ to make the first term small uniformly, then take $n$ large. The triangle inequality now gives $\Vert B_n^{\ast }f-f{\Vert }_{\infty }\to 0$. We have proved the integer-coefficient polynomial approximation characterization

A strictly convex normed space is a normed vector space whose unit sphere contains no nontrivial line segment. Equivalently, for distinct unit vectors $x,y$,Suppose $u,v\in U$ are both elements of best approximation in a normed space to $f$, and let $d={\inf }_{w\in U}\Vert f-w\Vert$. If $d=0$ then $u=v=f$. If $d>0$ and $u\ne v$, the vectors $(f-u)/d$ and $(f-v)/d$ are distinct unit vectors. Strict convexity givesBut $(u+v)/2\in U$, contradicting the definition of $d$. Thus there is at most one best approximant. This proves uniqueness of best approximation in a strictly convex space, and does not assert existence for an arbitrary, possibly nonclosed, linear subspace.

Take $n\ge 1$ and $1<p<\infty$. The Lp space is strictly convex because $z\mapsto |z{|}^p$ is strictly convex: for distinct unit functions its pointwise midpoint inequality is strict on a set of positive measure, hence integration gives norm strictly below one. The finite-dimensional linear subspace ${\mathcal{T}}_{n-1}$ has a best approximant: any minimizing sequence is bounded by $\Vert t{\Vert }_p\le \Vert f-t{\Vert }_p+\Vert f{\Vert }_p$, and finite-dimensional compactness gives a convergent subsequence whose limit minimizes the continuous error. Uniqueness follows from part 1.

Write that unique minimizer as $t^{\ast }$ and its residual as $F=f-t^{\ast }$. Translation on the circle preserves the Lp norm. Since $f(x+2\pi /n)=f(x)$, the translated polynomial $t^{\ast }(x+2\pi /n)$ is another minimizer. Uniqueness forcesAlso $f(x+\pi /n)=-f(x)$. Therefore the polynomial $-t^{\ast }(x+\pi /n)$ has residual $-F(x+\pi /n)$, with the same norm as $F$, and is again a minimizer. HenceTo extract the consequence, write the trigonometric polynomial as $t^{\ast }(x)={\sum }_{|\ell |\le n-1}{c}_{\ell }{e}^{i\ell x}$. The first identity gives $(e^{2\pi i\ell /n}-1)c_{\ell }=0$. Only $\ell =0$ in the indicated frequency range is a multiple of $n$, so $t^{\ast }$ is constant. The second identity makes this constant its own negative and therefore zero. Thus the lower-frequency Lp approximation to a single harmonic isFor $n=1$ the space already consists only of constants, and the negative-translation argument gives the same result.

For a real continuous $2\pi$-periodic function $f$, the trigonometric Chebyshev alternation theorem says that $t^{\ast }\in {\mathcal{T}}_n$ is its best uniform approximation if and only if there are $2n+2$ distinct cyclically ordered points in one period,and a sign $\epsilon \in \{1,-1\}$ such thatThe best approximant exists and is unique. Alternation is cyclic: the last and first displayed extrema also have opposite signs across the closing interval. If the error is zero, $f=t^{\ast }$ and the characterization holds trivially.

The sufficiency can be seen from zero counting. A strictly improving trigonometric polynomial would have a difference from $t^{\ast }$ with the alternating nonzero signs at these points, forcing at least $2n+2$ zeros on the circle. A nonzero member of ${\mathcal{T}}_n$ has at most $2n$ zeros: multiplying its Laurent expression by $e^{inx}$ gives an ordinary polynomial of degree at most $2n$ in $e^{ix}$. This contradiction is the alternation mechanism used in the next part.

The coefficient sum is finite, so the Weierstrass M-test makes the cosine series uniformly convergent and $f$ continuous. Put $Q=5^{m+1}$ and $A_m={\sum }_{k=m+1}^{\infty }{a}_k$. The indicated partial sum belongs to ${\mathcal{T}}_n$ because its largest frequency is $5^m\le n$. Its tail satisfiesand equality holds at $x=0$. Thus its supremum norm error is exactly $A_m$.

At the $2Q$ points $x_j=j\pi /Q$, $0\le j<2Q$, every omitted frequency is an odd integer multiple of $Q$. Indeed for $k\ge m+1$,Uniform convergence permits summing these values, givingThese are cyclically alternating extrema. Since $n<Q$, there are $2Q\ge 2n+2$ of them, so the trigonometric Chebyshev alternation theorem proves that the partial sum is the unique best approximant. Consequently the positive lacunary trigonometric series hasThe positivity of every tail coefficient makes the same tail attain its full coefficient sum with alternating signs; a triangle bound alone would not establish optimality.

Let $y=(f(x_1),\dots ,f(x_n){)}^T$ and write the interpolating spline as $P_{x}f={\sum }_{j=1}^n{c}_j{N}_j$. The interpolation equations are $A_{x}c=y$, so $c=A_x^{-1}y$. Since $P_x$ is defined as a unique interpolant for arbitrary data, its B-spline collocation matrix is invertible. Ordered sites satisfying diagonal positivity ensure this by question 7. Positivity alone without admissible ordering does not: two equal sites in overlapping basis supports could give two identical rows. The norm argument below uses the existence of the operator stipulated here.

Standard partition-normalized B-splines satisfy $N_j\ge 0$ and ${\sum }_{j=1}^n{N}_j\le 1$. The latter is a subpartition of unity for B-splines: extending the knot sequence gives a full partition of unity, and discarding basis functions cannot increase its sum. HenceTaking the supremum over $t$ and then over unit-norm $f$ gives the B-spline interpolation operator norm estimateHere the matrix norm is the induced maximum-row-sum norm, not the maximum of its individual entries. The proof only needs nonnegative basis functions, their sum at most one, and invertible interpolation.

Use the Cox-de Boor recurrence. For unit knots the order-two hat is $L(u)=u$ on $[0,1]$, $L(u)=2-u$ on $[1,2]$, and zero elsewhere. The order-three quadratic cardinal B-spline isThus $N_j(t)=q(t-j)$. At $x_i=i+3/2$, the only possible arguments in its support are $3/2$ and $1/2,5/2$ at neighboring indices. Their values giveIndices outside $1,\dots ,n$ are absent, so the first and last rows have just one neighboring nonzero value.

The centered quadratic spline interpolation matrix is the symmetric tridiagonal Toeplitz matrixFor $n=1$, this means simply $A_x=(3/4)$. To evaluate the inverse norm exactly, let $D=\mathrm{diag}((-1{)}^i{)}_{i=1}^n$ and $M=8D{A}_{x}D=\mathrm{tridiag}(-1,6,-1)$. If $J$ is the nonnegative adjacency matrix of the path, then $M=6I-J$ and $\Vert J/6{\Vert }_{\infty }\le 1/3$. The convergent Neumann seriestherefore has nonnegative entries. Since $A_x^{-1}=8D{M}^{-1}D$, its entrywise absolute values are $8M^{-1}$. Let $r_i={\sum }_j|(A_x^{-1}{)}_{ij}|$. Then $r=8M^{-1}1$, orThe homogeneous characteristic roots are $3\pm 2\sqrt{2}$. Put $\tau =3-2\sqrt{2}\in (0,1)$. The particular solution $r_i=2$ and the two boundary conditions giveThese row sums are symmetric and increase toward the centre: the exponential sum in the numerator is minimized at the middle integer or pair of integers. With $m=\lfloor (n+1)/2\rfloor$, the exact finite-size inverse norm is thusFor example it equals $4/3$ at $n=1$ and $8/5$ at $n=2$, tending to $2$ as $n\to \infty$. Stating only the bound two would not evaluate the finite matrix norm requested here.

The general estimate from part 1 and the exact inverse norm from part 2b implyand in particular $\Vert P_x{\Vert }_{L^{\infty }}\le 2$, uniformly in the number of knots. This bound concerns the support-centred sites $x_i=i+3/2$; shifting the sampling sites changes the B-spline collocation matrix and can destroy uniform stability.

Use the central second difference ${\Delta }_t^{2}f(x)=f(x+t)-2f(x)+f(x-t)$ and define the second modulus of smoothness byWe first need its scaling inequality. If $q$ is a positive integer, translation by $h$ gives the telescoping identityThe weights sum to $q^2$. For $t>0$, choose $q=\lceil t/\delta \rceil$ and $h=t/q\le \delta$; thenThe same bound covers $t=0$ trivially.

In the paper's normalization, the Fejér kernel is even and nonnegative, with ${\pi }^{-1}{\int }_{-\pi }^{\pi }{F}_n=1$. Pairing the positive and negative translations expresses the Fejér sum error asUse the scaling bound and $(1+s{)}^2\le 2(1+s^2)$ to obtainFor $|t|\le \pi$, $\sin (|t|/2)\ge |t|/\pi$. Bounding the numerator sine by one givesThe bound at $t=0$ holds by continuity. Choosing $\delta =n^{-1/2}$ proves the Fejér second-modulus approximation bound with an explicit universal constant:Finally, for twice continuously differentiable periodic $f$, two applications of the fundamental theorem of calculus give the second-difference integral formulaThe triangular weight has integral $h^2$, so ${\omega }_2(f,\delta )\le {\delta }^2\Vert f^{\prime \prime }{\Vert }_{\infty }$. Therefore

Use the standard knot-domain convention in which the spline space contains every polynomial of degree at most $k-1$ on $[a,b]$, with completed or clamped endpoint knots. The De Boor–Fix functional extracts a local spline coefficient, and its Hahn-Banach theorem extension is linear on continuous local data with the stated bound. Only that bound and spline reproduction are needed here.

For $x$ in a knot cell $[t_j,t_{j+1}]$, support and Gram bandwidth of B-splines implies that only indicescan contribute, restricted also to $1\le i\le n$. Every corresponding local support $[t_i,t_{i+k}]$ lies insideNonnegativity and subpartition of unity for B-splines therefore giveTaking the supremum over the cell proves the local stability estimate for spline quasi-interpolation:Endpoint limits follow by continuity for $k\ge 2$; the order-one version uses the usual one-sided interval convention.

Let $h={\max }_i|t_{i+1}-t_i|$ and $f\in C^k[a,b]$. Choose any point $y_j$ in the stencil and form its degree-$k-1$ Taylor polynomial $p_j$. The Taylor theorem remainder givesThe polynomial is itself a spline, so $Q{p}_j=p_j$. By linearity and the local stability estimate,Taking the maximum over cells yieldsThe constant depends only on $k$ and the supplied functional bound, not on mesh ratios or the number of knots.

The endpoint convention is essential to the global assertion. The domain can be the basic knot interval, with any needed exterior data extended smoothly, or the full approximation interval can use clamped endpoint knots. If one instead takes a finite, unclamped collection on the entire outer support interval $[t_1,t_{n+k}]$, every order-$k\ge 2$ basis function vanishes at $t_1$, so $Q1(t_1)=0$ and uniform approximation to the constant one there is impossible. This does not affect the local estimate; it explains the usual boundary completion implicit in the global spline approximation statement.

First take $k\ge 2$, so the simple-knot B-splines are continuous, vanish at both support endpoints, and are strictly positive inside their supports. Thus the diagonal condition is $t_i<x_i<t_{i+k}$. We prove both directions of the Schoenberg–Whitney theorem, deriving the weighted zero-count fact needed for sufficiency rather than relying on an ambiguous coefficient-free hint.

For necessity, suppose $N_i(x_i)=0$. If $x_i\le t_i$, then for every row $r\le i$ and column $j\ge i$ we have $x_r\le x_i\le t_i\le t_j$, hence $N_j(x_r)=0$. The first $i$ rows have nonzero entries in at most $i-1$ columns and are linearly dependent. If instead $x_i\ge t_{i+k}$, then for $r\ge i$ and $j\le i$ we have $x_r\ge x_i\ge t_{i+k}\ge t_{j+k}$, so those entries vanish. The last $n-i+1$ rows have nonzero entries in at most $n-i$ columns and are again dependent. In either case the B-spline collocation matrix is singular. Thus invertibility implies the diagonal positivity condition.

We establish two elementary spline facts for the converse. For local linear independence of B-splines, extend the strictly increasing knots in both directions. On a cell $(t_j,t_{j+1})$ the $k$ active basis functions have indices $j-k+1,\dots ,j$. Their knot polynomials are ${\psi }_i(y)={\prod }_{\ell =1}^{k-1}(y-t_{i+\ell })$. The Cox-de Boor recurrence proves Marsden's identityHere is the induction behind that identity. For order one the indicator functions sum to one. On passing from order $k-1$ to $k$, collect the coefficient of each lower-order basis function. With $u=t_i$, $v=t_{i+k-1}$, its extra factor isThus the identity at one order multiplies by $y-x$ at the next.

The $k$ polynomials ${\psi }_i$ are independent: evaluate successively at $y=t_j,t_{j-1},\dots ,t_{j-k+1}$. The first evaluation isolates ${\psi }_j$; after its coefficient has been eliminated the next isolates ${\psi }_{j-1}$, and so on, with nonzero diagonal factors because the knots are distinct. Comparing powers of $y$ in the identity then shows that the active $N_i$ span all polynomials of degree at most $k-1$ on the cell. There are $k$ of them, so they are independent. In particular, a spline vanishes on a whole open cell exactly when all its active coefficients vanish. Padding the finite coefficient vector with zeros makes this fact apply also near the outer knots.

Next let $s={\sum }_{i=p}^q{c}_i{N}_i$ be a real spline on $I=(t_p,t_{q+k})$, with no identically zero knot cell there. The simple-knot B-spline regularity gives $s\in C^{k-2}$, and its derivatives through order $k-2$ vanish at both endpoints because it is supported on the closed interval. Suppose it has $Z$ distinct interior zeros. Its zero set initially has $Z+2$ connected components, counting the endpoints; the zeros are isolated because no cell vanishes identically.

A useful form of Rolle's theorem counts zero components, including any zero intervals that arise after differentiation. Between two successive zero components a real differentiable function is nonzero and has an interior extremum, supplying a zero of its derivative. These derivative-zero components are distinct: a zero interval connecting two such extrema would make the original function constant across an intervening zero and nonzero gap, which is impossible. If its derivative also vanishes at both endpoints, those supply two further distinct components. Thus differentiation increases the zero-component count by at least one. Apply this successively through derivative order $k-2$; every required endpoint derivative vanishes. No derivative in this process can vanish identically: that would make $s$ a global polynomial of degree below $k-1$, with all its endpoint derivatives through that degree zero, forcing $s=0$. The final derivative has at least $Z+k$ zero components.

That final derivative is continuous and piecewise affine on $q-p+k$ knot cells. Each closed affine cell can meet at most one zero component: two different zeros would force the whole cell to vanish, joining them into one component. Every zero component meets a cell, so there are at most $q-p+k$ of them. For $k=2$ this argument applies directly without differentiation. We have proved the compact-support spline zero countThis proof also accommodates zero intervals of the derivatives; counting them as infinitely many distinct zeros would invalidate a naive repeated-Rolle argument.

Now assume $N_i(x_i)>0$ for all $i$ and suppose $A_{x}c=0$ for a nonzero coefficient vector. Since $A_x$ is real, a nonzero real null vector can be chosen. Set $s={\sum }_i{c}_i{N}_i$, so $s(x_i)=0$ for all $i$. Consider one connected component of the union of the open supports of the terms with $c_i\ne 0$. If its first and last indices are $p,q$, the component is exactly $I=(t_p,t_{q+k})$. On this interval $s$ equals $s_0={\sum }_{i=p}^q{c}_i{N}_i$. Each knot cell in $I$ has at least one active nonzero coefficient, so local independence ensures $s_0$ does not vanish on any whole cell.

For every $p\le i\le q$, diagonal positivity gives $t_i<x_i<t_{i+k}$, and this places $x_i$ inside $I$. Thus $s_0$ has the $q-p+1$ distinct zeros $x_p,\dots ,x_q$, contradicting the upper bound $q-p$. There is no nonzero null vector, proving sufficiency. Together the two directions giveFor completeness, order $k=1$ consists of disjoint interval indicators, with the usual left-closed, right-open convention. An invertible ordered collocation requires exactly one site in each interval; ordering makes this equivalent to $N_i(x_i)>0$, and the matrix is then the identity. This handles possible sites at left knots without incorrectly replacing positivity by a strict interior inequality for order one.