Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 75 (Approximation Theory)

Assume $a<b$. A Chebyshev system of dimension $n+1$ is a family of real continuous functions $u_0,\dots ,u_n$ for which every linear combination $u={\sum }_{j=0}^n{c}_j{u}_j$ with coefficients not all zero has at most $n$ distinct zeros in the interval. In particular the functions are linearly independent: an identically zero nontrivial combination would violate that bound. Multiplicities are not counted in this definition.

For distinct points $x_0,\dots ,x_n$, form the evaluation matrix $A=(u_j(x_i){)}_{i,j=0}^n$. If its determinant vanished, a nonzero vector $c$ would satisfy $Ac=0$. Its associated combination would vanish at all $n+1$ points, contradicting the Chebyshev system property. Conversely, if the property failed, some nonzero coefficient vector would give a combination vanishing at $n+1$ distinct points. At those points $Ac=0$, so the evaluation matrix would be singular. We have proved the determinant criterion for a Chebyshev system:This is also the existence-and-uniqueness condition for interpolation from the span of the functions: any prescribed $n+1$ data values give a uniquely solvable linear system.

The exponents are real, as required for this family of real continuous functions. We prove the exponential Chebyshev system property by induction on the number of functions. A single nonzero multiple of an exponential function has no zero, so the base case holds.

Suppose the result holds for $n$ distinct real exponents, and consider a nontrivial combination $F(x)={\sum }_{j=0}^n{c}_j{e}^{{\lambda }_{j}x}$. If it had $n+1$ distinct zeros, so wouldsince the prefactor is everywhere positive. Applying Rolle's theorem between consecutive zeros gives at least $n$ distinct zeros ofThe $n$ exponents in this derivative are distinct. By induction, a nontrivial combination of them has at most $n-1$ zeros. Therefore every coefficient $c_j({\lambda }_j-{\lambda }_0)$ must be zero. Distinctness gives $c_j=0$ for $j\ge 1$. Then $g=c_0$ has a zero only if $c_0=0$, contradicting the original nontriviality. Consequently $F$ has at most $n$ zeros, and

Let $d$ be the dimension of a proposed real Chebyshev system on the circle, and regard its functions as continuous $2\pi$-periodic functions on the real line. Choose lifted points ${\theta }_0<{\theta }_1<\cdots <{\theta }_{d-1}<{\theta }_0+2\pi$ and set ${\theta }_d={\theta }_0+2\pi$. Move the points byFor every $s$ the points remain distinct on the circle. Indeed, each consecutive gap is a convex combination of positive gaps; the closing gap is also a convex combination of the original closing gap and ${\theta }_1-{\theta }_0$. The evaluation determinantis therefore nonzero for every $s$ by the determinant criterion for a Chebyshev system. It is continuous, so the intermediate value theorem forbids a sign change. At $s=1$, however, periodicity makes its rows the cyclic permutation of the initial rows, giving $D(1)=(-1{)}^{d-1}D(0)$. For even $d$ this reverses the sign, a contradiction. Hence every such periodic Chebyshev system has odd dimension; none has even dimension. This determinant argument avoids assuming differentiability or simple zeros of the functions.

The Korovkin theorem states that if positive linear operators on continuous functions $L_n:C[0,1]\to C[0,1]$ satisfythen $\Vert L_{n}f-f{\Vert }_{\infty }\to 0$ for every real continuous function $f$.

