论文部分内容阅读
随机 Kaczmarz 算法(Randomized Kaczmarz Algorithm,RK)已经证明 了其在求解超定和欠定相容线性方程组问题中的有效性,并且其随机思想也已被广泛地推广和应用于其他算法中。但RK算法中按照正比于||ai(i=1,2,...,m)的概率随机选择矩阵A的行的随机选择方式并不一定是最优的。当||ai||22相等时,RK算法的优势就不明显了。首先,本文针对上述问题提出了新的随机Kaczmarz算法(New Randomized Kaczmarz Algorithm,NRK),该算法按照正比于当前迭代点到超平面距离的概率随机地选择矩阵A的行。理论分析证明当矩阵A的行范数相等时,该算法是依期望线性收敛的,且其收敛率至少与Strohmer和Vershynin的RK算法一致。数值实验不仅证实了上述结论,而且表明该算法的收敛速度明显快于RK算法。其次,本文还提出了 一种最大矫正Kaczmarz算法(Maxmial Correction Kaczmarz Algorithm,MCK),与Kaczmarz算法不同,该算法是将当前迭代点优先向距离最远的超平面投影,从而加快了收敛速度,并分别从理论和数值实验上证明和验证了其收敛性和有限终止性。同时也将最大矫正思想推广到求解非线性方程组中,提出了非线性最大矫正 Kaczmarz 算法(Nonlinear Maxmial Correction Kaczmarz Algorithm,NMCK)。为了减少有关计算雅可比矩阵的计算量,对NMCK算法进行了改进,提出了无矩阵的非线性最大残量矫正 Kaczmarz 算法(Nonlinear Maxmial Residual Correction Kaczmarz Algorithm,NMRCK),并通过数值实验证明在预优后上述非线性算法的有效性。