如何分离多项式的根

Question

如何分离一个多项式的根部？

多项式的次数是n (10

在使用牛顿/拉夫森或其他众所周知的数值方法来寻找根之前，我需要分离根。

我很久以前就知道有一些方法可以分离词根，但我丢失了我的笔记，而且我不记得了。

我不想要任何mathematica/maple或数学软件库解决方案，因为我必须在软件中实现它。

Answer 1

也许你正在考虑一个Sturm sequence

Answer 2

解决方案是在a，b的范围内构造Sturm chain f0(x) = f(x)，f1(x)，…，fs(x)，并在边界点a和b中计算该链中符号的变化次数: Va - Vb，其中

Va =链中符号的变化f0(a) = f(a)，f1(a)，...，fs(a)

Vb =链中符号的变化f0(b) = f(b)，f1(b)，...，fs(b)

Va-Vb是该多项式在(a，b)范围内的不同根的个数。您可以将您的域划分为多个范围，并在每个范围中应用此过程。

现在最后一个问题是如何构建这样的链。常见的方法是使用Euclidean Algorithm的修改，即：

f0(x) = f(x) f1(x) = f'(x)

并从以下位置检索下一个术语：

f0(x) = q1(x)f1(x) - f2(x) ...fk-1(x) = qk(x)fk(x) - fk+1(x) ...fs-1(x) = qs(x)fs(x)

这是任意范围a，b中的Sturm链，其中f(a) != 0 != f(b)。或者，您也可以搜索可用于构建Sturm链的Legendre polynomials。你可能还想看看Budan-Fourier定理。

Answer 3

Vincent-Akritas方法通过递归确定根的连分式展开，通过封闭有理区间找到可证明的所有实根。

Dedieu-Yakoubsohn发表了二等分-排除原理，即Dandelin-Graeffe根平方迭代和根半径估计的组合，以可靠地定位实线或复平面上的所有根。

排除算法的简单形式描述(http://algo.inria.fr/seminars/sem92-93/yakoubsohn.ps‎) (需要Postscript查看器)

Published paper上一种更高效的算法形式。

Durand-Kerner (以及Aberth-Ehrlich)方法同时找到多项式的所有根，因此也不会遗漏任何根。此外，该方法的偏移量允许确定复平面中的根包围盘。