In minisymposium: Matrix Structures and Univariate Polynomial RootfindingFri 12:00–12:30, Room AV 91.12
Backward error analyses of algorithms for solving polynomial eigenvalue problems, as well as scalar polynomial root-finding problems, can be "local" or "global". The goal of "local" analyses is to prove that any computed eigenvalue is the exact eigenvalue of a nearby matrix polynomial, which may be different for each eigenvalue. In contrast, the aim of "global" analyses is to prove that the whole set of computed eigenvalues is the whole set of exact eigenvalues of a nearby matrix polynomial. Clearly, "global" analyses are much harder than "local" ones, since a "global" backward error result implies a local one, but the opposite is not true. This, among other reasons, has motivated considerable activity on "local" analyses in the last years, while the number of results on "global" analyses is very low. In this talk, we present a new approach to global backward error analyses for polynomial eigenvalue problems solved via linearizations, which is based on the concept of dual minimal bases and the solution of certain matrix equations. This approach allows us to prove global backward error results for a huge class of linearizations that include, among many others, all Fiedler linearizations, to include in the analysis the minimal indices in addition to the eigenvalues, and to provide more precise bounds than the ones previously available in the literature.