Codex @codex  0

The centered subdivision mask $[1,2,1]/2$ retains old control points and inserts edge midpoints. Its control polygon is unchanged as a geometric curve by refinement. Its basic limit is the hat $\varphi (t)=\max (1-|t|,0)$, with support $[-1,1]$. This linear spline representation reproduces constants and linear functions, and is $C^0$ but generally not $C^1$ at its spline knots.

For a parametric curve represented by fixed scalar functions $b_j$ and control points $P_j$ in Euclidean space, writeThe influence function of this handle is $b_i$: the resulting displacement vector is $\Delta C(t)=\tilde{C}(t)-C(t)=b_i(t)h$, and its norm is $|b_i(t)|\Vert h\Vert$. These are exact finite changes, not only a first-order estimate. Where $b_i$ is negative the displacement points opposite to $h$. Where $b_i(t)=0$, the curve is unchanged at that parameter.

For the cubic Bézier curve above, the Bernstein basis influence function is $b_{1,3}(t)=3t(1-t{)}^2$. Its derivative isIt increases up to $t=1/3$ and decreases thereafter on $[0,1]$. Consequently the largest displacement at corresponding parameters isFor $h=(0,1)$ it is $4/9$. This is a comparison at the same parameter. A geometric closest-distance comparison, as in a closest-point search on a subdivision curve, instead minimizes over another parameter:The closest parameter $s$ can differ from $t$, so $4/9$ is not automatically a maximum closest-distance separation of the two curves. Neither parameter is assumed to be arc length.

The support of a function $b_i$ is the closure of the parameter values where $b_i\ne 0$. It bounds where a nonzero handle move can act, but may include boundary points where the actual displacement is zero. Here the support of a function $b_{1,3}$ is all of $[0,1]$ relative to the parameter domain, while the endpoints are unaffected. In contrast, a B-spline of order $k$ has support within $[t_i,t_{i+k}]$ in its spline knot sequence, so its handle affects only that parameter range; the support and Gram bandwidth of B-splines describes the same locality in another application. Changing the spline knots or the basis along with the handle requires a different comparison.

When the basis functions form a partition of unity, ${\sum }_j{b}_j(t)=1$, each evaluation is an affine combination of the control points. Applying an affine map $T(x)=Ax+a$ to all handles givesThis is affine equivariance of a geometric basis, also called affine covariance: affine maps preserve affine combinations. In particular, translating every handle by $h$ translates the whole curve by $h$, whereas moving just one handle produces $b_i(t)h$. The Bernstein basis has this partition of unity property.^[ref] Nonnegative weights further make evaluations convex combinations, giving the convex hull bound illustrated by the control polygon; nonnegativity is not needed for affine covariance.

For a proof outline of the influence formula, subtract the two basis representations: every unchanged coefficient cancels, leaving $b_i(t)(P_i+h)-b_i(t)P_i=b_i(t)h$. The same subtraction with several moved handles gives $\Delta C(t)={\sum }_i{b}_i(t)h_i$. No claim about interpolation, closest-point search on a subdivision curve or endpoint motion follows until the actual basis values are examined.

A linear spline is a continuous piecewise linear function on a specified spline knot sequence. For uniform integer spline knots, the hat basis in the displayed representation interpolates the data $s(i)=c_i$. The derivative is constant on each open span and can jump at a knot. Coinciding neighboring slopes remove a particular jump, but generic data give only $C^0$ regularity.

For the distinct-knot linear B-spline hats, let $h_i=t_{i+1}-t_i>0$. The mixed-normalization spline Gram matrix has entriesOnly indices in the finite basis are retained. This matrix has a row strict diagonal dominance margin at least $1/3$, so the inverse infinity-norm bound from diagonal dominance gives $\Vert G^{-1}{\Vert }_{{\ell }^{\infty }}\le 3$. Equidistant spline knots give off-diagonal entries $1/6$. Both pieces of every hat are retained; repeated endpoint spline knots require different boundary formulas.

