Oscillatory behavior example (shown by Runge)¶
In this example we will learn:
- the limit of Newton's method
- why spline interpolation is necessary
In [1]:
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
def evalPoly(a,xData,x):
n = len(xData)-1 # order of polynomial
p = a[n]
for i in range(1,n+1):
#print "a[", (n-i),"]=", a[n-i]
p = a[n-i] + (x-xData[n-i])*p
return p
def coefficients(xData,yData):
n = len(xData)
a = np.zeros((n, n));
for i in range(0, n):
a[i, 0] = yData[i];
for j in range(1, n):
for k in range(0, n-j):
a[k, j] = (a[k+1, j-1] - a[k, j-1])/(xData[k+j]-xData[k])
return a[0, :] # return the zeroth row
With 8 data points¶
In [4]:
# plot the data points
numDataPoints = 8
xData = np.linspace(-1, 1, numDataPoints)
print xData
yData = 1.0/(1+25*xData**2)
print yData
plt.plot(xData,yData,'bo',markersize=10)
# plot the exact function
x = np.linspace(-1, 1, 50)
y = 1.0/(1+25*x**2)
plt.plot(x,y)
# plot the interpolation polynomial
a = coefficients(xData, yData)
xs=np.linspace(-1, 1, 50)
ys=np.zeros(50)
i=0
for x in xs:
ys[i] = evalPoly(a,xData,x)
i=i+1
plt.plot(xs,ys,'r--')
[-1. -0.71428571 -0.42857143 -0.14285714 0.14285714 0.42857143 0.71428571 1. ] [ 0.03846154 0.0727003 0.17883212 0.66216216 0.66216216 0.17883212 0.0727003 0.03846154]
Out[4]:
[<matplotlib.lines.Line2D at 0x108043450>]
With 12 data point¶
In [9]:
# plot the data points
numDataPoints = 12
xData = np.linspace(-1, 1, numDataPoints)
print xData
yData = 1.0/(1+25*xData**2)
print yData
plt.plot(xData,yData,'bo',markersize=10)
# plot the exact function
x = np.linspace(-1, 1, 50)
y = 1.0/(1+25*x**2)
plt.plot(x,y)
# plot the interpolation polynomial
a = coefficients(xData, yData)
xs=np.linspace(-1, 1, 50)
ys=np.zeros(50)
i=0
for x in xs:
ys[i] = evalPoly(a,xData,x)
i=i+1
plt.plot(xs,ys,'r--')
[-1. -0.81818182 -0.63636364 -0.45454545 -0.27272727 -0.09090909 0.09090909 0.27272727 0.45454545 0.63636364 0.81818182 1. ] [ 0.03846154 0.05638397 0.08989599 0.16219839 0.34971098 0.82876712 0.82876712 0.34971098 0.16219839 0.08989599 0.05638397 0.03846154]
Out[9]:
[<matplotlib.lines.Line2D at 0x1086b4f90>]
With 20 data points¶
In [7]:
# plot the data points
numDataPoints = 20
xData = np.linspace(-1, 1, numDataPoints)
print xData
yData = 1.0/(1+25*xData**2)
print yData
plt.plot(xData,yData,'bo',markersize=10)
# plot the exact function
x = np.linspace(-1, 1, 50)
y = 1.0/(1+25*x**2)
plt.plot(x,y)
# plot the interpolation polynomial
a = coefficients(xData, yData)
xs=np.linspace(-1, 1, 50)
ys=np.zeros(50)
i=0
for x in xs:
ys[i] = evalPoly(a,xData,x)
i=i+1
plt.plot(xs,ys,'r--')
[-1. -0.89473684 -0.78947368 -0.68421053 -0.57894737 -0.47368421 -0.36842105 -0.26315789 -0.15789474 -0.05263158 0.05263158 0.15789474 0.26315789 0.36842105 0.47368421 0.57894737 0.68421053 0.78947368 0.89473684 1. ] [ 0.03846154 0.04758766 0.06030738 0.07871784 0.10661548 0.15129925 0.22761665 0.36612576 0.61604096 0.93523316 0.93523316 0.61604096 0.36612576 0.22761665 0.15129925 0.10661548 0.07871784 0.06030738 0.04758766 0.03846154]
Out[7]:
[<matplotlib.lines.Line2D at 0x10847c8d0>]
In [ ]: