使用二分法求解复数域上多项式的根

5.00/5 (2投票s)

2024年6月4日

2分钟阅读

7757

244

使用“扩展”二分法寻找具有复数系数的多项式的根

引言

据我所知，二分法的缺点在于事先难以确定 p(a)*p(b) = -1 的条件，即多项式（在实数域上）何时改变符号。在上一篇文章（使用二分法求解实数和虚数根）中，通过求导多项式来找到这些点。现在，对于复数域上的多项式，只需要“上界”即可。

如果 P(x) = c_nxⁿ+a_n−1xⁿ⁻¹+...+c₀，根据柯西半径，所有根都将位于半径为

上界半径 = max { 1, ||c₀/c_n||, ||c₁/c_n||, ...,||c_n-1/c_n|| }。下界半径则是它的倒数，即

下界半径 = 1/(上界半径)。（如果上界 < 1，则交换上下界）。

如果半径为 1，实部和虚部的范围可能是 ±1 和 ±i。

现在，该应用程序找到在这些界限内，两个点的多项式值的实部和虚部具有相反符号的位置（Re(P(a))=-Re(P(b)) 且 Im(P(a))=-Im(P(b))）。当找到这些点（例如，“a”和“b”）时，可以确定根将位于以 (a+b)/2 为中心，半径为 (a-b)/2 的所有可能的圆的集合内。

修复了一些错误。

修复了一些错误。

修复了 Complex 类中的一个错误。复数求非整数次幂失败，因此最后两个根大多被错误地计算出来。

二分法得到了改进，响应速度也提高了。

提高了根的精度，尤其是在存在重根时。

在此版本中，根的精度是可选择的，因此执行时间也会相应变化。

为了提高精度，一些变量的类型从 Double 更改为 Rational。

在通过由“a”和“b”定义的圆的每次成功迭代后，代码会检查 Banach 不动点定理的条件。如果满足条件，则应用牛顿法。

这些更改使得选择精度变得不必要，因此已将其删除。