Let $r=k-1\ge 2$ and $h_n=|{\Delta }_n|$. For the B-splines in this question, $N_{i,n}\ge 0$ and their sum is one on the basic interval. Thus the Schoenberg spline operator $V_n$ is linear and positive. To verify the three test functions, suppress the index $n$ and write the Marsden identity with ${\omega }_i(x)={\prod }_{j=1}^r(x-t_{i+j})$. Comparing the coefficients of $x^r,x^{r-1},x^{r-2}$ gives the monomial B-spline coefficientswhereThe first coefficient is the partition of unity; the second is the Greville abscissa. Every internal knot and the sample point ${\tau }_i$ lie in $[t_i,t_{i+k}]$, of width at most $k{h}_n$. Consequently $|{\tau }_i-{\xi }_i|\le k{h}_n$. Since all these numbers lie in $[0,1]$, for any two internal knots $u,v$ we also haveAveraging gives $|{\tau }_i^2-q_i|\le 2k{h}_n$. Nonnegative weights of sum one now yieldHere the spline order $k$ is fixed, so all three errors tend to zero. The Korovkin theorem therefore provesNo special selection such as the Greville abscissae is required for the sample points. In fact the local-support error bound for a Schoenberg spline operator also gives $\Vert V_{n}f-f{\Vert }_{\infty }\le \omega (f,k{h}_n)$. Under the usual continuous-spline convention the operators have the codomain required by the stated theorem. If the permissive knot notation is taken to allow full interior multiplicities and hence discontinuous splines, the same conclusion in the uniform norm still follows from this direct bound, although each approximant need not then be continuous.

For a real continuous function on $[-1,1]$, the Chebyshev alternation theorem gives a unique best uniform approximation $p_n^{\ast }$ from the space of polynomials of degree at most $n$. If $f$ is not already in that space, a candidate $p$ is best if and only if there exist ordered points $x_0<\cdots <x_{n+1}$ and a sign $\sigma \in \{1,-1\}$ withThus a nonzero best error has at least $n+2$ alternating extrema of equal magnitude. If $f$ is already a polynomial of degree at most $n$, the unique best approximant is $f$ itself with zero error.

Existence does not require assuming that the infimum is attained: a minimizing sequence has uniformly bounded polynomial norms, and evaluation at $n+1$ fixed distinct nodes bounds its coefficients through an invertible interpolation matrix. A convergent coefficient subsequence then attains the infimum. The alternation criterion characterizes that minimum and gives uniqueness. In the following parts, $n\ge 1$ whenever $E_{n-1}$ occurs.

A nontrivial example is $f_n=T_{n+1}$, the Chebyshev polynomial characterized by $T_{n+1}(\cos \theta )=\cos ((n+1)\theta )$. Its supremum norm is one. At the $n+2$ points $\cos (j\pi /(n+1))$, $0\le j\le n+1$, its values alternate between $1$ and $-1$; reversing their order gives increasing nodes with the same alternation.

The zero polynomial therefore satisfies the Chebyshev alternation theorem for degree at most $n$, so $E_n(f_n)=1$. Since the smaller polynomial space is contained in the larger one, $E_{n-1}(f_n)\ge 1$; the zero polynomial is feasible in the smaller space as well, giving the reverse inequality. HenceA constant function would also give equality with both errors zero, but this example shows that equality can occur at a positive approximation error.

Let $p$ be the best uniform approximation to the exponential function from the degree-at-most-$n-1$ polynomial space. Suppose that $E_{n-1}(e^x)=E_n(e^x)$. Then the same $p$ is best in the larger space. Its error $g(x)=e^x-p(x)$ is nonzero, since the exponential is not a polynomial. The Chebyshev alternation theorem supplies $n+2$ ordered points where $g$ has alternating signs. By the intermediate value theorem, $g$ has at least one zero in each of the $n+1$ intervening intervals, hence at least $n+1$ distinct zeros.

Applying Rolle's theorem successively $n$ times forces a zero of $g^{(n)}$. But $\mathrm{deg}p\le n-1$, soeverywhere. This is a contradiction. Together with the automatic non-increase of best errors, it provesThe argument is an instance of strict polynomial error decrease from nonvanishing derivatives.

For each $n$, choose the best uniform approximation $p_n^{\ast }$. If its error is nonzero, take its $n+2$ alternating extrema. The intermediate value theorem supplies a point $y_j$ strictly between the $j$th and $(j+1)$st extrema such that $f(y_j)=p_n^{\ast }(y_j)$, for $0\le j\le n$. These $n+1$ points are distinct. The polynomial interpolation problem at them has a unique solution of degree at most $n$, so its solution is exactly $p_n^{\ast }$. This constructs the interpolation nodes from best uniform approximation.

