Abstract
In the literature efficient algorithms have been described for calculating guaranteed inclusions for the solution of a number of standard numerical problems [3,4,8,11,12,13]. The inclusions are given by means of a set containing the solution. In [12,13] this set is calculated using an affine iteration which is stopped when a nonempty and compact set is mapped into itself. For exactly given input data (point data) it has been shown that this iteration stops if and only if the iteration matrix is convergent (cf. [13]).
In this paper we give a necessary and sufficient stopping criterion for the above mentioned iteration for interval input data and interval operations. Stopping is equivalent to the fact that the algorithm presented in [12] for solving interval linear systems computes an inclusion of the solution. An algorithm given by Neumaier is discussed and an algorithm is proposed combining the advantages of our algorithm and a modification of Neumaier's. The combined algorithm yields tight bounds for input intervals of small and large diameter.
Using a paper by Jansson [6,7] we give a quite different geometrical interpretation of inclusion methods. It can be shown that our inclusion methods are optimal in a specified geometrical sense. For another class of sets, for standard simplices, we give some interesting examples.
Zusammenfassung
In der Literatur werden eine Reihe effizienter Algorithmen beschrieben zur Berechnung garantierter Einschließungen der Lösung numerischer Standardprobleme [3,4,8,11,12,13]. Die Einschließungen werden in Form von Mengen gegeben. In [12, 13] wird diese Menge mit Hilfe einer affinen Transformation berechnet, die stoppt, wenn eine nichtleere kompakte Menge in sich selbst abgebildet wird. Für Punkteingabedaten wurde gezeigt, daß diese Iteration genau dann stoppt, wenn die Iterationsmatrix konvergent ist [13].
In der vorliegenden Arbeit werden notwendige und hinreichende Stop-Bedingungen angegeben für Intervalleingabedaten und Intervalloperationen im reellen und im komplexen. Stoppen heißt hierbei, daß der Algorithmus aus [12] für Intervallgleichungssysteme eine Einschließung liefert. Ein Algorithmus von Neumaier wird diskutiert, und es wird ein Hybrid-Algorithmus vorgeschlagen, der die Vorteile Neumaiers und unseres Algorithmus kombiniert.
Unter Benutzung einer Arbeit von Jansson [6, 7] wird eine interessante geometrische Interpretation von Einschließungsalgorithmen gegeben. Es wird gezeigt, daß die Einschließungsalgorithmen in bestimmtem Sinne optimal sind. für eine andere Klasse von Mengen, für Standardsimplexe, geben wir einige interessante Beispiele.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
ACRITH High-Accuracy Arithmetic Subroutine Library: General Information Manual, IBM Publications, GC33-6163 (1985).
Alefeld, G., Herzberger, J.: Introduction to interval computations. New York: Academic Press 1983.
Hansen, E.: Interval arithmetic in matrix computations, Part I. SIAM J. Numer. Anal.2, 308–320 (1965).
Hansen, E.: Interval arithmetic in matrix computations, Part II. SIAM J. Numer. Anal.4, 1–9 (1967).
IEEE 754 Standard for Floating-Point Arithmetic (1986).
Jansson, C.: A geometric approach for computing a posteriori error bounds for the solution of a linear system. Computing47, 1–9 (1991).
Jansson, C.: Guaranteed error bounds for the solution of linear systems, Contributions to Computer Arithmetic and Self-Validating Numerical Methods (C. Ullrich editor), J. C. Baltzer AG, Scientific Publishing Co. IMACS, S. 103–110 (1990).
Krawczyk, R.: Newton-Algorithmen zur Besimmung von Nullstellen mit Fehlerschranken. Computing4, 187–220 (1969).
Kulisch, U., Miranker, W. L.: Computer arithmetic in theory and practice. New York: Academic Press 1981.
Moore, R. E.: Interval analysis. Englewood Cliffs, New Jersey: Prentice Hall 1966.
Neumaier, A.: Interval methods for systems of equations. Cambridge University Press (1990).
Rump, S. M.: Kleine Fehlerschranken bei Matrixproblemen, Dissertation Universität Karlsruhe (1980).
Rump, S. M.: New results on verified inclusions, in: Miranker, W. L., R. Toupin (eds.): Accurate scientific computations. Springer Lecture Notes in Computer Science235, 31–69 (1986).
Siemens AG: Arithmos (BS2000). Benutzerhandbuch, (1986).
Varga, R. S.: Matrix iterative analysis. Englewood Cliffs, New Jersey: Prentice Hall 1962.
Rump, S. M.: Rigorous sensitivity analysis for systems of systems of linear and nonlinear equations. MATH. of Comp.54, (190) 721–736 (1990).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rump, S.M. On the solution of interval linear systems. Computing 47, 337–353 (1992). https://doi.org/10.1007/BF02320201
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02320201