RUNGE'S PHENOMENON

Author's Name : Benson Daniel Cosman

Date:20-12-2024

INTRODUCTION:

Runge's Phenomenon demonstrates numerical instability in polynomial interpolation, discovered by Carl Runge in 1901. This phenomenon arises when interpolating a smooth function with high-degree polynomials at equally spaced nodes. As the polynomial degree increases, oscillations near the boundaries distort the approximation, showcasing the risks of overfitting and instability in numerical and computational techniques. This phenomenon is particularly relevant to areas like data fitting, spectral methods, and machine learning.

Historical Context:

Carl Runge's study, detailed in his 1901 paper Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten, focused on the function

He observed significant divergence near interval boundaries when using equally spaced nodes with high-degree polynomial interpolation. This critical insight laid the groundwork for understanding the limitations of interpolation in numerical analysis [RUN 01].

THE MATHEMATICS OF RUNGE'S PHENOMENON:

Error Analysis

The interpolation error for a polynomial of degree n is expressed as:

where P_n (x) is the interpolating polynomial, x_i are the nodes, and ξ is a point in the interval. For equally spaced nodes, the term ∏_(i=0)^n▒(x-x_i ) grows rapidly near the boundaries, leading to severe oscillations and loss of accuracy [RUN 02].

Instability in Lagrange Basis

Lagrange basis functions, defined as:

they are another source of instability in equally spaced node interpolation. As n increases, the functions exhibit pronounced peaks at the interval edges, amplifying errors. This behavior underpins the challenges in high-degree polynomial interpolation [RUN 03].

PRACTICAL DEMONSTRATION:

The function

was interpolated over [-1,1] using equally spaced nodes for n=7, 10, 18, and 24.

The code to demonstrate Runge's Phenomenon:

# Import libraries import numpy as np import matplotlib.pyplot as plt from scipy.interpolate import lagrange # Define the Runge function def runge_function(x): return 1 / (1 + (5 * x)**2) # Points to plot the original function x_plot = np.linspace(-1, 1, 600) y_plot = runge_function(x_plot) # Try interpolation with different numbers of points for n in [7, 10, 18, 24]: x_nodes = np.linspace(-1, 1, n) # Nodes for interpolation y_nodes = runge_function(x_nodes) # Values at those nodes # Polynomial interpolation using lagrange poly = lagrange(x_nodes, y_nodes) y_interp = poly(x_plot) # Plot the results plt.figure() plt.plot(x_plot, y_plot, color='red', label="Runge Function") plt.plot(x_plot, y_interp, '--', label=f"Interpolation (n={n})") plt.scatter(x_nodes, y_nodes, color='black', label="Nodes") plt.title("Runge's Phenomenon") plt.xlabel("x") plt.ylabel("y") plt.legend() plt.grid() plt.show()

Run to view results

Results include: For n=7: Accurate approximation across the interval. For n=10: Noticeable oscillations emerge near the boundaries. For n=18: Oscillations become pronounced and dominate near the edges. For n=24: Severe oscillatory behavior leads to a distorted interpolant. These results empirically validate Runge's observations and highlight the practical challenges of high-degree polynomial interpolation.

REMEDIES:

Chebyshev Nodes

