On convergence rate of the randomized Gauss-Seidel method

doi:10.1016/j.laa.2020.10.028

CSpace

	On convergence rate of the randomized Gauss-Seidel method
	Bai, Zhong-Zhi 1,2; Wang, Lu 1,2; Wu, Wen-Ting 3
	2021-02-15
发表期刊	LINEAR ALGEBRA AND ITS APPLICATIONS
ISSN	0024-3795
卷号	611 页码:237-252
摘要	The Gauss-Seidel and Kaczmarz methods are two classic iteration methods for solving systems of linear equations, which operate in column and row spaces, respectively. Utilizing the connections between these two methods and imitating the exact analysis of the mean-squared error for the randomized Kaczmarz method, we conduct an exact closed-form formula for the mean-squared residual of the iterate generated by the randomized Gauss-Seidel method. Based on this new formula, we further estimate an upper bound for the convergence rate of the randomized Gauss-Seidel method. Theoretical analysis and numerical experiments show that this bound measurably improves the existing ones. Moreover, these theoretical results are also extended to the more general extrapolated randomized Gauss-Seidel method. (C) 2020 Elsevier Inc. All rights reserved.
关键词	System of linear equations Randomized Gauss-Seidel method Randomized Kaczmarz method Convergence rate
DOI	10.1016/j.laa.2020.10.028
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation, P.R. China[12071472] ; National Natural Science Foundation, P.R. China[11671393] ; National Natural Science Foundation, P.R. China[12001043] ; Grant of the Government of the Russian Federation, Russia[075-15-2019-1928] ; China-Russia (NSFC-RFBR) International Cooperative Research Project[11911530082] ; China-Russia (NSFC-RFBR) International Cooperative Research Project[19-51-53013] ; Beijing Institute of Technology Research Fund Program for Young Scholars ; Science and Technology Commission of Shanghai Municipality, P.R. China[18dz2271000]
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied ; Mathematics
WOS记录号	WOS:000600065400013
出版者	ELSEVIER SCIENCE INC
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/57847
专题	中国科学院数学与系统科学研究院
通讯作者	Bai, Zhong-Zhi
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Inst Computat Math & Sci Engn Comp, State Key Lab Sci Engn Comp, POB 2719, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China 3.Beijing Inst Technol, Sch Math & Stat, Beijing 100081, Peoples R China
推荐引用方式 GB/T 7714	Bai, Zhong-Zhi,Wang, Lu,Wu, Wen-Ting. On convergence rate of the randomized Gauss-Seidel method[J]. LINEAR ALGEBRA AND ITS APPLICATIONS,2021,611:237-252.
APA	Bai, Zhong-Zhi,Wang, Lu,&Wu, Wen-Ting.(2021).On convergence rate of the randomized Gauss-Seidel method.LINEAR ALGEBRA AND ITS APPLICATIONS,611,237-252.
MLA	Bai, Zhong-Zhi,et al."On convergence rate of the randomized Gauss-Seidel method".LINEAR ALGEBRA AND ITS APPLICATIONS 611(2021):237-252.