Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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

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

$\displaystyle T = \left[ {\begin{array}{*{20}{c}} 1 & { - 1} & {} & { - 1} & {}... ...\cdot & { - 1} \\ {} & {} & {} & {} & {} & {} & {} & 1 \\ \end{array} } \right]$

that has an nth pivot equal to $ 2^{-(n-2)}$.

References [Enhancements On Off] (What's this?)

  • [1] T. F. Chan, "An improved algorithm for computing the singular value decomposition," ACM Trans. Math. Software, v. 8, 1982, pp. 72-83. MR 661122 (83f:65058)
  • [2] T. F. Chan, Deflation Techniques and Block-Elimination Algorithms for Solving Bordered Singular Systems, Technical Report 226, Computer Science Department, Yale University, New Haven, CT, 1982; SIAM J. Sci. Statist Comput., v. 5, 1984. MR 731886 (85h:65065)
  • [3] T. F. Chan, Deflated Decomposition of Solutions of Nearly Singular Systems, Technical Report 225, Computer Science Department, Yale University, New Haven, CT, 1982; SIAM J. Numer. Anal. (To appear.) MR 749368 (86a:65029)
  • [4] T. F. Chan & H. B. Keller, "Arclength continuation and multi-grid techniques for nonlinear eigenvalue problems," SIAM J. Sci. Statist. Comput., v. 3, 1982, pp. 173-194. MR 658631 (83d:65152)
  • [5] A. K. Cline, "An elimination method for the solution of linear least squares problems," SIAM J. Numer. Anal., v. 10, 1973, pp. 283-289. MR 0359294 (50:11748)
  • [6] A. K. Cline, C. B. Moler, G. W. Stewart & J. H. Wilkinson, "An estimate for the condition number of a matrix," SIAM J. Numer. Anal., v. 16, 1979, pp. 368-375. MR 526498 (80g:65048)
  • [7] A. K. Cline & R. J. Plemmons, "$ {l_2}$ solutions to underdetermined linear systems," SIAM Rev., v. 18, 1976, pp. 92-106. MR 0396604 (53:466)
  • [8] J. J. Dongarra, J. R. Bunch, C. B. Moler & G. W. Stewart, LINPACK User's Guide, SIAM, Philadelphia, PA, 1979.
  • [9] G. H. Golub & C. Reinsch, "Singular value decomposition and least squares solutions," Numer. Math., 14, 1970, pp. 403-420. MR 1553974
  • [10] G. H. Golub & J. H. Wilkinson, "Ill-conditioned eigensystems and the computation of Jordan canonical form," SIAM Rev., v. 18, 1976, pp. 578-619. MR 0413456 (54:1570)
  • [11] H. B. Keller, "Numerical solution of bifurcation and nonlinear eigenvalue problems," In Applications of Bifurcation Theory (P. Rabinowitz, ed.), Academic Press, New York, 1977, pp. 359-384. MR 0455353 (56:13592)
  • [12] H. B. Keller, Singular Systems, Inverse Interation and Least Squares, unpublished manuscript, Applied Mathematics Department, Caltech, Pasadena, CA, 1978.
  • [13] H. B. Keller, Numerical Continuation Methods, Short Course Lecture Notes, National Bureau of Standards, Center for Applied Mathematics, 1981.
  • [14] 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.
  • [15] H. B. Keller, "The bordering algorithm and path following near singular points of higher nullity," SIAM J. Sci. Statist. Comput., v. 4, 1983. MR 725653 (85e:65012)
  • [16] R. G. Melhem & W. C. Rheinboldt, "A comparison of methods for determining turning points of nonlinear equations," Computing, v. 29, 1982, pp. 201-226. MR 680470 (84b:65054)
  • [17] D. P. O'Leary, "Estimating matrix condition numbers," SIAM J. Sci. Statist. Comput., v. 1, 1980, pp. 205-209. MR 594756 (82c:15006)
  • [18] G. Peters & J. H. Wilkinson, "The least squares problem and pseudo-inverses," Comput. J., v. 13, 1970, pp. 309-316.
  • [19] R. J. Plemmons, "Linear least squares by elimination and MGS," J. Assoc. Comput. Mach., v. 21, 1974, pp. 581-585. MR 0356474 (50:8944)
  • [20] W. C. Rheinboldt, "Numerical methods for a class of finite dimensional bifurcation problems," SIAM J. Numer. Anal., v. 15, 1978, pp. 1-11. MR 0494915 (58:13694)
  • [21] G. W. Stewart, "On the implicit deflation of nearly singular systems of linear equations," SIAM J. Sci. Statist. Comput., v. 2, 1981, pp. 136-140. MR 622710 (82f:65030)
  • [22] R. K. H. Szeto, The Flow Between Rotating Coaxial Disks, Ph.D. thesis, California Institute of Technology, 1978.
  • [23] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford Univ. Press, London, 1965. MR 0184422 (32:1894)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F05, 15A23

Retrieve articles in all journals with MSC: 65F05, 15A23


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1984-0736451-4
Keywords: LU-factorizations, singular systems
Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society