My first post here, so I’m not really sure how to do all the formatting and stuff. It’ll take me a while to get used to the Latex.

I’ll get started.

We have a set of points, ; how would we find a polynomial function that passes through all of the points?

Let’s have an example here. We have the four points and we need to find a polynomial function so that , and .

Remember that a polynomial function of order can be represented by . So a line would be , which is more commonly seen as . Similarly a quadratic would be .

What we need to do to find the polynomial is to determine a set of coefficients so that for every point in our set of points the statement is true.

Notice here that the number of coefficients is always one more than the order of the function. This implies that to interpolate a polynomial of points we need an order polynomial.

We have four points, so we need to determine the correct cubic polynomial:

We simply substitute the four points into the equation:

Simplify:

Now we have a simple set of linear equations. We solve this and get:

Plot this in Mathematica:

Of course we could have saved all that work and just used the built in function:

So now that we know how to do polynomial interpolation, let’s have some fun with this. Take the Runescape level XP table (don’t laugh) and find a function that generates these values.

I used Vim to transform the table into a mathematica input, then computed the 98-th degree generating polynomial. The computation only took about a second, and produced a very large (several pages worth) output. Here’s an image.

This is normal, right? Now let’s try plotting the polynomial, as before:

Yes, this function passes through all of our 99 points. But with such a large number of points, the function oscillates wildly between points. This is known as Runge’s phenomenon.

Like this:

LikeLoading...

Related

This entry was posted on Friday, February 12th, 2010 at 6:56 pm and is filed under Mathematics, Programming. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

One Response to Notes on interpolating polynomials

Lol @ RuneScape xD