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
Corrigendum: Math. Comp. 44 (1985), 282.
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)}$.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, 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 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, 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 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," 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 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, 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
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