RUNGE'S PHENOMENON

Author's Name: Gohul GOVINDARAJ

Date: 20-12-2024

Motivation:

Interpolation is a fundamental numerical technique used to estimate unknown values or approximate functions based on a limited set of data points. It has widespread applications in fields such as computer graphics, engineering, physics, and machine learning. However, relying on high-degree polynomials for interpolation can sometimes lead to significant challenges. A well-known example is Runge's Phenomenon, which highlights the potential pitfalls of these methods and underscores the importance of choosing appropriate interpolation techniques. Runge's Phenomenon occurs when high-degree polynomials, constructed using evenly spaced nodes, produce large oscillations, especially near the edges of the interpolation interval. Although these polynomials accurately pass through all the given data points, they can deviate substantially from the true function, leading to poor approximations. This issue illustrates the dangers of overfitting and numerical instability, particularly in practical contexts involving real-world data. The function y(x)= 1/ (1+(5x)^2) is often used to demonstrate this phenomenon. Despite its smooth and simple nature, attempting to interpolate this function with high-degree polynomials highlights the limitations of standard methods. Visualizing the oscillatory behavior that arises provides valuable insights into the drawbacks of using evenly spaced nodes for polynomial interpolation.

Recent studies have shown that exploring various algorithms, such as blending methods, can address the challenges posed by the Runge phenomenon. In particular, piecewise interpolation techniques and higher-order strategies were evaluated for their ability to reduce oscillations near interval boundaries. These strategies, as outlined in [RUN 01], provide alternative approaches that yield improved stability and accuracy when compared to standard polynomial interpolation.

Another innovative solution to mitigate the Runge phenomenon involves the use of artificial neural networks (ANNs) for interpolation. [RUN 02] demonstrates how single-layer ANNs can outperform traditional methods, particularly when the training data includes strategically placed nodes like Chebyshev nodes. By leveraging the adaptability of neural networks, this approach enhances approximation accuracy while maintaining computational efficiency.

An important perspective offered by [RUN 03] involves the application of modern backward error analysis to understand and address the numerical instability caused by high-degree polynomial interpolation. This analysis highlights the theoretical underpinnings of the Runge phenomenon and provides a solid foundation for designing alternative interpolation frameworks.

In dynamic applications such as attitude reconstruction from inertial measurements, mitigating the Runge phenomenon becomes critical. [RUN 04] introduces a "borrowing-and-cutting" strategy that not only reduces oscillations but also preserves the accuracy of interpolated values in practical scenarios. This approach is particularly relevant for real-world data interpolation where precision is paramount.

Finally, [RUN 05] underscores the importance of node distribution, emphasizing the role of "mock-Chebyshev" nodes derived from equispaced grids. This method effectively addresses the divergence seen in least-squares polynomial approximations, making it a robust and efficient choice for practical applications. A well-established solution to mitigate these issues is to use Chebyshev nodes. Unlike evenly spaced points, Chebyshev nodes are strategically distributed, with a higher concentration near the interval’s boundaries. This distribution helps to minimize oscillations and significantly improves the accuracy and stability of interpolation.

Introduction:

Runge's Phenomenon is a critical challenge in numerical analysis, examined in this assignment. While the goal of interpolation is to create a smooth curve that closely aligns with a set of data points, this expectation is not always met. Runge's Phenomenon demonstrates how using high-degree polynomials with evenly spaced points can result in erratic oscillations, particularly near the edges of the interval. These oscillations tend to worsen as the polynomial degree increases, often leading to unreliable outcomes in practical applications. This problem is not purely theoretical—it has practical implications. Interpolation is widely used in fields such as data analysis, computer science, and engineering to estimate values within a given range based on known data points. However, when high-degree polynomials are applied to evenly spaced points, the resulting curve can deviate significantly from the true function due to overfitting. This divergence can lead to unstable and inaccurate outcomes, posing challenges in building reliable models or making accurate predictions. Studying Runge's Phenomenon sheds light on the limitations of polynomial interpolation and highlights the importance of choosing suitable methods for data modeling. This exploration not only introduces a foundational concept in numerical analysis but also serves as a cautionary reminder for professionals working in data-intensive fields to adopt methods that minimize errors and enhance the reliability of their interpretations and analyses.

Runge's Phenomenon:

