Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 62 / 5

For the usual spline interpolation problem the sites are distinct and ordered; the Schoenberg–Whitney theorem then makes $A_x$ invertible under the stated support positivity. More generally, the following argument applies whenever the interpolation map in the question is well defined and $A_x$ is invertible.

Factor the spline interpolation operator as $P_x=B{A}_x^{-1}R$, whereSampling has operator norm at most one from the supremum norm to ${\ell }_{\infty }$. Nonnegativity and the subpartition of unity for B-splines giveConsequently $\Vert P_x\Vert \le \Vert A_x^{-1}{\Vert }_{{\ell }_{\infty }}$.

For the reverse bound, select a row $r$ of $A_x^{-1}$ with maximal absolute row sum, and choose $y_j=\mathrm{sgn}((A_x^{-1}{)}_{rj})$, assigning any value of modulus at most one when the entry is zero. Then $\Vert y{\Vert }_{{\ell }_{\infty }}=1$ andAt distinct sites there is a continuous piecewise linear function $f$ with $f(x_j)=y_j$ and $\Vert f{\Vert }_{\infty }=1$: interpolate linearly between the ordered sites and extend constantly to the endpoints. The given uniform-norm stability of a B-spline basis therefore impliesThus the B-spline interpolation operator norm satisfiesPositivity $N_i(x_i)>0$ alone, without the usual distinct-site convention, is insufficient to define an interpolation operator. For example, take order-two B-splines with knots $0,1,2,3$ and $x_1=x_2=3/2$. Both diagonal values are $1/2$, but the B-spline collocation matrix has identical rows $(1/2,1/2)$ and is singular. The displayed proof uses the well-defined interpolation map posited in the question; ordered distinct sites supply its standard existence guarantee.

For unit-spaced knots, the quadratic cardinal B-spline with support $[i,i+3]$ is $N_i(t)=B(t-i)$, where the Cox-de Boor recurrence givesIn particular $B(1)=B(2)=1/2$ and $B(0)=B(3)=0$. At $x_i=i+2$, the only nonzero entries in row $i$ are $A_{ii}=1/2$ and, if $i<n$, $A_{i,i+1}=1/2$. Write $U$ for the upper shift matrix, with ones immediately above its diagonal. Thensince $U^n=0$. Thus $(A_x^{-1}{)}_{ij}=2(-1{)}^{j-i}$ for $j\ge i$, and zero otherwise. The largest absolute row sum is the first, giving $\Vert A_x^{-1}{\Vert }_{{\ell }_{\infty }}=2n$.

Using (1) and the permitted $d_3=3$ proves the stronger linear growth of shifted quadratic spline interpolation estimateTherefore $\Vert P_x\Vert =\Theta (n)$ and is not uniformly bounded. An $O(n)$ upper bound alone would not imply unboundedness; the lower bound is essential.