×

Convergence of Rump’s method for computing the Moore-Penrose inverse. (English) Zbl 1413.65115

Rump proposed a numerically verified algorithm for computing the inverse of an extremely ill-conditioned matrix. Later, S. Oishi et al. [J. Comput. Appl. Math. 205, No. 1, 533–544 (2007; Zbl 1120.65040)] proposed a modified version of this method. In this paper, the authors extend this modified Rump’s method and utilize the rank-revealing decomposition to compute the Moore-Penrose inverse of an extremely ill-conditioned matrix. Convergence analysis is presented. Several examples are presented to demonstrate the efficiency of the proposed method.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
15A09 Theory of matrix inversion and generalized inverses
65F35 Numerical computation of matrix norms, conditioning, scaling
15A24 Matrix equations and identities

Citations:

Zbl 1120.65040

Software:

Matlab; INTLAB
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] A. Ben-Israel, T. N. E. Greville: Generalized Inverses. Theory and Applications. Springer, New York, 2003. · Zbl 1026.15004
[2] Å. Björck: Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1996. · Zbl 0847.65023
[3] S. L. Campbell, C. D. Meyer: Generalized Inverses of Linear Transformations. Dover Publications, New York, 1991. · Zbl 0732.15003
[4] N. Castro-González, J. Ceballos, F. M. Dopico, J. M. Molera: Accurate solution of structured least squares problems via rank-revealing decompositions. SIAM J. Matrix Anal. Appl. 34 (2013), 1112–1128. · Zbl 1296.65060 · doi:10.1137/12088642X
[5] L. Chen, E. V. Krishnamurthy, I. Madeod: Generalised matrix inversion and rank computation by successive matrix powering. Parallel Comput. 20 (1994), 297–311. · Zbl 0796.65055 · doi:10.1016/S0167-8191(06)80014-1
[6] P. Courrieu: Fast computation of Moore-Penrose inverse matrices. Neural Information Processing 8 (2005), 25–29.
[7] F. Cucker, H. Diao, Y. Wei: On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems. Math. Comput. 76 (2007), 947–963. · Zbl 1115.15004 · doi:10.1090/S0025-5718-06-01913-2
[8] F. Cucker, H. Diao, Y. Wei: Smoothed analysis of some condition numbers. Numer. Linear Algebra Appl. 13 (2006), 71–84. · Zbl 1198.65084 · doi:10.1002/nla.464
[9] J. Demmel, M. Gu, S. Eisenstat, I. Slapničar, K. Veselić, Z. Drmač: Computing the singular value decomposition with high relative accuracy. Linear Algebra Appl. 299 (1999), 21–80. · Zbl 0952.65032 · doi:10.1016/S0024-3795(99)00134-2
[10] J. W. Demmel, Y. Hida, X. S. Li, E. J. Riedy: Extra-precise iterative refinement for overdetermined least squares problems. ACM Trans. Math. Software 35 (2009), Art. 28, 32 pages. · Zbl 05517421 · doi:10.1145/1462173.1462177
[11] J. Demmel, N. J. Higham: Improved error bounds for underdetermined system solvers. SIAM J. Matrix Anal. Appl. 14 (1993), 1–14. · Zbl 0770.65025 · doi:10.1137/0614001
[12] H. Diao, Y. Wei: On Frobenius normwise condition numbers for Moore-Penrose inverse and linear least-squares problems. Numer. Linear Algebra Appl. 14 (2007), 603–610. · Zbl 1199.65128 · doi:10.1002/nla.540
[13] H. Diao, Y. Wei, S. Qiao: Structured condition numbers of structured Tikhonov regularization problem and their estimations. J. Comput. Appl. Math. 308 (2016), 276–300. · Zbl 1346.65015 · doi:10.1016/j.cam.2016.05.023
[14] F. M. Dopico, J. M. Molera: Accurate solution of structured linear systems via rankrevealing decompositions. IMA J. Numer. Anal. 32 (2012), 1096–1116. · Zbl 1251.65040 · doi:10.1093/imanum/drr023
[15] M. Fiedler: Moore-Penrose biorthogonal systems in Euclidean spaces. Linear Algebra Appl. 362 (2003), 137–143. · Zbl 1022.15004 · doi:10.1016/S0024-3795(02)00510-4
[16] M. Fiedler, T. L. Markham: A characterization of the Moore-Penrose inverse. Linear Algebra Appl. 179 (1993), 129–133. · Zbl 0764.15003 · doi:10.1016/0024-3795(93)90325-I
[17] G. H. Golub, C. F. Van Loan: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, 2013.
[18] M. Gulliksson, P. Å. Wedin, Y. Wei: Perturbation identities for regularized Tikhonov inverses and weighted pseudoinverses. BIT 40 (2000), 513–523. · Zbl 0965.65063 · doi:10.1023/A:1022319830134
[19] J. Jones, N. P. Karampetakis, A. C. Pugh: The computation and application of the generalized inverse via Maple. J. Symb. Comput. 25 (1998), 99–124. · Zbl 0894.68088 · doi:10.1006/jsco.1997.0168
[20] V. N. Katsikis, D. Pappas: Fast computing of the Moore-Penrose inverse matrix. Electron. J. Linear Algebra (electronic only) 17 (2008), 637–650. · Zbl 1176.65048
[21] Z.-C. Li, H.-T. Huang, Y. Wei, A. H.-D. Cheng: Effective Condition Number for Numerical Partial Differential Equations. Alpha Science International, Oxford, 2014.
[22] Z. Li, Q. Xu, Y. Wei: A note on stable perturbations of Moore-Penrose inverses. Numer. Linear Algebra Appl. 20 (2013), 18–26. · Zbl 1289.65091 · doi:10.1002/nla.838
[23] T. Ogita, S. M. Rump, S. Oishi: Accurate sum and dot product. SIAM J. Sci. Comput. 26 (2005), 1955–1988. · Zbl 1084.65041 · doi:10.1137/030601818
[24] T. Ohta, T. Ogita, S. M. Rump, S. Oishi: Numerical verification method for arbitrarily ill-conditioned linear systems. Transactions of the Japan Society for Industrial and Applied Mathematics 15 (2005), 269–287.
[25] S. Oishi, S. M. Rump: Fast verification of solutions of matrix equations. Numer. Math. 90 (2002), 755–773. · Zbl 0999.65015 · doi:10.1007/s002110100310
[26] S. Oishi, K. Tanabe, T. Ogita, S. M. Rump: Convergence of Rump’s method for inverting arbitrarily ill-conditioned matrices. J. Comput. Appl. Math. 205 (2007), 533–544. · Zbl 1120.65040 · doi:10.1016/j.cam.2006.05.022
[27] C. R. Rao, S. K. Mitra: Generalized Inverses of Matrices and Its Applications. Wiley Series in Probability and Mathematical Statistics, Wiley & Sons, New York, 1971.
[28] S. M. Rump: Verified bounds for least squares problems and underdetermined linear systems. SIAM J. Matrix Anal. Appl. 33 (2012), 130–148. · Zbl 1255.65082 · doi:10.1137/110840248
[29] S. M. Rump: Inversion of extremely ill-conditioned matrices in floating-point. Japan J. Ind. Appl. Math. 26 (2009), 249–277. · Zbl 1185.65050 · doi:10.1007/BF03186534
[30] S. M. Rump: INTLAB–Interval Laboratory, the Matlab toolbox for verified computations, Version 5.3. Institute for Reliable Computing, Hamburg, 2006.
[31] S. M. Rump: Ill-conditioned matrices are componentwise near to singularity. SIAM Rev. 41 (1999), 102–112. · Zbl 0923.15003 · doi:10.1137/S0036144598323216
[32] S. M. Rump: Ill-conditionedness need not be componentwise near to ill-posedness for least squares problems. BIT 39 (1999), 143–151. · Zbl 0970.65039 · doi:10.1023/A:1022377410087
[33] S. M. Rump: A class of arbitrarily ill-conditioned floating-point matrices. SIAM J. Matrix Anal. Appl. 12 (1991), 645–653. · Zbl 0738.65042 · doi:10.1137/0612049
[34] S. M. Rump: Approximate Inverses of Almost Singular Matrices Still Contain Useful Information, Technical Report 90.1. Faculty for Information and Communications Sciences, TU Hamburg, Harburg, 1990.
[35] A. Smoktunowicz, J. Barlow, J. Langou: A note on the error analysis of classical Gram-Schmidt. Numer. Math. 105 (2006), 299–313. · Zbl 1108.65021 · doi:10.1007/s00211-006-0042-1
[36] A. Smoktunowicz, I. Wróbel: Numerical aspects of computing the Moore-Penrose inverse of full column rank matrices. BIT 52 (2012), 503–524. · Zbl 1251.65053 · doi:10.1007/s10543-011-0362-0
[37] G. W. Stewart: On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM Rev. 19 (1977), 634–662. · Zbl 0379.65021 · doi:10.1137/1019104
[38] G. Wang, Y. Wei, S. Qiao: Generalized Inverses: Theory and Computations. Science Press, Beijing, 2004. · Zbl 1395.15002
[39] P. Å. Wedin: Perturbation theory for pseudo-inverses. BIT, Nord. Tidskr. Inf.-behandl. 13 (1973), 217–232.
[40] Y. Wei: Generalized inverses of matrices, Chapter 27. Handbook of Linear Algebra (L. Hogben, ed.). Chapman & Hall/CRC Press, Boca Raton, 2014, pp. 27-1–27-15.
[41] Y. Wei, J. Ding: Representations for Moore-Penrose inverses in Hilbert spaces. Appl. Math. Lett. 14 (2001), 599–604. · Zbl 0982.47003 · doi:10.1016/S0893-9659(00)00200-7
[42] Y. Wei, H. Wu: Expression for the perturbation of the weighted Moore-Penrose inverse. Comput. Math. Appl. 39 (2000), 13–18. · Zbl 0957.15003 · doi:10.1016/S0898-1221(00)00041-9
[43] Y. Wei, P. Xie, L. Zhang: Tikhonov regularization and randomized GSVD. SIAM J. Matrix Anal. Appl. 37 (2016), 649–675. · Zbl 1339.65057 · doi:10.1137/15M1030200
[44] W. Xu, Y. Wei, S. Qiao: Condition numbers for structured least squares problems. BIT 46 (2006), 203–225. · Zbl 1093.65045 · doi:10.1007/s10543-006-0049-0
[45] L. Zhou, L. Lin, Y. Wei, S. Qiao: Perturbation analysis and condition numbers of scaled total least squares problems. Numer. Algorithms 51 (2009), 381–399. · Zbl 1171.65031 · doi:10.1007/s11075-009-9269-0
[46] G. Zielke: Report on test matrices for generalized inverses. Computing 36 (1986), 105–162. · Zbl 0566.65026 · doi:10.1007/BF02238196
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.