Forward Stability of Iterative Refinement with a Relaxation for Linear Systems
DOI:
https://doi.org/10.15377/2409-5761.2016.03.02.1Keywords:
Iterative refinement, numerical stability, condition number.Abstract
Stability analysis of Wilkinson’s iterative refinement method IR(ω) with a relaxation parameter ω for solving linear systems is given. It extends existing results for ω=1, i.e., for Wilkinson’s iterative refinement method. We assume that all computations are performed in fixed (working) precision arithmetic. Numerical tests were done in MATLAB to illustrate our theoretical results. A particular emphasis is given on convergence of iterative refinement method with a relaxation. A preliminary error analysis of the Algorithm IR(ω) was given in [11]. Our opinion is opposite to that given in [11], since our experiments show that the choice ω=1 is the best choice from the point of numerical stability.
Downloads
References
Buttari A, Dongarra J, Langou J, Langou J, Luszczek JP, Kurzak J. Mixed precision iterative refinement techniques for the solution of dense linear systems. International Journal of High Performance Computing Applications 2007; 21(4): 457- 466. https://doi.org/10.1177/1094342007084026 DOI: https://doi.org/10.1177/1094342007084026
Demmel JW, Higham NJ, Schreiber RS. Stability of block LU factorization. Numer Linear Algebra Appl 1995; 12: 173-190. https://doi.org/10.1002/nla.1680020208 DOI: https://doi.org/10.1002/nla.1680020208
Foster LV. Gaussian elimination with partial pivoting can fail in practice. SIAM J Matrix Anal Appl 1994; 15(4): 1354-1362. https://doi.org/10.1137/S0895479892239755 DOI: https://doi.org/10.1137/S0895479892239755
Higham NJ. Iterative refinement enhances the stability of QR factorization methods for solving linear equations. BIT 1991; 31: 447-468. https://doi.org/10.1007/BF01933262 DOI: https://doi.org/10.1007/BF01933262
Higham NJ. Iterative refinement for linear systems and LAPACK. IMA J Numer Anal 1997; 17: 495-509. https://doi.org/10.1093/imanum/17.4.495 DOI: https://doi.org/10.1093/imanum/17.4.495
Jankowski M, Woźniakowski H. Iterative refinement implies numerical stability. BIT 1977; 17: 303-311. https://doi.org/10.1007/BF01932150 DOI: https://doi.org/10.1007/BF01932150
Rozložník M, Smoktunowicz A, Kopal J. A note on iterative refinement for seminormal equations. Applied Numerical Mathematics 2014; 75: 167-174. https://doi.org/10.1016/j.apnum.2013.08.005 DOI: https://doi.org/10.1016/j.apnum.2013.08.005
Skeel RD. Iterative refinement implies numerical stability for Gaussian elimination. Math Comp 1980; 35: 817-832. https://doi.org/10.1090/S0025-5718-1980-0572859-4 DOI: https://doi.org/10.1090/S0025-5718-1980-0572859-4
Smoktunowicz A, Smoktunowicz A. Iterative refinement techniques for solving block linear systems of equations. Applied Numerical Mathematics 2013; 67: 220-229. https://doi.org/10.1016/j.apnum.2011.11.004 DOI: https://doi.org/10.1016/j.apnum.2011.11.004
Wilkinson JH. The Algebraic Eigenvalue Problem, Oxford University Press 1965.
Wu X, Wang Z. A new iterative refinement with roundoff error analysis. Numer Linear Algebra Appl 2011; 18: 275-282. https://doi.org/10.1002/nla.723 DOI: https://doi.org/10.1002/nla.723
Downloads
Published
Issue
Section
License
Copyright (c) 2016 Alicja Smoktunowicz, Jakub Kierzkowski, Iwona Wróbel
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
All the published articles are licensed under the terms of the Creative Commons Attribution Non-Commercial License (CC BY-NC 4.0) which permits unrestricted, non-commercial use, distribution and reproduction in any medium, provided the work is properly cited.
