基于贪婪随机Kaczmarz方法的算法研究

张选静 何清龙 陈敏 范芷萍 刘丽霞

【摘要】贪婪随机Kaczmarz算法（GRKM）是一种求解大型稀疏矩阵方程组的有效方法.基于GRKM方法和Nesterov加速策略，本文给出了一种求解线性方程组的快速AGREK迭代方法.AGREK算法的主要思想是在每步迭代中依据更有效的概率准则进行随机正交投影并采用Nesterov技术进行加速.为了验证AGREK算法的有效性，针对随机矩阵线性方程组进行数值实验，数值实验表明本文给出的AGREK方法是可行和高效的.

【关键词】线性方程组;Kaczmarz方法;AGREK方法

【基金项目】贵州大学大学生创新创业训练计划项目资助，项目编号：2018520067.

一、引 言

在理论研究和实际工程问题中，Kaczmarz方法是一种有效的迭代方法，该方法每次迭代将当前点投影到选取行所形成的超平面上.经过多次迭代，从而达到逐渐接近线性方程组的真实解的目的.若初始估计量为x0，则求解线性方程组Ax=b的Kaczmarz方法迭代过程为：

xk+1=xk+（b（i）-A（i）xk）‖A（i）‖22（A（i））T，

其中，i=kmodm+1，A（i）表示系数矩阵A的第i行，b（i）表示右端项b的第i个元素，（·）T表示转置，‖·‖2表示欧几里得范数.

基于Kaczmarz方法的研究一直是数值代数理论研究的热点.Strohmer和Vershynin提出具有指数收敛速度的随机化Kaczmarz方法，使用随机选取系数矩阵A的行进行投影，大大提高Kaczmarz方法的收敛速度[1].Zhong基于更加有效的随机选取行的准则，建立了贪婪随机Kaczmarz方法（Greedy Randomized Kaczmarz Method，GRKM）[2].向徐提出了基于Nesterov加速技术的AREK算法[3].本文基于GRKM算法中提出的引入指标集的概率选择准则和Nesterov加速的AREK算法，给出了一种快速高效的AGREK算法并给出数值试验以验证方法的有效性.

二、AGREK算法

输入：m×n系数矩阵A，向量b，迭代次数l，初始化v0=x0=0，z0=b，w-1=0.

输出：xl

for k=0，1，…，l-1 do

STEP 1.求解方程w2k=w2k+w2k-1λ-1mwk-w2k-1=0，令wk的值为方程组的较大根.

计算βk=m-wkλwk（m2-λ），tk=1-wkλm.

STEP 2.选择jk∈{1，2，…，n}列的概率为：

pr（jk）=‖A（j）‖22‖A‖2F.

STEP 3.随机正交投影：zk+1=zk-（A（jk）T，zk）‖A（jk）‖22A（jk）.

STEP 4.计算

εk=121‖b-Axk‖22max1≤ik≤m|b（ik）-A（ik）xk|2‖A（ik）‖22+1‖A‖2F.

STEP 5.定義正整数指标集uk={ik||b（ik）-A（ik）xk|2≥εk‖b-Axk‖22‖A（ik）‖22}.

STEP 6.根据

r（i）k=b（i）-A（i）xk，if i∈uk，0，otherwise，

计算向量rk中的第i个分量r（i）k.

STEP 7.选择ik∈uk行的概率为：pr（ik）=|r（ik）k|2‖rk‖22.

STEP 8.Nesterov加速过程

yk=βkvk+（1-βk）xk，

xk+1=yk-（A（ik）T（A（ik）yk-（b（ik）-z（ik）k）））‖A（ik）‖22，

vk+1=tkvk+（1-tk）yk-wk（A（ik）T（A（ik）yk-（b（ik）-z（ik）k）））‖A（ik）‖22

end for.

三、数值实验

（一）适定方程组

本节中的数值实验均以零向量为初始值，即x0=（0，0，…，0），使用随机生成的矩阵A∈Rm×n（m=n）和向量x∈Rn 进行数值实验，右端项b=Ax，程序每运行100次对应1次迭代次数.对当前迭代xk，若满足相对误差RSE<10-6或已经达到最大运行次数，算法停止运行，将其视为一次数值实验.为了避免随机性结果，求解同一个线性方程组的数值实验重复进行5次，最终实验结果取5次数值实验的均值.实验结果如下.

由表1、图1、图2显示的实验结果可以看出，求解适定方程组时，当达到最大迭代次数时，GRKM方法仍不能得到满足相对误差条件的有效解，AREK方法、AGREK方法均收敛得比GRKM方法快，AGREK方法比AREK方法收敛得更快.

（二）超定方程组

求解超定线性方程组Ax=b，A∈Rm×n（m>n）.我们利用该方程的最小二乘解作为该方程的广义解，于是广义解等价于求解线性方程组ATAx=ATb.程序每运行1次对应1次迭代次数.对当前迭代xk，仍为了避免随机性结果，求解同一个线性方程组的数值实验每次进行5次，实验结果取5次数值实验的均值.实验结果如表2所示.

由表2可知，当求解超定方程组时，三种方法随着方程数目的增加，求解随机矩阵所需的迭代时间和迭代次数呈现减小的趋势.当求解超定矩阵时，GRKM方法收敛得比AREK和AGREK方法快，AGREK方法收敛得比AREK方法快.

四、结 语

针对求解线性方程组问题，本文基于GRKM方法和AREK方法，提出了一种更加快速有效的AGREK方法.AGREK方法兼具GRKM方法的概率准则优点和Nesterov加速特性，因此，能够快速求解线性方程组.数值试验表明，当求解线性方程组时，AGREK方法的收敛速度优于AREK方法和GRKM方法，验证了AGREK算法的高效性.

【参考文献】

[1]T.Strohmer and R.Vershynin.A randomized Kaczmarz algorithm with exponential convergence[J].Journal of Fourier Analysisand Applications，2008（15）：262.

[2]Zhong Zhi Bai，Wen Ting Wu.On greedy randomized Kaczmarz method for solving large sparse linear systems[J]，SIAM J.Sci.Comput.，2018（40）：A592-A606.