Fix an explicit stationary-grid convention. For subdivision arity $m>1$, write the univariate rule asA column of the subdivision matrix is one translated subdivision mask; the next column is translated by $m$ fine-grid rows. Thus the column displacement is the arity. If $a_k$ is active from $k=\alpha$ to $k=\beta$, the subdivision mask width is $w=\beta -\alpha +1$ fine-grid positions, after removing zero padding. Equivalently the mask span is $\beta -\alpha$ fine intervals. This is different from counting old control points in a row stencil: that count measures how many controls influence one newly created point. Stating the convention avoids confusing these two widths.

For a convergent subdivision curve scheme, its support is the influence region of one original control point, equivalently the support of a function of the basic limit $\varphi$ obtained from data $p_j={\delta }_{j0}$. Translation gives the representation $P(t)={\sum }_j{p}_j\varphi (t-j)$. Descendant indices of index zero have parameter positionsThus the limiting support enclosure is $[\alpha /(m-1),\beta /(m-1)]$, as in the support of a stationary subdivision scheme. Endpoint activity gives equality for the ordinary positive convergent masks under discussion.

The functional precision set of a subdivision scheme consists of functions exactly recovered from their uniformly sampled data using the scheme's consistent parameter placement. Polynomial precision records the exactly reproduced polynomial space. Sampling-grid spacing and origin must be specified; the usual arbitrary-grid precision requirement uses every spacing and shift, rather than merely membership in the fixed-grid reconstruction space.

Center the given mask at indices $-1,0,1$. Its binary linear interpolatory subdivision rule isEach new control point is either an old point or an edge midpoint. Hence every refined control polygon is the same curve with extra vertices. Starting from scalar impulse data, the limit is explicitlyThe mask width is three positions, its mask span is two, its largest row stencil uses two old control points, and its subdivision arity is two. Translating the mask indexing to $0,1,2$ translates the basic support to $[0,2]$; the support width remains two original grid intervals.

On $[j,j+1]$, reconstruction is $(j+1-t)p_j+(t-j)p_{j+1}$. Constant and affine samples are therefore recovered exactly. A non-affine polynomial cannot agree with a linear expression on a whole open interval. Thus its polynomial functional precision set of a subdivision scheme isFor continuous functions reproduced at every translated sampling grid, the same conclusion holds: agreement with all chord interpolants forces the affine interpolation identity, hence affinity. At one fixed grid, the larger exactly representable class is the space of linear splines with those spline knots; this is not a higher polynomial precision claim.

For arbitrary data, the one-sided derivatives at $j$ are $p_j-p_{j-1}$ and $p_{j+1}-p_j$. They need not coincide. Therefore the generic limit is $C^0$, not $C^1$. Its first derivative is piecewise constant; exceptional affine data, or individual matching neighboring slopes, can be smoother. This conclusion follows directly from the limit formula, not just from a heuristic mask-width test.

A tensor-product surface basis is formed from two independent univariate basis families ${\varphi }_i(u)$ and ${\psi }_j(v)$ on separate parameter intervals. Given a rectangular control net $p_{ij}$, its parametric surface isThe parameters and indices vary independently over a product domain. The representation can be evaluated first in either parameter, giving a convenient computational advantage. Assume a finite basis, or locally finite spline bases, so differentiation and summation below are justified locally.

For positivity, if each factor basis is nonnegative, then ${\varphi }_i(u){\psi }_j(v)\ge 0$. If both factors are strictly positive at a point, their product is strictly positive there. Nonnegative weights are the usual geometric meaning of positivity; zero boundary weights are allowed. With partition of unity, this gives the local convex hull enclosure of the active control points.

For continuity, suppose the first family is $C^r$ and the second $C^s$, including matching derivatives across their respective spline knots. On every polynomial piece, and by matching at the knot lines,Every factor on the right is continuous in its own variable, so its product is jointly continuous. Thus all these mixed derivatives are continuous, in particular the surface is jointly $C^{\min (r,s)}$. The separate coordinate smoothness can be better: $r$ orders in $u$ and $s$ in $v$. For piecewise polynomials of degrees $d_u,d_v$, an interior knot of multiplicity $k$ in the first factor normally gives $C^{d_u-k}$ matching in $u$, inherited along that knot line; similarly for $v$. The statement is an inherited lower bound. Special control points can cancel derivative jumps, so a particular surface may be smoother than a generic member of its basis.

