巫文婷

（北京理工大学数学与统计学院，北京 100081）

对于系数矩阵为A∈Cm×n且右端向量为b∈Cm的大规模相容线性代数方程组

的求解，Kaczmarz方法［1］是经典的行处理迭代方法，在信号与图像处理领域有着广泛的应用。其每步迭代只需按照给定的循环顺序选取系数矩阵的某一行，并将当前迭代向量正交投影至由该行所形成的超平面上。Strohmer等［2］提出按照与系数矩阵每一行的欧氏范数平方成比例的概率准则随机选取系数矩阵的行，得到了收敛更为快速的随机Kaczmarz方法。若用(·)*表示相应矩阵或向量的共轭转置，则当初始迭代向量在A*的列空间中时，随机Kaczmarz方法期望线性收敛［2-5］到线性代数方程组（1）的最小欧氏范数解x⋆=A†b，其中A†表示系数矩阵A的Moore-Penrose伪逆。当线性代数方程组（1）的右端向量发生扰动时，Needell［6］给出了随机Kaczmarz方法的期望解误差的上界，并说明了随着迭代步数的增长，随机Kaczmarz方法的期望解误差会以线性速率下降至一个误差阈值。之后，Zouzias等［7］对Needell所提出的期望解误差的上界进行了改进。

影响随机Kaczmarz方法收敛速率的关键在于其中所蕴含的用于选取每步迭代所需调用的系数矩阵行的概率准则。为了提高随机Kaczmarz方法的收敛速率，Bai等［8-9］提出了一个可以获取每步迭代中残向量的模较大分量的概率准则，并基于该概率准则构造出了贪婪随机Kaczmarz方法。当初始迭代向量在A*的列空间时，贪婪随机Kaczmarz方法所产生的迭代序列收敛到线性代数方程组（1）的最小范数解x⋆=A†b且具有期望线性收敛速率

当线性代数方程组（1）的右端向量b被加上一个不为零的扰动向量r∈Cm时，实际求解的线性代数方程组问题将变为