Polynomial root finding using iterated Eigenvalue computation

摘要

We analyze an iterative algorithm that approximates all roots of a univariate polynomial. The algorithm is based on (hardware) floating-point eigenvalue computation of a generalized companion matrix. With some assumptions, we show that it approximates the roots to floating-point accuracy within about log&rgr;/e X(P) iterations, where ∈ is the relative error of floating-point arithmetic, &rgr; is the relative separation of the roots, and X(P) is the condition number of the polynomial. Each iteration requires an n × n floating-point eigenvalue computation, n the polynomial degree, and evaluation of the polynomial to floating-point accuracy at n points. On some hard examples of ill-conditioned polynomials, e.g. high-degree Wilkinson polynomials, the algorithm is an order of magnitude faster than the best alternative.