Runge's Phenomenon describes the significant oscillations that can arise when high-degree polynomials are used for interpolating a set of data points, particularly when the points are evenly spaced. These oscillations are most noticeable near the edges of the interpolation interval. As the degree of the polynomial increases, the phenomenon becomes more pronounced, often producing a curve that passes through the data points but deviates considerably from the actual function. This issue is commonly illustrated using the function f(x)f(x)f(x), where interpolation with evenly spaced nodes and higher-degree polynomials results in substantial errors near the interval boundaries. The primary lesson from Runge's Phenomenon is that high-degree polynomial interpolation can be unreliable, especially with evenly spaced nodes. A widely used solution is to employ Chebyshev nodes, which are more concentrated near the interval boundaries. This distribution helps minimize oscillations and enhances the accuracy of the interpolation.

Core of Runge's Phenomenon:

• High-degree polynomials: The phenomenon typically occurs when using a high-degree polynomial for interpolation. As the degree of the polynomial increases, the polynomial can become increasingly sensitive to small changes in the data points, causing large oscillations.

• Equidistant data points: Runge's phenomenon is most noticeable when the interpolation nodes are chosen to be equidistant. In such cases, the interpolating polynomial tends to diverge at the boundaries of the interval, leading to large oscillations.

• Exponential growth of derivatives: The underlying reason for the oscillations is related to the fact that higher-degree polynomials have rapidly increasing derivatives, which cause the polynomial to overshoot and oscillate between the data points, especially near the edges of the interval.

Practical Implications of Runge's Phenomenon:

• Oscillations: High-degree polynomial interpolations, especially with equidistant data points, cause large oscillations at the boundaries.

• Poor Approximation: Despite passing through all data points, the interpolation can significantly deviate from expected values.

• Numerical Instability: Small changes in input data can cause large fluctuations, leading to unstable results.

• Inefficiency: For large datasets, high-degree polynomials become inefficient and computationally expensive.

• Design Challenges: In engineering and CAD, the phenomenon can result in unrealistic or unphysical designs.

• Overfitting: In data fitting or machine learning, high-degree polynomials can overfit the training data, reducing generalization.

• Alternative Methods: Solutions like spline interpolation or Chebyshev nodes provide smoother, more stable results.

Code Implementation: Lagrange Interpolation with Uniform and Chebyshev Nodes

The two codes below provide distinct approaches to interpolating Runge's function using Lagrange polynomials. Each highlights the effects of node selection.

Code 1: Lagrange Interpolation with Uniform Nodes

This implementation demonstrates Runge's phenomenon using equidistant nodes for interpolation. The function and its interpolated values are plotted for visual comparison.

# 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 + 50 * x**2) # Changed scaling factor to make the function sharper # Function to perform interpolation and plotting def interpolate_and_plot(node_counts, x_plot, y_plot): for n in node_counts: # Generate interpolation nodes and values x_nodes = np.linspace(-1, 1, n) # Nodes for interpolation y_nodes = runge_function(x_nodes) # Function values at nodes # Perform Lagrange interpolation poly = lagrange(x_nodes, y_nodes) y_interp = poly(x_plot) # Plot results plt.figure(figsize=(7, 5)) # Added figure size adjustment plt.plot(x_plot, y_plot, color='darkblue', label="Runge Function", linewidth=2) plt.plot(x_plot, y_interp, linestyle='--', color='orange', label=f"Interpolation (n={n})", linewidth=1.5) plt.scatter(x_nodes, y_nodes, color='green', edgecolor='black', s=60, label="Nodes") plt.title(f"Lagrange Interpolation with {n} Nodes", fontsize=14, color='maroon') plt.xlabel("x", fontsize=12, color='darkgreen') plt.ylabel("y", fontsize=12, color='darkgreen') plt.legend() plt.grid(color='gray', linestyle=':', linewidth=0.6) # Changed grid style plt.tight_layout() # Ensures plot fits nicely within the figure plt.show() # Define main block if __name__ == "__main__": # Define inputs x_plot = np.linspace(-1, 1, 800) # Increased resolution y_plot = runge_function(x_plot) node_counts = [7, 13, 19, 25] # Changed number of nodes # Call function to interpolate and plot interpolate_and_plot(node_counts, x_plot, y_plot)

Run to view results

Result for Code 1 (Uniform Nodes Only)

•The Runge function is interpolated using uniform nodes with n = 7, 13, 19, 25.

