百斯托法的初始二次逼近

Question

拜斯托根查找法需要非常好的初始近似值来收敛二次因子。

我尝试了各种常数、随机数、分数（通过Lin计算-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查找根需要的时间是使用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%）

---

尝试使用柯西(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

很遗憾，这并没有真正加快收敛速度。

- Ecir Hana

Answer 1

我已经为这篇文章提供了图片，可以告诉你并不需要非常精确的近似值。

最重要的初始步骤是将多项式降至偶次幂，如文章中所述。之后，你不会做错任何事情，几乎应该有全局收敛性。确保的方法与牛顿法相同：如果经过10步没有明显的收敛迹象，请使用不同的初始点重新开始。

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

---

请查看http://catc.ac.ir/mazlumi/jscodes/bairstow.php的源代码中的javascript实现，其中包括一个“naive”或“vanilla”但看起来很稳健的实现。不进行偶次幂降低，不考虑系数/根大小，...

---

此例子是单位圆盘内的奇次多项式，其中一个根为-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)等方式进行初始化。

- Lutz Lehmann

---

第一个问题不应该经常发生。多个根始终是一个问题。在通常的算法中，只有Jenkins-Traub相对而言比较强大，它仅在小除数的情况下受到取消误差的影响。如果可能的话，您能否在问题中记录第一个问题的一个小实例？ - Lutz Lehmann

看到你的编辑了。顺便说一下，当我将这个例子插入你提供的“原始”实现中时，它会冻结。 - Ecir Hana

但是只有每三到四次，这表明对初始条件的重度依赖，在脚本中是随机的。 - Lutz Lehmann

抱歉，我不理解最后一句话的意思：第二部分是半径为R的圆上的随机点，但第一部分是什么？我的意思是，我需要两个数字来猜测二次因子，请问在“x^2-R^2”中的“x”是什么？ - Ecir Hana

这个多项式有一个很大的系数。在原始比例下，它接近于 x^8+118*x^7。它有一个根 x=-118 和七个根 x=0。在小扰动下，这不会改变太多。对于小根，主导项 x^8 是一个小扰动，支配二项式是 7 次多项式 118*x^7+1。因此，对于具有小根的二次因子，这基本上是奇次情况。如果收敛到复杂解，则行为良好，如果是实根，则发散或收敛缓慢。 - Lutz Lehmann