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-1^th order polynomial equation y=axⁿ+bx^n-1+...+d?

If you have four (x,y) values, it means that you have these equations:
y₁=ax₁³ + bx₁² + cx₁ + d
y₂=ax₂³ + bx₂² + cx₂ + d
y₃=ax₃³ + bx₃² + cx₃ + d
y₄=ax₄³ + bx₄² + cx₄ + 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 = (bx₁² + cx₁ + d - y₁) / x₁³
You can now substitute all a's in the other three equations with this this one:
y₂=((bx₁² + cx₁ + d - y₁) / x₁³)x₂³ + bx₂² + cx₂ + d
repeat this process untill only an equation of the form:
d = f(x₁, y₁, x₂, y₂, x₃, y₃, x₄, y₄)
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

[sql_lall]

Look up Lagrange Interpolation Polynomial:

http://mathworld.wolfram.com/Lagrang...olynomial.html

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

[wossname]

Am I right in thinking that this...

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

[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! ) 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.