Please use this identifier to cite or link to this item:
Main Title: Least squares residuals and minimal residual methods
Author(s): Liesen, Jörg
Rozlozník, Miroslav
Strakoš, Zdeněk
Type: Article
Language Code: en
Abstract: We study Krylov subspace methods for solving unsymmetric linear algebraic systems that minimize the norm of the residual at each step (minimal residual (MR) methods). MR methods are often formulated in terms of a sequence of least squares (LS) problems of increasing dimension. We present several basic identities and bounds for the LS residual. These results are interesting in the general context of solving LS problems. When applied to MR methods, they show that the size of the MR residual is strongly related to the conditioning of different bases of the same Krylov subspace. Using different bases is useful in theory because relating convergence to the characteristics of different bases offers new insight into the behavior of MR methods. Different bases also lead to different implementations which are mathematically equivalent but can differ numerically. Our theoretical results are used for a finite precision analysis of implementations of the GMRES method [Y. Saad and M. H. Schultz, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856--869]. We explain that the choice of the basis is fundamental for the numerical stability of the implementation. As demonstrated in the case of Simpler GMRES [H. F. Walker and L. Zhou, Numer. Linear Algebra Appl., 1 (1994), pp. 571--581], the best orthogonalization technique used for computing the basis does not compensate for the loss of accuracy due to an inappropriate choice of the basis. In particular, we prove that Simpler GMRES is inherently less numerically stable than the Classical GMRES implementation due to Saad and Schultz [SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856--869].
Issue Date: 2012
Date Available: 20-Dec-2017
DDC Class: 518 Numerische Analysis
512 Algebra
Subject(s): linear systems
least squares problems
Krylov subspace methods
minimal residual methods
rounding errors
Journal Title: SIAM Journal on Scientific Computing
Publisher: Society for Industrial and Applied Mathematics
Publisher Place: Philadelphia, Pa
Volume: 23
Issue: 5
Publisher DOI: 10.1137/S1064827500377988
Page Start: 1503
Page End: 1525
EISSN: 1095-7197
ISSN: 1064-8275
Appears in Collections:FG Numerische Lineare Algebra » Publications

Files in This Item:
File Description SizeFormat 
2012_Liesen_et-al.pdf227.04 kBAdobe PDFThumbnail

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.