= Solution
Fix a clamped nondecreasing <spline knot sequence> $t_1,\ldots,t_{n+k}$ on $[a,b]$, with $t_1=\cdots=t_k=a$ and $t_{n+1}=\cdots=t_{n+k}=b$. For continuous <splines> assume interior multiplicities at most $k-1$, and assume $t_i<t_{i+k}$. An order-$k$ <spline> has degree at most $k-1$ on each nonempty knot interval; at a knot of multiplicity $r$ it has $k-1-r$ continuous <derivatives>. Its dimension is $n$, and a normalized <B-spline> <basis> $N_1,\ldots,N_n$ has local <support>, nonnegative values and sum one on $[a,b]$.
These properties are visible in the <Cox-de Boor recurrence>. Starting with interval indicators at order one, set
$$
N_{i,k}(x)=\frac{x-t_i}{t_{i+k-1}-t_i}N_{i,k-1}(x)+\frac{t_{i+k}-x}{t_{i+k}-t_{i+1}}N_{i+1,k-1}(x),
$$
with a term of zero denominator defined to be zero. On each contributing <support> the weights are nonnegative, and summing the recurrence makes the coefficients of each lower-order <B-spline> add to one. This gives partition of unity and $\operatorname{supp}N_{i,k}=[t_i,t_{i+k}]$, with endpoint values defined by limits.
At distinct ordered sites $x_1<\cdots<x_n$, interpolation is the <linear system>
$$
A_{\mathbf x}c=y,\qquad (A_{\mathbf x})_{ij}=N_j(x_i).
$$
It has a unique solution for every data <vector> exactly when the <B-spline collocation matrix> is invertible. The <Schoenberg–Whitney theorem> characterizes this by $N_i(x_i)>0$ for every $i$; away from clamped endpoints this is $t_i<x_i<t_{i+k}$. At the clamped endpoints the first and last <B-splines> have value one, so the endpoint version uses this positive-value formulation rather than the strict inequalities. Both ordering and the support conditions matter. A <spline> space with interior knots is generally not a <Chebyshev system> on the entire interval: a locally supported <B-spline> vanishes on an interval. Thus arbitrary distinct nodes need not permit interpolation. Merely specifying all data sites as knots also need not fix the remaining freedom; for example, cubic interpolation with simple interior knots at $m-2$ data sites has dimension $m+2$, and two extra boundary conditions are needed to interpolate $m$ values uniquely.
The positivity governing this existence theorem is <total nonnegativity of B-spline collocation matrices>: every square minor with increasing row and column indices is nonnegative. In spline terminology this is often called total positivity, but it permits zero minors caused by disjoint <supports>. It is not the stronger assertion that every minor is strictly positive. A useful proof uses <knot insertion>. Each refinement step changes <coefficients> by
$$
\widetilde c_j=\alpha_jc_j+(1-\alpha_j)c_{j-1},\qquad 0\le\alpha_j\le1,
$$
with the unchanged endpoint pieces. The refinement <matrix> is nonnegative bidiagonal, and its minors are nonnegative: any nonzero determinant has its allowed diagonal matching and is a product of nonnegative entries. Products preserve this property by the <Cauchy–Binet formula>. Insert each sampling site to full multiplicity, so evaluation at that site becomes selection of an ordered refined <coefficient>. The collocation <matrix> is then an ordered row submatrix of the refinement product, proving total nonnegativity. The strict support criterion is the strict part of this argument: an ordered path through the consecutive support intervals exists exactly when every diagonal <B-spline> value is positive, giving the <Schoenberg–Whitney theorem> determinant criterion.
If $A$ is invertible, its determinant is positive and the <adjugate identity> yields
$$
(A^{-1})_{ij}=(-1)^{i+j}\frac{\det A_{\widehat j,\widehat i}}{\det A},\qquad(-1)^{i+j}(A^{-1})_{ij}\ge0.
$$
This <checkerboard inverse of a totally nonnegative matrix> is the central stability fact. With alternating data $e_i=(-1)^i$, the absolute row sums satisfy
$$
|(A^{-1}e)_j|=\sum_i|(A^{-1})_{ji}|,\qquad\|A^{-1}\|_\infty=\|A^{-1}e\|_\infty.
$$
For general data, the cardinal <splines> are $\ell_i(x)=\sum_jN_j(x)(A^{-1})_{ji}$. The <spline interpolation operator> and its exact <Lebesgue constant of interpolation> are
$$
P_{\mathbf x}f=\sum_if(x_i)\ell_i,\qquad\|P_{\mathbf x}\|=\Lambda_{\mathbf x}:=\max_x\sum_i|\ell_i(x)|\le\|A_{\mathbf x}^{-1}\|_\infty.
$$
The equality for the <operator norm> follows by extending the signs at distinct sites to a continuous unit-norm data <function>, as in Solution 2. That solution also shows the last inequality can be very strict. Stability concerns the range <function> as well as its <coefficients>.
An optimal interpolation set must be specified relative to an objective. For the normalized <B-spline> <coefficients>, every admissible sampling set satisfies
$$
\kappa(\mathcal S)\le\|A_{\mathbf x}^{-1}\|_\infty,
$$
since $c(s)=A_{\mathbf x}^{-1}(s(x_i))$ and sampling cannot increase the <supremum norm>. If a unit-norm <spline> $s_*$ has $n$ ordered alternating extrema $s_*(x_i)=(-1)^i$ at admissible sites, the checkerboard identity gives
$$
|c_j(s_*)|=\sum_i|(A_{\mathbf x}^{-1})_{ji}|.
$$
Taking the largest row shows $\|A_{\mathbf x}^{-1}\|_\infty\le\kappa(\mathcal S)$, so equality holds. This proves the <optimal spline coefficient interpolation sites> property and the <Chebyshev spline coefficient and dual norm equality>. In particular, for the cubic space of Solution 1 the alternating extrema $-1,-2/3,0,2/3,1$ satisfy the support conditions. Its <coefficients> have maximum magnitude $11/2$, so these sites are optimal for coefficient recovery and
$$
\boxed{\kappa(\mathcal S)=\frac{11}{2}=\|A_{\mathbf x}^{-1}\|_\infty\quad\text{at those five sites}.}
$$
The argument proves optimality whenever this admissible equioscillating <spline> is available; it does not identify extrema of an arbitrary <spline> as optimal sites, or transfer coefficient optimality automatically to the <Lebesgue constant of interpolation>.
For the intrinsic interpolation objective, minimize $\Lambda_{\mathbf x}$ itself. There is a minimizer for a fixed finite-dimensional continuous <spline> space. Indeed the sites lie in a compact ordered simplex. On admissible sets, inverse entries and hence $\Lambda_{\mathbf x}$ vary continuously. As a collocation <matrix> tends to a singular one, its inverse <norm> diverges. The <uniform-norm stability of a B-spline basis> gives the complementary bound
$$
\|P_{\mathbf x}\|\ge\frac{\|A_{\mathbf x}^{-1}\|_\infty}{\kappa(\mathcal S)}:
$$
choose sample signs attaining a largest inverse row, extend them to a continuous unit-norm <function>, and use $\|Tc\|_\infty\ge\|c\|_\infty/\kappa(\mathcal S)$. Thus a minimizing sequence with bounded <Lebesgue constants of interpolation> cannot approach a singular site set. A convergent subsequence has an admissible limit attaining the minimum.
<Fekete interpolation sites for a continuous function space> offer another useful, constructive criterion: maximize the absolute evaluation determinant. A nonzero maximum exists by compactness and linear independence. Replacing one row by evaluation at $x$ multiplies the determinant by the corresponding cardinal <function>, so maximality gives $|\ell_i(x)|\le1$, and therefore $\Lambda_{\mathbf x}\le n$. These sites are determinant-optimal, with a proven interpolation bound; one should not claim without further argument that they minimize $\Lambda_{\mathbf x}$. <Greville abscissae> provide inexpensive admissible sites for the usual continuous clamped <spline> spaces of order at least two. Admissibility alone does not give the best stability bound.
Finally, the <coefficient condition number of a normalized B-spline basis> is bounded by a constant depending only on order. To see the mechanism, for each <coefficient> choose a longest nonempty knot cell in that <B-spline>'s support. If its length is $h$ and the support width is $W$, then $W/h\le k$. On that cell the <spline> is a degree-at-most-$k-1$ <polynomial>; repeated <Markov polynomial inequalities> bound its $r$th <derivative> by $C_kh^{-r}\|s\|_\infty$. In the <De Boor–Fix spline coefficient functional>, the accompanying derivative of the knot <polynomial> is bounded by $C_kW^r$. Each term is consequently at most $C_k(W/h)^r\|s\|_\infty$, yielding $\|c(s)\|_\infty\le C_k\|s\|_\infty$ independently of the number and spacing of knots. This is basis stability; it does not bound $\|A_{\mathbf x}^{-1}\|$ at arbitrarily poor sampling sites.
For approximation, reproduction gives the <Lebesgue inequality for approximation projectors>
$$
\|f-P_{\mathbf x}f\|_\infty\le(1+\Lambda_{\mathbf x})\inf_{s\in\mathcal S}\|f-s\|_\infty.
$$
As the maximum knot gap tends to zero with fixed order, <spline quasi-interpolation> gives an approximant with error at most $\omega(f,kh)$, so the infimum tends to zero. A sequence of uniformly bounded interpolation <linear operators> therefore converges to every continuous target. Local <support> and a stable choice of sites make <spline interpolation> effective; mesh refinement without control of the interpolation <operator norm> is not by itself a convergence proof.
Back to article page
