Polynomial and rational spectral problemsconditioning, backward errors and inverse problems

Résumé

This PhD thesis belongs to the areas of Matrix Analysis and Numerical Linear Algebra and has been devoted to solve problems that have arisen as a consequence of the development of new applications during the last two decades. More precisely, these problems belong to two related areas: polynomial eigenvalue problems (PEPs) and rational eigenvalue problems (REPs). Due to the mentioned recent interest into the numerical solution of the PEP, several condition numbers for simple eigenvalues of regular matrix polynomials have appeared in the literature. In order to study the conditioning of all the eigenvalues of a matrix polynomial in a unified framework, some of these eigenvalue condition numbers consider the matrix polynomial to be expressed in homogeneous form. Then, the first problem we address in the field of matrix polynomials is to obtain a relationship between the two main homogeneous eigenvalue condition numbers that have appeared in the literature. Furthermore, we also obtain a relationship between the non-homogeneous and the former homogeneous eigenvalue condition numbers. This latter relationship allows to extend results that have been proved for one of the versions of the eigenvalue condition numbers to the other. We also obtain a relationship between the homogeneous and the non-homogeneous backward errors of approximate eigenpairs that states they are essentially equivalent. Möbius transformations is a classical tool that have been used in the theory of matrix polynomials (and in their applications) since, at least, the 1950s. One of the main use of these transformations is to convert a polynomial eigenvalue problem into another that can be solved more easily. If the numerical solution of a problem is obtained by applying a Möbius transformation, an important question is to study if this transformation worsens the conditioning of the problem and/or the backward errors of the approximate solutions. In this dissertation, we present for the first time, up to our concern, a general study of the effect of Möbius transformations on the eigenvalue condition numbers and backward errors of approximate eigenpairs of matrix polynomials. The study of the effect of Möbius transformations on eigenvalue condition numbers and backward errors of approximate eigenpairs is separated in two parts: one for the homogeneous and another for the non-homogeneous version of these magnitudes. Since the homogeneous formulation allows us to obtain two clear and simple results, we perform this analysis first on the homogeneous case. We prove that for any matrix polynomial and any simple eigenvalue, if the matrix that induces the Möbius transformation is well conditioned, then the transformation approximately preserves the homogeneous eigenvalue condition numbers and backward errors of approximate eigenpairs when small perturbations of the matrix polynomial relative to the norm of the whole polynomial are considered in the definition of both the condition number and the backward error. If in the definition of the former magnitudes, perturbations in each coefficient of the matrix polynomial are small relative to the norm of that coefficient, well-conditioned matrices induce Möbius transformations that approximately preserve the eigenvalue condition numbers and backward errors of approximate eigenpairs only if a factor that depends on the norm of the coefficients of the polynomial is moderate. For the non-homogeneous versions of the eigenvalue condition number, the conclusions obtained are not so simple. Nevertheless, we present sufficient conditions depending not only on the conditioning of the matrix that induces the Möbius transformation, but also on the eigenvalue and the corresponding eigenvalue of the Möbius transform. In order to perform this analysis, we use the study realized for the homogeneous case and the relationship obtained between the homogeneous and the non-homogeneous eigenvalue condition numbers. Furthermore, the relationship between the homogeneous and the non-homogeneous backward error of approximate eigenpairs allows us to conclude that the effect of Möbius transformations is the same in the homogeneous and the non-homogeneous backward errors. We also address the problems of degree-preserving quasi-triangularization of matrix polynomials and inverse quasi-triangularization. These two problems have already been studied in the literature by Taslaman, Tisseur and Zaballa in 2013, but only for matrix polynomials defined over algebraically closed fields or R. In this dissertation we find preserving degree quasi-triangularizations of regular matrix polynomials defined over an arbitrary field, that is, for a given matrix polynomial P(λ) we build a block upper triangular matrix polynomial Q(λ) that is unimodularly equivalent to P(λ) and has the same size and the same degree as P(λ), as well as the same finite and infinite elementary divisors. The maximum size of the blocks of the obtained matrix polynomial Q(λ) is the maximum degree of the irreducible factors of the invariant polynomials of P(λ). Furthermore, we prove that given a list of prescribed data (including possibly infinite elementary divisors), we can find a quasi-triangular matrix polynomial of given degree d and size nxn that realizes that list and such that the maximum size of the blocks does not exceed the maximum degree of the irreducible factors of the prescribed invariant polynomials if and only if dn is equal to the sum of the degrees of the invariant polynomials and the infinite elementary divisors (if any). The rational matrices problem that we study in this PhD thesis (which has been settled recently for matrix polynomials by De Terán, Dopico and Van Dooren in 2015) consists of finding a necessary and sufficient condition for the existence of a rational matrix that realizes a prescribed complete list of structural data (finite and infinite zeros and poles together with their structural indices and the minimal indices of left and right rational nullspaces). This necessary and sufficient condition is that these data satisfy a fundamental relation appearing in Van Dooren's Index Sum Theorem.