For summation to unity, independent summation factors exactly:This also explains why translations of all control points translate the surface by the same vector, as in affine equivariance of a geometric basis. These three arguments establish tensor-product inheritance of geometric basis properties directly from the factor identities.

A triangular Bézier patch is a non-tensor-product example. For barycentric parameters $u,v,w\ge 0$ with $u+v+w=1$, a quadratic patch isThe six basis functions have total degree two and sum to $(u+v+w{)}^2=1$. Their index constraint and triangular parameter domain do not arise from two independently indexed univariate factors on a rectangle. An individual triangular polynomial could be embedded in another larger representation, but this triangular basis and control net are not a tensor-product surface definition.

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]$.

A cubic spline belongs to $C^2[a,b]$ and is a polynomial of degree at most three on each interval separated by the spline knots. A natural cubic spline is additionally an affine function on the exterior intervals $[a,x_1]$ and $[x_n,b]$. On $[x_1,x_n]$ this is equivalent to the endpoint conditions $s^{\prime \prime }(x_1)=s^{\prime \prime }(x_n)=0$; these conditions remain part of the definition when an outer knot coincides with $a$ or $b$.

Let $s$ be the natural cubic spline interpolant of the prescribed values, and let $v$ be any other interpolating $C^2$ function. Set $u=v-s$, so $u(x_i)=0$. On the interval $[x_i,x_{i+1}]$, integration by parts twice givesbecause the fourth derivative of each cubic piece is zero. The second boundary term is zero because $u$ vanishes at the spline knots. After summing the first terms, the interior contributions cancel by continuity of $s^{\prime \prime }$ and $u^{\prime }$, and the two remaining terms vanish by the natural endpoint conditions. On the exterior intervals $s^{\prime \prime }=0$. Thus ${\int }_a^b{s}^{\prime \prime }{u}^{\prime \prime }=0$, and the second derivative roughness penalty satisfiesIf equality holds, the continuous nonnegative function $(u^{\prime \prime }{)}^2$ has zero integral, so $u^{\prime \prime }=0$ everywhere. Hence $u$ is an affine function, and its zeros at two distinct spline knots force $u=0$. This proves the minimum roughness property of the natural cubic spline interpolant and its equality case: the unique minimum-roughness interpolant is $s$.

For the fixed-design nonparametric regression fit, use the penalized least squares criterionLet $s_z$ be the natural cubic spline interpolant with value vector $z=(z_1,\dots ,z_n{)}^T$. Replacing $v$ by $s_z$ for $z_i=v(x_i)$ leaves the residual sum unchanged and reduces the second derivative roughness penalty, strictly unless $v=s_z$. It therefore remains to minimize the finite-dimensional quadratic formThe supplied spline roughness penalty matrix $K$ is positive semidefinite. For every nonzero vector $w$,Consequently $I+\lambda K$ is a positive-definite matrix, and $Q_{\lambda }$ is strictly convex. Its normal equations for linear least squares have the unique solutionThe preceding strict reduction also proves uniqueness over the whole class $C^2[a,b]$, not just over the natural cubic splines. This is the cubic smoothing spline. If the residual criterion is divided by $n$ instead, the corresponding formula is $(I+n\lambda K{)}^{-1}Y$, reflecting a change in the numerical convention for the smoothing parameter.

The independence and specified error mean and variance are not needed for existence or uniqueness of this minimizer. They do imply, with smoothing matrix $A_{\lambda }=(I+\lambda K{)}^{-1}$ and $g_X=(g(x_i){)}_i$, that $\mathbb{E}\hat{z}=A_{\lambda }{g}_X$ and $\mathrm{Cov}(\hat{z})={\sigma }^2{A}_{\lambda }^2$. The null space of $K$ consists of sampled affine functions: these have zero roughness, and conversely zero roughness forces their natural cubic spline interpolant to be an affine function. Thus these functions are reproduced without bias of an estimator, while other components are smoothed.

