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., v. 5, 1963, pp. 78-87. MR 0159412 (28:2629)
  • [2] F. L. BAUER, J. STOER & C. WITZGALL, "Absolute and monotonie norms," Numer. Math., v. 3, 1961, pp. 257-264. MR 0130104 (23:B3136)
  • [3] G. E. FORSYTHE, M. A. MALCOLM & C. B. MOLER, Computer Methods for Mathematical Computations, Prentice-Hall, Englewood Cliffs, N. J., 1977. MR 0458783 (56:16983)
  • [4] G. E. FORSYTHE & C. B. MOLER, Computer Solution of Linear Algebraic Systems, Prentice-Hall, Englewood Cliffs, N. J., 1967. MR 0219223 (36:2306)
  • [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 &. M. WOŹNIAKOWSKI, "Iterative refinement implies numerical stability," BIT, v. 17, 1977, pp. 303-311. MR 0464560 (57:4490)
  • [8] W. MILLER, "On the stability of finite numerical procedures," Numer. Math., v. 19, 1972, pp. 425-432. MR 0351066 (50:3557)
  • [9] W. MILLER, Private communication, 1977.
  • [10] W. MILLER & C. WRATHALL, Software for Roundoff Analysis of Matrix Algorithms, Academic Press, New York. (To appear.) MR 595503 (82e:65047)
  • [11] W. OETTLI & W. PRAGER, "Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides," Numer. Math., v. 6, 1964, pp. 405-409. MR 0168106 (29:5371)
  • [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] R. D. SKEEL, "Scaling for numerical stability in Gaussian elimination," J. Assoc. Comput. Mach., v. 26, 1979, pp. 494-526. MR 535268 (80e:65051)
  • [14] G. W. STEWART, Introduction to Matrix Computations, Academic Press, New York, 1973. MR 0458818 (56:17018)
  • [15] J. H. WILKINSON, Rounding Errors in Algebraic Processes, Prentice-Hall, Englewood Cliffs, N. J., 1963. MR 0161456 (28:4661)

Similar Articles

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

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

Additional Information

Keywords: Iterative refinement, iterative improvement, numerical stability, Gaussian elimination, pivoting, backward error analysis, roundoff analysis
Article copyright: © Copyright 1980 American Mathematical Society

American Mathematical Society