Runge's Phenomenon

AUTHOR : ADITH JUSTIN PACHEN

DECEMBER 20, 2024

Background and Motivations

A smooth approximation may be expected when interpolating data, particularly when high-degree polynomials are used but that's not always the case. A surprising behaviour is brought to light by Runge's Phenomenon, first observed by Carl David Tolmé Runge in 1901. Although we might anticipate that a higher degree would result in a better fit, the interpolation can oscillate wildly near the interval's edges as the polynomial degree increases. When evenly spaced points are interpolated over a finite interval, this behaviour is especially prevalent. This key concept must be understood in order to comprehend data over-fitting. One significant example is Runge's Phenomenon, which demonstrates that higher degree polynomials can produce instability that over-fits the data rather than accurately modelling the underlying trend, and that this does not always translate into better interpolation.

This phenomenon has broad implications in numerical analysis and machine learning, where overfitting—a model capturing noise instead of the underlying trend—is a critical challenge. Understanding and addressing Runge's Phenomenon is crucial for ensuring reliable interpolation and model performance [RUN 01] [RUN 02].

Problem Statement

Our goal is to: 1. Understand Runge's Phenomenon and its implications in polynomial interpolation. 2. Demonstrate the phenomenon using Runge's function, given by:

Dataset Description

We will use Runge’s function as our dataset:

The independent variable x will be sampled over the interval [-1, 1] using evenly spaced points for polynomial interpolation.

Code :

Remedies

Alternative Nodes: Chebyshev Points

Chebyshev points cluster more densely near the interval's edges, reducing the oscillations observed with equidistant points [RUN 04] [RUN 05]. By avoiding the large oscillations that are common with evenly spaced nodes and minimising the interpolation error, they achieve error bounds for polynomial interpolation that are almost optimal.

Code Implementation for Chebyshev points :

Piecewise Linear Interpolation

Although the method is simple to compute and apply and avoids high-degree polynomial oscillations by fitting straight-line segments between data points, it might not capture smooth data variations. Discontinuous derivatives at the segment boundaries [RUN 06].

Cubic Spline Interpolation

This method uses cubic polynomials to create a smooth curve without oscillations, suitable for functions with varying curvature, but requires solving linear equations to compute spline coefficients. Computationally more expensive than linear interpolation [RUN 06].

Radial Basis Function (RBF) Interpolation

Using radial basis functions such as Gaussian, linear, or cubic kernels for interpolation, this method provides smooth interpolation with user-defined kernel functions and flexibility in handling scattered data in higher dimensions. Computationally intensive for large datasets due to dense matrix operations [RUN 05] [RUN 06].

Least Squares Polynomial Fitting

This method reduces overfitting by not forcing the curve through all points and is suitable for noisy data. May not capture all data trends if the polynomial degree is too low. [RUN 05]

Fourier Series Interpolation

The advantages of this method include its suitability for periodic data and its ability to provide spectral accuracy for smooth functions. Not suitable for non-periodic data without modifications [RUN 06].

Results

The following results demonstrate the behavior of polynomial interpolation, Runge's Phenomenon, and the effectiveness of Chebyshev nodes and alternative interpolation methods.

Polynomial Interpolation with Equally Spaced Points

Large oscillations are observed near the edges as the degree of the polynomial increases. This confirms the instability of polynomial interpolation with equidistant points, as predicted by Runge's Phenomenon [RUN 01] [RUN 02].

Polynomial Interpolation with Chebyshev Points

Oscillations are significantly reduced, and the approximation is much closer to the true function. Chebyshev points ensure that the polynomial interpolant converges uniformly to the target function [RUN 04] [RUN 05].

Piecewise Linear and Spline Interpolation

Piecewise Linear: Produces a continuous but non-smooth approximation.

Cubic Spline: Provides a smooth curve, better capturing the true function’s shape without oscillations [RUN 06].

Radial Basis Function Interpolation

Achieves smooth and accurate interpolation for scattered data but may be slower for larger datasets [RUN 05] [RUN 06].

Fourier Series Interpolation

Provides excellent results for periodic data but may introduce artifacts (Gibbs' Phenomenon) near discontinuities [RUN 06].

Conclusion

Runge's Phenomenon: Polynomial interpolation with equidistant points leads to significant oscillations, particularly near the interval edges [RUN 01] [RUN 02].

Chebyshev Points: Using Chebyshev nodes effectively mitigates oscillations, providing a more accurate polynomial approximation [RUN 04] [RUN 05].

Alternative Methods: Piecewise linear, cubic spline, radial basis function, and Fourier series interpolation offer various advantages depending on the data and application [RUN 06].

General Understanding:

Appropriate node selection and alternative techniques are essential for stable and accurate approximations. Interpolation using high-degree polynomials is not always the best option. Appropriate node selection and alternative techniques are essential for stable and accurate approximations. Runge's Phenomenon demonstrates that interpolation with increasing polynomial degree can result in significant oscillations, especially near the edges of an interval. This behaviour exemplifies the risk of over-fitting, where a model fits training data too closely but performs poorly on unseen data. The oscillatory behaviour is reduced and the function is more accurately and steadily approximated when Chebyshev nodes are used instead of evenly spaced points. Through edge smoothing, this technique reduces the likelihood of over-fitting.

Bibliography

1. [RUN 01] Runge, C. (1901). On the Theory of Interpolation. Mathematische Annalen.

2. [RUN 02] Trefethen, L. N. (2013). Approximation Theory and Approximation Practice. SIAM.

3. [RUN 03] Boyd, J. P., & Ong, J. R. (2009). Exponentially-Convergent Strategies for Defeating the Runge Phenomenon. Communications in Computational Physics.

4. [RUN 04]Chebyshev, P. L. (1859). On Interpolation by the Method of Least Squares. Journal of Applied Mathematics.

5. [RUN 05] Tikhonov, A. N. (1943). Regularization of Ill-Posed Problems. Soviet Mathematics.

6. [RUN 06] de Boor, C. (2001). A Practical Guide to Splines. Springer.