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

For a continuous function $f$ on $[0,1]$, its Bernstein polynomial isThe weights are nonnegative and, by the binomial theorem, sum to $(x+1-x{)}^n=1$. Thus $|B_n(f,x)|\le {\sum }_j|f(j/n)|\left(\genfrac{}{}{0ex}{}{n}{j}\right)x^j(1-x{)}^{n-j}\le \Vert f{\Vert }_{\infty }$ at every $x\in [0,1]$, including the endpoints. Taking the supremum norm givesIn particular, $B_n$ is a linear operator of norm one, since it preserves the constant function one.

At a sampling point $j/n$, the given polynomial has value $f_{nm}(j/n)=n^{-m}{j}^{\underline{m}}$, where $j^{\underline{m}}=j(j-1)\cdots (j-m+1)$ is a falling factorial. It vanishes when $j<m$. The binomial coefficient identity $j^{\underline{m}}\left(\genfrac{}{}{0ex}{}{n}{j}\right)=n^{\underline{m}}\left(\genfrac{}{}{0ex}{}{n-m}{j-m}\right)$ therefore givesThe last step is the binomial theorem, and $n^{\underline{m}}/n^m={\prod }_{r=0}^{m-1}(1-r/n)=f_{nm}(1)$. For $m=0$ the empty product is one and the identity is simply $B_{n}1=1$. This is the Bernstein falling-factorial identity.

Fix $m$ and take $n\ge m$. Comparing the two products defining $f_{nm}$ and the monomial $g_m(x)=x^m$, change one factor at a time. Every factor has absolute value at most one on $[0,1]$, so the triangle inequality givesThe contraction proved in (a) and the Bernstein falling-factorial identity from (b) now giveThis proves uniform convergence for each fixed monomial; linearity then gives it for every fixed polynomial. The cases $m=0,1$ have zero error for every $n$.

Use degree-indexed Fourier partial sums and Fejér sums, as in this paper. For a $2\pi$-periodic continuous function, putEquivalently,These are trigonometric polynomials of degree at most $n$. Some treatments index the Fejér sum by the number of terms rather than its degree; the degree convention here is why the formulas below contain ${\sigma }_{2n-1}$ and ${\sigma }_{n-1}$.

For a trigonometric polynomial $t_n(x)={\sum }_{|k|\le n}{c}_k{e}^{ikx}$, orthogonality of the exponential Fourier modes gives $s_j(t_n)=t_n$ whenever $j\ge n$. Every term in the de la Vallée Poussin sum has such an index, soHere and below $n\ge 1$.

Subtracting the two initial averages of Fourier partial sums givesbecause $2n{\sigma }_{2n-1}={\sum }_{j=0}^{2n-1}{s}_j$ and $n{\sigma }_{n-1}={\sum }_{j=0}^{n-1}{s}_j$. The positive normalized Fejér kernel gives the uniform-norm contraction of Fejér summation, namely $\Vert {\sigma }_{m}f{\Vert }_{\infty }\le \Vert f{\Vert }_{\infty }$. The triangle inequality therefore gives

For any trigonometric polynomial $t_n$ of degree at most $n$, reproduction from (a) and the operator norm bound from (b) implyTaking the infimum over $t_n$ givesThis is the polynomial reproduction error bound with $\Vert v_n\Vert \le 3$; attaining the best uniform approximation is not needed for this inequality.

Let $p\in A$, $r=f-p$, $E=\Vert r{\Vert }_{\infty }$ and $M=\{x\in [0,1]:|r(x)|=E\}$. The Kolmogorov criterion for uniform approximation saysIf $E=0$, $p=f$ is already best and the criterion holds. Suppose $E>0$. If $q=p+h$ were strictly better, then $|r(x)-h(x)|<|r(x)|=E$ on $M$, which forces $r(x)h(x)>0$ there. Conversely, if a direction $h$ has $rh>0$ everywhere on $M$, compactness gives a positive lower bound on this product. On a sufficiently small neighborhood of $M$, $r$ and $h$ therefore have matching signs with $|h|$ bounded away from zero and $|r|$ bounded away from zero. On its compact complement, $|r|\le E-\delta$ for some $\delta >0$. Choose $\epsilon >0$ so small that $\epsilon \Vert h{\Vert }_{\infty }<\delta$ and that subtracting $\epsilon h$ does not cross zero on that neighborhood. Then $\Vert r-\epsilon h{\Vert }_{\infty }<E$, so $p$ is not a best uniform approximation. This proves both directions.

The Chebyshev alternation theorem states that $p\in {\mathcal{P}}_n$ is a best uniform approximation to real $f$ precisely when there are $n+2$ increasingly ordered points $x_0<\cdots <x_{n+1}$ withFor sufficiency, an improving polynomial direction $h$ would have to share these alternating signs, by the Kolmogorov criterion for uniform approximation. The intermediate value theorem would give at least $n+1$ distinct roots of a polynomial between consecutive points. A nonzero polynomial of degree at most $n$ cannot do that. If $E=0$, no improvement is possible anyway.