Chebyshev nodes are a set of specific points used in numerical interpolation, particularly designed to minimize the error and reduce the instability often encountered when using equally spaced nodes in polynomial interpolation (a phenomenon known as Runge's Phenomenon). These nodes are particularly important in the context of polynomial interpolation and function approximation, as they improve the accuracy and stability of the resulting interpolating polynomial.

Chebyshev nodes, defined as:

provide an effective solution to mitigate Runge's Phenomenon. By clustering nodes near the boundaries, they minimize oscillations and enable stable interpolation, even for high-degree polynomials. The key feature of Chebyshev nodes is that they are non-equidistant, meaning they are clustered more densely near the endpoints of the interval and spaced farther apart in the middle. This distribution helps reduce the oscillations at the edges, which is a major issue when using equally spaced nodes in high-degree polynomial interpolation.

The provided Python code demonstrates an implementation of Runge's Phenomenon, showcasing how polynomial interpolation using both equidistant and Chebyshev nodes affects the approximation of a smooth function.

# Import necessary libraries import numpy as np import matplotlib.pyplot as plt from scipy.interpolate import lagrange # Define the Runge function def runge_function(x): return 1 / (1 + (5 * x) ** 2) # Function to get Chebyshev nodes def chebyshev_nodes(n, a, b): return 0.5 * (a + b) + 0.5 * (b - a) * np.cos(((2 * np.arange(1, n + 1) - 1) / (2 * n)) * np.pi) # Generate points to plot the actual function x_plot = np.linspace(-1, 1, 600) y_plot = runge_function(x_plot) # Try different numbers of nodes for interpolation for n in [7, 10, 18, 24]: # Equidistant nodes x_equidistant = np.linspace(-1, 1, n) y_equidistant = runge_function(x_equidistant) # Chebyshev nodes x_chebyshev = chebyshev_nodes(n, -1, 1) y_chebyshev = runge_function(x_chebyshev) # Interpolate using equidistant nodes poly_equidistant = lagrange(x_equidistant, y_equidistant) y_interp_equidistant = poly_equidistant(x_plot) # Interpolate using Chebyshev nodes poly_chebyshev = lagrange(x_chebyshev, y_chebyshev) y_interp_chebyshev = poly_chebyshev(x_plot) # Plot the original function and interpolations plt.figure(figsize=(8, 5)) # Adjust figure size for better readability # Plot the original function plt.plot(x_plot, y_plot, label="Original Function", color="red", linewidth=1.5) # Plot equidistant nodes interpolation plt.plot(x_plot, y_interp_equidistant, label=f"Equidistant Interpolation (n={n})", color="black", linestyle="--") plt.scatter(x_equidistant, y_equidistant, color="black", label="Equidistant Nodes") # Plot Chebyshev nodes interpolation plt.plot(x_plot, y_interp_chebyshev, label=f"Chebyshev Interpolation (n={n})", color="blue", linestyle="-.") plt.scatter(x_chebyshev, y_chebyshev, color="blue", label="Chebyshev Nodes") # Add title, labels, legend, and grid plt.title(f"Runge's Phenomenon (n={n})", fontsize=10) plt.xlabel("x") plt.ylabel("y") plt.legend() plt.grid() # Show the plot plt.show()

Run to view results

In conclusion, the use of Chebyshev nodes significantly reduces the oscillations that occur with equidistant nodes, effectively preventing Runge's Phenomenon . As seen in the code results, interpolation with Chebyshev points leads to smoother and more accurate approximations, even as the number of nodes increases (7, 10, 18, 24). This demonstrates that Chebyshev nodes help maintain stability in polynomial interpolation, preventing large boundary oscillations that would otherwise distort the results.

Tikhonov Regularization

Tikhonov regularization offers another powerful remedy. By introducing a penalty term for large coefficients, it smoothens the interpolation and reduces high-frequency oscillations. Boyd's work on defeating Runge's Phenomenon using Tikhonov regularization demonstrates its practical efficacy in improving stability for equally spaced node interpolation [RUN 05].

Piecewise Polynomials

Piecewise polynomials, such as splines, divide the interpolation interval into smaller subintervals and fit a low-degree polynomial to each subinterval. This approach avoids the pitfalls of high-degree polynomials by focusing on local accuracy rather than global approximation. For instance, cubic splines, which use third-degree polynomials, maintain continuity and smoothness at the boundaries between subintervals. By restricting the polynomial degree and localizing the interpolation, oscillatory behavior is significantly reduced, even with equispaced nodes.

Basis Selection

The choice of basis functions can profoundly affect interpolation stability. Chebyshev polynomials are particularly advantageous due to their well-behaved nature on [-1,1]. These orthogonal polynomials minimize the error by distributing oscillations evenly across the interval, unlike Lagrange basis functions. Fourier spectral methods, another alternative, leverage trigonometric functions as bases, ensuring stability and convergence in periodic domains. The careful selection of basis functions allows practitioners to tailor the interpolation process to the problem's specific needs, mitigating the challenges posed by equispaced nodes [RUN 04].

BROADER IMPLICATIONS:

Runge's Phenomenon extends beyond polynomial interpolation, offering insights for broader fields. In machine learning, the phenomenon is analogous to overfitting, where complex models fail to generalize. Similarly, in numerical computation, stability can be ensured by carefully choosing basis functions and regularization techniques.

CONCLUSION:

Runge's Phenomenon highlights a fundamental challenge in numerical analysis, particularly when working with polynomial interpolation. It demonstrates how the choice of interpolation nodes significantly influences the accuracy and stability of the approximation. As the degree of the polynomial increases, interpolation at equally spaced nodes leads to large oscillations, especially near the boundaries of the interval. This issue underscores the importance of judicious node selection to avoid these instabilities, which can severely affect the quality of the approximation.

Various techniques have been proposed to address this issue and ensure more accurate and stable interpolations. Chebyshev nodes, for example, have been shown to minimize interpolation errors by clustering near the boundaries, reducing the amplitude of oscillations and providing a much more stable solution. This approach effectively prevents Runge’s Phenomenon, even with higher-degree polynomials. Another remedy is Tikhonov regularization, which helps by introducing a penalty for high-frequency oscillations in the polynomial, providing a form of smoothing and regularizing the interpolation process.

Additionally, piecewise polynomials such as splines or piecewise linear functions offer an alternative that is less sensitive to the placement of nodes. These methods avoid the problems caused by high-degree polynomials, particularly when interpolating smooth functions. Careful basis selection is another crucial factor, as using appropriately chosen basis functions can significantly reduce numerical instability.

Together, these techniques—Chebyshev nodes, Tikhonov regularization, piecewise polynomials, and careful basis selection are essential in ensuring that polynomial interpolation remains both stable and accurate. These methods are not only fundamental in addressing Runge’s Phenomenon but also continue to shape modern numerical practices and influence computational techniques in a wide range of applications, from data fitting to machine learning and computational physics. These approaches highlight the ongoing evolution of methods that enhance computational reliability and precision across various fields of science and engineering .

BIBILIOGRAPHY:

1. [RUN 01] Runge, C. "Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten," 1901.

2. [RUN 02] Trefethen, L. N. "Is Gauss quadrature better than Clenshaw–Curtis?" SIAM Review, vol. 50, no. 1, 2008.

3. [RUN 03] Boyd, J. P. Chebyshev and Fourier Spectral Methods. Dover Publications, 2001.

4. [RUN 04] Higham, N. J. Accuracy and Stability of Numerical Algorithms. SIAM, 2002.

5. [RUN 05] Boyd, J. P. "Defeating the Runge phenomenon for equispaced polynomial interpolation via Tikhonov regularization." Applied Mathematics Letters, 1992. Accessed via ScienceDirect.

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