Abstract :
This paper presents some topological and graph theoretical properties of the solution set of linear algebraic systems with interval coefficients. Based on these properties, we describe a method which, in a finite number of steps, either calculates exact bounds for each component of the solution set, or finds a singular matrix within the interval coefficients. The calculation of exact bounds of the solution set is known to be NP-hard. Our method needs p calls of a polynomial-time algorithm, where p is the number of nonempty intersections of the solution set with the orthants. Frequently, due to physical or economical requirements, many variables do not change the sign. In those cases p is small, and our method works efficiently.
