Bairstow的方法初始二次近似

Question

Bairstow的根寻找方法需要对二次因子进行非常好的初始近似以便收敛.

我尝试了各种常数,随机数,尾随系数中的分数(-a1/a2,-a0/a2;林？)无效.

请问,有没有人知道选择这些因素的好方法？

例如:

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需要3倍,而0.2,2.0.

要么:

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%)

---

尝试使用Cauchy的边界进行初始二次近似:

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位于虚拟无穷远。对于每一步的初始化，都应该计算外根半径，它是R=119“1+最大系数的绝对值”（前导系数 1）版本。然后用x^2-R^2orphi=2*pi*random();和x^2+R^2*cos(phi)*x+R^2*sin(phi)或类似的东西初始化。