Chapter 04

Hard

Piecewise Polynomials and Splines

00 · Symbol Glossary

$s$s — cubic spline

A function that is a cubic polynomial on each subinterval of a partition and belongs to $C^{2}$ across the whole interval. Once end conditions are fixed, the interpolating $s$ is the unknown this chapter solves for. Read " $s$ " as "the spline."

$h_i$h sub i — mesh spacing

$h_i=x_{i+1}-x_i$ , the length of the $i$ th subinterval. The mesh is uniform when every $h_i$ equals the same $h$ . The largest spacing is written $h=\max_i h_i$ .

$\delta_i$delta sub i — secant slope

$\delta_i=(y_{i+1}-y_i)/h_i$ , the slope of the chord through consecutive data. Jumps $\delta_i-\delta_{i-1}$ are the right-hand side of the moment equations.

$M_i$M sub i — moment

$M_i=s''(x_i)$ , the second derivative of the spline at a node. The vector of moments is the unknown in a tridiagonal linear system. On each subinterval, $s''$ is the straight line joining $M_i$ to $M_{i+1}$ .

$C^{k}$C to the k — continuity class

The functions on $[a,b]$ whose derivatives through order $k$ exist and are continuous. $C^{0}$ allows corners. $C^{2}$ is the smoothness a cubic spline is built to have.

$p_n\in\mathcal{P}_n$p sub n in P sub n — global interpolant

$\mathcal{P}_n$ is Chapter 03's space of polynomials of degree at most $n$ . The element $p_n$ is the unique member that matches $n+1$ samples at distinct nodes. Read "p sub n in P sub n."

$\omega(x)$omega of x — nodal polynomial

Chapter 03's monic product $\prod_{i=0}^{n}(x-x_i)$ . The pointwise error is $f^{(n+1)}(\xi)\,\omega(x)/(n+1)!$ . On one subinterval of length $h_i$ the same product is a power of $h_i$ .

01 · Where a Single Polynomial Breaks

Chapter 03 builds, for distinct nodes $x_0,\ldots,x_n$ , a unique interpolant $p_n\in\mathcal{P}_n$ , and proves

f(x)-p_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega(x)

whenever $f^{(n+1)}$ is continuous on an interval containing $x$ and the nodes. The same chapter proves that the formula need not tend to zero. For

f(x)=\frac{1}{1+25x^{2}}\qquad\text{on}\quad [-1,1],

with equispaced nodes $x_i=-1+2i/n$ , the uniform error $\|f-p_n\|_\infty$ is unbounded as $n\to\infty$ . The degree- $4$ interpolant is already the wrong sign inside the interval: $p_4(4/5)=-11/29$ while $f(4/5)=1/17$ . The poles at $\pm i/5$ make the high derivatives large, and the equispaced Lebesgue constant

\Lambda_n\sim\frac{2^{n+1}}{e\, n\ln n}

lets $p_n$ leave a good comparison polynomial by an exponential factor. Weierstrass still supplies some sequence in $\mathcal{P}_n$ that converges to $f$ uniformly. The equispaced selection is the one that diverges.

The uniform errors below continue that example and set the clamped cubic spline of this chapter beside it, on the same nodes. Two significant figures are enough to see the split.

$n$	uniform error of $p_n$	uniform error of the cubic spline
$8$	$1.05$	$5.6\times 10^{-2}$
$16$	$14$	$3.7\times 10^{-3}$
$32$	$5.1\times 10^{3}$	$6.6\times 10^{-4}$

At $n=32$ the polynomial is off by thousands where $f$ itself never exceeds $1$ . The spline error has dropped below $10^{-3}$ . Adding equispaced nodes makes $p_n$ worse and the spline better.

The split is local flexibility instead of one stiff high-degree curve. Each subinterval of a spline carries its own cubic, so a large derivative near the middle is not forced into a single polynomial that then overshoots both ends. The equispaced $p_n$ has no local piece: every coefficient participates at every $x$ .

Chapter 03's other lever moves the nodes. The zeros of $T_{n+1}$ are the Chebyshev nodes, the monic nodal polynomial there satisfies $\max_{[-1,1]}|\omega|=2^{-n}$ , and the Lebesgue constant grows only like $(2/\pi)\ln(n+1)$ . A comparison error that decays geometrically dominates that logarithm, so for this $f$ the Chebyshev interpolant converges. Those nodes are a choice. When the samples are required to stay where they were measured, the degree on each piece stays fixed and the mesh is what gets refined. That is the construction below. The local bounds in Section 02 are Chapter 03's error formula applied to one subinterval, where $\omega$ is a power of the local spacing.

❌ What Breaks — Raising the degree on a fixed equispaced mesh

The error formula has $(n+1)!$ in the denominator, so a higher degree is expected to win. For the Runge function above, the degree- $8$ interpolant already has uniform error about $1$ , and the degree- $32$ interpolant has uniform error about $5\times 10^{3}$ .

Where it breaks: Chapter 03's asymptotic for $\Lambda_n$ grows exponentially, and the table is that growth made numerical. The factorial in the error formula does not dominate this $f$ on these nodes.

Consequence: a plot that oscillates near the endpoints is not an under-resolved picture of a convergent sequence. The next equispaced degree is a larger oscillation. Convergence has to come from a different space, or from different nodes.

02 · Piecewise Polynomials

Fix a partition $a=x_0\lt x_1\lt \cdots\lt x_n=b$ . A piecewise polynomial of degree at most $d$ is a function whose restriction to each $[x_i,x_{i+1}]$ is a polynomial of degree at most $d$ . The pieces are independent until continuity requirements glue them. The picture is many short polynomials taped together at the knots: on each open subinterval the formula is an ordinary polynomial, and neighboring pieces meet, if they meet, only at the shared knot.

