Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 61 (Approximation Theory)

Interpret convergence in $C[0,1]$ as uniform convergence, and work first with real continuous functions. Set $e_{n,j}=U_n(p_j)-p_j$, for $j=0,1,2$, and put $M=\Vert f{\Vert }_{\infty }$. The given barriers have one $\gamma \ge 0$ independent of both $t$ and $n$. A positive linear operator on continuous functions preserves non-strict inequalities, so application of $U_n$ and evaluation at $t$ giveStrict pointwise inequalities need not remain strict under a positive operator; non-strict ones suffice. Linearity and the cancellation of the exact moments yieldSubtracting $f(t)$ rather than $f(t)U_{n}1(t)$ therefore gives the quadratic barrier estimate for positive approximation operators:For fixed $\epsilon$, all three moment errors tend uniformly to zero. Thus ${\mathrm{limsup}}_n\Vert U_{n}f-f{\Vert }_{\infty }\le \epsilon$. Since $\epsilon$ was arbitrary,This completes the Korovkin theorem proof. Complex-valued functions follow by applying the real result to real and imaginary parts. Uniform convergence of the three test functions is essential to this uniform conclusion; purely pointwise test convergence should not be silently substituted.

The reproduction hypothesis gives $U1=1$, $U(\cdot )(t)=t$ and $U((\cdot {)}^2)(t)=t^2$. If “quadratic” were read as degree exactly two, the same identities follow by subtracting pairs of such reproduced polynomials. HenceApply the same positive-barrier argument as in part (a), now with no moment errors. It gives $|Uf(t)-f(t)|\le \epsilon$ for every $t$ and every $\epsilon >0$. ThereforeThe identity is itself a positive linear operator on continuous functions reproducing all quadratics, so existence as well as uniqueness is established. In particular, reproducing three small test functions is much stronger for a positive operator than merely fixing one finite-dimensional polynomial space without positivity.

The relevant uniqueness is uniqueness of the node set, with $n\ge 1$. Reordering the same nodes cannot change a constraint imposed at every node, so an unsorted “different sequence” obtained only by permutation would not give the claimed counterexample. Order the genuinely different nodes as $1\ge t_0>t_1>\cdots >t_n\ge -1$ and let $L_i$ be their Lagrange cardinal polynomials:The denominator has sign $(-1{)}^i$. For $1\le k\le n$, repeated differentiation of its numerator givesAll products are nonnegative. At most one factor $1-t_j$ is zero, and because $n-k\le n-1$, some product omits that factor. The derivative is consequently strictly positive, including when $k=n$, for which the product is empty and equals one. This proves the endpoint derivative signs of Lagrange cardinal polynomials:Choose a single Lagrange interpolation polynomial by prescribing $q(t_i)=(-1{)}^i$:It satisfies $|q(t_i)|=1$ at every prescribed node. Its leading coefficient is ${\sum }_{i}1/|{\prod }_{j\ne i}(t_i-t_j)|>0$, so it has degree exactly $n$. The endpoint sign formula gives $q^{(k)}(1)={\sum }_i|L_i^{(k)}(1)|$ simultaneously for all $k$.

Interpolate the Chebyshev polynomial $T_n$ on the same nodes. Since $|T_n(t_i)|\le 1$,The only points at which $|T_n|=1$ are its $n+1$ extrema. A different set of $n+1$ distinct nodes includes at least one nonextremal point; at that point the bracket is strictly positive, and so is its derivative weight for every $k$. Moreover $T_n^{(k)}(1)>0$: differentiating its differential equation gives $T_n^{(k+1)}(1)=(n^2-k^2)T_n^{(k)}(1)/(2k+1)$, beginning with $T_n(1)=1$ and ending at $k=n-1$. ThusThe same $q$ violates every sharp derivative bound, proving uniqueness of Chebyshev derivative-norming nodes for the given Markov-Duffin-Schaeffer theorem. The result concerns node sets or consistently ordered sequences; a mere permutation is the literal ordering exception noted above.

The original PDF prints $O(n^{\alpha })$, with a positive exponent. That premise is insufficient; the intended decay rate is $O(n^{-\alpha })$. Indeed every bounded continuous periodic function has $E_n(f)\le \Vert f{\Vert }_{\infty }=O(n^{\alpha })$. For an explicit counterexample, on $[-\pi ,\pi ]$ setand extend periodically. This is continuous, but $\omega (h,\delta )\ge 1/\log (e/\delta )$ for $0<\delta <1$, which is not $O({\delta }^{\alpha })$ for any $\alpha >0$. Thus the sign correction is required in the actual printed question, not just in its converted TeX.

