algorithm - 在 3 个未知变量上找到 N 多项式方程组的数值解的快速算法是什么？

Question

我正在寻找一种快速算法来求解包含 3 个未知变量的 N 个多项式方程组。也就是说，给定 3 个函数，F0(x,y,z), F1(x,y,z)... FN(x,y,z)，我想找到 x, y, z 这样 F0(x,y,z) = F1(x,y,z) = ... = FN(x,y,z) = 0 .

我尝试在几个不同的地方找到解决方案，但我只能找到关于代数几何或密码学等主题的非常高级的论文。不过，我需要的是一种返回快速数值解的简单/快速算法。有这样的算法吗？

Answer 1

求解多个变量的多项式方程是一个难题。在平均情况下在多项式时间内这样做 is Smale's 17th problem.您不太可能会找到一种快速简单的算法来真正起作用。

您可以查看 Cox、Little 和 O'Shea 合着的“理想、变体和算法”，了解 Groebner 基的介绍。 Buchberger 的算法为给定的多项式理想找到 Groebner 基础。您可以使用 Groebner 基为多项式生成的理想找到给定多项式系统的所有解，尽管解的形式有点笨拙。

牛顿法是求解多变量非线性方程组的基本方法。天真地应用，牛顿的方法是启发式的；即使存在解决方案，它也不会总是找到系统的解决方案。但是，如果牛顿法收敛，那么它收敛得非常快。因此，Smale 提出的理论问题的挑战在于找到一个可证明良好的初始猜测来启动牛顿方法。

Beltran and Pardo made considerable progress on Smale's 17th problem ，给出了一个算法，该算法适用于使用实数算法的有界度系统的平均值。这已经是turned into a finite-precision algorithm by Briquel, Cucker, Pena, and Roshchina .尽管它们很吸引人，但我不知道这些想法的任何实现或任何实现尝试——我们离拥有可用代码来解决以下问题的系统还很遥远多项式方程。