Runge's Phenomenon

Author's Name: Mayur Mahesh

Date: 16 / 11 / 2024

1. Background

A key technique in data approximation and numerical analysis is polynomial interpolation, which is used to estimate a function based on discrete number of points. However, interpolation using high-degree polynomials with equally spaced points can result in oscillatory behavior around the interval borders, a phenomenon known as Runge's Phenomenon, as Carl Runge showed in 1901. The precision and stability of polynomial interpolation are restricted by these oscillations, underscoring the necessity for reliable methods to address this problem. In domains where interpolation is frequently used, like numerical techniques, signal processing, and machine learning, it is essential to comprehend and deal with this issue.

2. Problem Statement

When utilisng high-degree polynomials with evenly spaced points, Runge's Phenomenon describes the occurrence of oscillations in polynomial interpolation, especially close to the boundaries of an interval.

This phenomenon shows that adding more interpolation points does not always result in increased accuracy but rather divergence and instability, particularly for functions that are sensitive to changes in input.

The constraints of high-degree polynomials for interpolation are demonstrated by these oscillations, as big coefficients increase mistakes and lead to instability.

Hence, Runge's Phenomenon is similar to data overfitting in machine learning, when too intricate models match data outliers or noise, resulting in subpar generalization.

This study explores the use of Chebyshev nodes as an alternative to equally spaced points and evaluates their effectiveness in mitigating oscillations.

3. Methods

3.1 Function Definition

We demonstrate Runge's Phenomenon using Runge's function :

3.2 Interpolation Points

Equally Spaced Points: Points are uniformly distributed across the interval

Chebyshev Nodes: Non-uniformly distributed points are concentrated near the boundaries, calculated as:

3.3 Lagrange Interpolation

Polynomial interpolation is performed using the Lagrange basis

3.4 Visualization with the Code:

The true function, interpolation results, and nodes are plotted for both equally spaced points and Chebyshev nodes to observe and compare their behavior.

import numpy as np import matplotlib.pyplot as plt # Runge's function def runge(x): return 1 / (1 + 25 * x**2) # Generate interpolation points def evenly_spaced(a, b, n): return np.linspace(a, b, n) def chebyshev_nodes(a, b, n): return 0.5 * (a + b) + 0.5 * (b - a) * np.cos((2 * np.arange(n) + 1) * np.pi / (2 * n)) # Lagrange interpolation def lagrange_interp(x, y, x_new): result = np.zeros_like(x_new) for i in range(len(x)): l = np.prod([(x_new - x[j]) / (x[i] - x[j]) for j in range(len(x)) if j != i], axis=0) result += l * y[i] return result # Set up arrays x and y ( with n = 11 ) a, b, n = -1, 1, 11 x_true = np.linspace(a, b, 500) y_true = runge(x_true) x_even = evenly_spaced(a, b, n) x_cheb = chebyshev_nodes(a, b, n) y_even, y_cheb = runge(x_even), runge(x_cheb) y_interp_even = lagrange_interp(x_even, y_even, x_true) y_interp_cheb = lagrange_interp(x_cheb, y_cheb, x_true) # Plot the runge's phenomenon and also how the chebyshev nodes reduce the extent of oscillation plt.figure(figsize=(12, 6)) plt.plot(x_true, y_true, label="True Function", linewidth=2) plt.plot(x_true, y_interp_even, '--', label="Evenly Spaced Interpoolation ", linewidth=2) plt.plot(x_true, y_interp_cheb, '-.', label="Chebyshev Interpolation Interpolation", linewidth=2) plt.scatter(x_even, y_even, color='red', label="Evenly Spaced Points") plt.scatter(x_cheb, y_cheb, color='green', label="Chebyshev Nodes") plt.title("Runge's Phenomenon and Chebyshev Nodes", fontsize=14) plt.xlabel("x"), plt.ylabel("y") plt.legend(fontsize=10), plt.grid(True) plt.show()

Run to view results

4. Results

4.1 Interpolation with Equally Spaced Points

Significant oscillations were observed near the interval boundaries.

The interpolating polynomial deviated notably from the true function, demonstrating Runge's Phenomenon.

4.2 Interpolation with Chebyshev Nodes

The oscillations were significantly reduced, and the interpolating polynomial closely matched the true function across the entire interval.

The stability and accuracy of the interpolation were much improved compared to equally spaced points.

5. Conclusion

The limitations of polynomial interpolation with evenly spaced points, especially for high-degree polynomials, are demonstrated by Runge's Phenomenon.

With their non-uniform distribution, Chebyshev nodes efficiently reduce spurious oscillations and enhance interpolation accuracy, as this study shows. Chebyshev nodes offer a workable solution to this age-old issue by concentrating nodes close to the interval borders, stabilizing the interpolation. These results have wider ramifications for data fitting and numerical modeling and emphasize the significance of node selection in interpolation.

6. Bibiliography

[1] Runge, C. "Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten." Zeitschrift für Mathematik und Physik, 46 (1901).

.css-15w88e5{color:var(--chakra-colors-fg-neutral-primary);font-weight:inherit;letter-spacing:-0.09px;}Runge's Phenomenon