Iterative refinement implies numerical stability for Gaussian elimination

Author:
Robert D. Skeel

Journal:
Math. Comp. **35** (1980), 817-832

MSC:
Primary 65F05; Secondary 65F35

DOI:
https://doi.org/10.1090/S0025-5718-1980-0572859-4

MathSciNet review:
572859

Full-text PDF

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.

**[1]**F. L. Bauer,*Optimally scaled matrices*, Numer. Math.**5**(1963), 73–87. MR**0159412**, https://doi.org/10.1007/BF01385880**[2]**F. L. Bauer, J. Stoer, and C. Witzgall,*Absolute and monotonic norms*, Numer. Math.**3**(1961), 257–264. MR**0130104**, https://doi.org/10.1007/BF01386026**[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**, https://doi.org/10.1007/BF01404925**[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**, https://doi.org/10.1007/BF01386090**[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**, https://doi.org/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**

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

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

Additional Information

DOI:
https://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