×

A contribution to the feasibility of the interval Gaussian algorithm. (English) Zbl 1086.65023

The author studies feasibility of the interval Gaussian algorithm for solving interval linear systems \([A]x=[b]\) in the case of generalized diagonally dominant matrices; an interval matrix \([A]\) is called generalized diagonally dominant if it satisfies \(\langle[A]\rangle x\geq 0\) for some \(x>0\), where \(\langle[A]\rangle\) is the comparison matrix. It is proved that for an irreducible generalized diagonally dominant interval matrix, the interval Gaussian algorithm is feasible if and only if the signs of the entries of the midpoint matrix follow certain pattern.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65G30 Interval and finite arithmetic

Software:

INTLAB; PASCAL-XSC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alefeld, G. : On the Convergence of Some Interval-Arithmetic Modifications of Newton’s Method, SIAM J. Numer. Anal. 21 (1984), pp. 363–372. · Zbl 0536.65026 · doi:10.1137/0721027
[2] Alefeld, G.: Über die Durchführbarkeit des Gaußschen Algorithmus bei Gleichungen mil Intervallen als Koeffizienten, Computing Suppl. 1 (1977), pp. 15–19. · Zbl 0361.65017
[3] Alefeld, G. and Herzberger, J.: Einführung in die Intervallrechnung, Reihe Informatik 12, Bibliographisches Institut, Mannheim, 1974. · Zbl 0333.65002
[4] Alefeld, G. and Herzberger, J.: Introduction to Interval Computations, Academic Press, New York, 1983. · Zbl 0552.65041
[5] Alefeld, G. and Mayer, G.: The Gaussian Algorithm for Linear Systems with Interval Data, in: Carlson, D., Johnson, C. R., Lay, D. C., and Porter, A. D. (eds), Linear Algebra Gems: Assets for the Undergraduate Mathematics, The Mathematical Association of America, MAA Notes 59. · Zbl 0796.65032
[6] Barth, W. and Nuding, E: Optimale Lösung von Intervallgleichungssystemen, Computing 12 (1974), pp. 117–125. · Zbl 0275.65008 · doi:10.1007/BF02260368
[7] Berman, A. and Plemmons, R. J.: Nonnegative Matrices in the Mathematical Sciences, Classics in Applied Mathematics 9, SIAM, Philadelphia, 1994. · Zbl 0815.15016
[8] Frommer, A: A Feasibility Result for Interval Gaussian Elimination Relying on Graph Structure, in: Alefeld, G., Rohn, J., Rump, S., and Yamamoto, T. (eds), Symbolic Algebraic Methods and Verification Methods, SpringerMathematics, Springer, Wien, 2001, pp. 79–86. · Zbl 0963.00018
[9] Frommer, A. and Mayer, G.: A New Criterion to Guarantee the Feasibility of the Interval Gaussian Algorithm, SIAM J. Matrix Anal. Appl. 14 (1993), pp. 408–419. · Zbl 0777.65012 · doi:10.1137/0614029
[10] Frommer, A. and Mayer, G.: Linear Systems with {\(\Omega\)}-Diagonally Dominant Matrices and Related Ones, Linear Algebra Appl. 186 (1993), pp. 165–181. · Zbl 0774.65013 · doi:10.1016/0024-3795(93)90289-Z
[11] Garloff, J.: Block Methods for the Solution of Linear Interval Equations, SIAM J. Matrix Anal. Appl. 11 (1990), pp. 89–106. · Zbl 0712.65016 · doi:10.1137/0611006
[12] Hansen, E. R.: Gaussian Elimination in Interval Systems, preprint, 1997.
[13] Hansen, E. R.: The Hull of Preconditioned Interval Linear Equations, Reliable Computing 6 (2) (2000), pp. 95–103. · Zbl 0961.65038
[14] Hansen, E. R. and Smith, R.: Interval Arithmetic in Matrix Computations, Part II, SIAM J. Numer. Anal. 4 (1967), pp. 1–9. · Zbl 0209.46601 · doi:10.1137/0704001
[15] Hebgen, M.: Eine scaling-invariante Pivotsuche für Intervallmatrizen, Computing 12 (1974), pp. 99–106. · Zbl 0275.65007 · doi:10.1007/BF02260366
[16] Klatte, R., Kulisch, U., Neaga, M., Ratz, D., and Ullrich, C.: PASCAL-XSC, Sprachbeschreibung mil Beispielen, Springer, Berlin, 1991.
[17] Mayer, G.: Old and New Aspects of the Interval Gaussian Algorithm, in: Kaucher, E., Markov, S. M., and Mayer, G. (eds), Computer Arithmetic, Scientific Computation and Mathematical Modelling, IMACS Annals on Computing and Applied Mathematics 12, Baltzer, Basel, 1991, pp. 329–349.
[18] Mayer, G. and Pieper, L.: A Necessary and Sufficient Criterion to Guarantee the Feasibility of the Interval Gaussian Algorithm for a Class of Matrices, Appl. Math. 38 (1993), pp. 205–220. · Zbl 0782.65044
[19] Mayer, G. and Rohn, J.: On the Applicability of the Interval Gaussian Algorithm, Reliable Computing 4 (3) (1998), pp. 205–222. · Zbl 0933.65027
[20] Mayer, J.: An Approach to Overcome Division by Zero in the Interval Gaussian Algorithm, Reliable Computing 8 (3) (2002), pp. 229–237. · Zbl 1002.65032 · doi:10.1023/A:1015565313636
[21] Moore, R. E.: Interval Analysis, Prentice Hall, Englewood Cliffs, 1966. · Zbl 0176.13301
[22] Moré, J. J.: Nonlinear Generalizations of Matrix Diagonal Dominance with Applications to Gauss-Seidel Iterations, SIAM J. Numer. Anal. 9 (1972), pp. 357–378. · Zbl 0243.65023 · doi:10.1137/0709035
[23] Neumaier, A.: Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, 1990. · Zbl 0715.65030
[24] Neumaier, A.: New Techniques for the Analysis of Linear Interval Equations, Linear Algebra Appl. 58 (1984), pp. 273–325. · Zbl 0558.65019 · doi:10.1016/0024-3795(84)90217-9
[25] Nickel, K.: Interval-Analysis, in: Jacobs, D. A. H. (ed.), The State of the Art in Numerical Analysis, Academic Press, London, 1977, pp. 193–225.
[26] Ortega, J. M.: Numerical Analysis, A Second Course, SIAM, Philadelphia, 1990.
[27] Reichmann, K.: Abbruch beim Intervall-Gauss-Algorithmus, Computing 22 (1979), pp. 355–361. · Zbl 0409.65019 · doi:10.1007/BF02265315
[28] Reichmann, K.: Ein hinreichendes Kriterium für die Durchführbarkeit des Intervall-Gauß-Algorithmus bei Intervall-Hessenberg-Matrizen ohne Pivotsuche, Z. Angew. Math. Mech. 59 (1979), pp. 373–379. · Zbl 0415.65028 · doi:10.1002/zamm.19790590806
[29] Rohn, J.: On Overestimations Produced by the Interval Gaussian Algorithm, Reliable Computing 3 (4) (1997), pp. 363–368. · Zbl 0887.65033 · doi:10.1023/A:1009993319560
[30] Rump, S. M.: INTLAB–INTerval LABoratory, in: Csendes, T. (ed.), Developements in Reliable Computing, Kluwer Academic Publishers, Dordrecht, 1999, pp. 77–104.
[31] Schäfer, U.: The Feasibility of the Interval Gaussian Algorithm for Arrowhead Matrices, Reliable Computing 7 (1) (2001), pp. 59–62. · Zbl 0979.65022 · doi:10.1023/A:1011439403749
[32] Schätzle, F.: Überschätzung beim Gauss-Algorithmus für lineare Intervallgleichungssysteme, Diplomarbeit, Freiburger Intervall-Berichte 84/3 (1984), pp. 1–122.
[33] Schwandt, H.: An Interval Arithmetic Approach for the Construction of an Almost Globally Convergent Method for the Solution of Nonlinear Poisson Equation on the Unit Square, SIAM J. Set. Statist. Comput. 5 (1984), pp. 427–452. · Zbl 0539.65076 · doi:10.1137/0905032
[34] Varga, R. S.: Matrix Iterative Analysis, 2nd ed., Springer, Berlin, 2000. · Zbl 0998.65505
[35] Wongwises, P.: Experimentelle Untersuchungen zur numerischen Auflösung von linearen Gle-ichungssystemen mil Fehlererfassung, in: Goos, G. and Hartmanis, J. (eds), Interval Mathematics, Lecture Notes in Computer Science 29, Springer, Berlin, 1975, pp. 316–325.
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.