Definition — Continuity of derivatives

A function $g$ on $[a,b]$ lies in $C^{k}$ when $g,g',\ldots,g^{(k)}$ exist and are continuous on $[a,b]$ . Matching values at the interior nodes puts a piecewise polynomial in $C^{0}$ . Matching values and first derivatives puts it in $C^{1}$ . Each extra derivative that is required to match is one linear condition per interior node, and it spends degrees of freedom that could otherwise have fitted the data.

Plain language: lying in $C^{k}$ means the function and its first $k$ derivatives exist and do not jump. At a knot, $C^{0}$ matches the value and $C^{1}$ matches the value and the slope. $C^{2}$ matches value, slope, and bend, where the bend is the second derivative. A corner is a joint that matched the value and missed the slope. Each extra match is one linear condition at that knot, paid for out of coefficients that could otherwise have fitted the data.

The piecewise-linear interpolant is the case $d=1$ with only values matched. It lies in $C^{0}$ and has a corner at each interior node, where the slope jumps from $\delta_{i-1}$ to $\delta_i$ . On a single subinterval the degree- $1$ case of Chapter 03's error formula gives, for some $\xi$ in that subinterval,

f(x)-\ell(x)=\frac{f''(\xi)}{2}(x-x_i)(x-x_{i+1}).

The quadratic factor $(x-x_i)(x-x_{i+1})$ has absolute value at most $h_i^{2}/4$ , so

|f(x)-\ell(x)|\leq \frac{1}{8}h_i^{2}\,\|f''\|_\infty.

The uniform error on the whole interval is $O(h^{2})$ when $f\in C^{2}$ and $h=\max h_i$ . The power of $h$ is local: refining one subinterval improves the error on that subinterval, and the formula on a distant subinterval does not contain that node.

Degree $2$ is a trap if the goal is $C^{2}$ . A piecewise quadratic has $3n$ coefficients. Continuity of the function, the first derivative, and the second derivative at the $n-1$ interior nodes imposes $3(n-1)$ conditions and leaves $3n-3(n-1)=3$ free parameters. Those three parameters are exactly the global polynomials of degree at most $2$ : once $s''$ is continuous and each piece has constant second derivative, $s''$ is the same constant on every piece, and $s$ is one parabola. Every $C^{2}$ piecewise quadratic on the partition is a single global quadratic. Cubics are the lowest degree at which $C^{2}$ piecewise polynomials form a larger space than the global polynomials of that degree.

A cubic Hermite piece makes the local comparison precise. On $[x_i,x_{i+1}]$ , the unique cubic that matches $f$ and $f'$ at both endpoints has error

f(x)-H_i(x)=\frac{f^{(4)}(\xi)}{24}(x-x_i)^{2}(x-x_{i+1})^{2},

and $(x-x_i)^{2}(x-x_{i+1})^{2}\leq h_i^{4}/16$ , so the uniform error on the piece is at most $h_i^{4}\,\|f^{(4)}\|_\infty/384$ . That is an $O(h^{4})$ bound, two orders past piecewise linear, and each piece is determined by its own endpoint data. The price is the derivatives $f'(x_i)$ at every node. A cubic spline pays a different price: it asks only for values, plus two end conditions, and it recovers the interior derivatives from a linear system. The error constant grows from $1/384$ to $5/384$ , which Section 06 records, and the power of $h$ stays $4$ when the end conditions agree with $f$ .

Global dependence with local influence

Every moment of a cubic spline depends on every data value, because the linear system of Section 05 is irreducible: each interior row ties three consecutive moments, so the chain runs from the first subinterval to the last. The inverse of a strictly diagonally dominant tridiagonal matrix has entries that decay geometrically away from the diagonal. Changing $y_k$ moves $M_i$ by a factor that shrinks geometrically in $|i-k|$ . The coupling is global, and the influence of one sample is local. A global polynomial has no such decay: each Lagrange weight $\ell_i$ is a degree- $n$ polynomial and feels every node at full strength.

03 · The Cubic Spline

Definition — Cubic spline interpolant

Let $a=x_0\lt \cdots\lt x_n=b$ and let $y_0,\ldots,y_n$ be given. A cubic spline interpolant is a function $s$ such that

on each $[x_i,x_{i+1}]$ , $s$ coincides with a polynomial of degree at most $3$ ;
$s(x_i)=y_i$ for every $i$ ;
$s\in C^{2}[a,b]$ .

The third derivative is then piecewise constant, with a possible jump at each interior node. Two further scalar conditions, imposed at the ends, are required before $s$ is unique. Those conditions are the subject of Section 04.

Plain language: tape one cubic onto each gap between consecutive knots, force every piece through the given values, and require value, slope, and bend to match at each interior knot. That is a $C^{2}$ piecewise cubic through the data. The third derivative is still allowed to jump. Two end numbers remain free, so many such curves fit the same points until Section 04 spends those two numbers.

The count that forces the two end conditions is worth doing in coefficients. There are $n$ subintervals and $4$ coefficients on each, hence $4n$ unknowns.

Setting the left-hand and right-hand values on each subinterval equal to the prescribed data is $2n$ conditions. At an interior node both one-sided values are set equal to the same $y_i$ , so $s$ is continuous there as soon as it interpolates.
Continuity of $s'$ at the $n-1$ interior nodes is $n-1$ conditions.
Continuity of $s''$ at those nodes is $n-1$ conditions.

