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

• ORIGINAL PAPERS • 上一篇    

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
  • 收稿日期:2023-11-27 修回日期:2024-02-08 接受日期:2024-02-10 出版日期:2024-05-20 发布日期:2024-05-20
  • 通讯作者: Fang Chen,E-mail:chenfreesky@126.com E-mail:chenfreesky@126.com
  • 基金资助:
    Supported by the R &D Program of Beijing Municipal Education Commission, China (Grant No. KM202011232019).

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).

摘要: 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.

关键词: Large sparse linear system, Multi-step randomized extended Kaczmarz (MREK) method, Inconsistency, Convergence property

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