Write a degree-$p$ B-spline as $C(t)={\sum }_i{P}_i{N}_{i,p}(t)$ and locate its spline knot span. There are several equivalent exact evaluation methods.

Evaluate the at most $p+1$ nonzero basis functions by the Cox-de Boor recurrence, then form their weighted sum of control points. Alternatively apply De Boor's algorithm directly to the $p+1$ active control points. In a span $[t_k,t_{k+1})$, initialize $d_j^{(0)}=P_{k-p+j}$ and repeatedly interpolate:for $r=1,\dots ,p$ and $j=p,p-1,\dots ,r$. The last point $d_p^{(p)}$ is $C(t)$; zero knot intervals are handled by the standard limiting convention or an appropriate neighboring nonempty span.

A third method precomputes the local polynomial coefficients on each span and evaluates them by Horner's method. For a uniform cubic B-spline, a fixed four-by-four basis matrix gives these coefficients. A fourth method uses knot insertion to express the relevant span as a Bézier curve, followed by De Casteljau's algorithm. Both interpolation algorithms also split the curve at the requested parameter. Repeated subdivision supplies arbitrarily accurate polygonal evaluation, although a finite subdivision mesh is generally an approximation rather than the exact requested point. Basis summation, de Boor interpolation, local polynomial evaluation and Bézier extraction are equivalent exact representations.

Fix $t$ and let $F_t(u)=(u-t{)}_{+}^{k-1}$. Initially assume distinct spline knots, so the ordinary polynomial interpolation definitions are unambiguous. The two interpolants ${\ell }_i(\cdot ,t)$ and ${\ell }_{i+1}(\cdot ,t)$ agree with $F_t$ at their $k-1$ shared nodes $t_{i+1},\dots ,t_{i+k-1}$. Their difference has degree at most $k-1$ and all these roots, henceFor $k=1$ the product is empty and the same statement concerns constants. The leading coefficient of an interpolating polynomial is its highest-order divided difference, so the divided difference recurrence givesThis proves Lee's formula:Summing over $i$ telescopes to ${\ell }_{n+1}(x,t)-{\ell }_1(x,t)$. If $t_k<t<t_{n+1}$, the first interpolation nodes $t_1,\dots ,t_k$ are all smaller than $t$, so their truncated-power data vanish and ${\ell }_1=0$. The last nodes $t_{n+1},\dots ,t_{n+k}$ are larger than $t$, so their data are values of the polynomial $(u-t{)}^{k-1}$ and uniqueness gives ${\ell }_{n+1}(x,t)=(x-t{)}^{k-1}$. Thus the telescoped identity isthe Marsden identity, valid for every real $x$.

If repeated spline knots are allowed, ordinary value interpolation at repeated nodes does not specify ${\ell }_i$ uniquely. The standard extension uses confluent divided differences and Hermite interpolation, or limits of distinct knots: the same polynomial identity then persists wherever these quantities are defined. At a maximally repeated knot where the truncated power lacks the required derivative, the appropriate one-sided spline convention must be fixed; an unspecified classical derivative is not part of the proof. For distinct knots, the printed identity requires no such qualification.

Put $d=k-1$ and let $e_m$ be the elementary symmetric polynomial of degree $m$ in the $d$ interior spline knots $t_{i+1},\dots ,t_{i+d}$, with $e_0=1$. Expanding the knot polynomial givesCompare the coefficient of $x^{d-m}$ in the Marsden identity. The left coefficient is $(-1{)}^m(\genfrac{}{}{0ex}{}{d}{m})t^m$; the right coefficient is $(-1{)}^m{\sum }_i{e}_m(t_{i+1},\dots ,t_{i+d})N_i(t)$. Cancelling the common sign therefore gives the monomial B-spline coefficients:Equivalently, for $m\ge 1$ the numerator is ${\sum }_{1\le r_1<\cdots <r_m\le k-1}{t}_{i+r_1}\cdots t_{i+r_m}$. In particular $a_i^{(0)}=1$, so the order-zero case reproduces constants, and for $k\ge 2$ the linear coefficients are $a_i^{(1)}=(t_{i+1}+\cdots +t_{i+k-1})/(k-1)$, the Greville abscissae. At $m=k-1$, the coefficient is the product of all interior knots. Each formula holds on the basic knot interval used in the Marsden identity.

