APPROXIMATING COMPLEX POLYNOMIAL ZEROS: MODIFIED

WEYL’S QUADTREE CONSTRUCTION AND IMPROVED NEWTON’S ITERATION

VICTOR PAN

Abstract. We propose a new algorithm for the classical and still practically important problem of approximating the zeros z_{j} of an n-th degree polynomial p(x)within the error bound 2^{−b} max_{j} |z_{j}|. The algorithm uses O((n^{2} 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) 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 in the process of computing allows the users to adapt the computational precision to the current level of approximation and ultimately to the requirements on the output precision for each zero of p(x). The algorithm relies on the novel versions of Weyl’s quadtree construction and Newton’s iteration.