求解大规模线性方程组快速随机Kaczmarz方法理论与应用研究
发布时间：2020-12-04 23:34
Kaczmarz方法是求解大规模线性方程组的一种常用迭代方法.该方法在信号处理,图像处理等领域得到了广泛的应用.经典的Kaczmarz方法通过循环遍历系数矩阵的行,在每次迭代时将当前点投影到由工作行形成的超平面上.但是,由于遍历矩阵的行的工作量很大,Kaczmarz方法在实际中往往运行很慢.随机Kaczmarz方法的出现大大提高了Kaczmarz方法效率.随机Kaczmarz方法的一个明显的缺点是它选择系数矩阵中工作行的概率准则存在失效的情况.最近Bai和Wu提出了一个新的概率准则,该准则在每个迭代步骤中尽可能地捕获残差向量较大分量对应的行,并由此提出了一种贪婪随机Kaczmarz方法（GRK）.然而,贪婪随机Kaczmarz方法在矩阵规模较大时,工作量非常大,不适于大数据问题的求解.本文的主要贡献如下:第一、我们从概率显著性的角度出发,提出了一种部分随机Kaczmarz方法,它可以降低贪婪随机Kaczmarz方法所需的计算成本,并建立了收敛性结果.第二、基于Chebyshev大数定律和Z-检验,我们将简单随机抽样方法应用于部分随机Kaczmarz方法,提出了新算法,并证明了其收敛性....
【文章来源】：中国矿业大学江苏省 211工程院校 教育部直属院校
【文章页数】：51 页
【学位级别】：硕士
【部分图文】：
–1算法3的收敛曲线
硕士学位论文(a)t=2(b)t=4(c)t=8(d)t=16图2–2算法3中工作行的概率Figure2–2ProbabilitiesoftheworkingrowsinAlgorithm3图2–2为算法3(第一次迭代)各行的概率在t=2,4,8,16时的情况.系数矩阵与图2–1是同一矩阵.在图2–1中,我们绘制算法3的收敛曲线.可以看出,算法在较大t时收敛更快.我们在图2–2中绘制了算法3(第一次迭代)对于不同参数t=2,4,8,16时的工作行的对应概率.可以看出,随着t的增加,具有较大概率的行变得更容易被选取到.因此,自然的想法是在算法3中设置t→∞.根据(2.19),选择第ik行的概率可以表示为如下形式:|r(ik)|‖A(ik)‖2=b(ik)A(ik)xkA(ik)2=max1≤j≤mb(jk)A(jk)xkA(jk)2(2.20)显然,此时选择到工作行的概率(几乎)为1.因此,我们有了以下算法:12
硕士学位论文=‖xkx‖221±εkm1‖rk‖221±εkm1∑mjk=1,jk=jk1‖Ajk‖22≤‖xkx‖22(1εk)λmin(AHA)(1+εk)γ‖xkx‖22=1(1εk)‖A‖2F(1+εk)γκ(A)2‖xkx‖22.(2.37)由(2.27),类似的,存在0≤εk1,εk11,并满足下式Ek1‖xkx‖22=‖xk1x‖221±εk1m1r2(ik1)1±εk1m1∑mjk1=1,jk1=jk2‖A‖2FA(jk1)22≤‖xk1x‖22(1εk1)λmin(AHA)(1+εk1)ξ‖xk1x‖22=1(1εk1)‖A‖2F(1+εk1)ξκ(A)2‖xk1x‖22.(2.38)从式(2.37)和(2.38),我们得到以下关于算法收敛性的定理5.定理2.10.根据以上假设和符号,算法5收敛到x的收敛率期望为:E‖xk+1x‖22≤1(1εk)‖A‖2F(1+εk)γκ(A)21(1εk1)‖A‖2F(1+εk1)ξκ(A)2‖xk1x‖22.由定理2.10和定理2.7可以看出算法5的收敛速度可能稍慢于算法4,即前者可能比后者的迭代次数更多.这是因为算法5每次只选取到矩阵的的少数行进行计算.我们对算法5赋予不同的采样率与贪婪方法以及算法4进行了数值实验,实验结果如下图:图2–3算法5(选择不的同参数η)与GRK算法的收敛曲线Figure2–3ConvergencecurvesofAlgorithm5(withdifferentη)andGRK18
本文编号：2898438
【文章来源】：中国矿业大学江苏省 211工程院校 教育部直属院校
【文章页数】：51 页
【学位级别】：硕士
【部分图文】：
–1算法3的收敛曲线
硕士学位论文(a)t=2(b)t=4(c)t=8(d)t=16图2–2算法3中工作行的概率Figure2–2ProbabilitiesoftheworkingrowsinAlgorithm3图2–2为算法3(第一次迭代)各行的概率在t=2,4,8,16时的情况.系数矩阵与图2–1是同一矩阵.在图2–1中,我们绘制算法3的收敛曲线.可以看出,算法在较大t时收敛更快.我们在图2–2中绘制了算法3(第一次迭代)对于不同参数t=2,4,8,16时的工作行的对应概率.可以看出,随着t的增加,具有较大概率的行变得更容易被选取到.因此,自然的想法是在算法3中设置t→∞.根据(2.19),选择第ik行的概率可以表示为如下形式:|r(ik)|‖A(ik)‖2=b(ik)A(ik)xkA(ik)2=max1≤j≤mb(jk)A(jk)xkA(jk)2(2.20)显然,此时选择到工作行的概率(几乎)为1.因此,我们有了以下算法:12
硕士学位论文=‖xkx‖221±εkm1‖rk‖221±εkm1∑mjk=1,jk=jk1‖Ajk‖22≤‖xkx‖22(1εk)λmin(AHA)(1+εk)γ‖xkx‖22=1(1εk)‖A‖2F(1+εk)γκ(A)2‖xkx‖22.(2.37)由(2.27),类似的,存在0≤εk1,εk11,并满足下式Ek1‖xkx‖22=‖xk1x‖221±εk1m1r2(ik1)1±εk1m1∑mjk1=1,jk1=jk2‖A‖2FA(jk1)22≤‖xk1x‖22(1εk1)λmin(AHA)(1+εk1)ξ‖xk1x‖22=1(1εk1)‖A‖2F(1+εk1)ξκ(A)2‖xk1x‖22.(2.38)从式(2.37)和(2.38),我们得到以下关于算法收敛性的定理5.定理2.10.根据以上假设和符号,算法5收敛到x的收敛率期望为:E‖xk+1x‖22≤1(1εk)‖A‖2F(1+εk)γκ(A)21(1εk1)‖A‖2F(1+εk1)ξκ(A)2‖xk1x‖22.由定理2.10和定理2.7可以看出算法5的收敛速度可能稍慢于算法4,即前者可能比后者的迭代次数更多.这是因为算法5每次只选取到矩阵的的少数行进行计算.我们对算法5赋予不同的采样率与贪婪方法以及算法4进行了数值实验,实验结果如下图:图2–3算法5(选择不的同参数η)与GRK算法的收敛曲线Figure2–3ConvergencecurvesofAlgorithm5(withdifferentη)andGRK18
本文编号：2898438
本文链接：https://www.wllwen.com/shoufeilunwen/benkebiyelunwen/2898438.html
