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$

Simplify:

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

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

=O says:

May 6, 2011 at 11:11 pm

Lol @ RuneScape xD

Reply

Lucky's Notes

Notes on interpolating polynomials

Like this:

One Response to Notes on interpolating polynomials

Leave a Reply Cancel reply

Categories

Tags

Email Subscription

Blog Stats

Follow “Lucky's Notes”