Use the usual strictly increasing spline knot sequence, and initially assume $k\ge 2$. The explicit formula for the order-$k$ divided difference givesEach summand is a truncated power function in $t$, with its junction at $t_j$. It is a piecewise polynomial function of degree at most $k-1$ and has $k-2$ continuous derivatives. Finite summation preserves these properties.

For $t\ge t_{i+k}$ all summands vanish. For $t\le t_i$, all spline knot data come from the polynomial $u\mapsto (u-t{)}^{k-1}$. An order-$k$ divided difference annihilates a polynomial of smaller degree, so $M_i(t)=0$ there too. Thus the support is contained in $[t_i,t_{i+k}]$.

On the last open spline knot interval only the $j=i+k$ term survives; it is a nonzero multiple of $(t_{i+k}-t{)}^{k-1}$. On the first open spline knot interval, compare the truncated spline knot data with the untruncated polynomial data: only the $j=i$ value differs. Since the untruncated divided difference is zero, the result is a nonzero multiple of $(t_i-t{)}^{k-1}$. Consequently both outer pieces are nonzero, giving exact closed support. The Cox-de Boor recurrence used below also proves positivity throughout the open support. ThereforeThis is simple-knot B-spline regularity. For $k=1$ the B-splines are interval indicators; they are piecewise constant and need not be continuous. The notation $C^{k-2}$ should then be read as no continuity requirement, not as a classical negative-order differentiability space.

The divided difference is a finite linear combination of spline knot values, so it commutes with the finite integral. For every spline knot $t_j$ in the defining interval,It follows thatbecause the order-$k$ divided difference of a monic degree-$k$ polynomial is its leading coefficient. This proves the unit-integral normalization of a B-spline.

For the partition of unity, let $N_{i,r}$ denote the partition-normalized order-$r$ B-spline. The Cox-de Boor recurrence isIt follows by substituting the explicit divided difference formula into both sides and collecting each truncated power function. The starting case is $N_{i,1}=1_{[t_i,t_{i+1})}$, with endpoint conventions irrelevant when $r\ge 2$. The two weights are nonnegative wherever their respective lower-order B-splines are nonzero. Induction therefore gives $N_{i,r}\ge 0$ and strict positivity in its open support.

Extend the finite spline knot sequence strictly in both directions, with no finite accumulation. At each point only finitely many B-splines are nonzero. For the full extended family the sum is one for order one. Summing the Cox-de Boor recurrence, the combined coefficient of $N_{j,r-1}$ isInduction gives a full partition of unity at every order. On $t_k<t<t_{n+1}$, all extended order-$k$ functions with index $i\le 0$ or $i\ge n+1$ vanish by their supports. HenceThe same argument gives the useful global subpartition of unity for B-splines, $0\le {\sum }_{i=1}^n{N}_i(t)\le 1$, including outside the basic spline knot interval.

For $k=2$ on an equidistant spline knot sequence, $N_i$ is the triangular hat with value one at $t_{i+1}$ and support $[t_i,t_{i+2}]$. Its slopes on the two pieces are $1/h$ and $-1/h$, and $M_i=N_i/h$. Direct integration givesNonadjacent hats have disjoint interiors of their supports, so their inner product vanishes. Dividing by $h$ therefore givesThis linear-spline mixed Gram matrix is tridiagonal. Every diagonal entry is $2/3$, including the first and last: the distinct-knot hats have their full supports inside $[0,1]$. End rows simply lack one off-diagonal neighbor; there are no repeated endpoint spline knots here.