For necessity, suppose $E>0$ and the active set $M$ has no alternating sequence of length $n+2$. Its positive-error and negative-error subsets are disjoint compact sets, hence separated by a positive distance. Reading them from left to right splits $M$ into finitely many consecutive sign blocks. If there are $L$ blocks, choosing one point per block gives an alternating sequence, so $L\le n+1$. Choose $z_j$ in the gap between each consecutive pair of blocks. The polynomial $h(x)=C{\prod }_{j=1}^{L-1}(x-z_j)$ has degree at most $n$; choose the sign of $C$ to match the error on the first block. Its sign then matches the error on every block, and it is nonzero throughout $M$. Thus $rh>0$ on $M$, contradicting the Kolmogorov criterion for uniform approximation. There must therefore be $n+2$ alternating extrema.

Choose a best uniform approximation $p_n\in {\mathcal{P}}_n$. It exists because this vector subspace is a finite-dimensional vector space and a minimizing sequence $q_j$ is bounded: $\Vert q_j{\Vert }_{\infty }\le \Vert f{\Vert }_{\infty }+\Vert f-q_j{\Vert }_{\infty }$. Finite-dimensional equivalence of norms then supplies a convergent subsequence of coefficients. If $E_n(f)>0$, the Chebyshev alternation theorem gives $n+2$ alternating error extrema. The intermediate value theorem supplies a zero $x_{n,k}$ of $f-p_n$ in each of the $n+1$ intervening open intervals. These interpolation nodes are distinct, and uniqueness of polynomial interpolation givesThe convergence follows from the Weierstrass approximation theorem. If $E_n(f)=0$, choose any $n+1$ distinct nodes: the polynomial interpolant is still $f=p_n$. This constructs interpolation nodes from best uniform approximation; the nodes depend on $f$, and no universal node system for all continuous functions is asserted.

Periodicity and the Hölder condition give $|f(x-t)-f(x)|\le M|t{|}^{\alpha }$ for $|t|\le \pi$. The positive normalized Fejér kernel therefore yieldsThe exponential-sum representation of the kernel bounds $F_{n-1}(t)\le n/2$. Also $\sin (t/2)\ge t/\pi$ for $0\le t\le \pi$, so $F_{n-1}(t)\le {\pi }^2/(2n{t}^2)$. Splitting at $1/n$ and using $0<\alpha <1$ givesHence the Hölder error bound for Fejér summation isThe constant depends on the Hölder exponent and $M$, but not on $n$ or $f$ beyond its Hölder seminorm bound.

The Markov interlacing lemma says that differentiation preserves interlacing roots of polynomials. More explicitly, if two degree-$d$ real polynomials have ordered real roots satisfying $a_1\le b_1\le a_2\le \cdots \le a_d\le b_d$, their $k$th derivatives have ordered roots $a_j^{(k)},b_j^{(k)}$ satisfyingThe analogous alternating order is preserved for polynomials of consecutive degrees. Common roots are allowed through weak inequalities; strictly interlacing simple roots give strict inequalities. When a derivative is constant, its root list is empty.

Order the interpolation nodes as $t_0<\cdots <t_n$, as required by their alternating nodal data. Write $w(x)={\prod }_{j=0}^n(x-t_j)$ and ${\ell }_i(x)=w(x)/[(x-t_i)w^{\prime }(t_i)]$ for the Lagrange cardinal polynomials. Differentiating Lagrange interpolation givesThe upper bound is the triangle inequality; equality follows by choosing each independent nodal value to be the sign of its weight. Thus this is the nodal derivative norm from Lagrange cardinal polynomials.

To identify the maximizing signs, put $P_i=w/(x-t_i)$, a monic polynomial of degree $n$. Since $\mathrm{sign}{w}^{\prime }(t_i)=(-1{)}^{n-i}$,For $0\le k<n$, let ${\xi }_{i,j}$ be the ordered roots of $P_i^{(k)}$, $1\le j\le n-k$. The roots of $P_i$ decrease componentwise as $i$ increases: deleting a later node replaces one retained node by an earlier one. The monotonicity of polynomial critical points in their roots, iterated $k$ times, therefore gives ${\xi }_{n,j}\le \cdots \le {\xi }_{0,j}$. Moreover, $P_n$ and $P_0$ weakly interlace, so the Markov interlacing lemma gives ${\xi }_{0,j}\le {\xi }_{n,j+1}$. Together,These root bands have disjoint interiors. At a fixed $x$, all but at most one band lie wholly on one side of $x$. In the possible remaining band, ${\xi }_{i,j}$ moves monotonically as $i$ increases. Since the leading coefficients of all $P_i^{(k)}$ are positive, the sequence $P_i^{(k)}(x)$ has at most one sign change after zero entries are ignored. The same holds for $(-1{)}^i{\ell }_i^{(k)}(x)$. If $k=n$, every $P_i^{(n)}=n!>0$, so the conclusion also holds.

