Numerical stability of GMRES (Q1904273): Difference between revisions

The generalized minimal residual (GMRES) method is one of the most popular methods for solving systems of linear equations with nonsymmetric coefficient matrices. The authors study the numerical stability of GMRES when the computation of approximations is based on constructing an orthonormal basis of Krylov subspaces (Arnoldi basis) and after that the transformed least squares problem is solved. It is shown that if the Arnoldi basis is computed via Householder orthogonalization and the transformed least squares problem is solved using Givens rotations, then the computed GMRES approximation has a guaranteed backward error of size at worst \(O(N^{{5\over 2}}\varepsilon)\), where \(N\) is the size of the coefficient matrix and \(\varepsilon\) is the machine precision. Reading the paper, one can find the description of the Arnoldi recurrence for the quantities actually computed in finite precision arithmetic and an analysis of the relation between the true and Arnoldi residuals in the presence of rounding errors.