Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 71 / 4

Let $y=(f(x_1),\dots ,f(x_n){)}^T$ and write the interpolating spline as $P_{x}f={\sum }_{j=1}^n{c}_j{N}_j$. The interpolation equations are $A_{x}c=y$, so $c=A_x^{-1}y$. Since $P_x$ is defined as a unique interpolant for arbitrary data, its B-spline collocation matrix is invertible. Ordered sites satisfying diagonal positivity ensure this by question 7. Positivity alone without admissible ordering does not: two equal sites in overlapping basis supports could give two identical rows. The norm argument below uses the existence of the operator stipulated here.

Standard partition-normalized B-splines satisfy $N_j\ge 0$ and ${\sum }_{j=1}^n{N}_j\le 1$. The latter is a subpartition of unity for B-splines: extending the knot sequence gives a full partition of unity, and discarding basis functions cannot increase its sum. HenceTaking the supremum over $t$ and then over unit-norm $f$ gives the B-spline interpolation operator norm estimateHere the matrix norm is the induced maximum-row-sum norm, not the maximum of its individual entries. The proof only needs nonnegative basis functions, their sum at most one, and invertible interpolation.

Use the Cox-de Boor recurrence. For unit knots the order-two hat is $L(u)=u$ on $[0,1]$, $L(u)=2-u$ on $[1,2]$, and zero elsewhere. The order-three quadratic cardinal B-spline isThus $N_j(t)=q(t-j)$. At $x_i=i+3/2$, the only possible arguments in its support are $3/2$ and $1/2,5/2$ at neighboring indices. Their values giveIndices outside $1,\dots ,n$ are absent, so the first and last rows have just one neighboring nonzero value.

The centered quadratic spline interpolation matrix is the symmetric tridiagonal Toeplitz matrixFor $n=1$, this means simply $A_x=(3/4)$. To evaluate the inverse norm exactly, let $D=\mathrm{diag}((-1{)}^i{)}_{i=1}^n$ and $M=8D{A}_{x}D=\mathrm{tridiag}(-1,6,-1)$. If $J$ is the nonnegative adjacency matrix of the path, then $M=6I-J$ and $\Vert J/6{\Vert }_{\infty }\le 1/3$. The convergent Neumann seriestherefore has nonnegative entries. Since $A_x^{-1}=8D{M}^{-1}D$, its entrywise absolute values are $8M^{-1}$. Let $r_i={\sum }_j|(A_x^{-1}{)}_{ij}|$. Then $r=8M^{-1}1$, orThe homogeneous characteristic roots are $3\pm 2\sqrt{2}$. Put $\tau =3-2\sqrt{2}\in (0,1)$. The particular solution $r_i=2$ and the two boundary conditions giveThese row sums are symmetric and increase toward the centre: the exponential sum in the numerator is minimized at the middle integer or pair of integers. With $m=\lfloor (n+1)/2\rfloor$, the exact finite-size inverse norm is thusFor example it equals $4/3$ at $n=1$ and $8/5$ at $n=2$, tending to $2$ as $n\to \infty$. Stating only the bound two would not evaluate the finite matrix norm requested here.

The general estimate from part 1 and the exact inverse norm from part 2b implyand in particular $\Vert P_x{\Vert }_{L^{\infty }}\le 2$, uniformly in the number of knots. This bound concerns the support-centred sites $x_i=i+3/2$; shifting the sampling sites changes the B-spline collocation matrix and can destroy uniform stability.