Pattern recognition

[wossname]

Does anyone have an algorithm (in code or pseudocode) that enables a program to identify a polynomial function from an array (1 or 2 dimensional array) giving (x, y) data?

I need at least to be able to identify quadratic and 3 term polynomials (y=ax^3 + bx^2 + cx + d).

Any programming language is fine by me.

[kedaman]

not sure what you mean, do you want to parse the polynominal from a string? why 1 or 2 dimensions?

[Acidic]

I have something on my TI83 to find sequences if thats what you mean. but it's very long so unless you definately want it, I won't write it.

it can find
An^3 +Bn^2 Cn + D
or
A^n +B

If you want, I'll write out the psuedo code if you don't have a TI83

[Acidic]

the other thing crappy with it is that it needs the first 6 items in the sequence to find the rest, though this can probably be improved if I really tried.

[twanvl]

Do you mean that given n (x,y) pairs, you want to find a n-1th order polynomial equation y=axn+bxn-1+...+d?

If you have four (x,y) values, it means that you have these equations:
y1=ax13 + bx12 + cx1 + d
y2=ax23 + bx22 + cx2 + d
y3=ax33 + bx32 + cx3 + d
y4=ax43 + bx42 + cx4 + d

You can solve this system of equations using a matrix inverse:

[x13 , x12 , x1 , 1]
A = [x23 , x22 , x2 , 1]
[x33 , x32 , x3 , 1]
[x43 , x42 , x5 , 1]

[y1]
B = [y2]
[y3]
[y4]

You need to find a matrix X, such that AX = B. This matrix can be found using X=A-1B.
This algorithm needs a function for a matrix inverse, i don't have code handy that does that, but I'm sure you can find something on google.

Another method involves rewriting the equations, and substituting them. Rewrite the first equation as:
a = (bx12 + cx1 + d - y1) / x13
You can now substitute all a's in the other three equations with this this one:
y2=((bx12 + cx1 + d - y1) / x13)x23 + bx22 + cx2 + d
repeat this process untill only an equation of the form:
d = f(x1, y1, x2, y2, x3, y3, x4, y4)
remains, now you have the value of d. substitute d in the equations to find the value of c, etc.

You may be able to find more info on mathworld (http://mathworld.wolfram.com/LinearSystemofEquations.html)

[sql_lall]

Look up Lagrange Interpolation Polynomial:

http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html

A nice and, most importantly, logical approach to finding these things. (finds degree (n-1) equation with n points)

[wossname]

:sick:

Am I right in thinking that this...
http://mathworld.wolfram.com/l1img246.gif
is the pertinent equation that I should implement?

Blimey.

[sql_lall]

yeah, that is a bit messy.

The 'nicer' and more logical one is the formual (3), after "Written explicity"
The logic of it is nice, cos when x = x1, every term = 0 but the first, which factors to 1*y1. When x = x2, every term = 0 but the second, which factors to 1*y2....
Its nice and easy to remember too :D

[wossname]

I wonder, would it be utterly rude of me at this stage to ask if anyone has actually coded such a function? I don't think even my considerable skills of logic (riiiight! :D) can figure out a way to code that.

Could I have a sneaky gander if so?

If not then not to worry, I have just been bombarded with several new projects to be getting on with in the meantime such as learning ASM:eek:.