荆燕飞，李彩霞，胡少亮

（1.电子科技大学 数学科学学院，四川成都 611731；2.中国工程物理研究院 高性能数值模拟软件中心，北京 100088）

考虑求解具有如下形式的相容线性系统：

其中，系数矩阵A∈Rm×n(m＞n)可为满秩或秩亏矩阵，且b∈Rm。通常考虑求式（1）的最小范数解

当系数矩阵A为列满秩时，x*为式（1）的惟一解；当线性系统（1）有无穷多组解时，x*为式（1）的最小范数解（这里的范数指欧式范数）。

为求解线性系统（1），许多迭代方法［1-5］已被开发和进一步研究。其中，Kaczmarz［5］于1937年首次提出的Kaczmarz方法，因其成本低廉、易于操作而迅速得到数值计算领域的专家学者的认可和广泛关注，进而使其获得巨大的理论发展［6-9］。因其是一种具有代表性的行处理迭代方法且在计算机上易于实现和并行化，因此被广泛应用于计算机断层扫描［10-13］，图像重建［14-16］，分布式计算［17-18］和信号处理［19-21］等领域。

若以随机顺序而不是以给定顺序选用系数矩阵的行可以极大地提高Kaczmarz方法的收敛速度［13，16，21］。尽管这些随机选行的Kaczmarz方法在应用中颇具吸引力，但尚不能保证其收敛速率。Strohmer等［22］首次采用选取工作行的概率与其所对向量的欧式范数的平方成正比这样的选行准则，提出能保证收敛速率的随机Kaczmarz方法，并证明其误差的期望具有指数收敛速率。Dai等［23］通过求解最小化收敛速度的上限这个凸优化问题来获得选择行的最佳概率分布，提出最优的随机Kaczmarz方法；Bai等［24］结合贪婪和随机的数学思想引入一种有效的行选择准则提出贪婪随机Kaczmarz方法。此后，松弛贪婪随机Kaczmarz方法［25］和贪婪距离随机Kaczmarz方法［26］也被提出并深入研究。……