Ask Your Question

Model of polynomial with integer coefficients

asked 2013-07-04 21:24:14 -0500

bakant gravatar image

updated 2013-07-05 06:56:00 -0500

tmonteil gravatar image

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))]
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

2 answers

Sort by ยป oldest newest most voted

answered 2013-07-05 06:47:50 -0500

tmonteil gravatar image

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

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

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

edit flag offensive delete link more


Thanks a lot! That's it!

bakant gravatar imagebakant ( 2013-07-05 20:48:46 -0500 )edit

answered 2013-07-04 23:07:02 -0500

tmonteil gravatar image

updated 2013-07-04 23:12:16 -0500

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 more


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 gravatar imagebakant ( 2013-07-05 03:34:25 -0500 )edit

Your Answer

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

Add Answer

Question Tools


Asked: 2013-07-04 21:24:14 -0500

Seen: 528 times

Last updated: Jul 05 '13