• Introduction
• Section I : Data.
• Section II: Polynomial interpolation for 5 data points.
• Section III: Polynomial interpolation for 9 data points.
• Section IV: Polynomial interpolation for 21 data points.
• Section V: Comparison.
• Section VI: Conclusion.

Higher Order Interpolation is a Bad Idea

2003 Nathan Collier, Autar Kaw, Jai Paul , University of South Florida , kaw@eng.usf.edu , http://numericalmethods.eng.usf.edu/mws .

NOTE: This worksheet demonstrates the use of Maple to show how higher interpolation can be a bad idea. It illustrates how choosing more data points can result in highly oscillatory polynomial functions.

Introduction

The following example illustrates why higher order polynomial interpolation, that is, interpolating using high number of data points, is a bad idea. In 1901, Carl Runge published his work on dangers of higher order polynomial interpolation.  He took a simple looking function  on the interval of [-1,1].  He took data points equidistantly spaced in [-1,1], and then interpolated the data points with polynomials.  He found that as he took more points, the polynomials and the original curve differed considerably in their value from each other.

>

restart;

Section I : Data.

Runge's function is given by:

>	fRunge:=x->1/(1+25*x^2);

Plotting Runge's Function:

Section II: Polynomial interpolation for 5 data points.

Let us first interpolate approximate Runge's function using polynomial interpolation.  For interpolation 5 equidistant data points, [-1, -0.5, 0, 0.5, 1] are chosen in [-1,1] . This will give us a 4th order polynomial.

>	poly5:=interp([-1, -0.5, 0, 0.5, 1],[fRunge(-1), fRunge(-0.5),fRunge(0),fRunge(0.5),fRunge(1)],t);

>	poly5:=t->interp([-1, -0.5, 0, 0.5, 1],[fRunge(-1), fRunge(-0.5),fRunge(0),fRunge(0.5),fRunge(1)],t):

let us now plot it against the actual Runge's function.

>	plot([fRunge,poly5],-1..1,-1..1,thickness=2,title="Runge's function and 4th order polynomial",legend=["Runge's Function","4th Order Polynomial"]);

Section III: Polynomial interpolation for 9 data points.

Runge' function is now approximated by choosing 9 equidistant data points, [-1, -0.75, -0.5, -0.25, 0, 0.25, 0.5, 0.75, 1] in [-1,1].  Interpolating with these values would give us an 8th order polynomial.

>	poly9:=interp([-1,-0.75,-0.5,-0.25,0,0.25,0.5,0.75,1],[fRunge(-1),fRunge(-0.75),fRunge(-0.5),fRunge(-0.25),fRunge(0),fRunge(0.25),fRunge(0.5),fRunge(0.75),fRunge(1)],t);

>	poly9:=t->interp([-1,-0.75,-0.5,-0.25,0,0.25,0.5,0.75,1],[fRunge(-1),fRunge(-0.75),fRunge(-0.5),fRunge(-0.25),fRunge(0),fRunge(0.25),fRunge(0.5),fRunge(0.75),fRunge(1)],t):

Plotting the 8th order polynomial against Runge's function,

>	plot([fRunge,poly9],-1..1,-1..1,thickness=2,color=[red,blue],title="Runge's function and 8th order polynomial",legend=["Runge's Function","8th Order Polynomial"]);

Section IV: Polynomial interpolation for 21 data points.

We will now interpolate Runge's function in [-1,1], by choosing 21 equidistant points, [-1,-0.9,-0.8,-0.7,-0.6,-0.5,-0.4,-0.3,-0.2,-0.1,0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1]. This will give us a 20th order polynomial.

>

poly21:=interp([-1,-0.9,-0.8,-0.7,-0.6,-0.5,-0.4,-0.3,-0.2,-0.1,0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1],[fRunge(-1),fRunge(-0.9),fRunge(-0.8),fRunge(-0.7),fRunge(-0.6),fRunge(-0.5),fRunge(-0.4),fRunge(-0.3),fRunge(-0.2),fRunge(-0.1),fRunge(0),fRunge(0.1),fRunge(0.2),fRunge(0.3),fRunge(0.4),fRunge(0.5),fRunge(0.6),fRunge(0.7),fRunge(0.8),fRunge(0.9),fRunge(1)],t);

>

poly21:=t->interp([-1,-0.9,-0.8,-0.7,-0.6,-0.5,-0.4,-0.3,-0.2,-0.1,0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1],[fRunge(-1),fRunge(-0.9),fRunge(-0.8),fRunge(-0.7),fRunge(-0.6),fRunge(-0.5),fRunge(-0.4),fRunge(-0.3),fRunge(-0.2),fRunge(-0.1),fRunge(0),fRunge(0.1),fRunge(0.2),fRunge(0.3),fRunge(0.4),fRunge(0.5),fRunge(0.6),fRunge(0.7),fRunge(0.8),fRunge(0.9),fRunge(1)],t):

Plotting this polynomial against Runge's function,

>	plot([fRunge,poly21],-1..1,-1..1,thickness=2,color=[red,gold],title="Runge's function and 20th order polynomial",legend=["Runge's Function","20th Order Polynomial"]);

Section V: Comparison.

Below is a plot to compare the interpolated polynomials obtained using 5, 9 and 21 data points, respectively, with the actual Runge's function :

>	plot([fRunge,poly9,poly5,poly21],-1..1,-2..2,thickness=[3,2,2,2],color=[RED,BLUE,GREEN,GOLD],title="Runge's function,4th, 8th and 20th order polynomials",legend=["Runge's function","8-th order polynomial","4-th order polynomial","20-th order polynomial"]);

>

Section VI: Conclusion.

Maple helped us to apply our knowledge of numerical methods of interpolation to see that higher order interpolation is a bad idea. As the interpolant order becomes higher, the difference between the values of the original function and the interpolated function are very different, especially close to the end points of -1 and +1.  

Choose even order of  polynomials of your own choice, and see the effect of the higher order interpolation at x=0.8 and x=0.

References:

[1] Autar Kaw, Holistic Numerical Methods Institute , See

http://numericalmethods.eng.usf.edu/mws/ind/05inp/mws_ind_inp_spe_higherorder.pdf

Disclaimer:  While every effort has been made to validate the solutions in this worksheet, University of South Florida and the contributors are not responsible for any errors contained and are not liable for any damages resulting from the use of this material.