For real continuous $2\pi$-periodic $f$, write $E_n$ for best uniform approximation by degree-at-most-$n$ trigonometric polynomials and $\omega (f,\delta )={\sup }_{|h|\le \delta }\Vert f(\cdot +h)-f{\Vert }_{\infty }$. A quantitative inverse theorem for trigonometric approximation iswhere $C$ is universal. Here is a direct reason for the sum. Choose best approximants $p_j$ and $2^r\le n<2^{r+1}$. WriteThe Bernstein inequality for trigonometric polynomials givesFor $j\ge 2$, monotonicity of best errors bounds $2^{j+1}{E}_{2^{j-1}}$ by $8{\sum }_{\nu =2^{j-2}}^{2^{j-1}-1}{E}_{\nu }$. The first terms are bounded by a fixed multiple of $E_0$. Also $2E_{2^r}\le 4n^{-1}{\sum }_{\nu =0}^n{E}_{\nu }$. Nowproves the theorem, for example with a sufficiently large absolute constant $C=20$.

Suppose, as intended, $E_{\nu }(f)\le A{\nu }^{-\alpha }$ for $\nu \ge 1$, after enlarging $A$ to include any finite exceptional indices, where $0<\alpha <1$. Since ${\sum }_{\nu =1}^n{\nu }^{-\alpha }\le n^{1-\alpha }/(1-\alpha )$, the inverse theorem givesFor $0<\delta \le 1$ take $n=\lfloor 1/\delta \rfloor$. Then $1/(n+1)<\delta \le 1/n$, so monotonicity of the modulus of continuity and $n^{-\alpha }\le 2^{\alpha }{\delta }^{\alpha }$ give $\omega (f,\delta )\le 2^{\alpha }{C}_f{\delta }^{\alpha }$. For $\delta >1$, the separate bound $\omega (f,\delta )\le 2\Vert f{\Vert }_{\infty }\le 2\Vert f{\Vert }_{\infty }{\delta }^{\alpha }$ covers the remaining scales. Therefore the corrected conclusion isNow put $\beta =\log 2/\log 3$. The given best approximant to the Weierstrass function leaves the uniformly convergent tail ${\sum }_{k=m+1}^{\infty }{2}^{-k}\cos (3^{k}x)$. Its supremum norm is exactly $2^{-m}$, attained at $x=0$; henceThe corrected inverse theorem gives $\omega (g,\delta )=O({\delta }^{\beta })$. To show that this order is sharp, set $h_m=\pi /3^{m+1}$. Every term of $g(0)-g(h_m)$ is nonnegative, and for $k\ge m+1$ the cosine equals $-1$ because $3^{k-m-1}$ is odd. ThusGiven small $\delta >0$, select $m$ with $h_m\le \delta <3h_m$. Then $\omega (g,\delta )\ge 4(3\pi {)}^{-\beta }{\delta }^{\beta }$. Combining the estimates gives the precise small-scale orderThe exact approximation error can also be verified independently of the supplied fact: at $x_j=j\pi /3^{m+1}$ the tail has alternating values $(-1{)}^j{2}^{-m}$. There are enough such points in one period for the trigonometric Chebyshev alternation theorem, since $n<3^{m+1}$. This is the positive lacunary trigonometric series mechanism behind the best partial sums.

Use the standard partition normalization of B-splines, with order $k$ meaning degree $k-1$. The Cox-de Boor recurrence on arbitrary increasing spline knots isstarting with $N_{i,1}(x)=1_{[t_i,t_{i+1})}(x)$. Terms with zero denominator are interpreted as zero in the usual repeated-knot convention. For the uniform knots here, $t_i=i$, this reduces toThe index of the second lower-order B-spline is $i+1$, not $i-1$. Both lower-order supports combine to give $[i,i+k]$.

Uniform knots give translation invariance $N_{i,k}(x)=N_{0,k}(x-i)$. Put $v_{k,j}=N_{0,k}(j)$ and set missing values to zero. The recurrence in part (a) gives the exact numerical recursionThe order-two starting row is $(0,1,0)$. For example, the order-four middle value is $(2\cdot \frac{1}{2}+2\cdot \frac{1}{2})/3=2/3$, and the order-six central value is $(3\cdot \frac{11}{24}+3\cdot \frac{11}{24})/5=66/120$. Iteration gives the requested array, listing $N_{0,k}(0),\dots ,N_{0,k}(k)$:The symmetry follows from reflection of the uniform Cardinal B-spline about the midpoint of its support. The row sums equal one, consistent with sampling the uniform partition of unity. These are partition-normalized values; normalizing each spline to have peak one would produce a different array.

