Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On the existence and computation of $ LU$-factorizations with small pivots

Author: Tony F. Chan
Journal: Math. Comp. 42 (1984), 535-547
MSC: Primary 65F05; Secondary 15A23
Corrigendum: Math. Comp. 44 (1985), 282.
MathSciNet review: 736451
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let A be an n by n matrix which may be singular with a one-dimensional null space, and consider the LU-factorization of A. When A is exactly singular, we show conditions under which a pivoting strategy will produce a zero nth pivot. When A is not singular, we show conditions under which a pivoting strategy will produce an nth pivot that is $ O({\sigma _n})$ or $ O({\kappa ^{ - 1}}(A))$, where $ {\sigma _n}$ is the smallest singular value of A and $ \kappa (A)$ is the condition number of A. These conditions are expressed in terms of the elements of $ {A^{ - 1}}$ in general but reduce to conditions on the elements of the singular vectors corresponding to $ {\sigma _n}$ when A is nearly or exactly singular. They can be used to build a 2-pass factorization algorithm which is guaranteed to produce a small nth pivot for nearly singular matrices. As an example, we exhibit an LU-factorization of the n by n upper triangular matrix

$\displaystyle T = \left[ {\begin{array}{*{20}{c}} 1 & { - 1} & {} & { - 1} & {}... ...\cdot & { - 1} \\ {} & {} & {} & {} & {} & {} & {} & 1 \\ \end{array} } \right]$

that has an nth pivot equal to $ 2^{-(n-2)}$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F05, 15A23

Retrieve articles in all journals with MSC: 65F05, 15A23

Additional Information

Keywords: LU-factorizations, singular systems
Article copyright: © Copyright 1984 American Mathematical Society