Runge's Phenomenon

Author's Name: Huang Chenyu

Date: 18/12/2022

Purpose of the experiment

What is Runge's Phenomenon?

The Runge's phenomenon was discovered in 1901 by Carl Runge. This phenomenon is characterised by oscillations at both ends of the interpolated interval when we interpolate functions with polynomials.[1] This oscillation tells us that when interpolating to fit certain functions, even though the polynomial approximates the function well in the interval, the approximation to the function may be poor at the edges of the interval or even outside the interval.

What is the significance of the Runge's phenomenon for polynomial fitting?

What it means for polynomial interpolation and in over-fitting is that when we fit points generated by the true distribution, the resulting polynomial function is not as close to the true function as the higher the number of times[2]. We need to do some preparatory work to understand the trend of the curve of the true function and then use the appropriate method to fit it. That is, do not readily use higher polynomials without being familiar with the trend of the curve movement.

Experimental procedure

Demonstrate Runge's Phenomenon using Runge's function :

The following code shows the generation of the Runge‘s phenomenon and the results, in which we mainly use Lagrange polynomials for interpolation[3], selecting the number of equidistant nodes as 10, 15, and 20.

The function is fitted according to three different node selections, and the fitting results are plotted against the original function in the following figure. The results are shown in the following figure.

# Demonstrate Runge's Phenomenon using Runge's function import numpy as np import matplotlib.pyplot as plt #Number of points where we want to evaluate our polynomial interpolation Ng = 10000 #Define the original function y(x) x0 = np.linspace(-1,1,num = Ng) y0 = 1/(1 + (5*x0)**2) #Select isometric nodes x1 = np.linspace(-1,1,10) x2 = np.linspace(-1,1,15) x3 = np.linspace(-1,1,20) y1 = 1/(1 + (5*x1)**2) y2 = 1/(1 + (5*x2)**2) y3 = 1/(1 + (5*x3)**2) #Lagrange interpolation def Lagrange(x,y,x0): n = len(x) a_l = y p_l = np.zeros_like(x0) for i in range(Ng): for j in range(n): Lp_j = 1. # Initialize Lagrange Polynomial for k in range(n): if j is not k: Lp_j *= (x0[i]-x[k])/(x[j]-x[k]) p_l[i] += a_l[j]*Lp_j return p_l #Plotting the function fit, the Runge's phenomenon is shown in Figure 1 fig, ax1 = plt.subplots() ax1.plot(x0,y0,linestyle = 'solid',color = 'black', label='Original') ax1.plot(x0, Lagrange(x1,y1,x0),'--g' , label='LI x=10') ax1.plot(x0, Lagrange(x2,y2,x0), '--b', label='LI x=15') ax1.plot(x0, Lagrange(x3,y3,x0), '--r', label='LI x=20') leg = ax1.legend(); plt.show()

Results & Problems

It is easy to see from Figure 1 that the Runge‘s phenomenon does not appear when the number of nodes is 10, but when we select the number of nodes to 15 and 20, there is a large oscillation at the edge of the selected range of functions, and the more nodes are selected, the greater the oscillation amplitude, which is the Runge's phenomenon.

What is a possible remedy to avoid spurious oscillations?

This oscillation is caused by the selection of nodes that are equidistant within the interval, so we can avoid the Runge's phenomenon by re-selecting the nodes using the Chebyshev function[4].

The fundamental reason for the Longe phenomenon is that the interpolation is performed using uniform nodes, and the interpolated function is not smooth enough, which means that the resolution region is not large enough. For Chebyshev points, the resolution area of the interpolated function becomes less demanding, as long as the interpolated function is resolved in an elliptical region containing [-1,1] with the x-axis as the long half-axis[5].

Demonstrate the effectiveness of this remedy though some example(s).

Here is an example. This example shows how we fit the original function using both Lagrangian interpolation with equidistant nodes and Lagrangian interpolation with Chebyshev nodes when we pick the number of nodes x = 15 and plot it as an image.

#Select Chebyshev nodes(Take x=15 as an example) x_Ch = np.linspace(-1,1,15) for i in range(15): x_Ch[i] = np.cos((2*(i+1) - 1)/(2*15)*np.pi) y_Ch = 1/(1 + (5*x_Ch)**2) #The curves from the original function, #Lagrange interpolation using equidistant nodes and using Chebyshev nodes are plotted in Figure 2 fig, ax2 = plt.subplots() ax2.plot(x0,y0,linestyle = 'solid',color = 'black', label='Original') ax2.plot(x0, Lagrange(x2,y2,x0), '--b', label='Li x=15') ax2.plot(x0, Lagrange(x_Ch,y_Ch,x0), '--r', label='Li_Ch x=15') leg = ax2.legend(); plt.show()

Conclusion

After re-selecting the nodes using the Chebyshev function, we compared the results of the refitting with the original function and the results of the fitting using equidistant nodes, which are shown in the figure above. The Runge's phenomenon largely disappears after the nodes are re-selected, proving that this method is effective in avoiding the oscillation phenomenon[6].