大型稀疏线性系统的一类含参数的贪心随机Kaczmarz算法

doi:10.12066/j.issn.1007-2861.2151

上海大学学报(自然科学版) ›› 2020, Vol. 26 ›› Issue (6): 1026-1034.doi: 10.12066/j.issn.1007-2861.2151

• 研究论文 • 上一篇

大型稀疏线性系统的一类含参数的贪心随机Kaczmarz算法

刘永¹^,²(), $\fbox{顾传青}$², 崔蓉蓉³

1. 常州信息职业技术学院, 江苏常州 213164
2. 上海大学理学院, 上海 200444
3. 盐城师范学院数学与统计学院, 江苏盐城 224002

收稿日期:2019-03-04 出版日期:2020-12-31 发布日期:2020-12-29
通讯作者: 刘永 E-mail:lyccit@yeah.net
作者简介:刘永(1988—), 男, 讲师, 博士, 研究方向为数值线性代数. E-mail: lyccit@yeah.net
基金资助:
国家自然科学基金建设资助项目(11371243);上海市重点学科建设资助项目(S30104);江苏省高等学校自然科学研究面上项目(16KJD110006);常州信息职业技术学院自然科学研究重点项目(CXKZ201908Z)

Parametric greedy randomized Kaczmarz algorithm for solving large sparse linear systems

LIU Yong¹^,²(), $\fbox{GU Chuanqing}$ ², CUI Rongrong³

1. Changzhou College of Information Technology, Changzhou 213164, Jiangsu, China
2. College of Sciences, Shanghai University, Shanghai 200444, China
3. School of Mathematics and Statistics, Yancheng Teachers University, Yancheng 224002, Jiangsu, China

Received:2019-03-04 Online:2020-12-31 Published:2020-12-29
Contact: LIU Yong E-mail:lyccit@yeah.net

摘要/Abstract

摘要：

为了求解大型稀疏线性系统, 在贪心随机Kaczmarz (greedy randomized Kaczmarz, GRK)算法的迭代公式中引入松弛因子,构造了一种含参数的贪心随机Kaczmarz算法.证明了当线性系统相容时该算法的收敛性. 数值实验表明,当选择恰当的松弛因子时, 该算法在迭代步数和计算时间上比贪心随机Kaczmarz算法更有效.

关键词: 大型稀疏线性系统, 贪心随机Kaczmarz算法, 松弛因子

Abstract:

To solve large sparse linear systems, a relaxation parameter in introduced in the involved iterative formula of greedy randomized Kaczmarz (GRK) algorithm, and obtain a parametric greedy randomizedKaczmarzalgorithm is obtained. The convergence of this algorithm is proved when the linear system is consistent, and it is showed that it can be more efficient than the greedy randomized Kaczmarz algorithm if the relaxation parameter is chosen appropriately.

Key words: large sparse linear system, greedy randomized Kaczmarz (GRK) algorithm, relaxation parameter

中图分类号:

O241.6

刘永, $\fbox{顾传青}$, 崔蓉蓉. 大型稀疏线性系统的一类含参数的贪心随机Kaczmarz算法[J]. 上海大学学报(自然科学版), 2020, 26(6): 1026-1034.

LIU Yong, $\fbox{GU Chuanqing}$ , CUI Rongrong. Parametric greedy randomized Kaczmarz algorithm for solving large sparse linear systems[J]. Journal of Shanghai University（Natural Science Edition）, 2020, 26(6): 1026-1034.

图/表 3

参考文献 12

[1]	Kaczmarz S. Angenäherte auflösung von systemen linearer gleichungen[J]. Bull Int Acad Polon Sci Lett A, 1937,35:355-357.
[2]	Herman G T, Meyer L B. Algebraic reconstruction techniques can be made computationally efficient[J]. IEEE Transactions on Medical Imaging, 1993,12(3):600-609. doi: 10.1109/42.241889 pmid: 18218454
[3]	Popa C, Zdunek R. Kaczmarz extended algorithm for tomographic image reconstruction from limited-data[J]. Mathematics and Computers in Simulation, 2004,65(6):579-598. doi: 10.1016/j.matcom.2004.01.021
[4]	Gordon R, Bender R, Herman G T. Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography[J]. Journal of Theoretical Biology, 1970,29(3):471-481. doi: 10.1016/0022-5193(70)90109-8 pmid: 5492997
[5]	Byrne C. A unified treatment of some iterative algorithms in signal processing and image reconstruction[J]. Inverse Problems, 2004,20(1):103-120. doi: 10.1088/0266-5611/20/1/006
[6]	Pasqualetti F, Carli R, Bullo F. Distributed estimation via iterative projections with application to power network monitoring[J]. Automatica, 2012,48(5):747-758. doi: 10.1016/j.automatica.2012.02.025
[7]	Bai Z Z, Liu X G. On the Meany inequality with applications to convergence analysis of several row-action iteration methods[J]. Numerische Mathematik, 2013,124(2):215-236. doi: 10.1007/s00211-012-0512-6
[8]	Bai Z Z, Wu W T. On convergence rate of the randomized Kaczmarz method[J]. Linear Algebra and its Applications, 2018,553(15):252-269. doi: 10.1016/j.laa.2018.05.009
[9]	Strohmer T, Vershynin R. A randomized Kaczmarz algorithm with exponential conver-gence[J]. Journal of Fourier Analysis and Applications, 2009,15(2):262-278. doi: 10.1007/s00041-008-9030-4
[10]	Zouzias A, Freris N M. Randomized extended Kaczmarz for solving least squares[J]. SIAM Journal on Matrix Analysis and Applications, 2013,34(2):773-793. doi: 10.1137/120889897
[11]	Bai Z Z, Wu W T. On greedy randomized Kaczmarz method for solving large sparse linear systems[J]. SIAM Journal on Scientific Computing, 2018,40(1):592-606.
[12]	Davis T A, Hu Y. The university of Florida sparse matrix collection[J]. ACM Transactions on Mathematical Software, 2011,38(1):1-25.

大型稀疏线性系统的一类含参数的贪心随机Kaczmarz算法

Parametric greedy randomized Kaczmarz algorithm for solving large sparse linear systems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 12

相关文章 0

编辑推荐

Metrics

本文评价