找到多项式的根

Question

给定n次多项式,如何可靠地找到x = 0的所有x值.

我目前正在使用该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求解器只会让你真实; 没有找到复杂的解决方案:

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获取最新的副本