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 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.

**[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)**

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