Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

Iterative refinement implies numerical stability for Gaussian elimination


Author: Robert D. Skeel
Journal: Math. Comp. 35 (1980), 817-832
MSC: Primary 65F05; Secondary 65F35
MathSciNet review: 572859
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Because of scaling problems, Gaussian elimination with pivoting is not always as accurate as one might reasonably expect. It is shown that even a single iteration of iterative refinement in single precision is enough to make Gaussian elimination stable in a very strong sense. Also, it is shown that without iterative refinement row pivoting is inferior to column pivoting in situations where the norm of the residual is important.


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

  • [1] F. L. Bauer, Optimally scaled matrices, Numer. Math. 5 (1963), 73–87. MR 0159412
  • [2] F. L. Bauer, J. Stoer, and C. Witzgall, Absolute and monotonic norms, Numer. Math. 3 (1961), 257–264. MR 0130104
  • [3] George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler, Computer methods for mathematical computations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1977. Prentice-Hall Series in Automatic Computation. MR 0458783
  • [4] George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
  • [5] C. W. GEAR, Numerical Errors in Sparse Linear Equations, File F-75-885, Dept. of Computer Sci., Univ. of Illinois at Urbana-Champaign, May 1975.
  • [6] R. W. HAMMING, Introduction to Applied Numerical Analysis, McGraw-Hill, New York, 1971.
  • [7] M. Jankowski and H. Woźniakowski, Iterative refinement implies numerical stability, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), no. 3, 303–311. MR 0464560
  • [8] Webb Miller, On the stability of finite numerical procedures, Numer. Math. 19 (1972), 425–432. MR 0351066
  • [9] W. MILLER, Private communication, 1977.
  • [10] Webb Miller and Celia Wrathall, Software for roundoff analysis of matrix algorithms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Computer Science and Applied Mathematics. MR 595503
  • [11] W. Oettli and W. Prager, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math. 6 (1964), 405–409. MR 0168106
  • [12] R. D. SKEEL, Gaussian Elimination and Numerical Instability, Report R-77-862, Dept. of Computer Sci., Univ. of Illinois at Urbana-Champaign, April 1977.
  • [13] Robert D. Skeel, Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach. 26 (1979), no. 3, 494–526. MR 535268, 10.1145/322139.322148
  • [14] G. W. Stewart, Introduction to matrix computations, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Computer Science and Applied Mathematics. MR 0458818
  • [15] J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F05, 65F35

Retrieve articles in all journals with MSC: 65F05, 65F35


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1980-0572859-4
Keywords: Iterative refinement, iterative improvement, numerical stability, Gaussian elimination, pivoting, backward error analysis, roundoff analysis
Article copyright: © Copyright 1980 American Mathematical Society