Backward Perturbation and Sensitivity analysis of Structured polynomial Eigenomial Eigenvalue Problem

Abstract

The main theme of the thesis is structured perturbation and sensitivity analysis of structured polynomial eigenvalue problem. Structured mapping problem naturally arises when analyzing structured backward per- turbation of structured eigenvalue problem. Given two matrices X and B of same size, the structured mapping problem requires to Dnd a \structured"" matrix A; if any, having the small- est norm such that AX = B: We provide a complete solution of structured mapping problem. More generally, we provide a complete solution of the structured inverse least-squared problem (SILSP): min A kAX D BkF ; where the minimum is taken over \structured"" matrices. As a consequence of structured map- ping problem, we determine structured backward errors of approximate invariant subspaces of structured matrices. We also analyze structured pseudospectra of structured matrices. Next, we undertake a detailed structured backward perturbation analysis of structured ma- trix polynomials and derive explicit computable expressions for structured backward errors of approximate eigenelements. We analyze structured pseudospectra of structured matrix poly- nomials and establish a partial equality between unstructured and structured pseudospectra, which plays an important role in solving certain distance problems associated with structured polynomials. We also derive relatively simple expressions for structured condition numbers of simple eigenvalues of structured matrix polynomials, which play an important role in ana- lyzing sensitivity of eigenvalues of structured polynomial eigenvalue problem. Generally, a polynomial eigenvalue problem is \linearized"" Drst and then solved by a back- ward stable algorithm. However, the eigenvalues of the resulting linear problem is usually more sensitive to perturbation than the original problem. Moreover, a polynomial admits inDnitely many linearizations. The same holds true for structured polynomials as well. Therefore, for computational purposes, it is of paramount importance to identify potential structured lin- earizations which are as well conditioned as possible. With the help of structured backward perturbation analysis and structured condition numbers of eigenvalues, we identify \good"" structured linearizations which guarantee almost as accurate solutions as that of the original polynomial eigenvalue problem..