Approximation function f(x) with a polynomial

Posted on 2009-05-06
Last Modified: 2012-05-06
I have a number of x,y value pairs. I want to approximate a function y= a + bx + cx^2 + dx^3 + ex^4 + fx^5 + gx^6 ...

How do I get this function with the use of the known x1, ... xn and y1, ... yn?
Question by:mdoland

Accepted Solution

nullsquid earned 125 total points
ID: 24312900
A simple but cpu intensive way is to substitute the x and y into the function
D= y - a + bx + cx^2 + dx^3 + ex^4 + fx^5 +..
where you have guessed the coefficients abcd..
This would give a 'distance', D, from the line for each point; add the absolute values of these together to get a score for the set of guessed coefficients. you then guess different sets of coefficients until you minimise D - such that the points are as close to the line as you can get.

I think Excel has a function that does it, you will get better results with more powers in the equation, because, I believe, you can always fit n points exactly to a nth - order polynomial.

further reading:
LVL 20

Assisted Solution

thehagman earned 125 total points
ID: 24312988
Actually, you can always fit a degree n-1 polynomial to n points.
One can also look for lower degree polynomials and fit them using least square methods.

One way to find an exact interpolation is to look at polynomials of the form
f_k(x) = (x - x_1)*(x - x_2)*...*(x - x_{k-1})*(x - x_{k+1})* ... * (x-x_n)
These are 0 at all sample points except at x_k.
Hence one can easily combine them to a polynomlia with f(x_i)=y_i for all i.

However, it is often the case that polynomial interpolation simply "does not look good" (shows large oscillation and other artefacts). You may want to have a look at spline interpolation (smoothly joined piecewise polynomials).
LVL 20

Assisted Solution

gatorvip earned 125 total points
ID: 24313889
It really depends on what you are trying to achieve. As has already been pointed out, if you have n points, you will always have at least one polynomial of degree at most n that fits your points exactly.

However, as thehagman points out, this type of polynomial is very dependent on the exact number of points. If you so happen to add the (n+1) point, your initial polynomial may not look at all like the new one. If you're dealing with a real-world application, this can have unintended results.

This is why, if your number of input points may vary, you don't always want to deal with max-degree polys. Instead, you choose something like a cubic spline where the addition or removal of a single point will generally not have any influence on the behavior of the curve outside of the neighborhood of the new point.

Take a look at
Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

LVL 20

Expert Comment

ID: 24313942
>>at least one polynomial of degree at most n
That should read "at most n-1"
LVL 27

Expert Comment

ID: 24314067
Nullsquid has given  you an intuitive way of doing what you wish. If the errors in your data are random (the usual assumption) you want to minimize the square of the distance, not the absolute value. The result will be a least square approximation as thehagman pointed out. Almost all math programs have a built in function which will fit a polynomial of any dergee you wish to your data. As thehagman pointed out any amount of data can be exactly fitted to a polynomial of n-1 degree but the utility of the exact fit is very limited.  Rarely does more than a third or fourth degree polynomial do any good. There are other functions which might be better depending upon the source of your data. Log curves and exponentials come to mind.
Excell, mathcad, matlab, mathematica, and most statistical programs will have a least square function which will do what you want.
LVL 84

Assisted Solution

ozo earned 125 total points
ID: 24323276
y1 = a + b x1 + c x1^2 + d x1^3 + e x1^4 + f x1^5 + g x1^6 .
 y2 = a + b x2 + c x2^2 + d x2^3 + e x2^4 + f x2^5 + g x2^6 .
is a system of linear equations which you can solve for a,b,c,d,e,f,g
LVL 84

Expert Comment

ID: 24323368
if you have more points than a...g coefficients, there may not be a simultaneous solution to all the equations,
If you want to find coefficients that minimize the sum of the squares of the errors, that turns out to be equivalent to solving another system of linear equations, this time with coefficients like:

sum(Yi) =          a  n                + b sum(Xi)     + c sum(Xi^2) + d sum(Xi^3 ) + ...
sum(Yi*Xi) =     a sum(Xi)       + b sum(Xi^2) + c sum(Xi^3) + d sum(Xi^3 ) + ...
sum(Yi*Xi^2) = a sum(Xi^2)  + b sum(Xi^3) + c sum(Xi^4) + d sum(Xi^5 ) + ...
where sums are over i=1..n for n points

LVL 31

Expert Comment

ID: 24326477
    Fitting a high order polynomial to data for purposes of interpolation is a BAD idea. This is because in general polynomials have many turning points. Although your polynomial may pass through or close to  the points it could osicillate wildly in between.

    There is no magic wand for data fitting. Giving more details of the problem you are trying to solve would help.
LVL 27

Expert Comment

ID: 24347231
The points could be approximated by a line, a simple curve like a parabola or a hyperbola with some errors or any other curve. If you are trying to find a trend or approximation is one thing and if you are trying to find an exact match is another thing.

Featured Post

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Representing TIME in Excel 8 51
Simplify expression 3 96
Math question 3 85
hardness of water, iron in it, and effect on humans.. 6 73
Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…

815 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now