Solved

Approximation function f(x) with a polynomial

Posted on 2009-05-06
9
248 Views
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?
0
Comment
Question by:mdoland
9 Comments
 
LVL 3

Accepted Solution

by:
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:
http://en.wikipedia.org/wiki/Curve_fitting
http://zunzun.com/
0
 
LVL 20

Assisted Solution

by:thehagman
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).
0
 
LVL 20

Assisted Solution

by:gatorvip
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
http://en.wikipedia.org/wiki/Spline_(mathematics)
http://mathworld.wolfram.com/Spline.html
http://mathworld.wolfram.com/CubicSpline.html
0
Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 20

Expert Comment

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

Expert Comment

by:aburr
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.
0
 
LVL 84

Assisted Solution

by:ozo
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
0
 
LVL 84

Expert Comment

by:ozo
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

0
 
LVL 31

Expert Comment

by:GwynforWeb
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.
0
 
LVL 27

Expert Comment

by:CaptainCyril
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.
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
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.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

860 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