Communications on Applied Mathematics and Computation ›› 2025, Vol. 7 ›› Issue (5): 1724-1743.doi: 10.1007/s42967-024-00385-y

• ORIGINAL PAPERS • Previous Articles    

On Multi-step Partially Randomized Extended Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems

Jin-Feng Mao, Fang Chen   

  1. School of Applied Science, Beijing Information Science and Technology University, Beijing, 100192, China
  • Received:2023-11-27 Revised:2024-02-08 Accepted:2024-02-10 Online:2024-05-20 Published:2024-05-20
  • Contact: Fang Chen,E-mail:chenfreesky@126.com E-mail:chenfreesky@126.com
  • Supported by:
    Supported by the R &D Program of Beijing Municipal Education Commission, China (Grant No. KM202011232019).

Abstract: To enhance the computational performance of the partially randomized extended Kaczmarz (PREK) method, we propose the multi-step PREK (MPREK) method. By iteratively updating at each step, we establish a non-smooth inner-outer iteration scheme to solve the large, sparse, and inconsistent linear systems. For the MPREK method, a proof of its convergence and an upper bound on the convergence rate are given. Moreover, we show that this upper bound can be lower than that of the PREK method and the multi-step randomized extended Kaczmarz (MREK) method for certain typical choices of the inner iteration step size. Numerical experiments also indicate that, for an appropriate choice of the number of inner iteration steps, the MPREK method has a more efficient computational performance.

Key words: Large sparse linear system, Multi-step randomized extended Kaczmarz (MREK) method, Inconsistency, Convergence property