When is cubic spline interpolation better than an interpolating polynomial?

The following plot is a slight variation of an example in a text book. The author used this example to illustrate that an interpolating polynomial over equally spaced samples has large oscillations near the ends of the interpolating interval. Of course cubic spline interpolation gives a good approximation over the whole interval. For years, I thought high order polynomial interpolation over equally spaced samples should be avoided for the reason illustrated here.

However, I recently found many examples of bandlimited signals where a high order interpolating polynomial gives less approximation error than cubic-spline interpolation. Typically an Interpolating polynomial is more accurate over the entire interpolating interval when the sample rate is sufficiently high. This seems to hold when the samples are equally spaced with a sample rate at least 3 times greater than the Nyquist frequency of the signal. Furthermore, the advantage over cubic spline interpolation improves as (sample rate)/(Nyquist frequency) increasees.

As an example, I compare cubic-spline interpolation with an interpolating polynomial for a sine wave with a Nyquist frequency of 2 Hz, and a sample rate of 6.5 Hz. Between the sample points, tthe interpolating polynomial looks exactly the same as the actual signal.

---

Below I compare the error in the two approximations. As with the first example, the polynomial interpolation does worst near the beginning and end of the sample interval. However, the interpolating polynomial has less error than a cubic spline over the whole sample interval. The interpolating polynomial also has less error when extrapolating over a small interval. Did I discover a well known fact? If so, where can I read about it?

Answer

The phenomenon being discussed is Runge's phenomenon.

The maximum absolute value of the $n$th derivative of $\sin(\omega t)$ is $\omega^n$. For Runge's function $\frac{1}{25t^2+1}$ the maximum absolute value of the $n$th (even) derivative is $5^nn!,$ where $n!$ denotes factorial. This is much faster growth. Only if the derivatives grow too fast by increasing $n$, then it is possible that interpolation error diverges as the interpolation order is increased. Exponential in $n$ is not yet too fast. Have a look at: James F. Epperson, On the Runge example, The American Mathematical Monthly, vol. 94, 1987, pp. 329-341.

If a function has only continuous derivatives, then the competing approach, piece-wise polynomial spline interpolation always converges if a small fixed number of its early derivatives are bounded over the interval of interest, see Wikipedia article on linear interpolation as an example.

If both methods converge, then (non-piecewise) polynomial interpolation has the advantage of a higher polynomial degree if many samples are used, and may provide a better approximation, as you saw in your sine example. You may also be interested in L.N Trefethen, Two results on polynomial interpolation in equally spaced points, Journal of Approximation Theory Volume 65, Issue 3, June 1991, Pages 247-260. Quote:

[...] in band-limited interpolation of complex exponential functions $e^{i\alpha x}\, (\alpha \in \mathbb{R}),$ the error decreases to $0$ as $n \to \infty$ if and only if $\alpha$ is small enough to provide at least six points per wavelength.

You have 6.5 samples per wavelength.