The maximizing nodal signs can consequently be chosen as $\pm (-1{)}^i$ throughout, or as $\pm (-1{)}^i$ before one index $s$ and $\mp (-1{)}^i$ from that index onward. Zero weights can be assigned either sign to complete such a pattern. These are precisely the nodal values of $\pm p^{\ast }$ or $\pm q_s$, provingThe argument works for all real $x$, hence in particular for $[-1,1]$. For $k>n$ every derivative vanishes and the result is immediate.

Assume the spline knot sequence is ordered and its relevant support spans satisfy $t_{i+k}>t_i$. For distinct knots, the divided difference is a finite linear combination of evaluations, so it commutes with integration. With $u\in [a,b]$,Taking the order-$k$ divided difference in $u$ givesIndeed, the order-$k$ divided difference of a degree-$k$ polynomial is its leading coefficient, here $1/k$. This proves the unit-integral normalization of a B-spline. Admissible repeated knots follow by coalescing knots, with the usual one-sided endpoint conventions.

Write $N_{i,k}$ for the order-$k$ B-spline. At order one, $N_{i,1}=1_{[t_i,t_{i+1})}$, and the finite sum is one on its basic knot interval. For larger order, the Cox-de Boor recurrence iswith a zero-denominator term defined as zero. Sum over $i=1,\dots ,n$. For each interior lower-order index $j=2,\dots ,n$, the combined coefficient isThe two unmatched lower-order terms have supports $[t_1,t_k]$ and $[t_{n+1},t_{n+k}]$, respectively, and vanish on the open basic interval $(t_k,t_{n+1})$. Induction therefore givesFor simple knots and $k\ge 2$, continuity extends the identity to both endpoints. In the order-one case and at admissible repeated endpoint knots, use the one-sided value from the basic interval. Extending the knot sequence in both directions also proves the subpartition of unity for B-splines, $0\le {\sum }_i{N}_i\le 1$ everywhere: the finite sum is a subset of a nonnegative full partition. That weaker global inequality will be needed in Question 7(a).

The orthogonal projection condition is $(f-s^{\ast },N_i)=0$ for all $i$. Since $M_i=k{N}_i/(t_{i+k}-t_i)$, it is equivalentlyThe mixed-normalization spline Gram matrix is invertible: $G=D^{-1}H$, where $D_{ii}=(t_{i+k}-t_i)/k>0$ and $H_{ij}=(N_i,N_j)$ is the positive-definite ordinary Gram matrix of the basis. Nonnegativity and the unit-integral normalization of a B-spline give $|b_i|\le \Vert f{\Vert }_{\infty }{\int }_0^1{M}_i=\Vert f{\Vert }_{\infty }$. The subpartition of unity for B-splines gives, on all of $[0,1]$,ConsequentlysoThis is the maximum-norm bound for spline projection. Using a subpartition matters when the basic knot interval is a proper subinterval of $[0,1]$. As in the paper's assertion that the image lies in $C[0,1]$, the spline space here must consist of continuous functions; order-one step splines or full-multiplicity interior knots do not have that property.

For distinct ordered knots, put $h_i=t_{i+1}-t_i>0$. The linear B-spline $N_i$ is the triangular hat supported on $[t_i,t_{i+2}]$, equal to $(t-t_i)/h_i$ on its rising segment and $(t_{i+2}-t)/h_{i+1}$ on its falling segment. Its integral-normalized partner is $M_i=2N_i/(h_i+h_{i+1})$. ThusFor example, the left overlap is ${\int }_0^{h_i}(u/h_i)(1-u/h_i)du=h_i/6$. Nonadjacent hats have disjoint interiors of their supports, so their inner product is zero. The linear-spline mixed Gram matrix therefore has rowRetain only column indices in $1,\dots ,n$: the first or last row has no neighbor outside this range. Admissible repeated endpoint knots are obtained by a limit with zero spacings, provided $h_i+h_{i+1}>0$; a degenerate hat with zero support width is not a basis element.

The entries in (b) satisfyThus $G$ has strict diagonal dominance with margin at least $1/3$. To prove the inverse infinity-norm bound from diagonal dominance directly, choose $i$ with $|a_i|=\Vert a{\Vert }_{{\ell }^{\infty }}$. The reverse triangle inequality givesThis also proves that the kernel is zero and hence that $G$ is invertible. Substituting $a=G^{-1}b$ and taking the operator norm givesCombined with (a), it yields $\Vert P_S{\Vert }_{\infty }\le 3$ for linear splines, independently of the knot spacings. The diagonal-dominance argument already proves the required estimate.