Determining the range of real eigenvalues for the interval generalized eigenvalue problem

Abstract

Purpose

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.

Design/methodology/approach

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.

Findings

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.

Research limitations/implications

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).

Practical implications

The method guarantees reliable numerical results when the original eigenproblems contain interval uncertainties as is, strictly speaking, most often the case in practice.

Originality/value

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).

Citation

Kolev, L. (2008), "Determining the range of real eigenvalues for the interval generalized eigenvalue problem", COMPEL - The international journal for computation and mathematics in electrical and electronic engineering, Vol. 27 No. 6, pp. 1463-1480. https://doi.org/10.1108/03321640810905909