# Model of polynomial with integer coefficients

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 close merge delete

Sort by » oldest newest most voted

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


by

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.

more

Thanks a lot! That's it!

( 2013-07-05 20:48:46 -0600 )edit

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

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/

( 2013-07-05 03:34:25 -0600 )edit