For order six, the support-midpoint sites are $x_i=i+3$, soBy part (b), the complete finite matrix is the symmetric five-diagonal matrixOnly indices from $0$ through $n$ are retained; the first and last rows are truncated, with no exterior coefficients or wraparound terms. For a row with all possible neighbors, the strict diagonal dominance margin is $(66-26-26-1-1)/120=1/10$. Boundary rows have an equal or larger margin.

Here is the appropriate inverse estimate with its proof. If a square matrix $A$ has $|a_{ii}|-{\sum }_{j\ne i}|a_{ij}|\ge d>0$, choose an index $i$ maximizing $|z_i|$. The reverse triangle inequality givesThus $Az=0$ implies $z=0$, and a square finite matrix is invertible. Applying the same estimate with $z=A^{-1}b$ proves $\Vert A^{-1}b{\Vert }_{{\ell }^{\infty }}\le d^{-1}\Vert b{\Vert }_{{\ell }^{\infty }}$. The inverse infinity-norm bound from diagonal dominance consequently yieldsThis also proves existence and uniqueness of the requested interpolating spline for every data vector and every finite $n$. The quintic cardinal spline midpoint collocation matrix includes the cases of one or two coefficients, where the dominance margin is even larger.

For real continuous $f$, the Chebyshev alternation theorem says that $p\in {\mathcal{P}}_n$ is the unique best uniform approximation to $f$ precisely when there are $n+2$ ordered points $0\le x_0<\cdots <x_{n+1}\le 1$ and a sign $\sigma \in \{-1,1\}$ such thatHere ${\mathcal{P}}_n$ means degree at most $n$. Best approximants exist: a minimizing sequence is bounded in the finite-dimensional polynomial space, and finite-dimensional equivalence of norms gives a convergent coefficient subsequence. When $f=p$, the zero error is treated separately; the derivative-sign hypothesis below excludes that case.

Let $p_n$ be a best degree-at-most-$n$ approximant and suppose for contradiction that $E_n(f)=E_{n+1}(f)$. Since $f^{(n+1)}>0$, $f$ is not a degree-at-most-$n$ polynomial and its error is nonzero. The same $p_n$ would be best in ${\mathcal{P}}_{n+1}$, so the Chebyshev alternation theorem at that degree supplies $n+3$ alternating error extrema. The intermediate value theorem gives at least $n+2$ distinct zeros of $e=f-p_n$, one between each consecutive pair of extrema.

Repeated Rolle's theorem then forces a zero of $e^{(n+1)}$. But $p_n^{(n+1)}=0$, whereas $e^{(n+1)}=f^{(n+1)}>0$ everywhere. This contradiction provesThe argument proves strict decrease of best polynomial approximation under a derivative sign; an everywhere negative $(n+1)$st derivative gives the same strict conclusion after replacing $f$ by $-f$.

The ordinary interpolation formulation is unambiguous for strictly increasing knots; repeated knots require specified confluent interpolation or a limiting convention. First take distinct knots and $k\ge 2$, and for fixed $t$ write $F_t(u)=(u-t{)}_{+}^{k-1}$. The two degree-at-most-$k-1$ Lagrange interpolation polynomials ${\ell }_i(\cdot ,t)$ and ${\ell }_{i+1}(\cdot ,t)$ agree at the $k-1$ shared knots $t_{i+1},\dots ,t_{i+k-1}$. Their difference is thereforeThis remains valid if their difference has lower degree: the coefficient is then zero. The leading coefficient of a degree-at-most-$k-1$ interpolant is its order-$(k-1)$ divided difference. Comparing leading coefficients and using the divided-difference recursion givesConsequently the Lee interpolation identity holds for every real $x,t$:No differentiability of the truncated power in its argument was needed for this distinct-node proof.

