We discuss an iterative algorithm that approximates all roots of a univariate polynomial. The iteration is based on floating-point computation of the eigenvalues of a generalized Companion matrix. With some assumptions, we show that the algorithm approximates The roots within about log_ρ/εχ(P)iterations, whereεis the relative error of floating- Point arithmetic,ρis the relative separation of the roots, andχ(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 up to n points.
展开▼
