求多项式的根

Question

给定一个 n 次多项式，我怎样才能可靠地找到 x 的所有值，其中 y = 0。

我目前正在使用 Math.Polynomial 库，它似乎没有内置此功能。但是，我可能在这里遗漏了一些东西，这似乎是一个广泛使用的功能。

谢谢

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 求解器只会为您提供 real-roots；不会找到复杂的解决方案：

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

获取最新副本

Answer 2

您可以使用dsp package的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

求多项式的根

Finding the roots of a polynomial

haskell

algebra

polynomials