Calculation of exact bounds for the solution set of linear interval systems

Publikationstyp
Journal Article
Date Issued
1997-01-15
Sprache
English
Author(s)
Jansson, Christian  
Institut
Zuverlässiges Rechnen E-19  
TORE-URI
http://hdl.handle.net/11420/9378
Journal
Linear algebra and its applications  
Volume
251
Start Page
321
End Page
340
Citation
Linear Algebra and Its Applications 251: 321-340 (1997-01-15)
Publisher DOI
10.1016/S0024-3795(96)00681-7
Scopus ID
2-s2.0-0031541012
Publisher
American Elsevier Publ.
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.
DDC Class
004: Informatik
510: Mathematik