Model of polynomial with integer coefficients

asked 2013-07-05 04:24:14 +0100

bakant
13 ●3 ●3 ●8

updated 2018-09-17 20:27:05 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

Can Sage find fit to the data in form of the polynomial with integer coefficients? I mean that I want to find polyinomial with integer coefficients which will approximate my date by the best way, that is the distance from points in "mydata" to graph of the polyinomial will be the least.
Now I have:

...
mydata = [[A[i],B[i]] for i in range(0,len(A))]
var('a,b,c,x,t')
def intPol(a,b,c,x):
    f=a*x^2 + b*x + c
    return f
myfit = find_fit(mydata,intPol,parameters = [a, b, c], variables = [x],solution_dict=True)

Is there any way to approximate my data by same polynomial without models? Sorry for my English(

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2013-07-05 13:47:50 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

So, we want to find a polynomial P with integer coefficients and a fixed degree that minimizes max(abs(P(point)-value) where the max is for all (point,value) in mydata.

With such a formulation, we see that there is a possibility with integer programming. But the abs() function is not linear. So we add a error variable (to be minimized) such that both linear inequalities P(point)-value <= error and value-P(point) <= error hold.

Putting all together, we get:

sage: degree = 3
sage: mydata = [(0,0),(1,5),(2,1),(4,6)]

sage: p = MixedIntegerLinearProgram(maximization=False)
sage: a = p.new_variable(integer=True)
sage: error = p.new_variable(real=True)
sage: p.set_objective(error[0])

sage: for point,value in mydata:
....:     p.add_constraint(sum(a[d]*point^d for d in range(degree+1)) - value <= error[0])
....:     p.add_constraint(value - sum(a[d]*point^d for d in range(degree+1)) <= error[0])

sage: error = p.solve()

sage: dico = p.get_values(a)

sage: R = PolynomialRing(ZZ, 'x')
sage: P = sum(R(v*x^d) for d,v in dico.items())

sage: P
x + 2
sage: error
3.0

If you want to find the best polynomial with real entries, you just have to replace the two lines

sage: a = p.new_variable(integer=True)
sage: R = PolynomialRing(ZZ, 'x')

sage: a = p.new_variable(real=True)
sage: R = PolynomialRing(RR, 'x')

In our example, you will get :

sage: P
0.500000000000000*x + 2.25000000000000
sage: error
2.25

For huge data, it should also be possible to approximate the best solution with lattice reduction algorithms.

edit flag offensive delete link

Comments

Thanks a lot! That's it!

bakant ( 2013-07-06 03:48:46 +0100 )edit

add a comment

answered 2013-07-05 06:07:02 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

updated 2013-07-05 06:12:16 +0100

I am not sure i understand your question. Given a list mydata of pairs (point, value), you want to find a polynomial P with integer coefficients such that P(point) == value for each element of mydata ?

If this is your question, you can do it with polynomials with coefficients on RationalField:

sage: mydata = [(0,0),(2,1),(4,6)]
sage: R = PolynomialRing(QQ, 'x')
sage: P = R.lagrange_polynomial(mydata); P
1/2*x^2 - 1/2*x

This will not work if you replace QQ by ZZ, because Lagrange interpolation needs to make divisions. Note also that it is not sufficient to require that the pairs (point, value) are integers to ensure that P will have integer coefficients. For example, there is no polynomial $P$ with integer coefficients such that $P(0) = 0$ and $P(2) = 1$ (otherwise the first condition implies that the variable $X$ divides $P$, which implies that $P(2)$ is even).

Now, if you want to approximate (not interpolate) you data with polynomials, you need to be more precise about the measure of the quality of the approximation. For example, if you are looking for a leas square approximation, you can hage a look at polyfit (but the coefficients will be floating points).

edit flag offensive delete link

Comments

Thanks, but I meant that I want to find polyinomial with integer coefficients which will approximate my date by the best way, that is the distance from points in "mydata" to graph of the polyinomial will be the least. It is possible to look at this another way, lets polynomial is the function of its coefficients. It is easy to write function which will find sum of distances from graph of the polynomial to each point, then I need to find ArgMin of this function. Is there function in Sage like "ArgMin[{f, cons}, {x, y, ...}, dom] gives a position at which f is minimized over the domain dom, typically Reals or Integers." in Mathematica? It is important that I can choose from Integers and Reals/

bakant ( 2013-07-05 10:34:25 +0100 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Model of polynomial with integer coefficients

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Model of polynomial with integer coefficients edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Model of polynomial with integer coefficients