寻找多项式的根

Question

针对一个n次多项式，如何可靠地找出所有y=0的x值。

我目前正在使用 Math.Polynomial 库，但似乎没有内置此功能。不过我可能漏看了什么，因为这似乎是一个广泛使用的函数。

谢谢。

- user1890615

---

separateRoots应该可以帮助你完成大部分工作，但它似乎不能正确地工作。例如，separateRoots BE [1,0,-1]无法分离。 - luqui

请注意，一旦n大于5，就没有代数精确的方法来找到根：https://en.wikipedia.org/wiki/Abel%E2%80%93Ruffini_theorem - Willem Van Onsem

@WillemVanOnsem 有趣。我确信这个定理最初是由Galois提出的。 - Stéphane Laurent

这个定理在1824年被证明，当时Galois只有13岁。尽管Galois在他去世时非常年轻（据我所知，是因为一段恋情和决斗而导致的），但据我所知，他并没有在13岁时写下那个定理。 - Willem Van Onsem

@luqui 这正是我所想的，但我不确定这是否是预期行为。我可能会提交一个错误报告。 - user1890615

Answer 1

如果您不介意使用外部SMT求解器，可以使用SBV包:

Prelude Data.SBV> allSat $ \x -> 2*x^3-19*x^2+15*x+72 .== (0::SReal)
Solution #1:
  s0 = 3.0 :: Real
Solution #2:
  s0 = 8.0 :: Real
Solution #3:
  s0 = -1.5 :: Real
Found 3 different solutions.

您可以放心，根将是精确的，即不会发生舍入误差。 Real 类型对应于无限精确的代数实数。如果结果不能以有限的形式打印，则将其写为简单方程的根，并扩展到当前打印精度：

Prelude Data.SBV> allSat $ \x -> x^2-2 .== (0::SReal)
Solution #1:
  s0 = root(1, x^2 = 2) = -1.414213562373095... :: Real
Solution #2:
  s0 = root(2, x^2 = 2) = 1.414213562373095... :: Real
Found 2 different solutions.

数字的位数可以任意长，且可配置：

Prelude Data.SBV> allSatWith z3{printRealPrec=20} $ \x -> x^2-2 .== (0::SReal)
Solution #1:
  s0 = root(1, x^2 = 2) = -1.4142135623730950488... :: Real
Solution #2:
  s0 = root(2, x^2 = 2) = 1.4142135623730950488... :: Real
Found 2 different solutions.

注意，SMT求解器只能为您得到实根；不会找到任何复杂解：

Prelude Data.SBV> allSat $ \x -> x^2+1 .== (0::SReal)
No solutions found.

如果仅有一些根是实数，那么它们将被找到：

Prelude Data.SBV> allSat $ \x -> x^3+2*x-1 .== (0::SReal)
Solution #1:
  s0 = root(1, x^3+2x = 1) = 0.4533976515164037... :: Real
This is the only solution.

PS. 为了使所有的工作正常运行，请不要忘记首先在您的计算机上安装Z3。 您可以从 https://github.com/Z3Prover/z3/releases 获取最新版本。

- alias

Answer 2

您可以使用dsp包中的Polynomial.Roots模块。该模块处理复值（复系数和复根）。

例如，要解决1+2x+2x²=0:

Prelude> import Polynomial.Roots 
Prelude Polynomial.Roots> roots 1e-16 1000 [1,2,2]
[(-0.5) :+ (-0.5),(-0.5) :+ 0.5]

作为一个合理性检查，R给出了相同的结果：

> polyroot(c(1,2,2))
[1] -0.5+0.5i -0.5-0.5i

- Stéphane Laurent