The total is $2n+2(n-1)=4n-2$ . Two degrees of freedom remain, for any $n\geq 1$ and any strictly increasing nodes.

The same deficit appears from the other direction. The vector space of all $C^{2}$ piecewise cubics on the partition, before interpolation, has dimension $4n-3(n-1)=n+3$ . Interpolation at $n+1$ nodes imposes $n+1$ linear conditions and leaves $(n+3)-(n+1)=2$ parameters. Both counts are the statement that a cubic spline interpolant is a two-dimensional affine family until the ends are tied down.

04 · End Conditions

The two free parameters are fixed by two linear conditions. Three choices cover the cases used in analysis. Each one produces a square system for the moments, and the first two are the systems proved nonsingular in Section 05.

Definition — Natural, clamped, and not-a-knot ends

Natural. $s''(x_0)=s''(x_n)=0$ , that is $M_0=M_n=0$ .
Clamped, also called complete. The end slopes are prescribed: $s'(x_0)=d_0$ and $s'(x_n)=d_n$ . When $s$ approximates a known $f$ , the accurate choice is $d_0=f'(a)$ and $d_n=f'(b)$ .
Not-a-knot. The third derivative is required to be continuous at $x_1$ and at $x_{n-1}$ . Equivalently $(M_1-M_0)/h_0=(M_2-M_1)/h_1$ and $(M_n-M_{n-1})/h_{n-1}=(M_{n-1}-M_{n-2})/h_{n-2}$ . On a uniform mesh those relations are $M_0-2M_1+M_2=0$ and $M_{n-2}-2M_{n-1}+M_n=0$ .

Plain language: a natural end is zero bend at the ends, so $s''(a)=s''(b)=0$ . A clamped end is prescribed slopes at the ends: $s'(a)$ and $s'(b)$ are data you supply, and the accurate supply is $f'(a)$ and $f'(b)$ when those derivatives are known. Not-a-knot refuses a jump in the third derivative at the first and last interior knots, so each outer pair of pieces is one cubic rather than two.

The name "natural" is variational, and the identity is proved in Section 05. Among all $C^{2}$ interpolants of the data, the natural spline minimizes $\int_a^b (g'')^{2}\,dx$ . The boundary term produced by integration by parts vanishes exactly when $g''$ vanishes at the endpoints, which is why those conditions, and no others, fall out of the unconstrained minimization. They are natural for the energy. They agree with a particular $f$ only when $f''(a)=f''(b)=0$ .

Clamped conditions are the ones that match a function whose end slopes are known. The cubic $f$ itself, restricted to the partition, is a clamped spline for its own values and its own end slopes. Uniqueness then says the clamped interpolant of a polynomial of degree at most $3$ is that polynomial. Nothing similar holds for the natural spline and a quadratic: $x^{2}$ has second derivative $2$ , which is not the natural boundary value $0$ .

