Sign in to follow this  
helloworld123

convert points(x,y) to equation?

Recommended Posts

Hi, I recall we were taught back in college about something like this: Given some points x/y, you could derive an equation using those points. For example, you have points (5,2), (8,21), (9,1000), (102,53). you could have an equation using those points. Does anyone know what it's called again? thanks!

Share this post


Link to post
Share on other sites
It is called "Curve Fitting" or "Regression"

Polynomial Interpolation or Polynomial Regression are two DIFFERENT special cases of general Regression.

Depending on your problem, you might want a linear regression, a polynomial regression, or even an exponential or trigonometric regression. You might even choose to regress to some arbitrary basis vector set. Which one you choose is dependant on what the set of points looks like when plotted.

The most GENERAL form of regression works like this, assuming you are comfortable with matrix math

Given some MxN matrix X, and and Mx1 matrix Y, such that each row of X and each row of Y make a point (x,y), we desire to find some function f such that f(x) = y. To do this,
create some function K called the kernel, that performs an operation K(x)=v, where v is a J dimensional vector. Set up the kernel such that v is linear in the space of function regression...to put another way, you set up the kernel such that v_1=K_1(x)= a basis function of the set, with linear coefficients. If you need to, you can use another function G(y)=y', which converts the scalars of y to scalars y'. Then, apply K(x) to each row of X, and apply G(y) to each row of Y, and you get a linear matrix equation you can solve directly for the unknown parameters of the function.

K(X)c=G(Y)
c=G(Y)/K(X)= (least squares solver)


Thats pretty dense, but I'm gonna show you how to do this with two cases: a 3rd order polynomial, and an exponential fit.

first, the 3rd order 1-d polynomial:
f(x) = c_0 + c_1 x + c_2 x^2 + c_3 x^3 = y

[1 x x^2 x^3]c' = y

Therefore, I setK(x) = [1 x x^2 x^3], G(y) = y

this means that, for an 10x1 matrix X
[x0]
[x1]
[x2]
[..]
[x9]

and an equivilent 10x1 matrix Y,

K(X)c = G(y)
K(X)c = y
[1 x0 x0^2 x0^3][c0] [y0]
[1 x1 x1^2 x1^3][c1] [y1]
[1 x2 x2^2 x2^3][c2]=[y2]
[1 .. .. .. ][..] [..]
[1 x9 x9^2 x9^3][c9] [y9]

which is solvable with least squares.

As an excersize, see if you can answer to yourself why the kernel functions to fit to
f(x)=c_0exp(c_1x+c_2x^2)
are
K(x)=[1 x x^2] and G(y) = ln(y)

Share this post


Link to post
Share on other sites
Quote:
Original post by helloworld123

Hi,

I recall we were taught back in college about something like this:

Given some points x/y, you could derive an equation using those points.

For example, you have points (5,2), (8,21), (9,1000), (102,53).

you could have an equation using those points.

Does anyone know what it's called again?

thanks!


For the simple case you're describing, it's pretty easy.

1) You have 4 points, so you want a polynomial of degree 4-1=3.

Ax^3 + Bx^2 + Cx + D

2) You know the value of 4 points on the curve. For each point, take the x value and plug it into the equation just above for x, set the answer equal to y.

125A + 25B + 5C + D = 2
256A + 64B + 8C + D = 21
721A + 81B + 9C + D = 1000
1061208A + 10404B + 102C + D = 53


You know have 4 equations in 4 unknowns. Solve for A, B, C, and D. Plug them back into the original polynomial and you have your answer.

Share this post


Link to post
Share on other sites
What cache_hit describes is a particular way to compute polynomial interpolation. You can also notice that it's easy to construct a polynomial whose value is 1 at one of your x coordinates and 0 at the others, like this one for the first point (x=5):

(x-8)*(x-9)*(x-102)
-------------------
(5-8)*(5-9)*(5-102)

Since you want the value of the polynomial at that point to be 2, multiply it by 2. Then do the same for the other values of x (8, 9 and 102), multiply the corresponding polynomials by the desired corresponding y value and finally add up all the resulting polynomials together.

Share this post


Link to post
Share on other sites
Hi,

sorry i wasn't clear, i'm not sure if the answers given here are what i was searching for.

it's like, this, given the already given sample points like: (5,2), (8,21), (9,1000), (102,53)

i'll derive a function/equation which will allow me to get more sample points (based off those given samples points already).


so it's like i get something like this to get the first sample point above (5,2):

functionX(1) = 5
functionY(1) = 2


then to get the 2nd point (8,21), is to do this:

functionX(2) = 8
functionY(2) = 21


(am i making sense? sorry it's been a while, but i do remember this being taught in college...)

Share this post


Link to post
Share on other sites
in what cache_hit said, his proposal would make it so that

f(5) = 2

and

f(8) = 21

what you want to do is make it so that

f(1) = 5
g(1) = 2

and

f(2) = 8
g(2) = 21

etc.

all the stuff he talked about still applies so read what he said and make sure you understand what he's talking about (:

Share this post


Link to post
Share on other sites
Quote:
Original post by helloworld123
how to extend this to three points? like: (5,2,18), (8,21,54), (583,25,1), (6,2,100), etc.

The extension to 3D is completely trivial. You probably haven't given it any thought, and decided that it was easier to ask here instead.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Quote:
Original post by helloworld123
how to extend this to three points? like: (5,2,18), (8,21,54), (583,25,1), (6,2,100), etc.

The extension to 3D is completely trivial. You probably haven't given it any thought, and decided that it was easier to ask here instead.



like i said, it's been years since i did any real math. so forgive me if i offended you with my stupidity over such trivial matters.

-------------------------

anyway, with what cache_hit says, he did: "For each point, take the x value and plug it into the equation just above for x, set the answer equal to y"


where do i plug the z?

Share this post


Link to post
Share on other sites
Quote:
Original post by helloworld123
like i said, it's been years since i did any real math. so forgive me if i offended you with my stupidity over such trivial matters.

No, I am not offended. Sorry my post sounded harsh.

Quote:
anyway, with what cache_hit says, he did: "For each point, take the x value and plug it into the equation just above for x, set the answer equal to y"


where do i plug the z?


Although you didn't mention it in your first post, you seem to be introducing another variable (let's call it `t' for `time'), and you need three functions, f(t), g(t) and h(t) such that
f(1)=5; g(1)=2; h(1)=18
f(2)=8; g(2)=21; h(2)=54
etc.

Your problem is finding three functions f, g and h that satisfy certain constraints. cache_hit and I suggested methods that can be applied to compute each function separately.

If you have more than 4 points, you may find the results too odd in some cases (large values appear suddenly, the curve is too sharp...). A smoother alternative (the smoothest in some sense) is using cubic splines. But those are harder to work with, so start with polynomial interpolation.

Share this post


Link to post
Share on other sites
well cache_hit gave this (which was helpful):

Ax^3 + Bx^2 + Cx + D = <solve for y>



now in what cache_hit gave, i can plug x and y values in it. now if i have another value Z, how would it look like now? where do i plug it?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this