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 Free Access

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ötz Alefeld and Jürgen Herzberger, Introduction to interval computations, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1983. Translated from the German by Jon Rokne. MR 733988
  • [3] H. Bauch, K.-U. Jahn, D. Oelschlägel, H. Süsse, and V. Wiebigke, Intervallmathematik, Mathematisch-Naturwissenschaftliche Bibliothek [Mathematical-Scientific Library], vol. 72, BSB B. G. Teubner Verlagsgesellschaft, Leipzig, 1987 (German). Theorie und Anwendungen. [Theory and applications]. MR 927085
  • [4] Walter Baur and Volker Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), no. 3, 317–330. MR 693063, 10.1016/0304-3975(83)90110-X
  • [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 Fehlerschranken., Computing (Arch. Elektron. Rechnen) 4 (1969), 187–201 (German, with English summary). MR 0255046
  • [8] R. Krawczyk and A. Neumaier, Interval slopes for rational functions and associated centered forms, SIAM J. Numer. Anal. 22 (1985), no. 3, 604–616. MR 787580, 10.1137/0722037
  • [9] Ulrich Kulisch, Grundlagen des numerischen Rechnens, Bibliographisches Institut, Mannheim-Vienna-Zurich, 1976 (German). Mathematische Begründung der Rechnerarithmetik; Reihe Informatik, Band 19. MR 0426403
  • [10] Ulrich W. Kulisch and Willard L. Miranker, Computer arithmetic in theory and practice, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1981. Computer Science and Applied Mathematics. MR 606741
  • [11] -, (eds.), A new approach to scientific computation, Academic Press, New York, 1981.
  • [12] Ramon E. Moore, Interval analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966. MR 0231516
  • [13] R. E. Moore, A test for existence of solutions to nonlinear systems, SIAM J. Numer. Anal. 14 (1977), no. 4, 611–615. MR 0657002
  • [14] -, Methods and applications of interval analysis, SIAM, Philadelphia, 1979.
  • [15] A. Neumaier, Overestimation in linear interval equations, SIAM J. Numer. Anal. 24 (1987), no. 1, 207–214. MR 874746, 10.1137/0724017
  • [16] Arnold Neumaier, Rigorous sensitivity analysis for parameter-dependent systems of equations, J. Math. Anal. Appl. 144 (1989), no. 1, 16–25 (English, with German summary). MR 1022559, 10.1016/0022-247X(89)90357-0
  • [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] S. M. Rump, Solving nonlinear systems with least significant bit accuracy, Computing 29 (1982), no. 3, 183–200 (English, with German summary). MR 680469, 10.1007/BF02241697
  • [20] Siegfried M. Rump, New results on verified inclusions, Accurate scientific computations (Bad Neuenahr, 1985) Lecture Notes in Comput. Sci., vol. 235, Springer, Berlin, 1986, pp. 31–69. MR 868284, 10.1007/3-540-16798-6_4
  • [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