Iterative refinement implies numerical stability for Gaussian elimination
Author:
Robert D. Skeel
Journal:
Math. Comp. 35 (1980), 817832
MSC:
Primary 65F05; Secondary 65F35
MathSciNet review:
572859
Fulltext 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.
5 (1963), 73–87. MR 0159412
(28 #2629)
 [2]
F.
L. Bauer, J.
Stoer, and C.
Witzgall, Absolute and monotonic norms, Numer. Math.
3 (1961), 257–264. MR 0130104
(23 #B3136)
 [3]
George
E. Forsythe, Michael
A. Malcolm, and Cleve
B. Moler, Computer methods for mathematical computations,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1977. PrenticeHall Series in
Automatic Computation. MR 0458783
(56 #16983)
 [4]
George
E. Forsythe and Cleve
B. Moler, Computer solution of linear algebraic systems,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
(36 #2306)
 [5]
C. W. GEAR, Numerical Errors in Sparse Linear Equations, File F75885, Dept. of Computer Sci., Univ. of Illinois at UrbanaChampaign, May 1975.
 [6]
R. W. HAMMING, Introduction to Applied Numerical Analysis, McGrawHill, 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
(57 #4490)
 [8]
Webb
Miller, On the stability of finite numerical procedures,
Numer. Math. 19 (1972), 425–432. MR 0351066
(50 #3557)
 [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
YorkLondon, 1980. Computer Science and Applied Mathematics. MR 595503
(82e:65047)
 [11]
W.
Oettli and W.
Prager, Compatibility of approximate solution of linear equations
with given error bounds for coefficients and righthand sides, Numer.
Math. 6 (1964), 405–409. MR 0168106
(29 #5371)
 [12]
R. D. SKEEL, Gaussian Elimination and Numerical Instability, Report R77862, Dept. of Computer Sci., Univ. of Illinois at UrbanaChampaign, 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
(80e:65051), http://dx.doi.org/10.1145/322139.322148
 [14]
G.
W. Stewart, Introduction to matrix computations, Academic
Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New
YorkLondon, 1973. Computer Science and Applied Mathematics. MR 0458818
(56 #17018)
 [15]
J.
H. Wilkinson, Rounding errors in algebraic processes,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
(28 #4661)
 [1]
 F. L. BAUER, "Optimally scaled matrices," Numer. Math., v. 5, 1963, pp. 7887. MR 0159412 (28:2629)
 [2]
 F. L. BAUER, J. STOER & C. WITZGALL, "Absolute and monotonie norms," Numer. Math., v. 3, 1961, pp. 257264. MR 0130104 (23:B3136)
 [3]
 G. E. FORSYTHE, M. A. MALCOLM & C. B. MOLER, Computer Methods for Mathematical Computations, PrenticeHall, Englewood Cliffs, N. J., 1977. MR 0458783 (56:16983)
 [4]
 G. E. FORSYTHE & C. B. MOLER, Computer Solution of Linear Algebraic Systems, PrenticeHall, Englewood Cliffs, N. J., 1967. MR 0219223 (36:2306)
 [5]
 C. W. GEAR, Numerical Errors in Sparse Linear Equations, File F75885, Dept. of Computer Sci., Univ. of Illinois at UrbanaChampaign, May 1975.
 [6]
 R. W. HAMMING, Introduction to Applied Numerical Analysis, McGrawHill, New York, 1971.
 [7]
 M. JANKOWSKI &. M. WOŹNIAKOWSKI, "Iterative refinement implies numerical stability," BIT, v. 17, 1977, pp. 303311. MR 0464560 (57:4490)
 [8]
 W. MILLER, "On the stability of finite numerical procedures," Numer. Math., v. 19, 1972, pp. 425432. 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 righthand sides," Numer. Math., v. 6, 1964, pp. 405409. MR 0168106 (29:5371)
 [12]
 R. D. SKEEL, Gaussian Elimination and Numerical Instability, Report R77862, Dept. of Computer Sci., Univ. of Illinois at UrbanaChampaign, April 1977.
 [13]
 R. D. SKEEL, "Scaling for numerical stability in Gaussian elimination," J. Assoc. Comput. Mach., v. 26, 1979, pp. 494526. 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, PrenticeHall, 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
DOI:
http://dx.doi.org/10.1090/S00255718198005728594
PII:
S 00255718(1980)05728594
Keywords:
Iterative refinement,
iterative improvement,
numerical stability,
Gaussian elimination,
pivoting,
backward error analysis,
roundoff analysis
Article copyright:
© Copyright 1980
American Mathematical Society