If $E_n(f)=0$, then $f$ itself belongs to the polynomial space, and any $n+1$ distinct nodes give the same conclusion. In either case, take $x_{n,j}=y_j$ or the arbitrary nodes just described. ThenThe Weierstrass approximation theorem gives $E_n(f)\to 0$; alternatively, the bound derived in part 4(b), combined with uniform continuity, gives this convergence directly. ThereforeThe nodes may depend on $f$ and on $n$. The conclusion does not assert a universal sequence of interpolation grids working for every continuous target.

For a function on an interval, the modulus of continuity is $\omega (f,t)={\sup }_{|x-y|\le t}|f(x)-f(y)|$, with the pair restricted to that interval. For a periodic function the equivalent definition is ${\sup }_{\theta ,|h|\le t}|g(\theta +h)-g(\theta )|$. The mean value theorem and $|\sin \theta |\le 1$ giveBoth cosine values lie in $[-1,1]$. Hence for $|h|\le t$,Taking the supremum provesIf the periodic modulus of continuity is defined using circular distance instead, choose lifts at that shortest distance and apply the same argument. The cosine substitution for polynomial approximation therefore does not enlarge this modulus.

The first Jackson theorem for periodic approximation states that an absolute constant $C_J$ exists such that, for every continuous $2\pi$-periodic function $g$ and integer $n\ge 1$, there is a trigonometric polynomial $q_n$ of degree at most $n$ satisfyingApply it to the continuous periodic function $g(\theta )=f(\cos \theta )$, which is even. Replace the approximant by its even partSince $g(-\theta )=g(\theta )$, the triangle inequality gives $\Vert g-q_n^{\mathrm{ev}}{\Vert }_{\infty }\le \Vert g-q_n{\Vert }_{\infty }$. This symmetrization cancels all sine terms, so $q_n^{\mathrm{ev}}={\sum }_{j=0}^n{\alpha }_j\cos (j\theta )$. The Chebyshev polynomials satisfy $T_j(\cos \theta )=\cos (j\theta )$ and have degree $j$; the latter follows inductively from $T_0=1$, $T_1=x$ and $T_{j+1}=2x{T}_j-T_{j-1}$. Thereforeis an algebraic polynomial of degree at most $n$, and $p_n(\cos \theta )=q_n^{\mathrm{ev}}(\theta )$. Because cosine maps onto $[-1,1]$, the supremum norms agree exactly:Finally, the definition of the best error, periodic Jackson approximation, and part (a) give the successive boundsThusNeither the constant nor the choice of approximation space depends on $f$. The cosine substitution for polynomial approximation and even symmetrization are what preserve the required degree bound.

Set $r=k-1$, with $k\ge 2$ for the final linear-reproduction assertion, and use the normalized knot polynomial ${\psi }_i={\omega }_i/r!$. Differentiate the Marsden identity $r-j$ times with respect to the auxiliary variable $x$, for $0\le j\le r$. This givesThe Taylor polynomial expansion of an arbitrary polynomial $p$ of degree at most $r$ about $x$ is exact:Substitute the differentiated identity into each term and collect the B-spline coefficients. The result isThis is the normalized Marsden dual functional. There is no extra factorial outside the sum, because it is already included in ${\psi }_i$.

To prove independence of $x$ directly, differentiate the finite sum. The contribution from differentiating ${\psi }_i$ in term $j$ cancels the contribution from differentiating $p$ in term $j-1$. Explicitly,The two uncancelled endpoint terms vanish because $p^{(r+1)}={\psi }_i^{(r+1)}=0$. Thus the coefficient functional is constant in the auxiliary variable, as required.

The leading two terms of the knot polynomial giveFor a linear polynomial $p(t)=A+Bt$, only $j=0,1$ survive, whenceThe coefficient points $t_i^{\ast }$ are the Greville abscissae. Inserting these coefficients proves exact linear reproduction:All identities hold on the basic knot interval $[t_k,t_{n+1}]$, including the endpoints with the standard continuous endpoint convention. Repeated knots cause no difficulty in these polynomial differentiations.

