Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Rigorous sensitivity analysis for systems of linear and nonlinear equations

Author: Siegfried M. Rump
Journal: Math. Comp. 54 (1990), 721-736
MSC: Primary 65G10; Secondary 65G05, 65H10
MathSciNet review: 1011445
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Methods are presented for performing a rigorous sensitivity analysis of numerical problems with independent, noncorrelated data for general systems of linear and nonlinear equations. The methods may serve for the following two purposes. First, to bound the dependency of the solution on changes in the input data. In contrast to condition numbers, a componentwise sensitivity analysis of the solution vector is performed. Second, to estimate the true solution set for problems whose input data are subject to tolerances. The methods presented are very effective and have the additional property that, owing to an automatic error control mechanism, every computed result is guaranteed to be correct. Examples are given for linear systems, demonstrating that the computed bounds are in general very sharp. Interesting comparisons to traditional condition numbers are given.

References [Enhancements On Off] (What's this?)

  • [1] ACRITH, High-Accuracy Arithmetic Subroutine Library, Program Description and User's Guide, IBM Publications, Document Number SC 33-6164-3, 1986.
  • [2] G. Alefeld and J. Herzberger, Introduction to interval computations, Academic Press, New York, 1983. MR 733988 (85d:65001)
  • [3] H. Bauch, K.-U. Jahn, D. Oelschlägel, H. Süsse, and V. Wiebigke, Intervallmathematik, Theorie und Anwendungen, Mathematisch-Naturwissenschaftliche Bibliothek, Band 72, Teubner, Leipzig, 1987. MR 927085 (89c:65061)
  • [4] W. Baur and V. Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), 317-330. MR 693063 (84c:68027)
  • [5] IEEE 754 Standard for Floating-Point Arithmetic, 1986.
  • [6] W. Kahan and E. LeBlanc, Anomalies in the IBM ACRITH package, Proc. 7th Sympos. on Computer Arithmetic (Kai Hwang, ed.), Urbana, Illinois, 1985.
  • [7] R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlershranken, Computing 4 (1969), 187-201. MR 0255046 (40:8253)
  • [8] R. Krawczyk and A. Neumaier, Interval slopes for rational functions and associated centered forms, SIAM J. Numer. Anal. 22 (1985), 604-616. MR 787580 (86h:65064)
  • [9] U. Kulisch, Grundlagen des numerischen Rechnens (Reihe Informatik, 19), Bibliographisches Institut, Mannheim, Wien and Zürich, 1976. MR 0426403 (54:14346)
  • [10] U. Kulisch and W. L. Miranker, Computer arithmetic in theory and practice, Academic Press, New York, 1981. MR 606741 (83b:65046)
  • [11] -, (eds.), A new approach to scientific computation, Academic Press, New York, 1981.
  • [12] R. E. Moore, Interval analysis, Prentice-Hall, Englewood Cliffs, N. J., 1966. MR 0231516 (37:7069)
  • [13] -, A test for existence of solutions to nonlinear systems, SIAM J. Numer. Anal. 4 (1977), 611-615. MR 0657002 (58:31801)
  • [14] -, Methods and applications of interval analysis, SIAM, Philadelphia, 1979.
  • [15] A. Neumaier, Overestimation in linear interval equations, SIAM J. Numer. Anal. 24 (1987), 207-214. MR 874746 (88h:65095)
  • [16] -, Rigorous sensitivity analysis for parameter-dependent systems of equations (to appear). MR 1022559 (90k:65121)
  • [17] L. B. Rall, Automatic differentiation: Techniques and applications. Lecture Notes in Computer Science, no. 120, Springer-Verlag, Berlin, Heidelberg, and New York, 1981.
  • [18] S. M. Rump, Solving algebraic problems with high accuracy, in A New Approach to Scientific Computation (U. Kulisch and W. L. Miranker, eds.), Academic Press, New York, 1981, pp. 51-120.
  • [19] -, Solving non-linear systems with least significant bit accuracy, Computing 29 (1982), 183-200. MR 680469 (84d:65037)
  • [20] -, New results on verified inclusions, in Accurate Scientific Computations (W. L. Miranker and R. Toupin, eds.), Lecture Notes in Computer Science, no. 235, Springer-Verlag, 1986, pp. 31-69. MR 868284 (88a:65061)
  • [21] B. Speelpennig, Compiling fast partial derivatives of functions given by algorithms, Ph. D. thesis, University of Illinois, Urbana, Illinois, 1980.
  • [22] P. Wongwises, Experimentelle Untersuchungen zur numerischen Auflösung von linearen Gleichungs-systemen mit Fehlererfassung, Interner Bericht 75/1, Institut für Praktische Mathematik, Universität Karlsruhe, 1975.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65G10, 65G05, 65H10

Retrieve articles in all journals with MSC: 65G10, 65G05, 65H10

Additional Information

Keywords: Sensitivity analysis, linear and nonlinear systems, guaranteed bounds, inner inclusions, condition numbers
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society