Quadratic spline with the smallest sum of squares of derivatives

Question

In quadratic spline interpolation, a formula is given and all we really need to do is calculate the values $$S_i'(t_i) = z_i$$ In quadratic spline interpolation specifically, one has a single degree of freedom. Can we have 'zero' degrees of freedom by imposing the new condition: $$ \sum_{i=0}^n z_i^2 \ \text{is a minimum.}\ $$ If so, how would one impose this condition in practice, theoretically or algorithmically? Would one pick $z_0 = 0$, calculate the others, then $z_1 = 0$, calculate the others, ...., then $z_n = 0$, calculate the others, and then pick the solution that give the smallest sum of squares?

Or would one solve for the general, infinite solutions, and then somehow pick the list of possible $z_i$ with the smallest sum of squares? If so, how would this work, exactly, solving for the infinite solutions with $n+1$ unknowns, $n$ equations?

Answer 1

You can set this up as an underdetermined linear system for $z_0,\dots,z_n$, and then pick the solution with the smallest norm. Here's how:

1. Since on the interval $[t_{i-1},t_i]$ the derivative of quadratic spline is linear, the average rate of growth is simply $\frac12(z_{i-1}+z_{i})$. This yields the system of equations $$\frac12(z_{i-1}+z_{i}) = \frac{y_{i}-y_{i-1}}{t_i-t_{i-1}},\quad i=1,\dots, n$$
2. Write the above system as $Az = b$. It's underdetermined: the set of solutions is a line. You want the point of the line $\{z:Az=b\}$ that's closest to $0$. The position vector of this point must be perpendicular to this line, equivalently, perpendicular to $\ker A$.
3. The orthogonal complement of $\ker A$ is the range of $A^T$ (standard fact).
4. So, $z$ must be in the form $z=A^Tw$ for some $w\in \mathbb{R}^n$.
5. Solve the system $AA^Tw=b$ (it has a nonsingular square matrix) and you have $z=A^Tw$ that you want.

Software like Matlab or Scilab offers built-in functions for least square solutions, saving you some of the above steps.