11
$\begingroup$

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.

enter image description 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. enter image description here

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?

enter image description here

Improve this question
$\endgroup$
5
  • $\begingroup$ Are you approximating a formula or data? Given a formula, like you have, you can always use more advanced splines where the higher order derivatives are also taken into account. You should also check the fact that the cubic spline minimizes a certain "energy" function. Look at wikipedia en.wikipedia.org/wiki/Spline_interpolation . So in a certain sense, curvature minimization, you can not do any better. An alternate interpretation is that cubic splines were/are used for fitting; not approximating. "Fitting" implies an certain metric to be optimatized. $\endgroup$
    – rrogers
    Mar 14, 2017 at 19:04
  • $\begingroup$ @rrogers, I was thinking an interpolating polynomial would be a better approach when one wants to estimate the function from measured samples and the and the bandwidth of the signal is known to be less than 1/6 of the sample rate. It $\endgroup$
    – Ted Ersek
    Mar 16, 2017 at 1:05
  • $\begingroup$ @TedErsek: One qualitative consideration: by their nature, polynomial functions diverge to $\pm \infty$ as the abscissa variable $\to \infty$. This effect is exacerbated as the polynomial order increases. Note that in your first example, the signal to be approximated is decaying to zero near the end of the interpolation interval; this is incompatible with the asymptotic behavior of the interpolant. The second plot has a steep slope and nonzero values near the edges of the interval, so you get a better approximation. Not very theoretic here, just an observation. $\endgroup$
    – Jason R
    Mar 16, 2017 at 2:36
  • $\begingroup$ @TedErsek As a practical aside addressing Ted Ersek's comment; have you tried rational polynomial approximation. BTW: I have the free copy of a curve formula estimating program from a year ago that really does pretty good. The program went from beta to payment so I don't have the current version. $\endgroup$
    – rrogers
    Mar 16, 2017 at 3:13
  • $\begingroup$ @JasonR I meant to address my last comment to you. Back on topic, In any case, there are en.wikipedia.org/wiki/Chebyshev_polynomials which provide uniform error (min/max) apporximations in polynomials if you know the function. But if you know the function you can always synthesize a "matched filter". $\endgroup$
    – rrogers
    Mar 16, 2017 at 12:22

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.