论文标题
全球收敛的多项式牛顿方法
A Globally Convergent Newton Method for Polynomials
论文作者
论文摘要
牛顿的多项式根发现方法是数学最著名的算法之一。该方法还存在其缺点：它在临界点不确定，它可能表现出混乱的行为，并且只能保证在本地汇聚。 Based on the {\it Geometric Modulus Principle} for a complex polynomial $p(z)$, together with a {\it Modulus Reduction Theorem} proved here, we develop the {\it Robust Newton's method} (RNM), defined everywhere with a step-size that guarantees an {\it a priori} reduction in polynomial modulus in each iteration.此外，我们证明RNM迭代全球收敛，无论是根或临界点。具体而言，给定的$ \ varepsilon $和任何种子$ z_0 $，in $ t = o（1/\ varepsilon^{2}）$ rnm的迭代，独立于$ p（z）$，$ | p（z_t）|独立于$ p（z）$ \ leq \ varepsilon $或$ | p（z_t）p'（z_t）| \ leq \ varepsilon $。通过在{\ it接近临界点}处调整迭代率，我们描述了一个{\ it修改} rnm，必须将其收敛到根。结合Smale的点估计，RNM导致全球收敛的牛顿的方法具有局部二次率。我们提出了样品多数式仪，这些样品表明与牛顿的方法RNM形成鲜明对比的是如何平滑根吸引根的分形边界。 RNM还发现了计算任意程度多项式的所有根的潜力。 RNM的特殊结果是用于求解立方方程的简单算法。
Newton's method for polynomial root finding is one of mathematics' most well-known algorithms. The method also has its shortcomings: it is undefined at critical points, it could exhibit chaotic behavior and is only guaranteed to converge locally. Based on the {\it Geometric Modulus Principle} for a complex polynomial $p(z)$, together with a {\it Modulus Reduction Theorem} proved here, we develop the {\it Robust Newton's method} (RNM), defined everywhere with a step-size that guarantees an {\it a priori} reduction in polynomial modulus in each iteration. Furthermore, we prove RNM iterates converge globally, either to a root or a critical point. Specifically, given $\varepsilon $ and any seed $z_0$, in $t=O(1/\varepsilon^{2})$ iterations of RNM, independent of degree of $p(z)$, either $|p(z_t)| \leq \varepsilon$ or $|p(z_t) p'(z_t)| \leq \varepsilon$. By adjusting the iterates at {\it near-critical points}, we describe a {\it modified} RNM that necessarily convergence to a root. In combination with Smale's point estimation, RNM results in a globally convergent Newton's method having a locally quadratic rate. We present sample polynomiographs that demonstrate how in contrast with Newton's method RNM smooths out the fractal boundaries of basins of attraction of roots. RNM also finds potentials in computing all roots of arbitrary degree polynomials. A particular consequence of RNM is a simple algorithm for solving cubic equations.
