Numerical stability of descent methods for solving linear equations

In this paper we perform a round-off error analysis of descent methods for solving a liner systemAx=b, whereA is supposed to be symmetric and positive definite. This leads to a general result on the attainable accuracy of the computed sequence {xi} when the method is performed in floating point arithmetic. The general theory is applied to the Gauss-Southwell method and the gradient method. Both methods appear to be well-behaved which means that these methods compute an approximationxi to the exact solutionA−1b which is the exact solution of a slightly perturbed linear system, i.e. (A+δA)xi=b, ‖δA‖ of order ɛ‖A‖, where ɛ is the relative machine precision and ‖·‖ denotes the spectral norm.