Approximating Complex Polynomial Zeros: Modified Weyl's Quadtree Construction and Improved Newton's Iteration
Approximating Complex Polynomial Zeros: Modified Weyl's Quadtree Construction and Improved Newton's Iteration
复制标题
逼近复杂多项式零点：改进的韦尔四叉树构造和改进的牛顿迭代
DOI：
10.1006/jcom.1999.0532
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
V. Pan
中科院分区：
文献类型：
--
作者：
V. Pan
本文给出了在误差界为2−b max j|zj|的情况下逼近n次多项式p(X)的零点zj的一个新算法。该算法使用O((N2)logn)和log(Bn))算术运算和比较来逼近所有n个零，并使用O((Kn)logn)和log(Bn)来逼近位于固定区域(圆盘或正方形)中的k个零且与其他零分离。不同于以往的这类快速算法，新算法具有简单的初等描述，便于实际实现，并允许用户根据计算过程中达到的当前逼近水平来调整计算精度，最终适应对p(X)的每个零的输出精度的要求。该算法依赖于我们对Weyl的四叉树结构和牛顿迭代的新版本。
Abstract We propose a new algorithm for the classical and still practically important problem of approximating zeros zj of an nth degree polynomial p(x) within error bound 2−b maxj |zj|. The algorithm uses O((n2 log n) log(bn)) arithmetic operations and comparisons for approximating all the n zeros and O((kn log n) log(bn)) for approximating the k zeros lying in a fixed domain (disc or square) and isolated from the other zeros. Unlike the previous fast algorithms of this kind, the new algorithm has its simple elementary description, is convenient for practical implementation, and allows the users to adapt the computational precision to the current level of approximation achieved in the process of computing and ultimately to the requirements to the output precision for each zero of p(x). The algorithm relies on our novel versions of Weyl's quadtree construction and Newton's iteration.