## Systems of linear interval equations.(English)Zbl 0712.65029

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.
Reviewer: A.Neumaier

### MSC:

 65F30 Other matrix algorithms (MSC2010) 65G30 Interval and finite arithmetic 65F05 Direct numerical methods for linear systems and matrix inversion 65F10 Iterative numerical methods for linear systems
Full Text:

### References:

 [1] Albrecht, J., Monotone Iterationsfolgen und ihre Verwendung zur Lösung linearer Gleichungssysteme, Numer. Math., 3, 345-358 (1961) · Zbl 0101.33804 [2] Alefeld, G.; Herzberger, J., Über die Verbesserung von Schranken für die Lösung bei linearen Gleichungssystemen, Angew. Informatik, 3, 107-112 (1971) · Zbl 0213.16304 [3] Alefeld, G.; Herzberger, J., Introduction to Interval Computations (1983), Academic: Academic New York · Zbl 0552.65041 [4] Barth, W.; Nuding, E., Optimale Lösung von Intervallgleichungssystemen, Computing, 12, 117-125 (1974) · Zbl 0275.65008 [5] Baumann, M., A regularity criterion for interval matrices, (Garloff, J.; etal., Collection of Scientific Papers Honouring Prof. Dr. K. Nickel on Occasion of his 60th Birthday (1984), Univ. Freiburg i. Br), Part I [6] Beeck, H., Charakterisierung der Lösungsmenge von Intervallgleichungssystemen, Z. Angew. Math. Mech., 53, T181-T182 (1973) · Zbl 0259.65048 [7] Beeck, H., Zur scharfen Aussenabschätzung der Lösungsmenge bei linearen Intervallgleichungssystemen, Z. Angew. Math. Mech., 54, T208-T209 (1974) · Zbl 0311.65026 [8] Beeck, H., Zur Problematik der Hüllenbestimmung von Intervallgleichungssystemen, (Nickel, K., Lecture Notes in Comput. Sci.. Lecture Notes in Comput. Sci., Interval Mathematics, 29 (1975), Springer-Verlag) · Zbl 0303.65025 [9] Cope, J.; Rust, B., Bounds on solutions of linear systems with inaccurate data, SIAM J. Numer. Anal., 16, 950-963 (1979) · Zbl 0437.65035 [10] Cottle, R.; Dantzig, G., Complementary pivot theory of mathematical programming, Linear Algebra Appl., 1, 103-125 (1968) · Zbl 0155.28403 [11] Deif, A., Sensitivity Analysis in Linear Systems (1986), Springer-Verlag: Springer-Verlag New York · Zbl 0624.65019 [12] Fiedler, M.; Pták, V., On matrices with non-positive off-diagonal elements and positive principal minors, Czechoslovak Math. J., 12, 382-400 (1962) · Zbl 0131.24806 [13] Gale, D.; Nikaido, H., The jacobian matrix and global univalence of mappings, Math. Ann., 159, 81-93 (1965) · Zbl 0158.04903 [14] Garloff, J., Totally nonnegative interval matrices, (Nickel, K., Interval Mathematics 1980 (1980), Academic: Academic New York) · Zbl 0537.15012 [15] Hansen, E., On the solution of linear algebraic equations with interval coefficients, Linear Algebra Appl., 2, 153-165 (1969) · Zbl 0185.40201 [16] Hansen, E., On linear algebraic equations with interval coefficients, (Hansen, E., Topics in Interval Analysis (1969), Oxford U.P: Oxford U.P Oxford) · Zbl 0185.40002 [17] Hudak, D., Ein Eigenwertproblem für Intervall-Matrizen, Z. Angew. Math. Mech., 64, 503-505 (1984) · Zbl 0561.65023 [18] Ingleton, A., A problem in linear inequalities, Proc. London Math. Soc., 16, 519-536 (1966) · Zbl 0166.03005 [19] Jahn, 0K.-U., Eine Theorie der Gleichungssysteme mit Intervallkoeffizienten, Z. Angew. Math. Mech., 54, 405-412 (1974) · Zbl 0284.65022 [20] Kuttler, J., A fourth-order finite-difference approximation for the fixed membrane eigenproblem, Math. Comp., 25, 237-256 (1971) · Zbl 0243.65065 [21] Lemke, C., Bimatrix equilibrium points and mathematical programming, Management Sci., 11, 681-689 (1965) · Zbl 0139.13103 [22] Murty, K., On the number of solutions to the complementarity problem and spanning properties of complementary cones, Linear Algebra Appl., 5, 65-108 (1972) · Zbl 0241.90046 [23] Murty, K., Note on a Bard-type scheme for solving the complementarity problem, Opsearch, 11, 123-130 (1974) [24] Murty, K., Computational complexity of complementary pivot methods, Math. Programming Stud., 7, 61-73 (1978) · Zbl 0381.90108 [25] Neumaier, A., New techniques for the analysis of linear interval equations, Linear Algebra Appl., 58, 273-325 (1984) · Zbl 0558.65019 [26] Neumaier, A., Linear interval equations, (Nickel, K., Interval Mathematics 1985 (1985), Springer-Verlag), Lecture Notes in Comput. Sci. · Zbl 0588.65023 [27] Nickel, K., Die Überschätzung des Wertebereichs einer Funktion in der Intervallrechnung mit Anwendungen auf lineare Gleichungssysteme, Computing, 18, 15-36 (1977) · Zbl 0348.65039 [28] Oettli, W., On the solution set of a linear system with inaccurate coefficients, SIAM J. Numer. Anal., 2, 115-118 (1965) · Zbl 0146.13404 [29] 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 (1064) · Zbl 0133.08603 [30] Samelson, H.; Thrall, R.; Wesler, O., A partition theorem for euclidean $$n$$-space, Proc. Amer. Math. Soc., 9, 805-807 (1958) · Zbl 0117.37901 [31] Rohn, J., On the interval hull of the solution set of an interval linear system, Freiburger Intervall-Ber., 81, 5, 47-57 (1981) · Zbl 0452.65013 [32] Rohn, J., An algorithm for solving interval linear systems and inverting interval matrices, Freiburger Intervall-Ber., 82, 5, 23-36 (1982) · Zbl 0496.65015 [33] Rohn, J., Solving interval linear systems, Freiburger Intervall-Ber., 84, 7, 1-14 (1984) [34] Rohn, J., Proofs to “Solving interval linear systems,”, Freiburger Intervall-Ber., 84, 7, 17-30 (1984) [35] Rohn, J., Interval linear systems, Freiburger Intervall-Ber., 84, 7, 33-58 (1984) [36] Rohn, J., Some results on interval linear systems, Freiburger Intervall-Ber., 85, 4, 93-116 (1985) [37] Rohn, J., Miscellaneous results on linear interval systems, Freiburger Intervall-Ber., 85, 9, 29-43 (1985) [38] Rohn, J., A note on solving equations of type $$A^Ix^{I$$ [39] Rohn, J., Testing regularity of interval matrices, Freiburger Intervall-Ber., 86, 4, 33-37 (1986) [40] Rohn, J., A note on the sign-accord algorithm, Freiburger Intervall-Ber., 86, 4, 39-43 (1986) [41] Rohn, J., Inverse-positive interval matrices, Z. Angew. Math. Mech., 67, T492-T493 (1987) · Zbl 0628.65027 [42] Varga, R., Matrix Iterative Analysis (1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0133.08602
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.