We learned a more efficient way to code Newton’s divided difference in class last week. We began by trying the code with the equation with five equally spaced points:

f=@(x) sin(pi*x)

n=5

x=linspace(-1,1,n)’

c=zeros(n,1)

F=f(x)

c(1)=F(1)

for i=1:n-1

F = diff(F)./(x(i+1:n)-x(1:n-i))

c(i+1)=F(1)

end

m=101;

xx = linspace(-1,1,m)’;

phi = ones(m,n);

for i=2:n

phi(:,i) = phi(:,i-1).*(xx-x(i-1));

end

P=phi*c;

plot(xx,f(xx),‘-r’)

hold on

plot(xx,P,‘-ob’)

With the error:

Using the same function with Gaussian points:

With the error:

Next we used Gaussian points with the equation

%f=@(x) sin(pi*x)

f=@(x) 1./(1+4.*x.^2)

n=7

%x=linspace(-1,1,n)’

x = -cos(pi*(0:n-1)/(n-1))

c=zeros(n,1)

F=f(x)

c(1)=F(1)

for i=1:n-1

F = diff(F)./(x(i+1:n)-x(1:n-i))

c(i+1)=F(1)

end

m=101;

xx = linspace(-1,1,m)’;

phi = ones(m,n);

for i=2:n

phi(:,i) = phi(:,i-1).*(xx-x(i-1));

end

P=phi*c;

plot(xx,f(xx),‘-r’)

hold on

plot(xx,P,‘-ob’)

With the error:

Using the same function with equidistant points:

With the error:

I thought it would be interesting to do a little research into finding out some more information on the Runge Phenomenon. The Runge phenomenon occurs with polynomial interpolation for polynomials of high degree. The higher the order of the polynomial used, the larger the bound of error becomes, showing that instead of moving towards zero, the error is increasing.

Using equally spaced points, as the degree of the polynomial increases, the error near the endpoints gets increasingly larger. It can be proven that the error of the Runge phenomenon using equally spaced points will approach infinity as the degree of the polynomial increases. This contradicts the Weierstrass approximation theorem that explains that there exists a sequence of approximating polynomials with the error converging to zero.

The following picture demonstrates this:

The red curve is the Runge function.

The blue curve is a 5th order interpolating polynomial.

The green curve is a 9th order interpolating polynomial

At the interpolating points, the error between the function and the polynomial is zero. Between the interpolating points, especially near the endpoints, as the degree of the polynomial increases, the error increases.

The following table shows the Runge function, its derivatives, and their evaluations at

Since the magnitude of higher order derivatives of the Runge function gets larger, the bound for error for higher order polynomial interpolations is larger.

The Runge phenomenon shows that using equally spaced points with interpolation of higher degree polynomials can cause problems. Using Gaussian points, the error appears to be more regular, oscillations are minimized, and the error decreases as the degree of the polynomial interpolation increases.

Using the cubic spline interpolation method can help to avoid this since it uses piecewise polynomials.