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

DOI:
https://doi.org/10.1090/S0025-5718-1984-0736451-4

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 *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({\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 *n*th pivot for nearly singular matrices. As an example, we exhibit an *LU*-factorization of the *n* by *n* upper triangular matrix \[ T = \left [ {\begin {array}{*{20}{c}} 1 & { - 1} & {} & { - 1} & {} & \cdot & \cdot & { - 1} \\ {} & 1 & {} & \cdot & {} & {} & {} & \cdot \\ {} & {} & {} & 1 & \cdot & {} & {} & {} \\ {} & {} & {} & {} & \cdot & \cdot & {} & \cdot \\ {} & {} & 0 & {} & {} & \cdot & \cdot & \cdot \\ {} & {} & {} & {} & {} & {} & \cdot & { - 1} \\ {} & {} & {} & {} & {} & {} & {} & 1 \\ \end {array} } \right ]\] that has an nth pivot equal to $2^{-(n-2)}$.

- Tony F. Chan,
*An improved algorithm for computing the singular value decomposition*, ACM Trans. Math. Software**8**(1982), no. 1, 72โ83. MR**661122**, DOI https://doi.org/10.1145/355984.355990 - Tony F. Chan,
*Deflation techniques and block-elimination algorithms for solving bordered singular systems*, SIAM J. Sci. Statist. Comput.**5**(1984), no. 1, 121โ134. MR**731886**, DOI https://doi.org/10.1137/0905009 - Tony F. Chan,
*Deflated decomposition of solutions of nearly singular systems*, SIAM J. Numer. Anal.**21**(1984), no. 4, 738โ754. MR**749368**, DOI https://doi.org/10.1137/0721050 - Tony F. C. Chan and H. B. Keller,
*Arc-length continuation and multigrid techniques for nonlinear elliptic eigenvalue problems*, SIAM J. Sci. Statist. Comput.**3**(1982), no. 2, 173โ194. MR**658631**, DOI https://doi.org/10.1137/0903012 - A. K. Cline,
*An elimination method for the solution of linear least squares problems*, SIAM J. Numer. Anal.**10**(1973), 283โ289. MR**359294**, DOI https://doi.org/10.1137/0710027 - 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), no. 2, 368โ375. MR**526498**, DOI https://doi.org/10.1137/0716029 - R. E. Cline and R. J. Plemmons,
*$l_{2}$-solutions to underdetermined linear systems*, SIAM Rev.**18**(1976), no. 1, 92โ106. MR**396604**, DOI https://doi.org/10.1137/1018004
J. J. Dongarra, J. R. Bunch, C. B. Moler & G. W. Stewart, - G. H. Golub and C. Reinsch,
*Handbook Series Linear Algebra: Singular value decomposition and least squares solutions*, Numer. Math.**14**(1970), no. 5, 403โ420. MR**1553974**, DOI https://doi.org/10.1007/BF02163027 - G. H. Golub and J. H. Wilkinson,
*Ill-conditioned eigensystems and the computation of the Jordan canonical form*, SIAM Rev.**18**(1976), no. 4, 578โ619. MR**413456**, DOI https://doi.org/10.1137/1018113 - Herbert B. Keller,
*Numerical solution of bifurcation and nonlinear eigenvalue problems*, Applications of bifurcation theory (Proc. Advanced Sem., Univ. Wisconsin, Madison, Wis., 1976) Academic Press, New York, 1977, pp. 359โ384. Publ. Math. Res. Center, No. 38. MR**0455353**
H. B. Keller, - Herbert B. Keller,
*The bordering algorithm and path following near singular points of higher nullity*, SIAM J. Sci. Statist. Comput.**4**(1983), no. 4, 573โ582. MR**725653**, DOI https://doi.org/10.1137/0904039 - R. G. Melhem and W. C. Rheinboldt,
*A comparison of methods for determining turning points of nonlinear equations*, Computing**29**(1982), no. 3, 201โ226 (English, with German summary). MR**680470**, DOI https://doi.org/10.1007/BF02241698 - Dianne Prost OโLeary,
*Estimating matrix condition numbers*, SIAM J. Sci. Statist. Comput.**1**(1980), no. 2, 205โ209. MR**594756**, DOI https://doi.org/10.1137/0901014
G. Peters & J. H. Wilkinson, "The least squares problem and pseudo-inverses," - Robert J. Plemmons,
*Linear least squares by elimination and MGS*, J. Assoc. Comput. Mach.**21**(1974), 581โ585. MR**356474**, DOI https://doi.org/10.1145/321850.321855 - Werner C. Rheinboldt,
*Numerical methods for a class of finite dimensional bifurcation problems*, SIAM J. Numer. Anal.**15**(1978), no. 1, 1โ11. MR**494915**, DOI https://doi.org/10.1137/0715001 - G. W. Stewart,
*On the implicit deflation of nearly singular systems of linear equations*, SIAM J. Sci. Statist. Comput.**2**(1981), no. 2, 136โ140. MR**622710**, DOI https://doi.org/10.1137/0902011
R. K. H. Szeto, - J. H. Wilkinson,
*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422**

*LINPACK Userโs Guide*, SIAM, Philadelphia, PA, 1979.

*Singular Systems, Inverse Interation and Least Squares*, unpublished manuscript, Applied Mathematics Department, Caltech, Pasadena, CA, 1978. H. B. Keller,

*Numerical Continuation Methods*, Short Course Lecture Notes, National Bureau of Standards, Center for Applied Mathematics, 1981. H. B. Keller, "Practical procedures in path following near limit points," in

*Computing Methods in Applied Sciences and Engineering*(Glowinski and Lions, eds.), North-Holland, Amsterdam, 1982.

*Comput. J.*, v. 13, 1970, pp. 309-316.

*The Flow Between Rotating Coaxial Disks*, Ph.D. thesis, California Institute of Technology, 1978.

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