python 通过去除变量简化具有渐近性的约束集

3qpi33ja 于 12个月前发布在 Python

关注(0)|答案(1)|浏览(77)

我目前正在为另一个软件项目编写一个简化工具，我想简化一些数学。
我给出了一组方程和不等式，

x = a
y + 1 = b
x = y
z = c
y > z

我想得到一组简化的方程和不等式，其中最好有更少的S={x,y,z}的变量，并且在方程的一边以某种方式归一化为0

0 = b - (a + 1)
0 > c - b + 1

因此，S中的变量充当中间存储，或变量{a,b,c}之间的连接。

所有变量和常量都可以被认为是整数
如果不存在这种简化，
结果不需要是最佳的
如果这也适用于非线性方程，这将是一个加号，但不是必须的
我可以使用其他python库而不是sympy
我想有一个通用的方法，给出的约束条件只是一个例子，我事先并不知道方程的结构

我试着去理解sympy.solve，sympy.simplify和sympy.reduce_inequalities。

我没有设法让simplify处理一组约束，而不是一个表达式。
solve似乎只能处理等式，而不能处理不等式。我也不认为我想解决这些方程，而是删除变量。
reduce_inequalities似乎仅限于一个变量。我不知道如何一次只对一个变量执行这个函数。它还考虑了方程。

我不需要完整的源代码，但一个粗略的方法如何解决这个问题，或者如果它是在所有可行的sympy。
非常感谢

python

来源：https://stackoverflow.com/questions/77288045/simplifying-a-set-of-constraints-with-sympy-by-removing-variables

1条答案

按热度按时间

cxfofazt1#

一种可能的方法是使用Groebner基。我将引入一个新的符号t和一个新的方程t = y - z，这样不等式就变成了t > 0（我们将单独记住）。然后，系统被转换为仅方程：

In [6]: a, b, c, t, x, y, z = symbols('a, b, c, t, x, y, z')

In [7]: eqs = [Eq(x, a), Eq(y+1, b), Eq(x, y), Eq(z, c), Eq(y - z, t)]

In [8]: eqs
Out[8]: [x = a, y + 1 = b, x = y, z = c, y - z = t]

现在你可以计算Groebner基了（注意符号的顺序很重要）：

In [20]: gb = groebner(eqs, [x, y, z, t, a, b, c])

In [21]: for p in gb: pprint(Eq(p, 0))
-b + x + 1 = 0
-b + y + 1 = 0
-c + z = 0
-b + c + t + 1 = 0
a - b + 1 = 0

最后两个不涉及x，y，z的方程就是你想要的。具有t的方程可以求解t以恢复不等式：

In [25]: S(0) < solve(gb[3], t)[0]
Out[25]: 0 < b - c - 1

In [26]: Eq(0, gb[4])
Out[26]: 0 = a - b + 1

更一般地说，这里的方法是：

使用符号排序计算Groebner基，首先列出要消除的符号（x，y，z），然后是伪符号（t），然后是要保留的符号（a，b，c）。
从基中丢弃第一个多项式，不管有多少个多项式涉及你不感兴趣的符号。
求解包含虚拟变量（如t）的多项式，以恢复不等式。
把剩下的多项式当作包含感兴趣的符号的方程。

对于更复杂的多项式输入，计算Groebner基可能非常昂贵，因此这种方法是否实用取决于您开始时的条件的复杂性。如果所有条件都是线性的，就像例子中那样，那么它会很快。

赞(0）回复(0）举报 12个月前

我来回答

python 通过去除变量简化具有渐近性的约束集

1条答案

相关问题

热门标签

最新问答