On backward errors of structured polynomial eigenproblems solved by structure preserving linearizations (Q630552)

If \(P\) is an \(n\times n\) matrix polynomial of degree \(m\), then the eigenvalue problem is to find pairs \((\lambda,x)\in({\mathbb C},{\mathbb C}^n)\) such that \(P(\lambda)x=0\) with \(x^Hx=1\). The structures considered here are \(P^T(z)=\pm P(z)\) or \(P^T(z)=\pm P(-z)\), \(\forall z\in{\mathbb C}\) or the Hermitian analogs where \(P^T\) is replaced by \(P^H\). Suppose that \((\lambda,x)\) is an approximate solution that satisfies exactly \((P(\lambda)+\Delta P(\lambda))x=0\) where \(\Delta P\) has the same structure as \(P\). A minimal \(\Delta P\) is constructed and computable bounds on \(\Delta P\) (backward error) are given. This generalizes similar results for matrix pencils by \textit{B. Adhikari} and \textit{R. Alam} [SIAM J. Matrix Anal.\ Appl. 31, No.~2, 331--359 (2009; Zbl 1252.65074)]. For small \(\Delta P\), the spectrum of \(P+\Delta P\) is a structured (unstructured) pseudospectrum of \(P\) if \(\Delta P\) has (has not) the same structure as \(P\). The structured pseudospectrum is analysed and its relation with the unstructured one is given. Finally several structured linearizations (i.e., the reduction of the structured polynomial problem of size \(n\) to a plain generalized eigenvalue problem of size \(mn\)) are considered and the effect that they have on the backward error is exposed.