math - Bairstow 方法初始二次近似

Question

Bairstow's root finding method需要非常好的二次因子初始近似才能收敛。

我尝试了各种常数、随机数、尾随系数的分数(-a1/a2、-a0/a2；由 Lin？)，但无济于事。

请问有人知道选择因素的好方法吗？

例如:

1*x^8 + 118*x^7 + 1*x^6 + 2*x^5 - 2*x^4 - 3*x^3 + 3*x^2 + 2*x + 1

使用初始近似值 0.1、0.2 查找根所需的时间是使用 0.2、2.0 查找根所需的时间的 3 倍。

或者:

1*x^8 - 36*x^7 + 546*x^6 - 4536*x^5 + 22449*x^4 - 67284*x^3 + 118124*x^2 - 109584*x + 40320

0.1、1.2 比 0.1、0.1 花费的时间稍长(约 50%)

<小时/>

尝试使用柯西界进行初始二次近似:

R=0
for i in range(1,n+1):
    R=max(abs(a[i]/a[0]),R)
R=1+R
phi=2*pi*random()
x1=complex(R*cos(phi),R*sin(phi))
x2=complex(x1.real,-x1.imag)
r=-x1.real-x2.real
s=(x1*x2).real

不幸的是，这并没有真正加速收敛。

Answer 1

由于我已经撰写了这篇文章并提供了图片，所以我可以看出您确实不需要那么好的近似值。

最重要的初始步骤是将多项式减少到偶数次，如文章中所述。之后，你就不会做错了，应该几乎是全局收敛的。当然，与牛顿方法相同:如果 10 步后没有明显的收敛迹象，则以不同的初始点重新开始。

计算一些外根半径并选择初始二次因子以使根在此半径内当然是明智的。

<小时/>

查看http://catc.ac.ir/mazlumi/jscodes/bairstow.php源代码中的javascript实现一个“天真的”或“普通”但看似强大的实现。不减少到偶数，不关心系数/根大小，...

<小时/>

该示例实际上是单位圆盘内的奇数次多项式，在虚拟无穷远处具有一个根-117.9917。对于每一步的初始化，都应该计算外根半径，在“1+系数的绝对值最大值”(前导系数 1)版本中为 R=119。然后使用 x^2-R^2 或 phi=2*pi*random(); 和 x^2+R^2*cos(phi )*x+R^2*sin(phi) 或类似的东西。