Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 68 (Approximation Theory)

Use the uniform norm and the central second difference ${\delta }_h^{2}f(x)=f(x+h)-2f(x)+f(x-h)$, withThe Jackson kernel is even, nonnegative and normalized. Pairing $t$ and $-t$ in its integral therefore givesWe will estimate this expression directly in terms of the second modulus of smoothness.

First prove the modulus scaling bound. With translations $T_{h}f(x)=f(x+h)$, the forward difference obeysEach function translation preserves the uniform norm, so $\Vert {\delta }_{mh}^{2}f{\Vert }_{\infty }\le m^2\Vert {\delta }_h^{2}f{\Vert }_{\infty }$. For $t\ne 0$, take $m=\lceil n|t|\rceil$ and $h=t/m$. Then $|h|\le 1/n$ andThe same bound is immediate at $t=0$.

For $|t|\le \pi$, $|\sin (t/2)|\ge |t|/\pi$. Also $|\sin (nt/2)/\sin (t/2)|\le n$, as follows by expressing the ratio, up to a unit-modulus factor, as a sum of $n$ complex exponentials. The given normalizing coefficient is at most a constant times $n^{-3}$. Consequentlyand these two estimates combine intoIndeed splitting at $n|t|=1$ shows this with an absolute change of constant. HenceSubstitute the modulus bound in the symmetrized convolution and take the supremum over $x$ to obtain the Jackson operator estimateThe constant is independent of $f$ and the positive integer $n$; the kernel's quartic decay is what makes the weighted second-difference integral uniformly bounded.

Put $x=\cos \theta$. The trigonometric identitygivesStarting with $T_0=1$ and $T_1=x$, this recurrence proves inductively that each Chebyshev polynomial is a polynomial. For $n\ge 1$, the highest-degree term in $2x{T}_n$ cannot cancel against $T_{n-1}$, so the degree increases by one and its leading coefficient doubles. ThusThe constant polynomial $T_0$ has leading coefficient one.

For $n\ge 1$, the points $x_j=\cos (j\pi /n)$, $j=0,\dots ,n$, give $T_n(x_j)=(-1{)}^j$. They are all the points where $|T_n|=1$, since $|\cos (n\theta )|=1$ exactly when $n\theta$ is an integer multiple of $\pi$. Therefore there are $n+1$ equioscillation points, including the two endpoints. Reversing their order makes an increasing alternating sequence. For $n=0$ the polynomial is constant: every point has unit value, but an alternating sequence has at most one point.

Now take $n\ge 1$ and $c=2^{1-n}$. Since $c{T}_n$ is monic, $p_0(x)=x^n-c{T}_n(x)$ has degree at most $n-1$, and $\Vert x^n-p_0{\Vert }_{\infty }=c$. This proves the upper bound for the best error.

For the lower bound, suppose a polynomial $p$ of degree at most $n-1$ had $\Vert x^n-p{\Vert }_{\infty }<c$. At each of the $n+1$ ordered extrema, $h=p-p_0$ must have the same strictly nonzero sign as $T_n$: if $c{T}_n=c$, then $|c-h|<c$ gives $h>0$, and if $c{T}_n=-c$, then $|-c-h|<c$ gives $h<0$. Between every consecutive pair, the intermediate value theorem gives a zero of $h$. These are $n$ distinct zeros, impossible for a nonzero polynomial of degree at most $n-1$; $h=0$ is incompatible with the strict error improvement. This first-principles sign argument proves the monic Chebyshev extremal polynomial bound without using the alternation theorem:The displayed $p_0$ supplies an actual best approximating polynomial.

Work with real-valued functions and put $\mathrm{sign}(0)=0$. Let $r=f-p_{\ast }$, and write an arbitrary competitor as $p=p_{\ast }+v$ with $v\in U$. Pointwise,For $r\ne 0$ this is $|r-v|\ge \mathrm{sign}(r)(r-v)$; for $r=0$ the right side is zero. Integrating and using the assumed orthogonality givesThus $p_{\ast }$ is a best $L^1$ approximation from $U$. This sign criterion for best L1 approximation is sufficient without any finite-dimensionality or uniqueness assumption; possible residual zeros do not invalidate the inequality.

