THE CONVERGENCE OF LINEAR STATIONARY ITERATIVE PROCESSES FOR SOLVING SINGULAR UNSTRUCTURED SYSTEMS OF LINEAR-EQUATIONS

This paper reviews the convergence properties of linear stationary iterative processes for solving large unstructured systems of linear equations. Special attention is given to the case where the system to be solved is singular and possibly inconsistent. The review starts by investigating the iteration x(k+1) = Hx(k) + f, k = 0, 1, 2, ..., when the system (I - H)x = f is inconsistent. In this case the sequence {x(k)} always diverges. Nevertheless, when H is "convergent" there exists a vector q-epsilon-Null (I - H) such that the sequence x(k) = x(k) - k(q) converges. the limit of this sequence, x, solves a certain least-squares problem, and the sequence of residual vectors, r(k) = (I - H)x(k) - f, converges to (I - H)x - f. Furthermore, if H is similar to a real diagonal matrix then the corresponding norms of r(k) and x(k) - x decreases monotonically. More can be said when x(o)-epsilon-Range (I - H). There are several iterative methods for solving a symmetric positive semidefinite system of linear equations, Gx = h, that have the form x(k + 1) = Q-1(Q - G)x(k + Q-1h. Here the iteration matrix, H = Q-1(Q - G), is convergent whenever the matrix P = Q + Q(T) - G is positive definite. In this case we obtain the surprising result that the sequence of residuals, {Gx(k) - h}, converges even when the system Gx = h is inconsistent. The developed theory reveals interesting properties of the "basic" iterative methods (e.g., Richardson's method, Jacobi's method, SOR, and SSOR) with minimal assumptions on the structure of G. For example, if H is convergent and symmetric as with Richardson's method, then the sequences {parallel-to x(k) - x parallel-to} and {parallel-to Gx(k) - h parallel-to} decrease monotonically, and the sequence {Gx(k) - h} converges to Gx - h, where x solves the least-squares problem: minimize parallel-to Gx - h parallel-to 2. Moreover, if x(o)-epsilon-Range (G) and the system Gx = h is solvable, then the sequence {X(k)} converges to the minimum-norm solution of this system. The paper ends with a discussion of iterative methods for solving a general linear system, Ax = b, where A is large, sparse, and unstructured. These methods can be divided into two classes. One is aimed at solving the normal equations A(T) Ax = A(T)b (e.g., column SOR or Cimmino's method), and one is aimed at solving the Bjorck-Elfving equations x = A(T)y and AA(T)y = b (e.g., Kaczmarz's method). It is shown that in both cases the theory developed for symmetric positive semidefinite systems enables us to characterize the behavior of the methods and to derive simplified proofs of convergence.