Runge's Phenomenon

Author's Name:

Date:

Assignment

Explain in your words what Runge's Phenomenon is, its implications in polynomial interpolation and, in general, in data over-fitting.

To my understanding, the Runge’s phenomenon is a kind of abnormality that occurs in polynomial interpolation. Theoretically, for every continuous function f(x) defined on an interval [a,b], there exists a set of polynomial functions Pn(x) for n=0, 1, 2, …,n. The more n is, the better approximation we will have, so when we set n to infinity, we will get uniform convergence over [a,b]. The abnormality of Runge’s phenomenon is that, as n increases, the polynomial functions Pn(x) would actually deviate from f(x) in a way of oscillation. This usually happens in the endpoints close to the interpolation point, when using equidistant data points for high-degree polynomial interpolation.

Demonstrate Runge's Phenomenon using Runge's function :

import numpy as np import matplotlib.pyplot as plt def y(x): return 1/(1+(5*x)**2) x = np.arange(-1,1,0.01) # interpolater with n order polynomial # a0 + a1 x + a2 x^2 + ... + an x^n = y(x), x taken as -1+2*i/n, i in [[0,n]] def polynomial_interpolate(n): A=np.zeros((n+1,n+1)) b=np.zeros((n+1,)) for i in range(n+1): for j in range(n+1): A[i,j]=(-1+2*i/n)**j b[i]=y(-1+2*i/n) return np.flipud(np.linalg.solve(A, b)) fig, ax = plt.subplots() ax.plot(x,y(x), label='original') ax.plot(x, np.polyval(polynomial_interpolate(4),x), label=r'$P_5(x)$') ax.plot(x, np.polyval(polynomial_interpolate(6),x), label=r'$P_7(x)$') ax.plot(x, np.polyval(polynomial_interpolate(8),x), label=r'$P_9(x)$') ax.legend() plt.show()

Run to view results

import numpy as np import matplotlib.pyplot as plt def y(x): return 1/(1+(5*x)**2) x = np.arange(-1,1,0.01) # interpolater with n order polynomial # a0 + a1 x + a2 x^2 + ... + an x^n = y(x), x taken as -1+2*i/n, i in [[0,n]] ''' def polynomial_interpolate(n): A=np.zeros((n+1,n+1)) b=np.zeros((n+1,)) for i in range(n+1): A[i,0]=1 for j in range(1,i+1,1): A[i,j]=A[i,j-1]*(x[i]-x[j-1]) b[i]+= return np.flipud(np.linalg.solve(A, b)) ''' def polynomial_interpolate(n): Lp=0 p= np.zeros_like(x) for i in range(n+1): for j in range(n+1): for k in range(n+1): if j is not k: Lp*= (x[i]-x[k])/(x[j]-x[k]) p[i]+=y(x)[j]*Lp return np.flipud(p) fig, ax = plt.subplots() ax.plot(x,y(x), label='original') ax.plot(x, np.polyval(polynomial_interpolate(5),x), label=r'$P_5(x)$') ax.plot(x, np.polyval(polynomial_interpolate(7),x), label=r'$P_7(x)$') ax.plot(x, np.polyval(polynomial_interpolate(9),x), label=r'$P_9(x)$') ax.legend() plt.show()

Run to view results

i=1000 n=2 x=-1+2*i/n print(x)

Run to view results

What is a possible remedy to avoid spurious oscillations?

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

import numpy as np import matplotlib.pyplot as plt def y(x): return 1/(1+(5*x)**2) x = np.arange(-1,1,0.01) def polynomial_interpolate_remedy1(n): A=np.zeros((n+1,n+1)) b=np.zeros((n+1,)) for i in range(n+1): if i != 0 and i != n: node = np.cos((2*i-1)/2/(n-1)*np.pi) elif i==0: node = -1 else: node = 1 for j in range(n+1): A[i,j]=(node)**j b[i]=y(node) return np.flipud(np.linalg.solve(A, b)) fig, ax = plt.subplots() ax.plot(x,y(x), label='original') #ax.plot(x, np.polyval(polynomial_interpolate_remedy1(4),x), label=r'$P_5(x)$') #ax.plot(x, np.polyval(polynomial_interpolate_remedy1(6),x), label=r'$P_7(x)$') ax.plot(x, np.polyval(polynomial_interpolate_remedy1(20),x), label=r'$P_20(x)$') ax.legend() plt.show()

Run to view results

# Start writing code here...

Run to view results

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

Assignment

Runge's Phenomenon