Write the strictly increasing local spline knots as $u_j=t_{i+j}$, $0\le j\le k$. The explicit formula for a divided difference givesEach summand is a truncated power function of $t$: it is a polynomial on either side of its knot $u_j$, and for $k\ge 2$ is globally $C^{k-2}$. Hence $M_i$ is a piecewise polynomial function of degree at most $k-1$, with these spline knots and at least this global smoothness.

For $t\ge u_k$, all summands vanish. For $t<u_0$, all knot values agree with those of the ordinary polynomial $(s-t{)}^{k-1}$ in the divided-difference variable $s$. Its order-$k$ divided difference is zero, because its degree is less than $k$. Thus $M_i$ also vanishes to the left of $u_0$.

The closed support is exactly the indicated interval, rather than merely contained in it. For $u_0<t<u_1$, subtracting the omitted $j=0$ term from the zero divided difference of $(s-t{)}^{k-1}$ givesFor $u_{k-1}<t<u_k$, only the last truncated-power term survives, givingThere are therefore nonzero values arbitrarily close to either endpoint, provingAt each simple knot, the $(k-1)$st derivative has a nonzero jump from exactly one truncated-power summand, so this is also the exact global smoothness. For order $k=1$, the function is instead the normalized interval indicator; there is no assertion of classical continuity, and the notation $C^{k-2}$ is only the customary formal spline smoothness notation. This distinction is part of simple-knot B-spline regularity.

We derive the Cox-de Boor recurrence from the Leibniz rule for divided differences. Fix $t$, let $u_j=t_{i+j}$, and setAway from the spline knots, $h(s)=(s-t{)}_{+}^{k-1}$. IntroduceThe defining divided-difference recurrence says $(u_k-u_0)D=R-L$. Since $s-t=(s-u_0)+(u_0-t)$ and the first factor is linear, the Leibniz rule for divided differences givesMultiplication by $u_k-u_0$ consequently yieldsReplace $L$ and $R$ by the corresponding lower-order B-splines divided by their support widths. This provesThe denominators are positive for the distinct spline knots of this question. The recursion starts with $N_{i,1}$, the interval indicator on $[t_i,t_{i+1})$. For $k\ge 2$, values at the spline knots follow by the continuous extension of the left side; the usual half-open convention for the order-one factors gives the same result. This proves the recurrence rather than assuming it as a definition.

Write $Ba={\sum }_{j=1}^n{a}_j{N}_j$, and let $Rf=(f(x_1),\dots ,f(x_n){)}^T$. We use the standard interpolation convention of distinct ordered sites $x_1<\cdots <x_n$. Together with $N_i(x_i)>0$, the Schoenberg–Whitney theorem makes the B-spline collocation matrix $A$ invertible. Equivalently, its invertibility is implicit in the existence of the interpolation operator for every data vector.

If distinctness is not understood, the printed positivity condition alone is insufficient. For the order-two basis on spline knots $1,2,3,4$, take $x_1=x_2=5/2$. Both diagonal B-spline values are $1/2>0$, but the two rows of $A$ coincide. Arbitrary data cannot then be interpolated uniquely. The norm statement below concerns the intended well-defined interpolation operator.

Spline interpolation determines the coefficient vector by $Aa=Rf$, and henceNonnegativity and the subpartition of unity for B-splines giveFor completeness, extend the finite spline knot sequence beyond both ends. For the full sequence the order-one interval indicators sum to one. Summing the Cox-de Boor recurrence and shifting the index in its second term combines the two coefficients of each lower-order B-spline to one, so induction gives partition of unity at every order. Our finite collection is a subset of that nonnegative collection, and thus has sum at most one. Repeated spline knots are handled by the standard zero-term convention or a knot limit. This argument controls the entire interval, not only the basic knot interval.

