Where can we find a proof that it is impossible to satisfy all three properties with cubic splines? Is it possible to satisfy all three properties with other kinds of splines? All the examples we saw in class failed to satisfy all three properties.
kmcrane
The proof is basically already there in the construction of natural splines: we wrote down the necessary conditions for the spline to be C2 and interpolating, and found that the degrees of freedom are related in a non-local way. Though I suppose this no free lunch "theorem" does need the extra admonition that we are forcing the curve to interpolate the data at knot locations. It is perhaps possible that there is a cubic, local, C2 scheme that interpolates at non-knot locations. (So to be more precise: there is "no free lunch" for locality, C2, and interpolating at knots, as demonstrated by the example of natural splines.)
By the way, you should always be wary of "no free lunch" theorems for precisely the reasons you raised here: they depend critically on the precise definitions of the desired properties. For instance, there is a no free lunch theorem for discrete Laplace operators which critically depends on the fact that a "discrete Laplace operator" uses only the immediate neighbors of a given vertex. Nobody knows what happen if, say, you use a larger neighborhood to define the Laplacian. Likewise, there is a "no free lunch" theorem that says you can't have a time integrator for ODEs that simultaneously preserves energy, momentum, and something called the symplectic form, but the critical assumption here is that you're always taking time steps of the same size; if you lift this restriction, then you can in principle conserve everything, as discussed in this paper. So, "no free lunch" theorems are very useful for understanding what can/can't be done with simple schemes, and good motivation for pursuing more interesting and/or complicated schemes. (Perhaps this conversation will motivate you to find an interesting new cubic spline interpolant? :-))
Where can we find a proof that it is impossible to satisfy all three properties with cubic splines? Is it possible to satisfy all three properties with other kinds of splines? All the examples we saw in class failed to satisfy all three properties.
The proof is basically already there in the construction of natural splines: we wrote down the necessary conditions for the spline to be C2 and interpolating, and found that the degrees of freedom are related in a non-local way. Though I suppose this no free lunch "theorem" does need the extra admonition that we are forcing the curve to interpolate the data at knot locations. It is perhaps possible that there is a cubic, local, C2 scheme that interpolates at non-knot locations. (So to be more precise: there is "no free lunch" for locality, C2, and interpolating at knots, as demonstrated by the example of natural splines.)
By the way, you should always be wary of "no free lunch" theorems for precisely the reasons you raised here: they depend critically on the precise definitions of the desired properties. For instance, there is a no free lunch theorem for discrete Laplace operators which critically depends on the fact that a "discrete Laplace operator" uses only the immediate neighbors of a given vertex. Nobody knows what happen if, say, you use a larger neighborhood to define the Laplacian. Likewise, there is a "no free lunch" theorem that says you can't have a time integrator for ODEs that simultaneously preserves energy, momentum, and something called the symplectic form, but the critical assumption here is that you're always taking time steps of the same size; if you lift this restriction, then you can in principle conserve everything, as discussed in this paper. So, "no free lunch" theorems are very useful for understanding what can/can't be done with simple schemes, and good motivation for pursuing more interesting and/or complicated schemes. (Perhaps this conversation will motivate you to find an interesting new cubic spline interpolant? :-))