SymPy 的 solve() 如何找到非线性系统的解？

Question

Python (see) 的 SymPy 符号数学库提供了一个 求解器 模块来求解奇异方程和方程组.使用示例如下：

import sympy as sym
x,y,z = sym.symbols('x,y,z')
c1 = sym.Symbol('c1')
eq1 = sym.Eq(2*x**2+y+z,1)
eq2 = sym.Eq(x+2*y+z,c1)
eq3 = sym.Eq(-2*x+y,-z)
result = sym.solve([eq1,eq2,eq3],(x,y,z))
print(result)

在尝试广度的自定义方法未能成功求解以下非线性系统后，我正在使用 solve()。它工作得很好，但是我找不到任何信息来说明 SymPy 如何实际解决这些问题。在尝试了这么长时间来实现我自己的求解器（作为一个有趣的练习）之后，我非常有兴趣了解这是如何完成的。

            (x - x_i) ** 2 + (y - y_i) ** 2 + (z - z_i) ** 2 - (299792458 * (t_i - t)) ** 2
            (x - x_j) ** 2 + (y - y_j) ** 2 + (z - z_j) ** 2 - (299792458 * (t_j - t)) ** 2
            (x - x_k) ** 2 + (y - y_k) ** 2 + (z - z_k) ** 2 - (299792458 * (t_k - t)) ** 2
            (x - x_m) ** 2 + (y - y_m) ** 2 + (z - z_m) ** 2 - (299792458 * (t_m - t)) ** 2

其中 x、y、z 和 t 未知，我的目标是找到 x,y,z

Answer 1

您展示的示例系统是未知数的多项式。求解多项式系统的一般框架由 Gröbner 基给出： https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis

你可以在 sympy 中计算：

In [14]: ps = [e.rewrite(Add) for e in (eq1, eq2, eq3)]                                                                           

In [15]: groebner(ps, [x, y, z])                                                                                                  
Out[15]: 
             ⎛⎡                                      2              2                     ⎤                                  ⎞
GroebnerBasis⎝⎣-c₁ + 5⋅x - z, -2⋅c₁ + 5⋅y + 3⋅z, 2⋅c₁  + 10⋅c₁ + 2⋅z  + z⋅(4⋅c₁ + 10) - 25⎦, x, y, z, domain=ℤ[c₁], order=lex⎠

这个想法是，这呈现了一种形式，希望通过一个一个地求解方程式来最容易地工作，类似于高斯消去法的反向代入步骤。在基础中，我们看到有 3 个多项式，其中一个只涉及 z。由于它是二次方程，我们可以应用公式来求解 z 的两个可能值。将其代入其他两个多项式得到 x 和 y 的单独线性方程。

对于较大的系统，计算 Gröbner 基可能会非常慢。随着多项式的次数或未知数的增加，使用任何方法解决任何问题也变得非常困难，但对于特殊情况肯定有更快的方法。

请注意，sympy 的 polys 模块非常庞大，并且包含大量代码，这些代码全部组合在一起，使得计算 Gröbner 基和查找多项式的根成为可能。

话虽这么说，但我认为在解决这些类型的系统时可以做出改进。理想情况下求解应该首先求解线性方程并尽可能多地消除变量。使用多项式结果也可能更有效： https://en.wikipedia.org/wiki/Resultant

同样值得注意的是 Abel Ruffini 定理，它对多项式方程的任何解析求解器可以达到的结果给出了一个严格的限制： https://en.wikipedia.org/wiki/Abel%E2%80%93Ruffini_theorem

SymPy 的 solve() 如何找到非线性系统的解？

How does SymPy's solve() find solutions to nonlinear systems?

python

solver

sympy