Graeffe's, Chebyshev-like, and Cardinal's Processes for Splitting a Polynomial into Factors
Graeffe's, Chebyshev-like, and Cardinal's Processes for Splitting a Polynomial into Factors
复制标题
将多项式分解为因子的格雷夫过程、类切比雪夫过程和卡迪纳尔过程
DOI：
10.1006/jcom.1996.0030
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
V. Pan
中科院分区：
文献类型：
--
作者：
Dario Bini;V. Pan
实际或复杂的单变量多项式分解为因子是近似复杂多项式零的分裂和诱导算法的基本步骤。这样的算法是最佳的（取决于多毛体因子），并且对于实际计算而言是非常有希望的。在本文中，我们开发了一些新技术，使我们能够改善已知拆分算法的数值分析，性能和计算成本范围。特别是，我们研究了Graeffe举重迭代的类似Chebyshev的修改（这是分裂算法的基本块，以及用于近似多项式零的其他几种已知算法），分析其数字性能，将其与Graeffe相比一些结果的结果是两个提升过程的数值稳定性（即Graeffe和类似于Chebyshev），研究其将其纳入多项式探望算法，并提出了Cardinal最近有效技术的一些改进，以将多项式分解为因素。我们的改进尤其依赖于对矩阵标志迭代的修改，基于对复杂平面的某些共形映射的分析以及递归提升/递归下降的技术。后一种分析揭示了Graeffe，类似Chebyshev和Cardinal的迭代过程之间的一些隐藏相关性，我们利用这些相关性以改善红衣主教的算法。我们的工作也可能具有一定的独立兴趣，可以研究复杂平面对多项式根找到的共形图的应用以及用于多项式根找到的基本技术的数值特性，例如Graeffe's和Chebyshev类似迭代。
Numerical splitting of a real or complex univariate polynomial into factors is the basic step of the divide-and-conquer algorithms for approximating complex polynomial zeros. Such algorithms are optimal (up to polylogarithmic factors) and are quite promising for practical computations. In this paper, we develop some new techniques, which enable us to improve numerical analysis, performance, and computational cost bounds of the known splitting algorithms. In particular, we study a Chebyshev-like modification of Graeffe's lifting iteration (which is a basic block of the splitting algorithms, as well as of several other known algorithms for approximating polynomial zeros), analyze its numerical performance, compare it with Graeffe's, prove some results on numerical stability of both lifting processes (that is, Graeffe's and Chebyshev-like), study their incorporation into polynomial root-finding algorithms, and propose some improvements of Cardinal's recent effective technique for numerical splitting of a polynomial into factors. Our improvement relies, in particular, on a modification of the matrix sign iteration, based on the analysis of some conformal mappings of the complex plane and of techniques of recursive lifting/recursive descending. The latter analysis reveals some otherwise hidden correlations among Graeffe's, Chebyshev-like, and Cardinal's iterative processes, and we exploit these correlations in order to arrive at our improvement of Cardinal's algorithm. Our work may also be of some independent interest for the study of applications of conformal maps of the complex plane to polynomial root-finding and of numerical properties of the fundamental techniques for polynomial root-finding such as Graeffe's and Chebyshev-like iterations.