•The interpolation closely matches the Runge function near the center of the interval but diverges significantly near the edges (Runge's phenomenon).

•Visual output: o Blue curve: Actual Runge function. o Orange dashed curve: Interpolated polynomial. o Green points: Uniform nodes used for interpolation.

Code 2: Lagrange Interpolation with Uniform vs. Chebyshev Nodes

This code compares the effects of equidistant nodes and Chebyshev nodes on polynomial interpolation, highlighting the stability offered by Chebyshev nodes.

# Import essential modules import numpy as np import matplotlib.pyplot as plt from scipy.interpolate import lagrange # Define the function to approximate def runge_func(x): return 1 / (1 + 25 * x**2) # Generate Chebyshev nodes over the interval def generate_chebyshev(n, lower, upper): indices = np.arange(n) + 0.5 return 0.5 * (lower + upper) + 0.5 * (upper - lower) * np.cos(np.pi * indices / n) # Prepare the true function values for visualization x_vals = np.linspace(-1, 1, 800) y_vals = runge_func(x_vals) # Loop through various interpolation scenarios for num_nodes in [5, 10, 15, 20]: # Uniform nodes uniform_x = np.linspace(-1, 1, num_nodes) uniform_y = runge_func(uniform_x) # Chebyshev nodes cheb_x = generate_chebyshev(num_nodes, -1, 1) cheb_y = runge_func(cheb_x) # Compute polynomial interpolations uniform_poly = lagrange(uniform_x, uniform_y) uniform_interp = uniform_poly(x_vals) cheb_poly = lagrange(cheb_x, cheb_y) cheb_interp = cheb_poly(x_vals) # Plot results for this number of nodes plt.figure(figsize=(10, 6)) # Plot the Runge function plt.plot(x_vals, y_vals, "k-", label="Runge Function", linewidth=2) # Plot uniform node interpolation plt.plot(x_vals, uniform_interp, "c--", label=f"Uniform Interpolation (n={num_nodes})") plt.scatter(uniform_x, uniform_y, color="cyan", label="Uniform Nodes") # Plot Chebyshev node interpolation plt.plot(x_vals, cheb_interp, "m-.", label=f"Chebyshev Interpolation (n={num_nodes})") plt.scatter(cheb_x, cheb_y, color="magenta", label="Chebyshev Nodes") # Add annotations and visuals plt.title(f"Interpolation Comparison with {num_nodes} Nodes", fontsize=14) plt.xlabel("x-axis", fontsize=12) plt.ylabel("y-axis", fontsize=12) plt.legend(fontsize=10) plt.grid(True) # Render the plot plt.show()

Run to view results

Result for Code 2 (Uniform vs. Chebyshev Nodes)

• The Runge function is interpolated with uniform nodes and Chebyshev nodes for n = 5, 10, 15, 20.

• Uniform Interpolation: Similar to Code 1, suffers from Runge's phenomenon at the edges.

• Chebyshev Interpolation: Provides a much closer approximation across the interval, especially at the edges, due to the clustering of nodes near the boundaries.

• Visual output: o Black curve: Actual Runge function. o Cyan dashed curve: Interpolation with uniform nodes. o Magenta dashed curve: Interpolation with Chebyshev nodes. o Cyan and magenta points: Uniform and Chebyshev nodes, respectively.

Conclusion:

Runge's phenomenon emphasizes the drawbacks of using equidistant nodes for interpolation.

Chebyshev nodes significantly reduce oscillations and improve interpolation stability.

The two codes provide clear evidence of the importance of selecting suitable node distributions, especially for higher-degree polynomials.

Bibliography:

1. [RUN 01] "A Case Study of the Runge Phenomenon Based on Multiple Algorithms" , Authors: Zhang Jianan, Wang Yiyi, Duan Hongyi, Li Qingyang , Year: 2023.

2. [RUN 02] "On the Accuracy of Interpolation Based on Single-Layer Artificial Neural Networks with a Focus on Defeating the Runge Phenomenon" , Authors: Ferdinando Auricchio, Maria Roberta Belardo, Gianluca Fabiani, Francesco Calabrò, Ariel F. Pascaner , Year: 2023.

3. [RUN 03] "The Runge Example for Interpolation and Wilkinson's Examples for Rootfinding", Authors: Robert M. Corless, Leili Rafiee Sevyeri, Year: 2018.

4. [RUN 04]"Attitude Reconstruction from Inertial Measurement: Mitigating Runge Effect for Dynamic Applications", Authors: Yuanxin Wu, Maoran Zhu, Year: 2021.

5. [RUN 05] "Divergence (Runge Phenomenon) for Least-Squares Polynomial Approximation on an Equispaced Grid and Mock-Chebyshev Subset Interpolation", Authors: Lloyd N. Trefethen, Mark Embree, Year: 2000.

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