Here $n$ is a positive integer and $m$ is an integer index of a Fourier coefficient. Split a period into $n$ intervals and set $y=nx-2\pi j$ on the $j$th interval. Periodicity and integrability giveFor $0<|m|<n$, $\zeta =e^{2\pi im/n}$ is a root of unity different from one and satisfies ${\zeta }^n=1$, so ${\sum }_{j=0}^{n-1}{\zeta }^j=(1-{\zeta }^n)/(1-\zeta )=0$. ThereforeFor $m=0$ the same substitution gives ${\int }_{\mathbb{T}}f(nx)dx={\int }_{\mathbb{T}}f(x)dx$. If the mean of $f$ is zero, this last mode vanishes as well. Since the linear span of the exponentials with $|m|\le n-1$ is the space of trigonometric polynomials of degree at most $n-1$, every pairing with that space is zero. This is the periodic dilation annihilates low Fourier modes property. The integer-index assumption is essential; the stated Fourier orthogonality would generally be false for noninteger $m$.

As printed in the original PDF, this claim is false for $n\ge 2$. The displayed frequency is one, so the function already belongs to the space of trigonometric polynomials of degree at most $n-1$. Its best approximation is then the function itself, with zero error; for example, $\alpha =1,\beta =0$ gives a zero-approximant error ${\int }_0^{2\pi }|\cos x|dx=4$ instead. For $n=1$, zero is indeed the best constant approximation. Thus the literal answer is

The natural intended version has frequency $n$. Set $g(y)=\alpha \cos y+\beta \sin y$ and $f_n(x)=g(nx)$. The sign function $h(y)=\mathrm{sign}g(y)$ is integrable and satisfies $h(y+\pi )=-h(y)$, so its mean is zero. Part (b) makes $h(nx)=\mathrm{sign}{f}_n(x)$ orthogonal to every degree-at-most-$n-1$ trigonometric polynomial. Part (a), with $p_{\ast }=0$, now provesThe error is $4\sqrt{{\alpha }^2+{\beta }^2}$ for the unnormalized integral over a period.

The best approximant is unique. If the amplitude is nonzero and another continuous trigonometric polynomial $p$ has the same optimal error, equality in part (a)'s pointwise inequality holds almost everywhere. Near each zero of $f_n$, the function changes sign; if $p$ did not vanish at that zero, continuity would force an interval on one side where $f_n-p$ has the wrong sign, making the integral inequality strict. Thus $p$ vanishes at all $2n$ distinct zeros of $f_n$. A nonzero trigonometric polynomial of degree at most $n-1$ has at most $2n-2$ zeros in one period, since multiplication by $e^{i(n-1)x}$ turns it into a polynomial in $e^{ix}$ of degree at most $2n-2$. Hence $p=0$. Zero amplitude is immediate. The same reasoning proves the literal frequency-one assertion when $n=1$, while retaining the counterexample for larger $n$.

For fixed $t$, put $g_t(u)=(u-t{)}_{+}^{k-1}$, a truncated power function. Begin with distinct increasing knots. The two interpolation polynomials ${\ell }_i(\cdot ,t)$ and ${\ell }_{i+1}(\cdot ,t)$ agree at their $k-1$ shared knots. Their difference has degree at most $k-1$, soFor $k=1$ the empty product is one and the same assertion holds for constant interpolants. The leading coefficient of a degree-at-most-$k-1$ interpolant on $k$ nodes is its order-$k-1$ divided difference, by the Newton interpolation polynomial. ThereforeThis proves the Lee interpolation identityThe identity holds for every real $x,t$, with the usual convention for the order-zero truncated power. Admissible repeated knots are handled by the corresponding confluent divided differences and consistent one-sided limits at breakpoints; taking these limits preserves the Lee interpolation identity.

Sum over $i$ to telescope:If $t_k<t<t_{n+1}$, the first $k$ knot values of $g_t$ are zero, so ${\ell }_1=0$. At the last $k$ knots $t_{n+1},\dots ,t_{n+k}$, the function $g_t$ agrees with the polynomial $(u-t{)}^{k-1}$, so uniqueness of polynomial interpolation gives ${\ell }_{n+1}(x,t)=(x-t{)}^{k-1}$. Thus the Marsden identity is

Let $d=k-1$ and let $e_m$ denote the elementary symmetric polynomial of degree $m$ in the $d$ interior knots $t_{i+1},\dots ,t_{i+d}$, with $e_0=1$. Expand the two sides of the Marsden identity as polynomials in $x$:andComparing the coefficient of $x^{d-m}$ and cancelling the common sign gives the monomial B-spline coefficientsEquivalently,In particular $a_i^{(0)}=1$, giving partition of unity on the interior interval. For $k\ge 2$, $a_i^{(1)}=(t_{i+1}+\cdots +t_{i+k-1})/(k-1)$, and the highest-degree coefficient is the product of those interior knots. The formulas also cover $k=1,m=0$ through empty products.

