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()
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()
i=1000
n=2
x=-1+2*i/n
print(x)
Loading...
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()
# Start writing code here...