Interpolation and approximation

A degree-n polynomial has exactly n+1 free coefficients, and pinning down n+1 point values uses up exactly that many degrees of freedom — no more, no less — so there is room for one solution and no room for two different ones.

Step 1 (existence). The Lagrange construction $P(x) = \sum_{i=0}^{n} y_i L_i(x)$ with $L_i(x) = \prod_{j\ne i} \dfrac{x-x_j}{x_i-x_j}$ already satisfies $P(x_k)=y_k$ for every $k$, since $L_i(x_k)$ equals $1$ when $i=k$ and $0$ otherwise, so the sum collapses to the single term $y_k \cdot 1 = y_k$. So at least one valid $P$ exists, and each $L_i$ has degree exactly $n$ (a product of $n$ linear factors), so $P$ has degree at most $n$.

Step 2 (suppose two solutions). Suppose $Q$ is any other polynomial of degree at most $n$ with $Q(x_i)=y_i$ for every $i$. Consider the difference $D(x) = P(x) - Q(x)$. Since both $P$ and $Q$ have degree at most $n$, so does $D$.

Step 3 (count the roots of the difference). For every node $x_i$, $D(x_i) = P(x_i)-Q(x_i) = y_i - y_i = 0$. Since there are $n+1$ distinct nodes $x_0, x_1, \dots, x_n$, $D$ has at least $n+1$ distinct roots.

Step 4 (force D to be identically zero). A nonzero polynomial of degree at most $n$ can have at most $n$ roots (each root contributes one linear factor, and a degree-$n$ polynomial cannot contain more than $n$ such factors). Since $D$ has $n+1$ roots, more than its degree allows unless $D$ is the zero polynomial, we conclude $D(x)\equiv0$, i.e. $Q=P$. So the interpolating polynomial found in Step 1 is the only one.

The interpolating polynomial matches f exactly at the nodes but knows nothing about f in between, so the leftover error must vanish at every node — exactly what the product term forces — scaled by a leftover derivative that measures how much f curves beyond what a degree-n polynomial can capture.

Step 1 (a clever auxiliary function). Fix a point $x$ that is not one of the nodes (if it is, the error is trivially $0$). Let $w(t) = \prod_{i=0}^{n} (t - x_i)$ and define the constant $c = \dfrac{f(x)-P(x)}{w(x)}$ (well-defined since $w(x)\ne0$). Define the auxiliary function $g(t) = f(t) - P(t) - c\, w(t)$.

Step 2 (count the roots of g). At every node $x_i$, both $f(x_i)-P(x_i)=0$ (by the interpolation property) and $w(x_i)=0$ (by definition of $w$), so $g(x_i)=0$ for all $n+1$ nodes. Also, by the choice of $c$, $g(x) = f(x)-P(x) - c\,w(x) = f(x)-P(x) - [f(x)-P(x)] = 0$. So $g$ has $n+2$ distinct roots: the $n+1$ nodes plus $x$ itself.

Step 3 (apply Rolle's theorem repeatedly). Between each pair of consecutive roots of $g$ (there are $n+1$ such gaps among $n+2$ roots), Rolle's theorem gives a point where $g'$ vanishes, so $g'$ has at least $n+1$ roots. Repeating this argument on $g', g'', \dots$ loses one root each time a derivative is taken, so after $n+1$ applications, $g^{(n+1)}$ has at least one root $\xi$ in the interval.

Step 4 (differentiate and solve for the error). Since $P$ has degree at most $n$, its $(n+1)$-th derivative is $0$; and $w$ is a monic polynomial of degree $n+1$, so $w^{(n+1)}(t) = (n+1)!$ for every $t$. Differentiating $g$ gives $g^{(n+1)}(t) = f^{(n+1)}(t) - 0 - c\,(n+1)!$, and setting $g^{(n+1)}(\xi)=0$ gives $c = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}$. Recalling $c=\dfrac{f(x)-P(x)}{w(x)}$ and solving for the error gives exactly $f(x) - P(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n} (x - x_i)$.

A single high-degree polynomial through many points tends to wiggle, but stitching together many gentle cubic pieces and only demanding they match up smoothly at the seams gives just enough freedom to fit the data without any wild swings, and the natural boundary conditions supply exactly the two extra equations needed to make the whole system solvable.

Step 1 (unknowns: the second derivatives at the knots). Let $M_i = S''(x_i)$ for $i=0,\dots,n$. The natural boundary conditions fix $M_0=0$ and $M_n=0$ immediately, leaving $n-1$ unknowns $M_1,\dots,M_{n-1}$ to determine.

Step 2 (reconstruct each cubic piece from its M values). On $[x_i,x_{i+1}]$, since $S$ is cubic, $S''$ is linear, so it must be the straight line through $(x_i,M_i)$ and $(x_{i+1},M_{i+1})$. Integrating this linear function twice and fixing the two constants of integration using $S(x_i)=y_i$ and $S(x_{i+1})=y_{i+1}$ determines $S$ completely on that piece, in terms of $M_i, M_{i+1}, y_i, y_{i+1}$ and the spacing $h_i=x_{i+1}-x_i$. So once all the $M_i$ are known, $S$ is fully known.

Step 3 (matching slopes gives a linear system). By construction $S$ and $S''$ are already continuous across each knot. Demanding that the first derivative $S'$ also matches from both sides at each interior knot $x_i$ ($i=1,\dots,n-1$) produces one linear equation per interior knot relating three consecutive unknowns: $h_{i-1} M_{i-1} + 2(h_{i-1}+h_i) M_i + h_i M_{i+1} = 6\left(\dfrac{y_{i+1}-y_i}{h_i} - \dfrac{y_i-y_{i-1}}{h_{i-1}}\right)$. This gives $n-1$ linear equations in the $n-1$ unknowns $M_1,\dots,M_{n-1}$ (using $M_0=M_n=0$).

Step 4 (the system has a unique solution). The coefficient matrix of this system is tridiagonal with diagonal entries $2(h_{i-1}+h_i)$ and off-diagonal entries $h_{i-1}$ and $h_i$; since $2(h_{i-1}+h_i) > h_{i-1}+h_i$ (as all spacings $h_i>0$), the matrix is strictly diagonally dominant, and a strictly diagonally dominant matrix is always invertible. So the linear system for $M_1,\dots,M_{n-1}$ has exactly one solution, and by Step 2 this determines exactly one spline $S$, proving both existence and uniqueness.