Iterative refinement implies numerical stability for Gaussian elimination
HTML articles powered by AMS MathViewer
- by Robert D. Skeel PDF
- Math. Comp. 35 (1980), 817-832 Request permission
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
- F. L. Bauer, Optimally scaled matrices, Numer. Math. 5 (1963), 73–87. MR 159412, DOI 10.1007/BF01385880
- F. L. Bauer, J. Stoer, and C. Witzgall, Absolute and monotonic norms, Numer. Math. 3 (1961), 257–264. MR 130104, DOI 10.1007/BF01386026
- George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler, Computer methods for mathematical computations, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1977. MR 0458783
- George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223 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. R. W. HAMMING, Introduction to Applied Numerical Analysis, McGraw-Hill, New York, 1971.
- M. Jankowski and H. Woźniakowski, Iterative refinement implies numerical stability, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), no. 3, 303–311. MR 464560, DOI 10.1007/bf01932150
- Webb Miller, On the stability of finite numerical procedures, Numer. Math. 19 (1972), 425–432. MR 351066, DOI 10.1007/BF01404925 W. MILLER, Private communication, 1977.
- Webb Miller and Celia Wrathall, Software for roundoff analysis of matrix algorithms, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR 595503
- 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 168106, DOI 10.1007/BF01386090 R. D. SKEEL, Gaussian Elimination and Numerical Instability, Report R-77-862, Dept. of Computer Sci., Univ. of Illinois at Urbana-Champaign, April 1977.
- Robert D. Skeel, Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach. 26 (1979), no. 3, 494–526. MR 535268, DOI 10.1145/322139.322148
- G. W. Stewart, Introduction to matrix computations, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR 0458818
- J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
Additional Information
- © Copyright 1980 American Mathematical Society
- 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