Notes on interpolating polynomials

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, [(x_0,y_0), (x_1,y_1), \cdots, (x_n,y_n)] ; how would we find a polynomial function f(x) that passes through all of the points?

Let’s have an example here. We have the four points (1,100), (2,30), (3,70), (4,1000) and we need to find a polynomial function so that f(1) = 100, f(2) = 30, f(3) = 70, and f(4) = 1000.

Remember that a polynomial function of order n can be represented by f(x) = a_0 x^n + a_1 x^{n-1} \cdots a_{n-1} x + a_n. So a line would be f(x) = a_0 x + a_1 , which is more commonly seen as y = mx + b. Similarly a quadratic would be f(x) = a_0 x^2 + a_1 x + a_2.

What we need to do to find the polynomial is to determine a set of coefficients a_0, a_1, \cdots, a_n so that for every point (x,y) in our set of points [(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)] the statement y = a_0 x^n + a_1 x^{n-1} + \cdots + a_n is true.

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

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

y = ax^3 + bx^2 + cx + d

We simply substitute the four points into the equation:

100 = a (1)^3 + b (1)^2 + c (1) + d
30 = a (2)^3 + b (2)^2 + c (2) + d
70 = a (3)^3 + b (3)^2 + c (3) + d
1000 = a (3)^3 + b (3)^2 + c (3) + d


a + b + c + d = 100
8a + 4b + 2c + d = 30
27a + 9b + 3c + d = 70
64a + 16b + 4c + d = 1000

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

a = 130
b = -725
c = 1195
d = -500

y = 130 x^3 - 725 x^2 + 1195 x - 500

Plot this in Mathematica:

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

Expand[InterpolatingPolynomial[{{1, 100}, {2, 30}, {3, 70}, {4,
    1000}}, x]]

> -500 + 1195 x - 725 x^2 + 130 x^3

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.

One thought on “Notes on interpolating polynomials

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s