FINITE PRECISION BEHAVIOR OF STATIONARY ITERATION FOR SOLVING SINGULAR SYSTEMS

A stationary iterative method for solving a singular system Ax = b con verges for any starting vector if lim(i-->infinity)G(i) exists, where G is the iteration matrix, and the solution to which it converges depe nds on the starting vector. We examine the behavior of stationary iter ation in finite precision arithmetic. A perturbation bound for singula r systems is derived and used to define forward stability of a numeric al method. A rounding error analysis enables us to deduce conditions u nder which a stationary iterative method is forward stable or backward stable. The component of the forward error in the null space of A can grow linearly with the number of iterations, but it is innocuous as l ong as the iteration converges reasonably quickly. As special cases, w e show that when A is symmetric positive semidefinite the Richardson i teration with optimal parameter is forward stable, and if A also has u nit diagonal and property A, then the Gauss-Seidel method is both forw ard and backward stable. Two numerical examples are given to illustrat e the analysis.