A note on estimating the error in Gaussian elimination without pivoting

ABSTRACT

This article deals with the problem of estimating the error in the computed solution to a system of equations when that solution is obtained by using Gaussian elimination without pivoting. The corresponding problem, where either partial or complete pivoting is used, has received considerable attention, and efficient and reliable methods have been developed. However, in the context of solving large sparse systems, it is often very attractive to apply Gaussian elimination without pivoting, even though it cannot be guaranteed a-priori that the computation is numerically stable. When this is done, it is important to be able to determine when serious numerical errors have occurred, and to be able to estimate the error in the computed solution. In this paper a method for achieving this goal is described. Results of a large number of numerical experiments suggest that the method is both inexpensive and reliable.

REFERENCES

• 1: Bruce A. Chartres , James C. Geuder, Computable Error Bounds for Direct Solution of Linear Equations, Journal of the ACM (JACM), v.14 n.1, p.63-71, Jan. 1967 [doi>10.1145/321371.321376]
• 2: E. C. H. Chu, J. A. George, J. W. H. Liu, and E. G. Y. Ng, "User's guide for SPARSPAK-A: Waterloo sparse linear equations package", Research Report CS-84-36 (1984).
• 3: A. K. Cline, A. R. Conn, and C. F. van Loan, "Generalizing the LINPACK Condition Estimator", in Lecture Notes in Mathematics,, Springer-Verlag (1982), pp. 73--83.
• 4: A. K. Cline, C. B. Moler, G. W. Stewart, and J. H. Wilkinson, "An estimate for the condition number of a matrix", SIAM J. Numer. Anal., 16 (1979), pp. 368--375.
• 5: A. K. Cline and R. K. Rew, "A Set of Counter-Examples to Three Condition Number Estimators", SIAM J. Sci. Stat. Comput., 4 (1983), pp. 602--611.
• 6: J. J. Dongarra, C. B. Moler, J. R. Bunch, and G. W. Stewart, LINPACK users' guide, SIAM, Philadelphia (1980).
• 7: A. M. Erisman and J. K. Reid, "Monitoring the Stability of the Triangular Factorization of a Sparse Matrix", Numer. Math., 22 (1974), pp. 183--186.
• 8: G. E. Forsythe and C. B. Moler, Computer solution of linear algebraic systems, Prentice-Hall Inc., Englewood Cliffs, N.J. (1967).
• 9: R. G. Grimes and J. G. Lewis, "Condition number estimation for sparse matrices", SIAM J. Sci. Stat. Comput., 2 (1981), pp. 384--388.
• 10: D. Heller, "More Counterexamples to the LINPACK Condition Estimator", Manuscript, Department of Computer Science, The Pennsylvania State University (1981).
• 11: D. P. O'Leary, "Estimating Matrix Condition Numbers", SIAM J. Sci. Stat. Comput., 1 (1980), pp. 205--209.