Publication: Backward error and conditioning of Fiedler linearizations
Loading...
Identifiers
Publication date
2020-05-01
Defense date
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
American Mathematical Society
Impact
Export
Abstract
The standard way to solve polynomial eigenvalue problems is
through linearizations. The family of Fiedler linearizations, which includes
the classical Frobenius companion forms, presents many interesting properties
from both the theoretical and the applied point of view. These properties make
the Fiedler pencils a very attractive family of linearizations to be used in the
solution of polynomial eigenvalue problems. However, their numerical features
for general matrix polynomials had not yet been fully investigated. In this
paper, we analyze the backward error of eigenpairs and the condition number
of eigenvalues of Fiedler linearizations in the solution of polynomial eigenvalue
problems. We get bounds for: (a) the ratio between the backward error of
an eigenpair of the matrix polynomial and the backward error of the corresponding
(computed) eigenpair of the linearization, and (b) the ratio between
the condition number of an eigenvalue in the linearization and the condition
number of the same eigenvalue in the matrix polynomial. A key quantity in
these bounds is ρ, the ratio between the maximum norm of the coefficients of
the polynomial and the minimum norm of the leading and trailing coefficient.
If the matrix polynomial is well scaled (i. e., all its coefficients have a similar
norm, which implies ρ ≈ 1), then solving the Polynomial Eigenvalue Problem
with any Fiedler linearization will give a good performance from the point of
view of backward error and conditioning. In the more general case of badly
scaled matrix polynomials, dividing the coefficients of the polynomial by the
maximum norm of its coefficients allows us to get better bounds. In particular,
after this scaling, the ratio between the eigenvalue condition number in any
two Fiedler linearizations is bounded by a quantity that depends only on the
size and the degree of the polynomial. We also analyze the effect of parameter
scaling in these linearizations, which improves significantly the backward error
and conditioning in some cases where ρ is large. Several numerical experiments
are provided to support our theoretical results.
Description
Keywords
Matrix polynomial, Matrix pencil, Eigenvalue, Eigenvector, Polynomial eigenvalue problem, Companion linearization, Fiedler Pencil, Conditioning, Backward error, Scaling
Bibliographic citation
Mathematics of Computation, (2020), 89(323), pp.: 1259-1300.