A Relaxed Greedy Block Kaczmarz Method for Solving Large Consistent Linear Systems

摘要

Many problems in science and engineering require solving large consistent linear systems. This paper presents a relaxed greedy block Kaczmarz method (RGBK) and an accelerated greedy block Kaczmarz method (AGBK) for solving large-size consistent linear systems. The RGBK algorithm extends the greedy block Kaczmarz algorithm (GBK) presented by Niu and Zheng in [1] by introducing a relaxation parameter to the iteration formulation of GBK, and the AGBK algorithm uses different iterative update rules to minimize the running time. The convergence of the RGBK is proved and a method to determine an optimal parameter is provided. Several examples are presented to show the effectiveness of the proposed methods for overdetermined and underdetermined consistent linear systems with dense and sparse coefficient matrix.