线性和非线性方程组的加速贪婪Kaczmarz迭代算法

作     者：谭龙泽 

作者单位：华东师范大学 

学位级别：硕士

导师姓名：郭学萍

授予年度：2023年

学科分类：07[理学] 070102[理学-计算数学] 0701[理学-数学] 

主      题：线性方程组 线性最小二乘问题 非线性方程组 多步贪婪随机Kaczmarz方法 非线性贪婪随机Kaczmarz方法 加速贪婪Kaczmarz方法 

摘      要：科学与工程计算领域中的诸多实际问题,比如,结构分析、网络分析、数据分析、数据拟合和微分方程数值解等最终都可归结为线性或非线性方程组问题的求解.因此,研究求解这些问题的高效算法是非常有实际意义的.在前人工作的基础上我们提出了一系列高效求解此类问题的新方法,并给出了它们的收敛性定理.首先,基于贪婪随机Kaczmarz(GRK)方法的选取目标行的准则,针对求解相容的超定或欠定线性方程组我们提出了多步贪婪随机Kaczmarz(MGRK)方法和加速贪婪Kaczmarz(AGK)方法,并证明了它们能收敛到线性方程组的唯一最小范数解.数值实验表明MGRK方法优于GRK方法,且对于大型稠密的欠定线性方程组而言MGRK方法也优于最大加权残差Kaczmarz(MWRK)方法.数值实验也表明了AGK方法的数值性能优于GRK方法、MWRK方法和快速确定性块Kaczmarz(FDBK)方法.其次,基于贪婪随机坐标下降(GRCD)方法的选取目标列的准则,对于求解超定的线性最小二乘问题我们提出了多步贪婪随机坐标下降(MGRCD)法以及加速贪婪坐标下降(AGCD)法.对于系数矩阵列满秩的超定线性方程组,我们证明了这两个方法可以收敛到唯一最小二乘解.数值实验表明MGRCD方法和AGCD方法都优于最大距离坐标下降(AMDCD)方法和GRCD方法,且对于大型稀疏病态的线性方程组而言AGCD方法也优于CGLS算法和LSQR算法.再次,基于GRK方法的思想,我们提出了求解非线性方程组的非线性贪婪随机Kaczmarz(NGRK)方法和非线性松弛贪婪随机Kaczmarz(NRGRK)方法,并且分析了NGRK方法的收敛性.为了提高NGRK方法和NRGRK方法的计算效率,我们设计了多步非线性贪婪随机Kaczmarz(MNGRK)方法和加速非线性贪婪Kaczmarz(ANGK)方法,也给出了这两种方法的收敛性分析.此外,受到最大距离坐标下降(MDCD)法思想的启发,我们提出了非线性最大距离Kaczmarz(NMDK)方法,并证明了该方法的收敛性.为了进一步提高NMDK方法的收敛速度,我们提出了其加速版本,即加速非线性最大距离Kaczmarz(ANMDK)方法.数值实验表明ANGK方法和ANMDK方法比非线性Kaczmarz方法、非线性随机Kaczmarz方法和Gauss-Newton法更有效.最后,我们将AGK方法和AGCD方法作为非精确牛顿(IN)法的内迭代,提出了求解非线性方程组的Newton-AGK方法和Newton-AGCD方法.数值实验表明了这两种方法具有局部二次收敛性.与经典的IN方法相比,我们提出来的这两个非精确牛顿法还能求解超定的非线性方程组.