Not-a-knot is the closure to use when end slopes are unknown and the energy boundary condition $s''=0$ is unmotivated. Continuity of $s'''$ at $x_1$ means the cubics on $[x_0,x_1]$ and on $[x_1,x_2]$ agree through order $3$ at $x_1$ . Their difference is a polynomial of degree at most $3$ with a zero of order $4$ , so the difference is identically zero: one cubic covers $[x_0,x_2]$ . The same reading applies at $x_{n-1}$ . For $f\in C^{4}$ the not-a-knot interpolant has the same $O(h^{4})$ uniform rate as the clamped interpolant. The diagonal-dominance proof in Section 05 covers the natural and clamped rows. The not-a-knot rows replace the two end equations; for distinct nodes that square system is nonsingular as well.

❌ What Breaks — Expecting every cubic spline to reproduce cubics

A polynomial of degree at most $3$ is a cubic on each subinterval, interpolates itself, and lies in $C^{2}$ . It is therefore some cubic spline interpolant. The natural end condition $s''(a)=s''(b)=0$ selects a different member of that family whenever $f''(a)$ or $f''(b)$ is nonzero.

Where it breaks: uniqueness holds inside one set of end conditions. The cubic $f$ satisfies the clamped conditions with $d_0=f'(a)$ and $d_n=f'(b)$ . It satisfies the natural conditions only when its second derivative already vanishes at both ends. On nodes $0,1/2,1$ , the natural interpolant of $x^{2}$ has middle moment $3$ , while $(x^{2})''=2$ . Exercise 4.3 computes that moment.

Consequence: reproduction of $\mathcal{P}_3$ is a theorem about the clamped spline with the true end slopes. A natural spline on curved data near the boundary leaves the end error that Section 06 measures as $O(h^{2})$ .

05 · The Moment System

On each subinterval, $s''$ is linear, because $s$ is cubic, and $s''$ is continuous, so the linear function is the interpolant of the endpoint moments:

s''(x)=\frac{x_{i+1}-x}{h_i}M_i+\frac{x-x_i}{h_i}M_{i+1},\qquad x\in[x_i,x_{i+1}].

Integrate twice. The two constants of integration are fixed by $s(x_i)=y_i$ and $s(x_{i+1})=y_{i+1}$ . Differentiating the resulting formula and matching $s'$ from the left and from the right at each interior node produces one equation in three consecutive moments. The algebra is the content of the next block; the equation it reaches is

h_{i-1}M_{i-1}+2(h_{i-1}+h_i)M_i+h_i M_{i+1}=6(\delta_i-\delta_{i-1}),\qquad i=1,\ldots,n-1.

The row is tridiagonal because each interior knot only talks to its neighbors. At $x_i$ the unknowns are $M_{i-1}$ , $M_i$ , and $M_{i+1}$ ; every farther moment is absent from that equation. The chain still carries a message from the first subinterval to the last, one neighbor at a time. Section 02's note is the quantitative form of that relay: the coupling is global, and one sample's influence decays geometrically with distance.

Step-by-step — From a linear second derivative to a tridiagonal row

Integrate $s''$ twice. An antiderivative of $(x_{i+1}-x)/h_i$ is $-(x_{i+1}-x)^{2}/(2h_i)$ , and an antiderivative of $(x-x_i)/h_i$ is $(x-x_i)^{2}/(2h_i)$ . A second integration produces the cubic

s(x)=M_i\frac{(x_{i+1}-x)^{3}}{6h_i}+M_{i+1}\frac{(x-x_i)^{3}}{6h_i}+A_i(x-x_i)+B_i.

The same two integrations give

s'(x)=-M_i\frac{(x_{i+1}-x)^{2}}{2h_i}+M_{i+1}\frac{(x-x_i)^{2}}{2h_i}+A_i.

Fit $A_i$ and $B_i$ to the values. At $x=x_i$ the first cubic term equals $M_i h_i^{2}/6$ and the second vanishes, so $B_i=y_i-M_i h_i^{2}/6$ . At $x=x_{i+1}$ ,

A_i=\delta_i-\frac{h_i}{6}(M_{i+1}-M_i).

Every coefficient of $s$ on this subinterval is now an affine function of $M_i$ and $M_{i+1}$ .

Read $s'$ at the two ends of the subinterval. Substitute the expression for $A_i$ . The endpoint evaluations collapse to

s'(x_i)=\delta_i-\frac{h_i}{3}M_i-\frac{h_i}{6}M_{i+1},

s'(x_{i+1})=\delta_i+\frac{h_i}{6}M_i+\frac{h_i}{3}M_{i+1}.

The coefficient $-h_i/3$ on $M_i$ at the left end is $-h_i/2+h_i/6$ , the sum of the term coming from $s''$ and the term coming from $A_i$ .

Match one-sided derivatives at the interior node $x_i$ . The right-hand derivative on the previous subinterval, written from the second display with the index shifted down by one, equals the left-hand derivative on the current subinterval:

\delta_{i-1}+\frac{h_{i-1}}{6}M_{i-1}+\frac{h_{i-1}}{3}M_i=\delta_i-\frac{h_i}{3}M_i-\frac{h_i}{6}M_{i+1}.

Move the moments to the left and multiply through by $6$ . The coefficient of $M_i$ becomes $2(h_{i-1}+h_i)$ , and the displayed tridiagonal row follows.

The interior rows involve $M_0$ and $M_n$ only in the first and last of them. End conditions replace those two moments, or add equations for them.

For a natural spline, $M_0=M_n=0$ . The unknowns are $M_1,\ldots,M_{n-1}$ , and the system is $(n-1)\times(n-1)$ . The first row loses the $M_0$ term and the last row loses the $M_n$ term.

For a clamped spline the end slopes determine two extra rows, now in the $n+1$ unknowns $M_0,\ldots,M_n$ . From the formula for $s'(x_0)$ on the first subinterval,

2h_0 M_0+h_0 M_1=6(\delta_0-d_0).

From the formula for $s'(x_n)$ on the last subinterval,

h_{n-1}M_{n-1}+2h_{n-1}M_n=6(d_n-\delta_{n-1}).

The interior rows are unchanged and now keep their $M_0$ and $M_n$ terms. The system is $(n+1)\times(n+1)$ .

On a uniform mesh, $h_i=h$ for every $i$ , divide the interior row by $h$ and rewrite $\delta_i-\delta_{i-1}=(y_{i+1}-2y_i+y_{i-1})/h$ :

M_{i-1}+4M_i+M_{i+1}=\frac{6}{h^{2}}(y_{i+1}-2y_i+y_{i-1}).

The coefficient pattern is $1,4,1$ . The right-hand side is six times the second difference of the data, divided by $h^{2}$ . The values $y_i$ enter the interior rows only through that second difference.

Practice — One unequal row

Take an interior node with $h_{i-1}=1$ , $h_i=2$ , and $M_{i-1},M_i,M_{i+1}$ still unknown. Write the numerical coefficients in the moment row, and check that the diagonal coefficient is strictly larger than the sum of the absolute values of the other two.

Example — Three nodes, natural, uniform

Take nodes $0,1,2$ and values $0,1,0$ , with $h=1$ . Then $M_0=M_2=0$ , and the single interior equation is $4M_1=6(0-2+0)=-12$ , so $M_1=-3$ . The data rise and then fall, and the middle moment is negative: the spline is concave down at $x=1$ .

On $[0,1]$ , $B_0=0$ and $A_0=1-(1/6)(-3)=3/2$ , so

s(x)=\frac{3}{2}x-\frac{1}{2}x^{3}.

On $[1,2]$ the same constants produce the translated form

s(x)=1-\frac{3}{2}(x-1)^{2}+\frac{1}{2}(x-1)^{3}.

Both formulas give $s'(1)=0$ , so the first derivative matches, and both give $s''(1)=-3$ . The unique polynomial of degree at most $2$ through the same three points is $p(x)=2x-x^{2}$ . At $x=1/2$ , $s(1/2)=11/16$ and $p(1/2)=3/4=12/16$ . The two interpolants share the data and differ by $1/16$ in the middle of the first subinterval, because $p''(x)=-2$ while the natural condition forces $s''(0)=s''(2)=0$ . With only two subintervals, the end conditions are a large part of the whole set of constraints. The advantage in the Runge table appears when many subintervals share those same two conditions.

Proof — The moment matrix is nonsingular

Consider first the natural system, with rows $i=1,\ldots,n-1$ in the unknowns $M_1,\ldots,M_{n-1}$ . In row $i$ the diagonal entry is $2(h_{i-1}+h_i)$ . The off-diagonal entries that are actually present are $h_{i-1}$ , or $h_i$ , or both. Their absolute sum is at most $h_{i-1}+h_i$ , which is strictly smaller than the diagonal because every spacing is positive. The matrix is strictly diagonally dominant.

Suppose $A\mathbf{v}=\mathbf{0}$ and $\mathbf{v}\neq\mathbf{0}$ . Scale so that $|v_k|=\max_j|v_j|=1$ . The $k$ th equation reads $a_{kk}v_k=-\sum_{j\neq k}a_{kj}v_j$ , hence

|a_{kk}|=|a_{kk}v_k|\leq\sum_{j\neq k}|a_{kj}|\,|v_j|\leq\sum_{j\neq k}|a_{kj}|\lt |a_{kk}|,

which is impossible. Thus the only solution of the homogeneous system is zero, and the natural moment matrix is invertible. A solution $(M_i)$ exists and is unique. The formulas for $A_i$ and $B_i$ then determine $s$ on every subinterval.

For the clamped system the unknowns include $M_0$ and $M_n$ . The first row has diagonal $2h_0$ and a single off-diagonal entry $h_0$ . The last row has diagonal $2h_{n-1}$ and a single off-diagonal entry $h_{n-1}$ . Every interior row is the full three-term row, whose diagonal $2(h_{i-1}+h_i)$ strictly exceeds $h_{i-1}+h_i$ . Strict diagonal dominance applies to every row, and the same argument gives uniqueness.

Proof — The natural spline minimizes bending energy

Let $s$ be the natural cubic spline interpolant, and let $g\in C^{2}[a,b]$ be any other function with $g(x_i)=y_i$ for every $i$ . Set $z=g-s$ , so $z(x_i)=0$ . Expand

\int_a^b (g'')^{2}\,dx=\int_a^b(s'')^{2}\,dx+\int_a^b(z'')^{2}\,dx+2\int_a^b s''z''\,dx.

Integrate the cross term by parts on each subinterval. The piecewise-constant third derivative satisfies $\int_{x_i}^{x_{i+1}} s''' z'\,dx=s'''\big(z(x_{i+1})-z(x_i)\big)=0$ . The boundary terms at interior nodes cancel because $s''$ and $z'$ are continuous: each interior node contributes $s''(x_i)z'(x_i)$ from the left piece and the negative of the same quantity from the right piece. The remaining ends are $s''(b)z'(b)-s''(a)z'(a)=0$ , because $s$ is natural. The cross term vanishes, and

