Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Polynomial roots from companion matrix eigenvalues

Authors: Alan Edelman and H. Murakami
Journal: Math. Comp. 64 (1995), 763-776
MSC: Primary 65F15; Secondary 65G10, 65H05
MathSciNet review: 1262279
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In classical linear algebra, the eigenvalues of a matrix are sometimes defined as the roots of the characteristic polynomial. An algorithm to compute the roots of a polynomial by computing the eigenvalues of the corresponding companion matrix turns the tables on the usual definition. We derive a first-order error analysis of this algorithm that sheds light on both the underlying geometry of the problem as well as the numerical error of the algorithm. Our error analysis expands on work by Van Dooren and Dewilde in that it states that the algorithm is backward normwise stable in a sense that must be defined carefully. Regarding the stronger concept of a small componentwise backward error, our analysis predicts a small such error on a test suite of eight random polynomials suggested by Toh and Trefethen. However, we construct examples for which a small componentwise relative backward error is neither predicted nor obtained in practice. We extend our results to polynomial matrices, where the result is essentially the same, but the geometry becomes more complicated.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F15, 65G10, 65H05

Retrieve articles in all journals with MSC: 65F15, 65G10, 65H05

Additional Information

Keywords: Algebraic equation, QR method, eigenvalue
Article copyright: © Copyright 1995 American Mathematical Society