Structural backward stability in rational eigenvalue problems solved via block Kronecker linearizations

Abstract

We study the backward stability of running a backward stable eigenstructure solver on a pencil $S(\lambda )$ that is a strong linearization of a rational matrix $R(\lambda )$ expressed in the form $R(\lambda )=D(\lambda )+C(\lambda I_{\ell }-A{)}^{-1}B$, where $D(\lambda )$ is a polynomial matrix and $C(\lambda I_{\ell }-A{)}^{-1}B$ is a minimal state-space realization. We consider the family of block Kronecker linearizations of $R(\lambda )$, which are highly structured pencils. Backward stable eigenstructure solvers applied to $S(\lambda )$ will compute the exact eigenstructure of a perturbed pencil $\hat{S}(\lambda ):=S(\lambda )+{\Delta }_S(\lambda )$ and the special structure of $S(\lambda )$ will be lost. In order to link this perturbed pencil with a nearby rational matrix, we construct a strictly equivalent pencil $\tilde{S}(\lambda )$ to $\hat{S}(\lambda )$ that restores the original structure, and hence is a block Kronecker linearization of a perturbed rational matrix $\tilde{R}(\lambda )=\tilde{D}(\lambda )+\tilde{C}(\lambda I_{\ell }-\tilde{A}{)}^{-1}\tilde{B}$, where $\tilde{D}(\lambda )$ is a polynomial matrix with the same degree as $D(\lambda )$. Moreover, we bound appropriate norms of $\tilde{D}(\lambda )-D(\lambda )$, $\tilde{C}-C$, $\tilde{A}-A$ and $\tilde{B}-B$ in terms of an appropriate norm of ${\Delta }_S(\lambda )$. These bounds may be inadmissibly large, but we also introduce a scaling that allows us to make them satisfactorily tiny. Thus, for this scaled representation, we prove that the staircase and the $QZ$ algorithms compute the exact eigenstructure of a rational matrix $\tilde{R}(\lambda )$ that can be expressed in exactly the same form as $R(\lambda )$ with the parameters defining the representation very near to those of $R(\lambda )$. This shows that this approach is backward stable in a structured sense.