Abstract
A new backward error analysis of LU factorization is presented. It allows to obtain a sharper upper bound for the forward error and a new definition of the growth factor that we compare with the well known Wilkinson growth factor for some classes of matrices. Numerical experiments show that the new growth factor is often of order approximately log2 n whereas Wilkinson's growth factor is of order n or \(\sqrt n\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
P. Amodio and F. Mazzia, Backward error analysis of cyclic reduction for the solution of tridiagonal linear systems, Math. Comp., 62 (1994), pp. 601–617.
J. L. Barlow and H. Zha, Growth in Gaussian elimination, orthogonal matrices, and two-norm, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 807–815.
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.
C. W. Cryer, Pivot size in Gaussian elimination, Numer. Math., 12 (1968), pp. 335–345.
J. Day and B. Peterson, Growth in Gaussian elimination, Amer. Math. Monthly, (1988), pp. 489–513.
C. de Boor and A. Pinkus, Backward error analysis for totally positive linear systems, Numer. Math., 27 (1977), pp. 485–490.
J. W. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia, 1997.
G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996.
N. Gould, On growth in Gaussian elimination with complete pivoting, SIAM J. Matrix Anal. Appl., 12 (1991), pp. 354–361.
N. J. Higham and D. J. Higham, Large growth factors in Gaussian elimination with pivoting, SIAM J. Matrix Anal. Appl., 10 (1989), pp. 155–164.
N. J. Higham, The accuracy of solutions to triangular systems, SIAM J. Numer. Anal., 26 (1989), pp. 1252–1265.
N. J. Higham, Bounding the error in Gaussian elimination for tridiagonal systems, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 521–530.
N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996.
V. Lakshmikantham and D. Trigiante, Theory of Difference Equations: Numerical Methods and Applications, Academic Press, New York, 1988.
R. D. Skeel, Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach., 26 (1979), pp. 494–526.
R. D. Skeel, Iterative refinement implies numerical stability for Gaussian elimination, Math. Comp., 35 (1980), pp. 817–832.
L. N. Trefethen and R. S. Schreiber, Average-case stability of Gaussian elimination, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 335–360.
J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, Oxford, 1965.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Amodio, P., Mazzia, F. A New Approach to Backward Error Analysis of Lu Factorization. BIT Numerical Mathematics 39, 385–402 (1999). https://doi.org/10.1023/A:1022358300517
Issue Date:
DOI: https://doi.org/10.1023/A:1022358300517