Fast enclosure for all eigenvalues in generalized eigenvalue problems (Q848556)

The author considers the generalized eigenvalue problem \(Ax=\lambda Bx\), where \(A,B\in{\mathbb C}^{n\times n}\), \(\lambda\in{\mathbb C}\), \(x\in{\mathbb C}^n\), and \(B\) is nonsingular. The proposed method supplies a rigorous error bound \(\epsilon\) such that all eigenvalues are included in the set \(\bigcup_{i=1}^n\{z\in{\mathbb C}; |z-\tilde\lambda_i|\leq\epsilon\}\), where \(\tilde\lambda_i\) denote approximate eigenvalues. It is assumed that, as a result of numerical computation, one has a diagonal matrix \(\tilde D\) and a matrix \(\tilde X\) such that \(A\tilde X\approx B\tilde X\tilde D\). The following theorem is established: Let \(Y\) be an arbitrary \(n\times n\) complex matrix. Let also \(n\times n\) complex matrices \(R_1\) and \(R_2\) be defined as \(R_1:=Y(A\tilde X-B\tilde X\tilde D)\) and \(R_2:=YB\tilde X-1\). If \(\|R_2\|_\infty<1\), then \(B\), \(\tilde X\) and \(Y\) are nonsingular and it follows that \(\min_{1\leq i \leq n}|\lambda-\tilde\lambda_i|\leq\epsilon\), where \(\epsilon:=\|R_1\|_\infty/(1-\|R_2\|_\infty)\). A theorem for accelerating the enclosure is presented. As an application, the author derives an effficient method of enclosing all eigenvalues in polynomial eigenvalue problems (\(\lambda^mA_m+\cdots+\lambda A_1+A_0)x=0\).