论文标题
通过动态系统查找多项式根部 - 案例研究
Finding polynomial roots by dynamical systems -- a case study
论文作者
论文摘要
我们研究了两个众所周知的动力系统，这些系统旨在通过迭代来找到单变量多项式的根：牛顿和埃里希·亚伯斯的方法。众所周知，两者都发现了所有具有良好复杂性的高度多项式根源。我们的目标是确定两种算法中哪种更有效的情况。我们得出的结论是，当递归给出多项式时，牛顿的速度更快，因此可以在对数时间中对其进行评估，或者当所有根都在其凸船上的边界附近时。相反，当没有对多项式的快速评估时，并且当根部在其他根部的凸壳内部时，Ehrlich-Aberth具有优势。
We investigate two well known dynamical systems that are designed to find roots of univariate polynomials by iteration: the methods known by Newton and by Ehrlich-Aberth. Both are known to have found all roots of high degree polynomials with good complexity. Our goal is to determine in which cases which of the two algorithms is more efficient. We come to the conclusion that Newton is faster when the polynomials are given by recursion so they can be evaluated in logarithmic time with respect to the degree, or when all the roots are all near the boundary of their convex hull. Conversely, Ehrlich-Aberth has the advantage when no fast evaluation of the polynomials is available, and when roots are in the interior of the convex hull of other roots.