\int_a^b(g'')^{2}\,dx=\int_a^b(s'')^{2}\,dx+\int_a^b(z'')^{2}\,dx\geq\int_a^b(s'')^{2}\,dx.

Equality holds precisely when $z''\equiv 0$ . Then $z$ is linear, and $z(a)=z(b)=0$ forces $z\equiv 0$ . So the minimizer is unique, and it is $s$ . The same expansion with a clamped spline uses $z'(a)=z'(b)=0$ to kill the boundary term, and the clamped spline minimizes the energy among interpolants with those prescribed end slopes.

On a uniform mesh the natural matrix, after the division by $h$ that produces the pattern $1,4,1$ , is the symmetric Toeplitz matrix $A$ with $4$ on the diagonal and $1$ on the off-diagonals. If the system has $m=n-1$ unknowns, the eigenvalues are

\lambda_k=4+2\cos\frac{k\pi}{m+1},\qquad k=1,\ldots,m.

To see it, fix $\theta=k\pi/(m+1)$ and set $v_j=\sin(j\theta)$ for $j=1,\ldots,m$ . The sine addition formula gives $\sin((j-1)\theta)+\sin((j+1)\theta)=2\sin(j\theta)\cos\theta$ , so

v_{j-1}+4v_j+v_{j+1}=(4+2\cos\theta)\,v_j.

The fictitious values $v_0=\sin 0=0$ and $v_{m+1}=\sin(k\pi)=0$ are exactly the missing neighbors at the two ends of $A$ , so $A\mathbf{v}=\lambda_k\mathbf{v}$ with $\lambda_k=4+2\cos\theta$ . The angles $k\pi/(m+1)$ lie in $(0,\pi)$ , and the cosine ranges through a proper subset of $(-1,1)$ . Every $\lambda_k$ lies in $(2,6)$ . The $2$ -norm condition number $\lambda_{\max}/\lambda_{\min}$ is therefore strictly less than $3$ , for every $m$ . A relative perturbation of the right-hand side moves the moment vector by a relative amount less than three times as large. The amplification stays bounded as $n$ grows.

What does grow as $h$ shrinks is the right-hand side itself. Absolute noise of size $\varepsilon$ in the values $y_i$ produces a second difference of size about $\varepsilon$ , and the uniform equation divides by $h^{2}$ . Moments inherit noise of size about $\varepsilon/h^{2}$ . That factor is the conditioning of a second derivative estimated from samples. Chapter 01 separates a well-conditioned map from a rounding error that a later operation can amplify; here the tridiagonal map stays well-conditioned, and the amplification sits in forming $(\delta_i-\delta_{i-1})/h$ . Chapter 05 studies that amplification for difference quotients directly.

