Inverse Power and Durand-Kerner Iterations for Univariate Polynomial Root-Finding

摘要

Univariate polynomial root-finding is the oldest classical problem of mathematics and computational mathematics, and is slill an important research topic, due to its impact on computational algebra and geometry. The Weierstrass (Durand-Kerner) approach and its variations as well as matrix methods based on the QR algorithm are among the most popular practical choices for simultaneous approximation of all roots of a polynomial. We propose an alternative application of the inverse power iteration to generalized companion matrices for polynomial root-finding, demonstrate its effectiveness, and relate its study to unifying the derivation of the Weierstrass (Durand-Kerner) algorithm (having quadratic convergence) and its extensions having convergence rates 4,6,8,… Our experiments show substantial improvement versus the latter algorithm, even though the inverse power iteration is most effective for the more limited tasks of approximating a single root or a few selected roots.