Write $r=x-u^{\ast }$. If $u^{\ast }$ is a best approximation, then for every $v\in {\mathcal{U}}_n$ and real $t$, the competitor $u^{\ast }+tv$ satisfiesThe linear coefficient must be zero, since otherwise choosing sufficiently small $t$ of the appropriate sign makes this expression negative. Hence $\mathrm{Re}(r,v)=0$. In a real inner product space this is the desired orthogonality; in a complex inner product space, apply the same argument to $iv$ to show that the imaginary part also vanishes. Thus $(r,v)=0$ for all $v\in {\mathcal{U}}_n$.

Conversely, suppose this orthogonality holds. Every competitor $u\in {\mathcal{U}}_n$ has $u-u^{\ast }\in {\mathcal{U}}_n$. The Pythagorean identity then givesEquality forces $u=u^{\ast }$. We have proved the characterization, as well as uniqueness:This is the orthogonal projection onto a finite-dimensional subspace. Completeness of the ambient space is not needed. Existence follows, for example, by solving the invertible Gram matrix system in a basis of the finite-dimensional linear subspace.

The dual vectors are the Riesz dual basis in an inner product space, and lie in ${\mathcal{U}}_n$ itself. Take the convention that the inner product is conjugate-linear in its first argument; in a real space the conjugations can simply be omitted. Since the $u_j$ form a basis, their Gram matrix $G$ is positive definite and invertible. Let $B=G^{-1}$ and putThe proposed vectors satisfyThey therefore give the unique dual family within ${\mathcal{U}}_n$. Their own Gram matrix isThe inverse of a Hermitian positive-definite matrix is Hermitian, so $B^{\ast }=B$. Using $GB=I$ gives $B^{\ast }GB=B$. ConsequentlyFor a real space this is the familiar identity $B^{T}GB=B$. If the opposite complex inner-product convention is adopted, conjugate the coefficients in the dual-vector formula; the stated identity remains the same. Requiring the dual vectors to lie in ${\mathcal{U}}_n$ is essential: arbitrary additions perpendicular to ${\mathcal{U}}_n$ preserve the pairings with $u_i$ but alter the Gram matrix of the dual vectors.

Use the standard nonnegative partition-normalized B-splines $N_j$; their sum is at most one, and is exactly one for the complete clamped basis on $[0,1]$. The printed question introduces $M_i$ only in its last matrix formula without defining it. The intended normalization is the unit-integral normalization of a B-spline:For supports wholly inside the interval, $c_i=(t_{i+k}-t_i)/k$. The positivity and partition convention, sometimes called $L_{\infty }$ normalization, should not be confused with individually rescaling every spline to have maximum exactly one.

The characterization in part 1(a) gives the normal equations for the orthogonal projection:Dividing each equation by $c_i$ yieldsThis is the mixed-normalization spline Gram matrix. It need not be symmetric, but $G=D^{-1}H$ with $D=\mathrm{diag}(c_i)$ and $H_{ij}=(N_i,N_j{)}_{L_2}$. The ordinary Gram matrix $H$ is positive definite because the splines are linearly independent, so $G$ is invertible and $a=G^{-1}d$.

Since each $M_i$ is nonnegative and has integral one,The induced matrix operator norm is the maximum absolute row sum, soFinally, nonnegativity and the subpartition of unity for B-splines giveTaking the supremum over $t$ and then over $\Vert f{\Vert }_{\infty }\le 1$ proves the maximum-norm bound for spline projection:The formulas also establish linearity and boundedness of the projection on continuous inputs. Its range is exactly the finite-dimensional spline space $\mathcal{S}$, since it fixes every spline in that space. Thus, when the splines are continuous, it is an operator $C[0,1]\to C[0,1]$ with range $\mathcal{S}$; it is not onto all of $C[0,1]$ as the printed wording says. For example, $e^t$ cannot belong to a fixed finite-degree spline space because it is not a polynomial on any nonempty knot interval. The missing $M_i$ normalization and this range correction are needed for a precise reading of the result.