Systems of linear interval equations (Q749156)

This highly interesting paper contains an extensive discussion of the problem of finding the interval hull of the solution set of linear interval equations, i.e. the narrowest interval vector containing the set of all solutions of \(Ax=b\) where the coefficients of A and b range over prescribed intervals. Various necessary and sufficient conditions are given for the nonsingularity of all admissible A, and computational procedures for finding the hull are given. For intervals with sufficiently small radii, this can be done in \(O(n^ 4)\), and in important special cases even in \(O(n^ 3)\), operations; in the general case, an exponential amount of work may be required. A thorough analysis implies finite termination of the algorithm employed, by using results on linear complementarity problems. A wealth of related problems is discussed, too.