Sum the identity over $i=1,\dots ,n$. The right side telescopes, giving ${\sum }_i{\omega }_i(x)N_i(t)={\ell }_{n+1}(x,t)-{\ell }_1(x,t)$. When $t_k<t<t_{n+1}$, all the nodes for ${\ell }_1$ lie below $t$, so its interpolation data are zero and ${\ell }_1\equiv 0$. All the nodes for ${\ell }_{n+1}$ lie above $t$, where $F_t(u)=(u-t{)}^{k-1}$ is already a polynomial of the admissible degree. Uniqueness of polynomial interpolation gives ${\ell }_{n+1}(x,t)=(x-t{)}^{k-1}$. Therefore the Marsden identity isFor order one the empty product is one, the interpolants are constants and a consistent half-open interval convention for $(u-t{)}_{+}^0$ gives the same telescoping proof. Nondecreasing repeated-knot sequences can be treated by the appropriate confluent or limiting convention wherever that definition is valid; merely specifying repeated data values does not uniquely determine the interpolation polynomials. The basic open knot interval in the Marsden identity avoids endpoint convention ambiguity.

Write $r=x-u^{\ast }$. If $u^{\ast }$ is a best approximation in the finite-dimensional linear subspace, then for every $v$ in it and every real $t$,A nonzero real linear coefficient would make this negative for sufficiently small $t$ of the appropriate sign. Hence $\mathrm{Re}(r,v)=0$. In a complex inner product space, apply the argument to $iv$ too; the imaginary part also vanishes. Thus $(x-u^{\ast },v)=0$ for every $v$ in the subspace.

Conversely, if that orthogonality holds, every other candidate has the form $u^{\ast }+v$, and the Pythagorean theorem in the inner product norm givesEquality requires $v=0$. ThereforeThe next part constructs this orthogonal projection explicitly. No completeness of the whole inner product space is required for projection onto a finite-dimensional subspace.

Take the inner product linear in its first argument; for a real space no conjugation convention is needed. Insert $u^{\ast }={\sum }_{j=1}^n{a}_j{u}_j$ into the orthogonality condition against each basis vector $u_i$. The normal equations areEquivalently $Ha=b$, where $H_{ij}=(u_j,u_i)$ and $b_i=(x,u_i)$. This orientation of the Gram matrix matches the stated inner-product convention. It is Hermitian and positive definite: for a nonzero coefficient vector $a$,by linear independence of the basis. Hence $H$ is invertible and $a=H^{-1}b$ gives existence and uniqueness of $u^{\ast }$. For an orthonormal basis this simplifies to $a_i=(x,u_i)$; for a general basis the Gram inverse correctly accounts for interactions between basis vectors.

Use the standard $L_{\infty }$-oriented partition normalization of B-splines, in contrast to the unit-integral normalization. Thus $N_i\ge 0$ and ${\sum }_i{N}_i(t)\le 1$ on $[0,1]$, with equality for a complete basis on its basic knot interval. This terminology does not mean that each basis function's maximum is exactly one; for example an order-three cardinal spline has maximum $3/4$. Assume the basis has positive support on the integration interval and is continuous, as is needed for a projection taking values in $C[0,1]$.

LetThe ordinary Gram matrix $H$ is positive definite by linear independence. The appropriate row-normalized, or mixed-normalization spline Gram matrix, isHere $M_i$ is a unit-integral nonnegative spline. Unlike $H$, $G$ need not be symmetric. If the full support lies inside the interval, $d_i=(t_{i+k}-t_i)/k$; otherwise use the actual interval integral rather than that full-support formula.

The normal equations for the $L_2$ orthogonal projection $P_{\mathcal{S}}f={\sum }_i{a}_i{N}_i$ say $Ha=c$, with $c_i=\int f{N}_i$. Divide each row by $d_i$ to obtainNonnegativity and unit integral give $|b_i|\le \Vert f{\Vert }_{\infty }$. The subpartition of unity for B-splines then givesTaking the supremum over $t$ and then over nonzero $f$ proves the uniform norm bound for B-spline orthogonal projection:The row normalization is essential; replacing $G$ with the ordinary Gram matrix would not be the same asserted estimate. The operator is defined on $C[0,1]$ and maps into its finite-dimensional spline subspace, onto $\mathcal{S}$, not onto all of $C[0,1]$ as one phrase in the PDF says. Its range follows both from the formula and from reproducing every $s\in \mathcal{S}$.

If “$L_{\infty }$-normalized” were instead read literally as individually peak-one splines, their sum can exceed one. The basis-dependent factor $K=\Vert {\sum }_i{N}_i{\Vert }_{\infty }$ must then be retained: $\Vert P_{\mathcal{S}}{\Vert }_{\infty }\le K\Vert (D^{-1}H{)}^{-1}{\Vert }_{{\ell }^{\infty }}$. Equivalently the displayed bound without an outside factor uses $G=K^{-1}{D}^{-1}H$. The standard partition-normalized convention has $K\le 1$ and yields the sharper bound proved above.