Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a set of estimated points, listed below, and I would like to know how to calculate the polynomial.

I've looked at Wikipedia, and I don't quite understand how at works. Example 1 on http://en.wikipedia.org/wiki/Lagrange_polynomial#Example_1 seems to be the closest to what I'm trying to do, but I don't know how to get the basis polynomials, i.e. turning the middle section into the right section. I can probably get it to the interpolating section from there.

My points are as follows: 800, 175; 600, 125; 400, 100; 200, 125; 0,0; -200, -125; -400, -100; -600, -125; -800, -175.

Eventually, I'm going to try and dynamically swap out the points above in the program I'm building, so I could really use a step by step description. I read Determining Coefficients of a Finite Degree Polynomial $f$ from the Sequence $\{f(k)\}_{k \in \mathbb{N}}$, but I don't quite follow it. It's very possible I'm out of my depth and should re-think what I'm trying to accomplish, but I'd really like to try this. Thanks!

share|improve this question
    
The post you linked to assumed the $x$-coordinates are $1,2,3,\dots$, so it isn't general enough for your purposes. If you say the polynomial is $P(x)$ with undetermined coefficients, then the system $P(x_i)=y_i$ for $i=0,1,2,\dots$ is a linear system in those coefficients that can be solved with linear algebra. As for Lagrange polynomials, the Wikipedia has the formulas for the basis polynomials explicitly written - so where is your issue specifically? Define $Q_j(z)$ to be the product of factors $(z-x_i)$ for all $i$ except $i=j$; then $$\ell_j(z)=Q_j(z)/Q_j(x_j)$$ are the basis polynomials. –  anon Aug 27 '11 at 0:53
    
Also, how do you figure the interpolated polynomial will be $5$-th degree? –  anon Aug 27 '11 at 1:04
    
The Lagrange polynomial passes exactly through the data points. Absent a lucky coincidence, it generates an $n-1$ degree polynomial from $n$ points, so in your case it would be $8$th degree (except for the antisymmetry, which would reduce it to $7$th degree) –  Ross Millikan Aug 27 '11 at 17:32

2 Answers 2

up vote 2 down vote accepted

If you know for a fact that your points lie on a polynomial of degree 5, you can use finite differences. This is especially easy when the $x$-values are in arithmetic progression, as in your case. Write the $y$-values:

175 125 100 125 0 -125 -100 -125 -175

Then write the difference between each number and the next:

-50 -25 25 -125 -125 25 -25 -50

Again:

25 50 -150 0 150 -50 -25

Again:

25 -200 150 150 -200 25

Again:

-225 350 0 -350 225

And once more:

575 -350 -350 575

Now if your points were really from a polynomial of degree 5, that last line would have been constant, but it's not, so they're not. But after all, you said they were estimated points - they still might be close to some polynomial of degree 5. To find the polynomial of degree 5 that comes closest to your points, there is a method called least squares, and there are many expositions of it on the web.

EDIT: Here's a start on least squares:

You want a polynomial $p(x)=ax^5+bx^4+cx^3+dx^2+ex+f$ such that $p(800)=175$, $p(600)=125$, etc. We already know that's impossible, so we settle for making all the numbers $p(800)-175$, $p(600)-125$, etc., small. In fact, we form the quantity $$(p(800)-175)^2+(p(600)-125)^2+\cdots+(p(-800)-175)^2$$ and we try to minimize it. This quantity is a function of the 6 variables $a,b,c,d,e,f$, and there are standard calculus techniques for minimizing such a function. It gets very messy, but fortunately you don't actually have to do it; someone has done it for you, in the most general case, and found that you can write down a very simple matrix equation which you can solve for the unknowns $a,b,c,d,e,f$. And that's what you'll find if you search for least squares polynomial fit.

share|improve this answer

With 9 points your data will not fit a 5th degree polynomial exactly. You need a least squares fit, which will smooth things. More information is found in chapter 15 of Numerical Recipes (obsolete versions are free) or any numerical analysis textbook. Your particular data is odd $(f(-x)=-f(x)$, so only $x, x^3, x^5$ terms will appear. I rescaled your x values for the fit below. You can rescale them back by dividing the coefficients by $200^{\text{power of x}}$. It doesn't look like a very good fit, but Excel claims it is the best you will get. The even order terms are roundoff error and should be ignored.

enter image description here

share|improve this answer
    
The numerical recipes book is definitely a great resource. I'm going to be looking through that more. –  rjferguson Aug 29 '11 at 17:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.