On the existence and computation of πΏπ-factorizations with small pivots
Tony Fan-Cheong Chan Β· Mathematics of Computation Β· 1984
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 n th pivot. When A is not singular, we show conditions under which a pivoting strategy will produce an n th pivot that is O ( Ο n ) O({\sigma _n}) or O ( ΞΊ β 1 ( A ) ) O({\kappa ^{ - 1}}(A)) , where Ο n {\sigma _n} is the smallest singular value of A and ΞΊ ( A ) \kappa (A) is the condition number of A . These conditions are expressed in terms of the elements of A β 1 {A^{ - 1}} in general but reduce to conditions on the elements of the singular vectors corresponding to Ο n {\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 n th pivot for nearly singular matrices. As an example, we exhibit an LU -factorization of the n by n upper triangular matrix \[