To suggest a polynomial complexity method for determining the range of real eigenvalues in the case of the generalized eigenvalue problem when the elements of the matrices involved are independent intervals.
The basic approach is to make use of approximate interval solutions as regards the right and left eigenvectors of the eigenproblem considered, the so‐called outer solutions, in order to determine the range.
First, a new method for computing the outer solutions has been suggested. The main result of the paper, however, is the development of a simple method for determining the range of the real eigenvalues. Unlike the known general‐purpose methods that have exponential complexity, the present range determination method is much simpler as its complexity is only polynomial.
The method is applicable if certain sufficient conditions reported in the paper are satisfied (an incomplete quadratic system is to have a positive solution and the signs of the outer solutions should satisfy a complete or partial invariance).
The method guarantees reliable numerical results when the original eigenproblems contain interval uncertainties as is, strictly speaking, most often the case in practice.
To the best of the author's knowledge, the present paper suggests, for the first time, a simple method of polynomial complexity for solving the problem considered which is inherently a NP‐hard problem (of exponential complexity).
