CHAPTER 05: SPECIAL TOPICS: Higher Order Interpolation is a Bad Idea

In this segment we're going to talk about why higher order interpolation is a bad idea. This was an experiment which was conducted by Runge, who was a German mathematician, and had a lot of contributions to numerical methods.  In 1901, what he wanted to show was that higher order interpolation is a bad idea.  So he took a simple function, which you are seeing here, 1 divided by 1 plus 25 x squared, and what we did was he said, hey, let me go ahead and take, let's suppose, six data points which are equidistantly spaced. So you have six data points which are equidistantly spaced on this function of 1 divided by 1 plus 25 x squared, from -1 to +1, and this blue line, which is shown there, is simply the function itself, so that's the original function.  So the six data points are given in the table here, right from the function itself, and what we wanted to do was to say that, hey, let me take these six data points, and let a fifth-order polynomial pass through those six data points. Because you have six data points, you can take a fifth-order polynomial and make it go through those six data points.  And this is what he obtained, so here what you are finding out that you have these six data points which you have, and the blue line which you are seeing here is the original function.  So the blue line is the original function, and the red line which you're seeing here is basically the fifth-order polynomial going through those six data points.  And you're already finding out there's a vast difference between what you get as the interpolated value at, let's suppose at x equal to 0, and what you have as the value at x equal to 1.  So fifth-order polynomial turns out to be not a good approximation for the original function, 1 divided by 1 plus 25 x squared.  So people thought that maybe . . . Runge thought that maybe it's because he's not taking enough data points from -1 to +1, maybe he should take more data points, and most probably what's going to happen is that the interpolant is going to be closer to the original function.  So this is what he did was that he said let me go ahead and take twenty data points now, which are equidistantly spaced from -1 to +1. So if you're taking twenty data points, as shown in the graph there, now what you want to do is you want to take those twenty data points, and let a nineteenth-order polynomial pass through those twenty data points.  So let's see what happens now.  And you can see that it's worse now. So you're finding out that your original function is the blue line, the interpolant, the nineteenth-order polynomial which you are seeing here is the red line, and you're already finding out the red line is giving you values which are astronomical, as opposed to what they originally are at these endpoints there.  So you're finding out that higher order interpolation's a bad idea.  In fact, if you take more and more data points equidistantly spaced from -1 to +1, what's going to happen is that you're going to get even more error in the interpolant between the function value and the interpolant value itself, especially at the endpoints.  What you are finding out is that as you take more data points, yes, between about maybe -0.7 and +0.7, you're finding out that the original function and the interpolant itself are matching, but it's at the endpoints where you're having the problem where you get the largest difference between the interpolant and the Runge's function itself.  So what is the antidote to this problem?  It is something called spline interpolation.  Spline interpolation is explained in a separate segment, and what we are finding out here is that if we do spline interpolation for the same twenty data points which we had in the previous graph, that the spline interpolant, which is the green curve which you are seeing here, you cannot see the blue line itself.  The blue line is the original function, and the reason why you're not able to see the blue line is because the original function and the spline are almost on top of each other.  So you're finding out that this cubic spline interpolation . . . interpolant which has been drawn through the twenty data points which were chosen for the interpolant, do a better job of interpolating the function, as opposed to . . . as opposed to the nineteenth-order polynomial. So this also shows you that spline interpolation is the answer to higher order interpolation, which might be a bad idea.  Now, there's a Wolfram demonstration which has been . . . which is being shown here with permission from Wolfram Research, who are the makers of Mathematica.  So what they have done is that they have made these demonstrations using Mathematica, something called Mathematica player, where they basically give you an interactive simulation of the Runge's phenomenon, which I just showed it to you through some graphs.  So let's go ahead and go through those and see that how, as we keep on increasing the polynomial interpolant, do we get . . . do we get a better . . . better approximation. So here we have . . . we are choosing equally spaced data points, and now this is a fifth-order polynomial which I . . . fourth-order polynomial going through the function itself.  So you have the function, 1 divided by 1 plus 25 x squared, you are choosing four data points . . . five data points, and you're passing a fifth-order . . . fourth-order polynomial through the data points.  At the bottom, there's a graph which shows you what the . . . what the error in the interpolant is, and in this case, the maximum error which you're getting is about 0.5 or so.  Now, if I increase the . . . increase the . . . increase the number of data points which I'm choosing.  So let's suppose if I'm choosing 25 data points now, which means that a 24th-order polynomial is going through those data points, and already you're finding out that at the endpoints, you are getting a large difference between the interpolant and the function itself, and the error in the interpolant is about 250 or so.  So as you keep on increasing the order of the polynomial, you find out that you're getting more and more error, the difference between the maximum error which you're getting in the interpolant is becoming more and more.  In fact, I can increase it . . . increase it all the way up to 50, because the simulation allows you to have 50 data points, so it's a 49th-order polynomial.  So in the 49th-order polynomial, the amount of error which you're getting in the interpolant is about 700000.  So you can very well see that the large difference which you're getting between the interpolant values and the function itself is about 700000, and it increases as you keep on increasing . . . keeping on increasing more and more data points.  Now, in this Wolfram demonstration, there's a good thing which has been shown there is that you have an option of choosing Chebyshev points.  So if I move this to Chebyshev points, you are finding out that you are getting a better interpolant than what you had previously.  So here, now, the error, which was 700000, the maximum error which you are getting is 0.0001. So what is the difference between the Chebyshev points and the equally spaced points which are used in this demonstration? It is that the Chebyshev points are skewed more towards the endpoints.  You have more . . . more points chosen for interpolation near the ends, as opposed to equally spaced, as we had previously, and this seems to answer the question that, hey, if we want to reduce the amount of error between the original function and the . . . and the . . . original function and the interpolant, that we need to choose Chebyshev points to be able to do that. Now, one of the things which you might be asking is that, hey, is there a similar scheme which I can use for any continuous function?  No, Faber, a great mathematician, he showed in a theorem that there is no specific way, no general way which you can come up with how to choose data points to approximate a curve without getting into too much error between the interpolant and the function itself. But in this particular case, for this particular function, 1 divided by 1 plus 25 x squared, the Chebyshev points do work the best in terms of reducing the amount of error between the interpolant and the function itself.  And that's the end of this segment.