刘 永,,崔蓉蓉

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

对于大规模线性系统

式中:A∈Cm×n为复数域上的m×n矩阵;b∈Cm为复数域上的m维已知向量;x∈Cn为复数域上的n维未知向量.Kaczmarz(K)算法[1]是计算其逼近解的一种非常有效的迭代算法.K算法由于其简单且收敛速度快,故被广泛应用于图像重构[2-4]、信号处理[5]和分布式计算[6]等领域.K算法的迭代公式为

式中:(·)∗为矩阵或向量的共轭转置;‖·‖2为向量的Euclidean范数;A(ik)为矩阵A的第ik行;b(ik)为向量b的第ik个元素,ik=(k mod m)+1.从ik的选择方式可以看出,K算法的收敛速率依赖于矩阵A的行顺序,有时一个特定的行顺序可能会导致算法收敛非常慢[7-8].

为了提高K算法的收敛速率,Strohmer等[9]在2009年提出了随机Kaczmarz(randomized Kaczmarz,RK)算法,该算法依概率P(row=ik)=的大小随机选择系统(1)中系数矩阵A的某一行,并按迭代式(2)进行计算,其中表示矩阵A的Frobenius范数.Strohmer等还首次证明了当相容线性系统(1)中系数矩阵A为列满秩且m≥n,或行满秩且m≤n时,RK算法依期望指数收敛到系统(1)的唯一最小二乘解或唯一最小范数解,其收敛速率为

式中:x∗为系统(1)的解;λmin(A∗A)和tr(A∗A)分别为矩阵A∗A的最小非零特征值和迹.从RK算法的行选择方式可以看出,其收敛速率并不取决于方程的个数,甚至可以不需要知道整个方程组,只是通过随机选取整个方程组的一部分进行计算就可以得到系统(1)的解.因此,该算法就特别适用于规模比较大的系统,单从这点来看,RK算法优于K算法.但是RK算法中行的随机选择方式也……