ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 05 Jul 2013 20:48:46 -0500Model of polynomial with integer coefficientshttp://ask.sagemath.org/question/10321/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(Thu, 04 Jul 2013 21:24:14 -0500http://ask.sagemath.org/question/10321/model-of-polynomial-with-integer-coefficients/Answer by tmonteil for <p>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. <br/>
Now I have:</p>
<pre><code>...
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)
</code></pre>
<p>Is there any way to approximate my data by same polynomial without models?
Sorry for my English(</p>
http://ask.sagemath.org/question/10321/model-of-polynomial-with-integer-coefficients/?answer=15199#post-id-15199So, 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.Fri, 05 Jul 2013 06:47:50 -0500http://ask.sagemath.org/question/10321/model-of-polynomial-with-integer-coefficients/?answer=15199#post-id-15199Comment by bakant for <p>So, we want to find a polynomial P with integer coefficients and a fixed <code>degree</code> that minimizes <code>max(abs(P(point)-value)</code> where the max is for all <code>(point,value)</code> in <code>mydata</code>.</p>
<p>With such a formulation, we see that there is a possibility with integer programming.
But the <code>abs()</code> function is not linear. So we add a <code>error</code> variable (to be minimized) such that both linear inequalities <code>P(point)-value <= error</code> and <code>value-P(point) <= error</code> hold.</p>
<p>Putting all together, we get:</p>
<pre><code>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
</code></pre>
<p>If you want to find the best polynomial with real entries, you just have to replace the two lines</p>
<pre><code>sage: a = p.new_variable(integer=True)
sage: R = PolynomialRing(ZZ, 'x')
</code></pre>
<p>by </p>
<pre><code>sage: a = p.new_variable(real=True)
sage: R = PolynomialRing(RR, 'x')
</code></pre>
<p>In our example, you will get : </p>
<pre><code>sage: P
0.500000000000000*x + 2.25000000000000
sage: error
2.25
</code></pre>
<p>For huge data, it should also be possible to approximate the best solution with lattice reduction algorithms.</p>
http://ask.sagemath.org/question/10321/model-of-polynomial-with-integer-coefficients/?comment=17348#post-id-17348Thanks a lot! That's it!Fri, 05 Jul 2013 20:48:46 -0500http://ask.sagemath.org/question/10321/model-of-polynomial-with-integer-coefficients/?comment=17348#post-id-17348Answer by tmonteil for <p>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. <br/>
Now I have:</p>
<pre><code>...
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)
</code></pre>
<p>Is there any way to approximate my data by same polynomial without models?
Sorry for my English(</p>
http://ask.sagemath.org/question/10321/model-of-polynomial-with-integer-coefficients/?answer=15196#post-id-15196I 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](http://docs.scipy.org/doc/numpy/reference/generated/numpy.polyfit.html) (but the coefficients will be floating points).
Thu, 04 Jul 2013 23:07:02 -0500http://ask.sagemath.org/question/10321/model-of-polynomial-with-integer-coefficients/?answer=15196#post-id-15196Comment by bakant for <p>I am not sure i understand your question. Given a list <code>mydata</code> of pairs <code>(point, value)</code>, you want to find a polynomial <code>P</code> with integer coefficients such that <code>P(point) == value</code> for each element of <code>mydata</code> ? </p>
<p>If this is your question, you can do it with polynomials with coefficients on <code>RationalField</code>:</p>
<pre><code>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
</code></pre>
<p>This will not work if you replace <code>QQ</code> by <code>ZZ</code>, because Lagrange interpolation needs to make divisions. Note also that it is not sufficient to require that the pairs <code>(point, value)</code> are integers to ensure that <code>P</code> 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).</p>
<p>Now, if you want to <em>approximate</em> (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 <a href="http://docs.scipy.org/doc/numpy/reference/generated/numpy.polyfit.html">polyfit</a> (but the coefficients will be floating points).</p>
http://ask.sagemath.org/question/10321/model-of-polynomial-with-integer-coefficients/?comment=17354#post-id-17354Thanks, 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/Fri, 05 Jul 2013 03:34:25 -0500http://ask.sagemath.org/question/10321/model-of-polynomial-with-integer-coefficients/?comment=17354#post-id-17354