The contrast with $p_n$ is the monomial Vandermonde on equispaced nodes, whose $2$ -norm condition number grows exponentially with $n$ . Even before Runge's divergence of the function values, the coefficients of $p_n$ in the monomial basis are an unstable encoding of the samples. The moment vector is a stable one. Stability of the encoding is a separate fact from smallness of $\|f-s\|_\infty$ : a well-conditioned system can still be the exact system for a crude approximation. Section 06 is about the approximation.

06 · Error against a Global Polynomial

The local Hermite cubic of Section 02, which is allowed to use $f'$ at every node, has uniform error at most $h^{4}\,\|f^{(4)}\|_\infty/384$ . The clamped spline uses $f'$ only at the two ends and determines every interior slope from the moment system. The classical bound, due to Hall and Meyer, says the loss is a factor $5$ in the constant and nothing in the power of $h$ .

Theorem — Clamped cubic spline error

Let $f\in C^{4}[a,b]$ , let $h=\max_i h_i$ , and let $s$ be the clamped cubic spline interpolant of $f$ at the nodes with $s'(a)=f'(a)$ and $s'(b)=f'(b)$ . Then

\|f-s\|_\infty\leq\frac{5}{384}\,h^{4}\,\|f^{(4)}\|_\infty.

The same smoothness gives $\|f^{(r)}-s^{(r)}\|_\infty=O(h^{4-r})$ for $r=0,1,2$ . In particular $s'$ approximates $f'$ to order $h^{3}$ . Each differentiation of the error costs one power of $h$ .

Plain language: with the true end slopes, the widest gap $h$ controls the error, and the error is at most a fixed multiple of $h^{4}$ times the size of $f^{(4)}$ . Halving every spacing multiplies that bound by $1/16$ . The factor $5$ in $5/384$ is the surcharge for recovering interior slopes from values alone; the Hermite cubic of Section 02, which is given those slopes, has constant $1/384$ and the same power of $h$ . Each derivative of the error costs one power of $h$ , so slopes are order $h^{3}$ and bends are order $h^{2}$ .

The constant is not proved here; the proof is a Peano-kernel comparison between $s$ and the piecewise Hermite cubic. The power $h^{4}$ is the part the applications use. Halving every spacing multiplies the bound by $1/16$ . Extra smoothness past $C^{4}$ does not raise the power. A cubic piece has a fourth derivative equal to zero, so the error expansion stops at the fourth derivative of $f$ . Analyticity improves the constant $\|f^{(4)}\|_\infty$ relative to a merely $C^{4}$ function, and it does not turn $O(h^{4})$ into a geometric rate. Geometric convergence requires the degree to grow, which is the global-polynomial regime, or it requires the spline degree itself to grow.

The natural end condition does not meet the hypotheses of the theorem unless $f''(a)=f''(b)=0$ . Forcing $M_0=0$ when $f''(a)$ is a nonzero constant is an $O(1)$ error in the second derivative at the endpoint. Integrated twice across a subinterval of length $h$ , an $O(1)$ moment error becomes an $O(h^{2})$ error in the function. The uniform norm sees that end layer, so the natural spline is $O(h^{2})$ in general. On subintervals bounded away from the ends the influence of the wrong moment decays geometrically in the number of nodes, and the interior error returns to $O(h^{4})$ . If $f''(a)=f''(b)=0$ , the natural condition is the true one and the fourth-order bound is recovered.

Example — $e^{x}$ on $[0,1]$, two end conditions

Let $f(x)=e^{x}$ on $[0,1]$ , so $f''=f$ and $f''(0)=1$ , $f''(1)=e$ , neither of which is zero. Uniform errors, two significant figures:

intervals $n$	natural spline	clamped spline
$4$	$8.2\times 10^{-3}$	$2.6\times 10^{-5}$
$8$	$2.1\times 10^{-3}$	$1.7\times 10^{-6}$
$16$	$5.2\times 10^{-4}$	$1.1\times 10^{-7}$
$32$	$1.3\times 10^{-4}$	$6.7\times 10^{-9}$

Doubling $n$ multiplies the natural error by about $1/4$ and the clamped error by about $1/16$ . Those are the ratios of $h^{2}$ and of $h^{4}$ . At $n=8$ the Hall–Meyer bound is $(5/384)(1/8)^{4}e\approx 8.6\times 10^{-6}$ , which sits above the clamped error $1.7\times 10^{-6}$ . The natural error at that same $n$ is about $2\times 10^{-3}$ , a hundred times larger than the clamped error, and its maximum lies next to the endpoint.

The companion function $\sin(\pi x)$ on $[0,1]$ has second derivative $-\pi^{2}\sin(\pi x)$ , which vanishes at both ends. Its natural spline then drops by a factor about $16$ when $n$ goes from $16$ to $32$ : the uniform errors are about $3.9\times 10^{-6}$ and $2.4\times 10^{-7}$ . The end condition decides the power of $h$ .

Put the two regimes next to each other. For the Runge function with equispaced nodes, Section 01 shows $p_n$ diverging while the cubic-spline error falls below $10^{-3}$ . The clamped theorem supplies the fourth-power rate; for this $f$ the natural and clamped errors agree to the digits in the table, because the large fourth derivative sits in the interior and $f''(\pm 1)$ is only about $0.21$ . For $e^{x}$ , a global polynomial of modest degree is already an excellent uniform approximation: $e^{x}$ is entire, so equispaced interpolation on $[0,1]$ converges geometrically, and a cubic spline remains $O(h^{4})$ . The spline is the accurate tool when the nodes are prescribed and numerous and the equispaced element of $\mathcal{P}_n$ is divergent. The global polynomial is the accurate tool when the degree may grow and either the nodes may be placed at the Chebyshev zeros or $f$ is entire, so that a geometric rate is available. Extra smoothness of $f$ , past $C^{4}$ , leaves a cubic spline at the same power of $h$ .