There are $n$ basis splines for the stated $n+k$ knots; the upper limit $k$ in the printed basis list is an indexing slip. LetThe strictly increasing sites and $t_i<x_i^{\ast }<t_{i+k}$ give invertibility by the Schoenberg–Whitney theorem. The needed additional matrix property is total nonnegativity of B-spline collocation matrices: every ordered minor of $A$ is nonnegative.

Here is a structural justification of that sign property. Knot insertion refines spline coefficients by rules of the form $b_j={\alpha }_j{a}_j+(1-{\alpha }_j)a_{j-1}$, $0\le {\alpha }_j\le 1$, with the usual unchanged coefficients before the insertion and shifted coefficients after it. Each coefficient map is a nonnegative rectangular bidiagonal matrix; all its ordered minors are nonnegative, as its nonzero terms preserve row/column order. Products preserve this property by the Cauchy–Binet formula. Insert each ordered sampling site until it has full knot multiplicity. Evaluation at such a break is one of the refined coefficients, with a consistent one-sided convention. Consequently the B-spline collocation matrix is an ordered row submatrix of the product of refinement matrices, proving its nonnegative minors. This also applies to repeated admissible original knots.

Since $A$ is invertible and totally nonnegative, $\det A>0$. The adjugate identity gives the checkerboard inverse of a totally nonnegative matrix:Now for any spline $s={\sum }_j{a}_j{N}_j$, its sampled-value vector is $y=Aa$. Hence the coefficient linear functional in the dual basis is exactlyIn particular ${\mu }_i(N_{\ell })={\delta }_{i\ell }$, verifying the hinted formula rather than assuming it. The operator norm of this linear functional is taken for the uniform norm on the spline's interval, containing all sampling sites. Evaluation at a sampling site has norm at most one, soFor the given unit-norm alternating spline, $s_{\ast }(x_j^{\ast })=(-1{)}^j$, and the checkerboard signs make all terms in a fixed inverse row align:Since $\Vert s_{\ast }{\Vert }_{\infty }=1$, this supplies the reverse operator norm inequality and proves the Chebyshev spline coefficient and dual norm equalityThis spline attains the operator norm of each coefficient linear functional.

Use the order of the three Bernstein basis functions given in this part. Endpoint evaluation givesso both endpoint coefficients have absolute value at most one. At the midpoint,The triangle inequality therefore gives the quadratic Bernstein coefficient boundAll three bounds are sharp. Indeed $p(x)=8x^2-8x+1=T_2(2x-1)$ has uniform norm one and coefficient vector $(1,-3,1)$ in this basis. The reversed ordering of endpoint Bernstein functions does not affect these symmetric endpoint bounds.

For order $k\ge 2$, set $g(u)=(u-t{)}_{+}^{k-2}$. Then $(u-t)g(u)=(u-t{)}_{+}^{k-1}$. Apply the given divided difference product identity with nodes $t_i,\dots ,t_{i+k}$ and multiply by the length $t_{i+k}-t_i$ of their knot interval:Using the definition of each lower-order normalized B-spline, the two divided differences are $N_{i,k-1}(t)/(t_{i+k-1}-t_i)$ and $N_{i+1,k-1}(t)/(t_{i+k}-t_{i+1})$. Hence the Cox-de Boor recurrence isFor completeness, the product identity itself follows fromand the ordinary divided difference recurrence. Substitution yields the stated convex combination of the two order-$k-1$ divided differences.

The initial order-one splines are the indicators $N_{i,1}(t)=1_{[t_i,t_{i+1})}(t)$. For repeated knots, a term with zero knot-span denominator is defined as zero; this agrees with the standard limiting basis convention. The recurrence uses the partition of unity normalization with $0\le N_{i,k}\le 1$, not a separate rescaling of each spline to make its actual supremum exactly one. The original PDF recurrence has the denominators above; several of these indices and signs were corrupted in the converted TeX.

For integer knots, the recurrence simplifies toOrder-two splines are triangular: $N_{i,2}(i)=N_{i,2}(i+2)=0$ and $N_{i,2}(i+1)=1$. Applying the recurrence once more givesFor example $N_{0,3}(1)=\frac{1}{2}{N}_{0,2}(1)+N_{1,2}(1)=1/2$ and $N_{0,3}(2)=N_{0,2}(2)+\frac{1}{2}{N}_{1,2}(2)=1/2$. Thus the Cardinal cubic B-spline values areThereforeIn particular its actual maximum is $2/3$ in this standard normalization; dividing by that maximum would change the requested recurrence normalization.