.
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.
.