Structured eigenvalue backward errors of matrix pencils and polynomials with Hermitian and related structures (Q2923352)

Given a regular structured matrix polynomial \(P(z)= z^kA_k+\cdots +zA_1+A_0\) with \(A_0, \dots, A_k\in {\mathbb C}^{n\times n}\). The authors answer the following question: If \(\lambda \in {\mathbb C}\), what is the smallest perturbation \((\Delta_0, \dots, \Delta_k)\) from some perturbation set \(S\subseteq ({\mathbb C}^{n\times n})^{k+1}\) such that \(\lambda\) is an eigenvalue of \(P(z)=z^k(A_k-\Delta_k)+\cdots +z(A_1-\Delta_1)+(A_0-\Delta_0)\)? This question is answered for matrix pencils as well as for polynomials which are Hermitian, skew-Hermitian, \(*\)-even and \(*\)-odd. The authors carry out numerical experiments from which they are able to conclude that, in many cases there is a significant difference between the backward errors with respect to perturbations that preserve structure and those with respect to arbitrary perturbations.