复平面上多项式方程的零点

Source: Dev.to

摘要

在本文中，我们讨论了用于在复平面上寻找次数为 (n) 的多项式方程零点的 Laguerre 算法。我们推导了一个特例并分析了对单根的收敛性。通过实现该算法的示例进行验证，展示了其优点和局限性。

介绍

寻找 (n) 次多项式零点的问题在几个世纪里对数学的发展产生了深远影响，并且在实际和理论应用中仍然重要。

目前，对形如

[ p(z)=\sum_{i=0}^{n} a_i z^{i}\qquad (1) ]

的多项式的研究并未在数学或应用数学中占据核心地位。在许多情况下，问题会被线性化并使用线性代数工具和快速傅里叶变换来求解，这可能涉及多项式方程的根。

尽管如此，这类方程在某些应用数学领域仍然受到关注，寻找其根的算法也在不断开发和研究。

正如阿贝尔在 1827 年所证明的，对于次数 (\ge 4) 的多项式，没有能够以根式给出精确解的公式；因此，任何需要求解此类多项式的问题都必须依赖数值方法。

在本文中，我们讨论复平面上的拉盖尔（Laguerre）方法以及针对几类多项式的实现。

理论结果

初始定义和定理

Definition 1 (order of convergence).
如果一个算法在根 (\eta) 处满足

[ \lim_{n\to\infty}\frac{|z_{n+1}-\eta|}{|z_n-\eta|^{\alpha}}=C\qquad (2) ]

其中常数 (C\neq0)，则称该算法的收敛阶为 (\alpha)。

Definition 2 (global vs. local method).
如果数值方法在收敛时 不需要 初始值足够接近多项式的零点，则称其为 global 方法；否则称为 local 方法。

Theorem 1.
设 (p(z)) 为次数 (n>1) 的复系数多项式，则 (p(z)) 恰好有 (n) 个复根（计重数）。

Theorem 2.
设 (p(z)) 为次数 (m>4) 的标准化多项式，记

[ P={p_i : i\in{1,\dots ,\ell}} ]

为其根的集合。对于初始点

[ u_0\in\mathbb{C}\setminus P,\qquad p’(u_0)\neq0\ \text{or}\ p”(u_0)\neq0, ]

定义序列

[ L_p(u_0)=\bigl(u_n\bigr)_{n\in\mathbb{N}} ]

通过

[ u_{n+1}=u_n-\frac{m}{,q(u_n)+s(u_n)r(u_n)}\qquad (3) ]

其中

[ \begin{aligned} q(z)&=\frac{p’(z)}{p(z)},\ t(z)&=q(z)^2-\frac{p”(z)}{p(z)},\ r(z)&=\sqrt{(m-1)\bigl(mt(z)-q(z)^2\bigr)}, \end{aligned} ]

且

[ s(z)= \begin{cases} ;1, & \text{if } \operatorname{Re}q(z),\operatorname{Re}r(z)+\operatorname{Im}q(z),\operatorname{Im}r(z)\ge0,\[4pt] -1, & \text{otherwise}. \end{cases} ]

分母永不为零：(q(u_n)+s(u_n)r(u_n)\neq0)。

如果存在一个 简单 根 (p\in P) 使得

[ |u_0-p|\le\frac{1}{2m-1}\min_{p_i\in P\setminus{p}}|p-p_i|, ]

则序列 (L_p(u_0)) 收敛到 (p)，并且

[ |u_n-p|\le\lambda^{,n},|u_0-p|,\qquad \lambda=\frac{15}{16},\qquad n\in\mathbb{N}\setminus{0}. ]

如果 所有 根都是简单的，则在上述不等式中

[ \mu_p=\min_{p_i\in P\setminus{p}}|p-p_i| ]

可以由下式下界估计

[ \Bigl(1+\frac{1}{d_0}\max_{1\le j\le\binom{m}{2}}|d_j|\Bigr)^{-\frac12} ]

（原文续）。

实现库

利用前一节的结果，构建了以下库：

在 deflation 和 evalpoly 例程中最容易出现舍入误差；因此所有计算均使用 long double 精度以减轻这些误差。

结果与讨论

进行了一系列测试；其中最具代表性的结果列在下表中。

• 对于低次数多项式，算法能够达到显著的精度——例如，一个数的平方根可以近似到 13 位小数。
• 对于重根次数 (\le 10) 的情况，算法表现异常良好，尽管它并非专门为多重根设计。
• 当次数升高时，开始出现发散。增加最大迭代次数并不能改善，因为对于多重根，方法仅线性收敛，可能需要极其大量的迭代次数才会收敛。
• 对于简单根且次数 (n>10) 的多项式，行为有所改善，但表中最后两个多项式仍展示了失败的情况：算法在计算最后一个根时发生发散，只找到了 14 个根中的 13 个。
• 随着次数显著增加，整体精度急剧下降。

测试结果表

Conclusion

对于首次实现，算法在中等规模问题上表现良好。然而，若投入更多开发时间，它可以得到显著优化。在当前状态下，代码不适用于高性能生产环境（例如 Mathematica 或 MATLAB 级别的任务）。

完整的源代码已在 GitHub 上提供。

参考文献

1. Pan, Y., & Victor, 求解多项式方程：一些历史与最新进展, SIAM Review, 39(2), 187‑220 (1997).
2. Ahlfors, L., 复变分析, McGraw‑Hill, 1979.
3. Møller, H., Laguerre根寻找算法的收敛性与可视化, 9 January 2015.
4. Acton, S. F., 有效的数值方法, The Mathematical Association of America, 1990.
5. Kiusalaas, J., 使用Python 3的工程数值方法, Cambridge University Press, 2013.