Structured backward error for palindromic polynomial eigenvalue problems (Q985700)

For given \(n\times n\) matrices \(A_j\), a palindromic matrix polynomial takes the form \[ P(\lambda) = \sum_{\ell = 0}^d \lambda^\ell A_\ell \quad A_{d-\ell} = \varepsilon A_\ell^\star, \quad \ell = 0,1,\dots,\lfloor d/2\rfloor, \] where \(\star\) denotes the transpose or conjugate transpose of a matrix and \(\varepsilon \in \{+1,-1\}\). If \(P(\lambda)x =0\) for \(x \not = 0\) then \((\lambda,x)\) is called an eigenpair of \(P\). The paper is concerned with the following structured backward error problem: Given a pair \((\mu,z)\), determine the norm of the minimal perturbation \(\triangle P\) such that \(P + \triangle P\) remains palindromic and \((\mu,z)\) becomes an eigenpair of \(P + \triangle P\). Here, the norm of \(\triangle P\) is understood as a weighted spectral or Frobenius norm of its coefficient matrices. Computable expressions for the structured backward error for all instances of palindromic matrix polynomials are provided. Moreover, numerical experiments highlight the critical cases \(|\mu| = 1\) (when \(\star\) denotes the conjugate transpose) and \(\mu = \pm 1\) (when \(\star\) denotes the transpose).