<p>To solve large-scale sparse overdetermined linear systems, the Kaczmarz algorithm is a well-established and effective iterative method. Based on the residual-driven greedy deterministic block Kaczmarz (FDBK) algorithm, this paper proposes an improved greedy selection strategy. The greedy criterion in the FDBK algorithm mainly depends on the residual size, which is susceptible to numerical errors and ignores the direction information. Accordingly, this paper employs cosine distance as a geometric criterion to capture the angular relationship between the current solution and the candidate hyperplane, and develops a cosine distance-driven greedy block Gaussian-Kaczmarz (CD-GBGK) algorithm. The algorithm introduces a relaxation factor, further summarizes the CD-GBGK algorithm, and proves that the algorithm converges to its unique minimum norm solution when the equations are consistent. In this paper, it is also proved in theory and numerical experiments that the performance of the CD-rGBGK algorithm is optimal when the relaxation factor is 0. Theoretical analysis shows that the algorithm has linear convergence, and numerical experiments further verify that it can significantly reduce the computational overhead and improve the computational efficiency while preserving the accuracy.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Cosine distance-driven greedy block Gaussian-Kaczmarz algorithm and its variants for solving large-scale sparse overdetermined linear systems

  • Tong-Xi Zhou,
  • Xin-Hui Shao,
  • Yu-Jia Chen

摘要

To solve large-scale sparse overdetermined linear systems, the Kaczmarz algorithm is a well-established and effective iterative method. Based on the residual-driven greedy deterministic block Kaczmarz (FDBK) algorithm, this paper proposes an improved greedy selection strategy. The greedy criterion in the FDBK algorithm mainly depends on the residual size, which is susceptible to numerical errors and ignores the direction information. Accordingly, this paper employs cosine distance as a geometric criterion to capture the angular relationship between the current solution and the candidate hyperplane, and develops a cosine distance-driven greedy block Gaussian-Kaczmarz (CD-GBGK) algorithm. The algorithm introduces a relaxation factor, further summarizes the CD-GBGK algorithm, and proves that the algorithm converges to its unique minimum norm solution when the equations are consistent. In this paper, it is also proved in theory and numerical experiments that the performance of the CD-rGBGK algorithm is optimal when the relaxation factor is 0. Theoretical analysis shows that the algorithm has linear convergence, and numerical experiments further verify that it can significantly reduce the computational overhead and improve the computational efficiency while preserving the accuracy.