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

HTML articles powered by AMS MathViewer

- by Tony F. Chan PDF
- Math. Comp.
**42**(1984), 535-547 Request permission

## 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)}$.

## References

- 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 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 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 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 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 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 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 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 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 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) Publ. Math. Res. Center, No. 38, Academic Press, New York, 1977, pp. 359–384. 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 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 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 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 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 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 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.

## Additional Information

- © Copyright 1984 American Mathematical Society
- Journal: Math. Comp.
**42**(1984), 535-547 - MSC: Primary 65F05; Secondary 15A23
- DOI: https://doi.org/10.1090/S0025-5718-1984-0736451-4
- MathSciNet review: 736451