×

Iterative refinement for ill-conditioned linear systems. (English) Zbl 1188.65053

The authors design and theoretically analyze an iterative refinement algorithm for a system of linear equations, in which the entries of the system matrix and the right hand side are floating point numbers. Forward and backward stability results are also obtained.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra

Software:

LAPACK
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] G.B. Moler, Iterative refinement in floating point. J. Assoc. Comput. Mach.,14 (1967), 316–321. · Zbl 0161.35501 · doi:10.1145/321386.321394
[2] N.J. Higham, Iterative refinement for linear systems and LAPACK. IMA J. Numer. Anal.,17 (1997), 495–509. · Zbl 0887.65034 · doi:10.1093/imanum/17.4.495
[3] M. Jankowsky and H. Woznlakowski, Iterative refinement implies numerical stability. BIT,17 (1997), 303–311. · Zbl 0372.65012 · doi:10.1007/BF01932150
[4] F. Tisseur, Newton’s method in floating point arithmetic and iterative refinement of generalized eigenvalue problems. SIAM J. Matrix Anal. Appl.,22 (2001), 1038–1057. · Zbl 0982.65040 · doi:10.1137/S0895479899359837
[5] R.D. Skeel, Iterative refinement implies numerical stability for Gaussian elimination. Math. Comp.,35 (1980), 817–832. · Zbl 0441.65027 · doi:10.1090/S0025-5718-1980-0572859-4
[6] S.M. Rump, Approximate inverses of almost singular matrices still contain useful information. Technical Report 90.1, Faculty of Information and Communication Sciences, Hamburg University of Technology, 1990.
[7] S. Oishi, K. Tanabe, T. Ogita and S.M. Rump, Convergence of Rump’s method for inverting arbitrary ill-conditioned matrices. J. Comp. and Appl. Math.,205 (2007), 533–544. · Zbl 1120.65040 · doi:10.1016/j.cam.2006.05.022
[8] S.M. Rump, Inversion of extremely ill-conditioned matrices in floating point. Submitted for publication in JJIAM, March 15, 2008. · Zbl 1185.65050
[9] T. Ogita, S.M. Rump and S. Oishi, Accurate sum and dot product. SIAM Journal on Scientific Computing,26 (2005), 1955–1988. · Zbl 1084.65041 · doi:10.1137/030601818
[10] S.M. Rump, T. Ogita and S. Oishi, Accurate floating-point summation I: Faithful rounding. Accepted for publication in SIAM Journal on Scientific Computing. Preprint is available from http://www.ti3.tu-harburg.de/publications/rump. · Zbl 1185.65082
[11] S.M. Rump, T. Ogita and S. Oishi, Accurate floating-point summation II: Sign,K-fold faithful and rounding to nearest. Accepted for publication in SIAM Journal on Scientific Computing. Preprint is available from http://www.ti3.tu-harburg.de/publications/rump. · Zbl 1190.65074
[12] T. Ohta, T. Ogita, S.M. Rump and S. Oishi, A method of verified numerical computation for ill-conditioned linear system of equations. Journal of JSIAM,15 (2005), 269–287, in Japanese.
[13] 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
[14] J.D. Rigal and J. Gaches, On the compativility of a given solution with the data of a linear equation. J. Assoc. Comput. Mach.,14 (1967), 543–548. · Zbl 0183.17704 · doi:10.1145/321406.321416
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.