Extrapolated Gauss-Seidel I and SOR methods for least-squares problems (Q1096331)

Recently, special attention has been given in the literature to the problems of accurately computing the least-squares solution of very large-scale over-determined systems of linear equations which occur in geodetic applications. In particular, it has been suggested that one can solve such problems iteratively by applying the block SOR (Successive Overrelaxation) and EGS1 (Extrapolated Gauss Seidel 1) plus semi- iterative methods to a linear system with coefficient matrix 2-cyclic or 3-cyclic. The comparison of 2-block SOR and 3-block SOR was made by \textit{T. L. Markham}, \textit{M. Neumann} and \textit{R. J. Plemmons} [Linear Algebra Appl. 69, 155-167 (1985; Zbl 0576.65026)] and showed that the 2-block SOR is better. The authors [The EGS1 and semi-iterative (SI) method for the solution of large sparse least-squares problems, Computer Studies 346, Loughborough University of Tech., U.K. (1987)] also proved that 3-block EGS1-SI is better than 3-block SOR. Here, we first show that the 2-block DJ (Double Jacobi)-SI, GS-SI and EGS1-SI methods are equivalent and all of them are equivalent to the 3- block EGS1-SI method; then, we prove that the composite methods and 2- block SOR have the same asymptotic rate of convergence; finally, numerical experiments are reported, and confirm that the 3-block EGS1-SI is better than the 2-block SOR.