×

Calculation of exact bounds for the solution set of linear interval systems. (English) Zbl 0869.65020

An algorithm for calculating the exact bounds for each component of the solution set of a linear interval system is described. This problem is known to be NP-hard. The proposed algorithm gives an error message if the solution is unbounded. The computations are done in \(p\) calls of a polynomial time algorithm, where \(p\) is the number of orthants intersecting the problem set. It is shown that the NP-hardness of the problem stems form the fact that the solution set may intersect exponentially many orthants.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65G30 Interval and finite arithmetic
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alefeld, G.; Herzberger, J., Introduction to Interval Computations (1983), Academic: Academic New York
[2] Alefeld, G.; Platzöder, L., A quadratically convergent Krawczyk-like algorithm, SIAM, J. Numer. Anal., 20, 1, 210-219 (1983) · Zbl 0505.65012
[3] Barth, W.; Nuding, E., Optimale Lösung von Intervallgleichungssystemen, Computing, 12, 117-125 (1974) · Zbl 0275.65008
[4] Beeck, H., Charakterisierung der Lösungsmenge von Intervallgleichungssystemen, Z. Angew. Math. Mech., 53, T181-T182 (1973) · Zbl 0259.65048
[5] Jansson, C., A Self-validating method for solving linear programming problems, Computing Suppl., 6, 33-46 (1988)
[6] Jansson, C., Some Properties of Linear Interval Systems and Applications, (Technical Report 94.3 (1994), Forschungsschwerpunkt Informations- und Kommunikationstechnik: Forschungsschwerpunkt Informations- und Kommunikationstechnik TU Hamburg-Harburg) · Zbl 0729.65016
[7] Krawczyk, R., Fehlerabschätzung bei linearer Optimierung, Interval Math., 29 (1975) · Zbl 0301.65034
[8] Kulisch, U.; Miranker, W. L., Computer Arithmetic in Theory and Practice (1981), Academic: Academic New York · Zbl 0487.65026
[9] Moore, R. E., Methods and Applications of Interval Analysis (1979), SIAM: SIAM Philadelphia · Zbl 0417.65022
[10] Neumaier, A., Interval Methods for Systems of Equations, (Encyclopedia Math. Appl. (1990), Cambridge U.P) · Zbl 0575.65045
[11] Nickel, K., Die Überschätzung des Wertebereichs einer Funktion in der Intervallrechnung mit Anwendungen auf lineare Gleichungstysteme, Computing, 18, 15-36 (1977) · Zbl 0348.65039
[12] Oettli, W., On the solution set of a linear system with inaccurate coefficients, SIAM J. Numer. Anal., 2, 115-118 (1965) · Zbl 0146.13404
[13] Oettli, W.; Prager, W., Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., 6, 405-409 (1964) · Zbl 0133.08603
[14] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0503.90060
[15] Poljak, S.; Rohn, J., Checking robust nonsingularity is NP-hard, Math. Control Signals Systems, 6, 1-9 (1993) · Zbl 0780.93027
[16] Rohn, J., Solving interval linear systems, Freiburger Intervallberichte, 84, 7, 1-14 (1984)
[17] Rohn, J., Systems of linear interval equations, Linear Algebra Appl., 126, 39-78 (1989) · Zbl 0712.65029
[18] Rohn, J., Checking robust stability of symmetric interval matrices is NP-hard, Comment. Math. Univ. Carol., 35, 795-797 (1994), in · Zbl 0818.65032
[19] Rohn, J., Enclosing solutions of linear interval equations is NP-hard, Computing, 53, 365-368 (1994) · Zbl 0809.65019
[20] J. Rohn, Checking bounds on solutions of linear interval equations is NP-hard, Linear Algebra Appl., to appear.; J. Rohn, Checking bounds on solutions of linear interval equations is NP-hard, Linear Algebra Appl., to appear. · Zbl 0832.65043
[21] Rohn, J., NP-hardness results for linear algebraic problems with interval data, (Herzberger, J., Topics in Validated Computation (1994), North-Holland) · Zbl 0810.65025
[22] Rohn, J.; Kreinovich, V., Computing exact componentwise bounds on solutions of linear systems with interval data is NP-hard, SIAM J. Matrix Anal. Appl., 16, 415-420 (1995) · Zbl 0824.65011
[23] Rump, S. M., Validated solution of large linear systems, (Albrecht, R.; Alefeld, G.; Stetter, H. J., Computing Supplementum 9, Validation Numerics (1993), Springer-Verlag), 191-212 · Zbl 0837.65013
[24] Rump, S. M., Verification methods for dense and sparse systems of equations, (Herzberger, J., Topics in Validated Computations—Studies in Computational Mathematics (1994), Elsevier: Elsevier Amsterdam), 63-136 · Zbl 0813.65072
[25] Schwandt, H., An interval arithmetic approach for the construction of an almost globally convergent method for the solution of the nonlinear Poisson equation on the unit square, SIAM J. Sci. Statist. Comput., 5, 2, 427-452 (1984) · Zbl 0539.65076
[26] Shary, S. P., Optimal solutions of interval linear algebraic systems, Interval Comput., 2, 7-30 (1991) · Zbl 0829.65038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.