Example — A discount function and the forward it induces

Let $P(t)$ be a discount factor observed at maturities $t_i$ , and let $s$ interpolate those values. Wherever $s$ is nonzero and differentiable, the instantaneous forward is the logarithmic derivative

f(t)=-\frac{s'(t)}{s(t)}.

Continuity of $f$ needs continuity of $s'$ . A piecewise-linear interpolant of $P$ has jumps in slope at the maturities, so the forward jumps. A cubic spline lies in $C^{2}$ , so $s'$ lies in $C^{1}$ and, on any subinterval where $s$ stays positive, the forward lies in $C^{1}$ . The maturities are rarely equally spaced; the moment row of Section 05 is already written with unequal $h_i$ , and strict diagonal dominance did not require equality of the spacings.

The spline does not enforce $s\gt 0$ or $s'\lt 0$ . Positivity of discount factors and positivity of forwards are constraints on the data and on the end conditions, checked after the moments are known. The natural choice $s''(t_0)=s''(t_n)=0$ is the energy boundary condition of Section 05. It is the right condition when that minimization is the one being solved, and it is the wrong match to a discount function whose end curvature is known to be something else. If the end slopes of $P$ are known, the clamped rows are the equations whose hypotheses agree with those slopes. The linear system is the same mathematics as the rest of the chapter.

07 · Exercises

EXERCISE 4.1

Count $4$ coefficients on each of $n$ subintervals. Values contribute $2$ conditions per subinterval. Each of $s'$ and $s''$ contributes one condition per interior node. The natural system drops $M_0$ and $M_n$ ; the clamped system keeps them and adds two rows.

There are $4n$ coefficients. Matching both endpoint values on every subinterval contributes $2n$ conditions and already forces continuity of $s$ at interior nodes. Continuity of $s'$ contributes $n-1$ conditions, and continuity of $s''$ contributes $n-1$ more. The sum is $4n-2$ , so two conditions remain for the ends.

For $n=5$ there are $20$ coefficients and $18$ conditions before the ends are fixed. The natural system is $4\times 4$ , in the unknowns $M_1,M_2,M_3,M_4$ . The clamped system is $6\times 6$ , in the unknowns $M_0,\ldots,M_5$ . The dimension count for the space of $C^{2}$ piecewise cubics gives the same deficit: dimension $n+3=8$ , interpolation imposes $n+1=6$ conditions, and $2$ parameters remain.

For a cubic spline on $n$ subintervals, count the polynomial coefficients and the conditions coming from values, from continuity of the first derivative, and from continuity of the second derivative. How many conditions are left for the ends? For $n=5$ , state the sizes of the natural and the clamped moment systems.

EXERCISE 4.2

Spacings $h_0=1$ and $h_1=2$ give secants $\delta_0=1$ and $\delta_1=0$ . The single natural equation is $2(h_0+h_1)M_1=6(\delta_1-\delta_0)$ . Then $A_0=\delta_0-(h_0/6)(M_1-M_0)$ and $B_0=y_0$ .

$M_0=M_2=0$ and $2(1+2)M_1=6(0-1)$ , so $6M_1=-6$ and $M_1=-1$ . On $[0,1]$ , $B_0=0$ and $A_0=1-(1/6)(-1)=7/6$ , hence

s(x)=\frac{7}{6}x-\frac{1}{6}x^{3}.

This satisfies $s(0)=0$ and $s(1)=1$ . The one-sided derivative formula at the right end of the first subinterval gives $s'(1)=\delta_0+(h_0/3)M_1=1-1/3=2/3$ . On $[1,3]$ one finds $A_1=-1/3$ and $B_1=5/3$ , and the left-end derivative formula on that piece also equals $2/3$ . The first derivative is continuous at $x=1$ . The diagonal coefficient $6$ is strictly larger than $1+2$ , which is the dominance check for this single row, in agreement with the practice block.

Nodes $0,1,3$ carry values $0,1,1$ . Find the natural moments and the formula for $s$ on $[0,1]$ . Check that the two one-sided first derivatives at $x=1$ agree.

EXERCISE 4.3

A linear function has second derivative $0$ , so it satisfies the natural end conditions and interpolates itself; uniqueness finishes the argument. For $x^{2}$ use $h=1/2$ in the uniform moment equation. For a cubic, compare end conditions with the clamped theorem's hypotheses and invoke uniqueness.

(a) If $f(x)=\alpha+\beta x$ , then $f''\equiv 0$ , so $f$ is a natural cubic spline interpolant of its own samples (each piece is the same degree- $1$ polynomial, which is a cubic with leading coefficients zero). Section 05 proved there is only one natural interpolant, so $s=f$ .

(b) Nodes $0,1/2,1$ , values $0,1/4,1$ , and $h=1/2$ . Then $6/h^{2}=24$ and $y_0-2y_1+y_2=1/2$ , so the right-hand side is $12$ . With $M_0=M_2=0$ one gets $4M_1=12$ and $M_1=3$ . But $f''(1/2)=2$ . The moments differ, so $s\neq f$ . Equivalently, $f''(0)=2\neq 0$ , so $f$ itself violates the natural condition and cannot be the natural interpolant.

(c) Let $f\in\mathcal{P}_3$ , and let $s$ be the clamped interpolant with $d_0=f'(a)$ and $d_n=f'(b)$ . Then $f$ satisfies every requirement in the definition of that clamped spline. Uniqueness forces $s=f$ . The natural end condition lies outside those requirements, which is why (b) can fail for a natural spline of a quadratic.

(a) Show that the natural cubic spline reproduces every polynomial of degree at most $1$ . (b) On the nodes $0,1/2,1$ , compute the natural middle moment of $f(x)=x^{2}$ and compare it with $f''(1/2)$ . (c) Show that the clamped cubic spline, given the true end slopes, reproduces every polynomial of degree at most $3$ .

EXERCISE 4.4

Replace $h$ by $h/2$ in the Hall–Meyer bound. For $e^{x}$ , compare the natural ratio $2.1\times 10^{-3}/5.2\times 10^{-4}$ with $4$ and with $16$ , and check $f''(1)$ against the natural condition. For Runge at $32$ equispaced nodes, read the two errors in Section 01. Geometric decay in the degree beats every fixed power of $1/n$ ; a cubic piece has vanishing fourth derivative, so the spline power stops at $4$ .

(a) $(h/2)^{4}=h^{4}/16$ , and $\|f^{(4)}\|_\infty$ does not depend on the mesh. The bound is multiplied by $1/16$ .

(b) The ratio is about $4.0$ , which is the factor for an $O(h^{2})$ bound when $h$ is halved. Here $f''(1)=e\neq 0$ , so the natural condition $M_n=0$ contradicts $f''$ at the endpoint. The Hall–Meyer bound applies to the clamped spline with the true end slopes. This natural spline falls outside those hypotheses, and the table shows the slower rate.

(c) Chapter 03 gives the Chebyshev nodes a Lebesgue constant of size about $(2/\pi)\ln(n+1)$ . For analytic $f$ on $[-1,1]$ there are comparison polynomials in $\mathcal{P}_n$ whose uniform error decays geometrically, and multiplication by $1+\Lambda_n$ preserves a geometric rate. A clamped cubic spline on a mesh of $n$ subintervals remains $O(h^{4})=O(n^{-4})$ , because each piece has degree $3$ and the Hall–Meyer power stops at $4$ . A geometric sequence eventually lies under every constant times $n^{-4}$ . With nodes free to move, the Chebyshev interpolant is the method that keeps the geometric decay. Raising the piecewise degree is what a spline would need in order to join it.

(d) Section 01 records, at $n=32$ equispaced nodes, a polynomial error of about $5.1\times 10^{3}$ and a cubic-spline error of about $6.6\times 10^{-4}$ . The samples are fixed, so the Chebyshev option in (c) is unavailable. The spline is the accurate interpolant of these samples. The polynomial has left any neighborhood of $f$ .

(a) The clamped bound is $(5/384)\,h^{4}\,\|f^{(4)}\|_\infty$ . If every spacing is halved, by what factor does the bound change? (b) For $e^{x}$ on $[0,1]$ , the natural errors at $8$ and $16$ intervals are about $2.1\times 10^{-3}$ and $5.2\times 10^{-4}$ . Which power of $h$ does that ratio indicate, and why do the hypotheses of the clamped theorem fail for this natural spline? (c) Nodes may be placed anywhere in $[-1,1]$ , and $f$ is analytic there. Explain why a single polynomial at Chebyshev nodes can eventually beat every cubic spline on the uniform error, even though the spline's mesh is also allowed to be refined. (d) The $32$ nodes are required to be equispaced samples of the Runge function in Section 01. Which interpolant is accurate, and what are the two uniform errors?

08 · Summary

Object	Statement
Equispaced $p_n$ on Runge's $f$	uniform error grows with $n$ ; good polynomials still exist
Piecewise linear	$C^{0}$ , corners at the nodes, uniform error $O(h^{2})$
Why cubics	$C^{2}$ piecewise quadratics are exactly the global quadratics
Cubic spline	$C^{2}$ piecewise cubics interpolating the data; two end conditions remain
Moment row	$h_{i-1}M_{i-1}+2(h_{i-1}+h_i)M_i+h_i M_{i+1}=6(\delta_i-\delta_{i-1})$
Natural ends	$M_0=M_n=0$ ; minimizes $\int(g'')^{2}$ ; error $O(h^{2})$ unless $f''$ vanishes at the ends
Clamped ends	prescribed end slopes; reproduces $\mathcal{P}_3$ ; error at most $(5/384)h^{4}\\|f^{(4)}\\|_\infty$
Not-a-knot	$s'''$ continuous at the first and last interior nodes; $O(h^{4})$ for $f\in C^{4}$
Uniform natural matrix	eigenvalues $4+2\cos(k\pi/(m+1))$ in $(2,6)$ , so $\kappa_2\lt 3$
Where the spline wins	many prescribed nodes, especially equispaced, and a $C^{2}$ interpolant is wanted
Where $p_n$ wins	degree may grow and nodes may cluster, so a geometric rate is available

The factor $\varepsilon/h^{2}$ in the moment right-hand side is a second derivative estimated from values. That estimation is differentiation, and its roundoff is the subject of the next chapter.

Next: Chapter 05 — Numerical Differentiation (coming soon). It builds difference quotients for $f'$ and $f''$ from values alone, and it balances their truncation against the rounding model of Chapter 01. The spline derivative $s'$ is one such approximation, of order $h^{3}$ when the clamped theorem applies, and the second-difference term $6(\delta_i-\delta_{i-1})/h$ in the uniform moment equation is a difference quotient already.