On maximum residual block Kaczmarz method for solving large consistent linear systems

Abstract

In this paper, we propose two block variants of the Kaczmarz method for solving large-scale consistent linear equations $ Ax = b $. The first method, named the maximum residual block Kaczmarz (denoted as MRBK) method, first partitions the coefficient matrix, and then captures the largest block in the residual vector during each block iteration to ensure that it is eliminated first. Simultaneously, in order to avoid the pseudo-inverse calculation of the MRBK method during block iteration and improve the convergence speed, we further propose the maximum residual average block Kaczmarz method. This method completes the iterative process by projecting the current solution vector onto each row of the constrained subset of the matrix $ A $ and averaging it with different extrapolation steps. We analyze and prove the deterministic convergence of both methods. Numerical experiments validate our theory and show that our proposed methods are superior to some other block Kaczmarz methods.

Keywords

• consistent linear system
• maximum residual block kaczmarz
• maximum residual average block kaczmarz
• free pseudo-inverse
• convergence property