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 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 \[ 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, LINPACK Userโs Guide, SIAM, Philadelphia, PA, 1979.
- 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, 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.
- 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," Comput. J., v. 13, 1970, pp. 309-316.
- 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, The Flow Between Rotating Coaxial Disks, Ph.D. thesis, California Institute of Technology, 1978.
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
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