A Method for Determining the Regularity Radius of Interval Matrices
Lubomir V. Kolev · 2011
Determination of the regularity radius r ∗ of interval matrices is known to be a NP-hard problem. In this paper, a method for determining r ∗ is suggested whose numerical complexity is not a priori exponential. The method is based on an equivalent transformation of the original problem to the problem of determining the real maximum magnitude eigenvalue µ ∗ of an associated interval generalized eigenvalue problem. The latter problem is solved iteratively, using lower bounds |µ | on |µ ∗ | and outer interval or interval hull solutions of corresponding linear interval systems. The method is capable of determining the regularity radius r ∗ if the interval solutions satisfy certain constant sign conditions; otherwise, it provides a tight upper bound r or r ∗. If the sign conditions are met for the interval matrix considered, r ∗ is computed in polynomial time. Numerical examples with interval matrices whose size goes up to n = 500 illustrate the potential of the method suggested.