Convergence of block iterative methods applied to sparse least-squares problems (Q1058819)

The paper is dealing with the problems of accurately computing the least squares solutions of overdetermined systems (1) \(Ax=b\) of linear equations, such as those arising in geodetical network problems. In (1) A is a large sparse \(m\times n\) matrix with \(m\geq n\), b is a vector in \(R^ m\) and x a vector in \(R^ n\). It turns out that an equivalent problem to find the least squares solution of (1) is to solve a linear system (2) \(Cz=d\) of \(m+n\) equations in \(m+n\) unknowns. In (2) C is a nonsingular \((m+n)\times (m+n)\) matrix, \(z=(x,w,v)^ T\in {\mathbb{R}}^{m+n}\) a vector with \(x\in {\mathbb{R}}^ n\), \(w\in {\mathbb{R}}^{m-n}\), \(v\in {\mathbb{R}}^ n\) and \(d=(b_ 1,b_ 2,0)^ T\in {\mathbb{R}}^{m+n}\) a vector with \((b_ 1,b_ 2)^ T=b,\) \(b_ 1\in {\mathbb{R}}^ n\), \(b_ 2\in {\mathbb{R}}^{m-n}\). As was observed by Chen in 1975 the block-SOR (successive overrelaxation) iterative method is in particular convenient to solve this special type (2) of linear systems. In the present paper several new results are obtained in case the block-Jacobi matrix J associated with the matrix C is a consistently ordered matrix, weakly cyclic of index 3. Theorem 1 gives the exact convergence domain of the block-SOR iterative method as well as the optimal relaxation factor, when the eigenvalues of \(J^ 3\) as assumed to be nonpositive. Theorem 2 answers the same questions when the eigenvalues of \(J^ 3\) are non-negative. In addition, Theorem 1 gives a new result that applications of the block-SOR method can be made even in some cases where the associated block-Jacobi iterative method is divergent. Furthermore, Theorem 1 corrects some erroneous results occuring in the literature.