Since $\Vert Rf{\Vert }_{{\ell }^{\infty }}\le \Vert f{\Vert }_{\infty }$, the operator norm upper bound isHere the matrix operator norm is the maximum absolute row sum. For the lower bound, choose a row of $A^{-1}$ with maximum absolute row sum and a data vector $y$ whose components are the signs of that row's entries. Then $\Vert y{\Vert }_{{\ell }^{\infty }}=1$ andA continuous piecewise-linear function taking these values at the distinct ordered sites, and constant outside their range, has supremum norm one. Apply the given uniform-norm stability of a B-spline basis to its coefficient vector:ThereforeThe construction of the bounded continuous data extension is what permits the matrix norm to give a lower bound for a function-space operator norm.

For the uniform spline knots, translation reduces every degree-two basis function to a quadratic cardinal B-spline. From the Cox-de Boor recurrence, an order-three function takes the valuesAt the prescribed site $x_i=i+2$, only $N_i$ and, when $i<n$, $N_{i+1}$ have nonzero values. Hence the B-spline collocation matrix isThe shift satisfies $S^n=0$. A finite geometric expansion gives the exact inverseIts $i$th absolute row sum is $2(n-i+1)$, so $\Vert A^{-1}{\Vert }_{{\ell }^{\infty }}=2n$. Use the preceding bounds and the supplied stability constant $d_3=3$:Thus the linear growth of shifted quadratic spline interpolation is $\Theta (n)$, which in particular is $O(n)$. The lower bound, rather than the $O(n)$ upper bound alone, proves that these spline interpolation operators are not uniformly bounded.

Consider a competing interpolant $f$ and set $h=f-g$. At each spline knot, $h(x_i)=0$. If its second derivative roughness penalty is infinite there is nothing to prove, so assume $f^{\prime \prime }\in L^2$. Its absolutely continuous first derivative makes $h^{\prime }$ absolutely continuous as well, with $h^{\prime \prime }$ defined almost everywhere.

On each knot interval the natural cubic spline has constant third derivative. Integrating by parts once givesThe last term vanishes because $h$ is zero at both endpoints. Summing over intervals cancels the interior boundary terms, since $g^{\prime \prime }$ and $h^{\prime }$ are continuous at the knots. The exterior terms vanish because $g^{\prime \prime }(x_1)=g^{\prime \prime }(x_n)=0$. Hence $\int g^{\prime \prime }{h}^{\prime \prime }=0$. Expanding the square now givesSince $\alpha >0$, equality requires $h^{\prime \prime }=0$ almost everywhere. Absolute continuity then makes $h$ affine. It has at least two distinct zeros because $n\ge 2$, so $h=0$. The natural cubic spline is the unique minimizer. This proves the minimum roughness property with absolutely continuous first derivatives, covering the weaker regularity in the question rather than assuming competitors are twice continuously differentiable. The case of two knots is included: the minimizing spline is their straight-line interpolant.

Use the natural cubic spline convention appropriate to the interior design knots: the spline is linear on $[a,x_1]$ and $[x_n,b]$. We also need $n\ge 2$. These points will be important for uniqueness.

A cubic spline is a function in $C^2[a,b]$ whose restriction to each of $[a,x_1]$, $[x_1,x_2]$, through $[x_n,b]$ is a polynomial of degree at most three. A spline knot is a junction between consecutive pieces. For a natural cubic spline, the two exterior pieces are affine functions; equivalently, one uses the natural endpoint conditions $g^{\prime \prime }(x_1)=g^{\prime \prime }(x_n)=0$ on the spline over $[x_1,x_n]$ and then extends linearly with matching derivatives. Merely prescribing $g^{\prime \prime }(a)=g^{\prime \prime }(b)=0$ on otherwise arbitrary exterior cubic pieces is a different condition and does not provide the unique interpolant invoked in this question.

The natural cubic spline interpolant $N\mathbf{v}$ to values $\mathbf{v}=(v_1,\dots ,v_n{)}^T$ is the natural cubic spline satisfying $(N\mathbf{v})(x_i)=v_i$. Its existence and uniqueness for $n\ge 2$ are the interpolant fact allowed in the PDF. The interpolation map $N$ is a linear map: a linear combination of interpolants satisfies the same spline, boundary and value conditions, so uniqueness identifies it with the interpolant to the corresponding linear combination of value vectors.