求一组二次方程的解

Question

我有一组二次方程，比如

x² + x + y = 7
x + 3y = -3
y² + x² + z = 11

所有系数都是整数。这组方程可以没有解，也可以是一组解中的一个解。

有谁知道这些方程是否有解的方法？

我的第一个想法是一个接一个地求解这些方程，然后用结果来求解其他方程。问题是舍入误差:如果，在理论上，我有两个方程

x + y = 5
x = 5 - y

将会有很多解决方案。但是如果我的方法结果是

x + y = 4.999999
x = 5 - y

系统突然没有解决方案。在下一步中，我可以添加epsilon来补偿舍入误差，但我不确定它们应该有多大。有什么想法或更好的方法吗？

PS:背景是在平面上寻找一组复杂的圆和线的交点。

Answer 1

因为你有精确的整数输入，你可以使用精确的算法。例如，你可以计算与你的方程相对应的多项式的Groebner basis，例如

x² + x + y - 7
x + 3y + 3
y² + x² + z - 11

使用术语的字典排序，你将得到一种“三角形”形式的Groebner基，其中第一多项式包含尽可能少的变量，例如

81z² - 176z + 92
2y + 9z - 8
2x - 27z + 30

一旦z固定，这将为z提供两个实根，并为y和x提供唯一的值。如果计算的基数的第一个多项式不包含变量，则您的方程式集没有任何解。如果计算基中的第一个多项式包含两个变量，那么您有无限多个解(可能是复杂的)。

您可以使用Wolfram Alpha在线试用Groebner bases (例如compute the basis for your example)。可以使用Buchberger algorithm计算Groebner基数，Java语言提供了一些实现。

注意: Buchberger算法的最坏情况下的复杂度在输入的最大总度中是双指数的，但在您的应用程序中，这可能并不重要。