COMPUTING CHARACTERISTIC POLYNOMIALS FROM EIGENVALUES

This paper concerns the computation of the coefficients ck of the characteristic polynomial of a real or complex matrix A. We analyze the forward error in the coefficients ck when they are computed from the eigenvalues of A, as is done by MATLAB's poly function. In particular, we derive absolut...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on matrix analysis and applications 2011, Vol.32 (1), p.90-114
Main Authors: REHMAN, Rizwana, IPSEN, Ilse C. F
Format: Article
Language:English
Subjects:
Accuracy
Algebra
Algebraic combinatorics
Algorithms
Combinatorics
Combinatorics. Ordered structures
Computation
Eigenvalues
Exact sciences and technology
Linear and multilinear algebra, matrix theory
Mathematical models
Mathematics
Matrix
Nonlinear algebraic and transcendental equations
Numerical analysis
Numerical analysis. Scientific computation
Numerical linear algebra
Perturbation methods
Polynomials
Roundoff error
Running
Sciences and techniques of general use
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper concerns the computation of the coefficients ck of the characteristic polynomial of a real or complex matrix A. We analyze the forward error in the coefficients ck when they are computed from the eigenvalues of A, as is done by MATLAB's poly function. In particular, we derive absolute and relative perturbation bounds for elementary symmetric functions, which we use in turn to derive perturbation bounds for the coefficients ck with regard to absolute and relative changes in the eigenvalues λj of A. We present the so-called Summation Algorithm for computing the coefficients ck from the eigenvalues λj , which is essentially the algorithm used by poly. We derive roundoff error bounds and running error bounds for the Summation Algorithm. The roundoff error bounds imply that the Summation Algorithm is forward stable. The running error bounds can be used to estimate the accuracy of the computed coefficients "on the fly," and they tend to be less pessimistic than the roundoff error bounds. Numerical experiments illustrate that our bounds give useful estimates for the accuracy of the coefficients ck. In particular, the bounds confirm that poly computes the coefficients ck to high relative accuracy if the eigenvalues are positive and given to high relative accuracy. [PUBLICATION ABSTRACT]
ISSN:0895-4798
1095-7162
DOI:10.1137/100788392