Suppose we have real numbers $x_1 < \cdots < x_n$ and $v_1, \ldots, v_n$. Let $f$ be the natural cubic spline such that $f(x_i) = v_i$. Is there a simple explicit bound on $\|f''\|_\infty$ in terms of $n, x_i, v_i$?
One can certainly be derived from the definition of the spline, but I thought I'd ask in case there was a nice reference somewhere, and before I bash through the algebra and clutter up my paper!
The first thing to notice is that the second derivative of a cubic spline is itself a degree-1 spline i.e., a piecewise linear function. Therefore, the maximal $|f''|$ value is attained at one of the $x_i$ values (the knots).
We denote by $k_i$ for $i=1,.. ,n-1$ the second derivatives at the knots $x_0,..,x_n$, where $k_0$ and $k_n$ are zero by the spline natural condition.
The second derivatives $k_i$ are then the solution of the following tri-diagonal system of linear equations:
$$ (x_{i-1}-x_i) k_{i-1} + 2(x_{i-1} - x_{i+1}) k_i + (x_i - x_{i+1}) k_{i+1} = 6 (\frac{v_{i-1} - v_i}{x_{i-1} - x_i} - \frac{v_i - v_{i+1}}{x_i - x_{i+1}}) $$
Or in matrix notation we have: $$ A k = b $$
Where the matrix $A$ is:
$$ \left[ {\begin{array}{ccc} 2(x_{0} - x_{2}) & (x_1 - x_{2}) & 0 & ... & 0 \\ (x_{1}-x_2) & 2(x_{1} - x_{3}) & (x_2 - x_{3}) & 0 & ... \\ & & ... & & \\ & (x_{i-1}-x_i) & 2(x_{i-1} - x_{i+1}) & (x_i - x_{i+1}) k_{i+1} & \\ & & ... & & \\ ... & 0 &(x_{n-3}-x_{n-2}) & 2(x_{n-3} - x_{n-1}) & (x_{n-2} - x_{n-1}) \\ 0 &... & 0 &(x_{n-2}-x_{n-1}) & 2(x_{n-2} - x_{n}) \\ \end{array} } \right] $$
the vector $b$ is:
$$ \left[ {\begin{array}{c} 6 (\frac{v_{0} - v_1}{x_{0} - x_1} - \frac{v_1 - v_{2}}{x_1 - x_{2}}) \\ .. \\ 6 (\frac{v_{i-1} - v_i}{x_{i-1} - x_i} - \frac{v_i - v_{i+1}}{x_i - x_{i+1}}) \\ .. \\ 6 (\frac{v_{n-2} - v_{n-1}}{x_{n-2} - x_{n-1}} - \frac{v_{n-1} - v_{n}}{x_{n-1} - x_{n}}) \\ \end{array} } \right] $$
and the unknown vector $k$:
$$ \left[ {\begin{array}{c} k_1 \\ .. \\ k_i \\ .. \\ k_{n-1} \end{array} } \right] $$
These equations (or variants of them) can be derived in several ways (for example, see here or here). However, I believe the most straightforward way to attain them in our context is in constructions of cubic splines that begin by integrating the second derivative constraints. Examples of such a construction can be found, for example, here and here (which is where the above formulation was taken from).
Now, the explicit formula for $|f''|_\inf$ becomes: $$ || A^{-1} b ||_\inf = \max_i (A^{-1} b) $$
The above is the exact solution (not a bound).
However, if you wish to simplify the expression further, we can bound the second derivative using bounds on the norm of the matrix $A^{-1}$.
Specifically, $|f''|_\inf \leq |A^{-1}|_\inf |b|_\inf$. Furthermore, $A$ in our problem is a diagonally dominant matrix. Therefore, we can use the Varah bound to bound its norm. The Varah bound states: $$ ||A^{-1}||_\inf < \frac{1}{\min_i (|a_{i,i}| - \sum_{j \neq i} |a_{i,j}|)} $$
Note that (except for the first and last row) for the tri-diagonal entries of our $A$ matrix, we have $|a_{i,i}| / 2 = (|a_{i, i-1}| + |a_{i, i+1}|)$, so the Varah bound just becomes: $$ ||A^{-1}||_\inf < \frac{1}{\min_i (|a_{i,i}|/2, |a_{1,1}|-|a_{1, 2}|, |a_{n-1,n-1}|-|a_{n-1, n-2}|)} = \frac{1}{\min_i (|x_{i-1} - x_{i+1}|, 2|x_{0} - x_{2}| - |x_{1} - x_{2}|, 2|x_{n-2} - x_{n}| - |x_{n-2} - x_{n-1}|)} $$
And we get: $$ |f''|_\inf \leq |A^{-1}|_\inf |b|_\inf \leq \frac{\max_i b_i}{\min_i (|a_{i,i}|/2, |a_{1,1}|-|a_{1, 2}|, |a_{n-1,n-1}|-|a_{n-1, n-2}|)} $$
So, an explicit simple bound on the second derivative of a natural cubic spline is: $$ \frac{\max_i |(6 (\frac{v_{i-1} - v_i}{x_{i-1} - x_i} - \frac{v_i - v_{i+1}}{x_i - x_{i+1}}))|} {\min_i (|x_{i-1} - x_{i+1}|, 2|x_{0} - x_{2}| - |x_{1} - x_{2}|, 2|x_{n-2} - x_{n}| - |x_{n-2} - x_{n-1}|)} $$
This is not necessarily a tight bound as can be seen in the example figures below. The second figure below is a plot of the (piecewise linear) second derivative function of the natural spline from the first figure.
The exact maximal second derivative in this example is 122.3, whereas the bound is 192. The $x$-values taken for this example were $(0, 1, 2, 3, 4, 5, 6)$, and the $v$-values were $(0, 2, 0, 8, 0, 32, 0)$.
