一类Krylov子空间方法的加速算法研究

发布时间：2020-06-18 21:15

【摘要】：在某些特殊情况下,Krylov子空间方法的残量下降曲线会出现不稳定的现象,如停滞现象,不规则振荡现象等,从而严重影响到Krylov子空间方法的收敛速度。本文以带多右端项的大规模稀疏线性系统为研究对象,针对上述不稳定问题提出两类用于求解对称正定线性系统的新型算法:带自适应重新启动过程的免中断块共轭梯度(Adaptive Restart procedures for the Breakdown-Free Block Conjugate Gradient,简称AR-BFBCG)算法,基于投影的收缩块共轭梯度(Projected variant of the Deflated Block Conjugate Gradient,简称PD-BCG)算法。详细的研究内容与主要成果如下:提出了一种自适应重启的AR-BFBCG方法。基于Powell在1977年针对共轭梯度算法提出的重新启动过程(后命名为:Powell’s restart),以及Dai等人于2004年在Powell’s restart基础上的工作,我们将这种重新启动过程推广并应用到求解带多右端项线性方程组的块共轭梯度(Block Conjugate Gradient,简称BCG)算法中。同时,结合Ji等人在2017年提出的免中断块共轭梯度(Breakdown-Free Block Conjugate Gradient,简称BFBCG)算法,提出AR-BFBCG方法用于求解带多右端项的对称正定线性系统。该方法继承了Powell’s restart的优点,可通过重启帮助消除BCG方法中出现的残差收敛行为不规则的现象,进而提高BCG的收敛速度。同时保留了BFBCG方法中免秩亏损的优点,可避免带重启的BCG方法在执行中可能会出现由秩亏损而导致的算法中断问题。数值试验表明,这类方法可有效“打破”残差收敛行为中的不规则现象,从而在一定程度上减少计算量,提高BFBCG算法的收敛速度。此外,在求解病态系统,或带秩亏损的多右端项线性系统时,该方法的数值优越性更加明显。设计了一种基于投影的PD-BCG方法。Chen在2011年提出收缩块共轭梯度(Deflated Block Conjugate Gradient,简称D-BCG)算法,该方法可通过收缩掉极端特征值(比如小特征值)来减小预处理矩阵的条件数,从而提高BCG算法收敛速度。但在有限精度算法(finite arithmetic)框架下,残差空间与收缩空间之间的正交性会随着算法的执行而逐渐丢失,而这种正交性的丢失会明显地影响算法的稳定性,导致残量下降曲线出现长时间停滞,甚至因正交性丢失过于严重而根本无法收敛。重正交(reorthogonalization)方法可用于修复这种丢失的正交性,但是其代价相当大。基于此,我们提出了PD-BCG算法来“延缓”这种正交性的丢失,并且理论表明这种“延缓”不需要任何额外代价,同时理论还表明PD-BCG与DBCG在数学上是等价的。最后数值实验表明,PD-BCG算法能够将这种正交性保持在一定程度内,进而有效解决了收敛停滞甚至不收敛的问题,验证了其有效性与数值稳定性。
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：O241.6

【相似文献】

相关期刊论文 前10条

1 王朝甫,方大纲;多层自适应共轭梯度方法及其在电磁问题中的应用[J];微波学报;1995年02期

2 曾维强;刘海林;;一种全局收敛的杂交谱共轭梯度方法[J];广东技术师范学院学报;2015年05期

3 朱志伟;一个新的共轭梯度类型方法[J];广西师范学院学报(自然科学版);2004年02期

4 陈卫军;金显华;;一种最大共轭梯度连续泛函的网络峰值预测[J];信阳师范学院学报(自然科学版);2015年02期

5 张昆;董浩;严加永;魏文博;吕庆田;;大地电磁场非线性共轭梯度三维反演[J];矿床地质;2012年S1期

6 蒲小丽;王丽平;;基于共轭梯度分解算法的电网谐波估计[J];计算机技术与发展;2013年02期

7 韩松,李建国;直接自适应调节的共轭梯度方法[J];哈尔滨师范大学自然科学学报;1999年02期

8 袁功林;李向荣;;一个新的解非线性对称方程组的非单调共轭梯度方法[J];广西科学;2009年02期

9 陈光源;雷卓;贺海靖;邓明;景建恩;;2.5维海洋非线性共轭梯度反演应用效果研究[J];海洋技术学报;2018年02期

10 张友兰;白素琴;;共轭梯度方法的应用[J];河北省科学院学报;1993年04期

相关会议论文 前10条

1 黎小圣;张国山;;区间分割共轭梯度混沌优化算法及其应用[A];第五届ABB杯全国自动化系统工程师论文大赛论文集[C];2011年

2 谷同祥;刘兴平;;预条件多搜索方向共轭梯度方法[A];中国工程物理研究院科技年报（2003）[C];2003年

3 靳一;李明玉;徐常志;杨光文;汪滴珠;杨丽;;星载自适应稀疏预失真技术研究[A];第四届高分辨率对地观测学术年会论文集[C];2017年

4 张昆;严加永;;一种大地电磁场非线性共轭梯度三维并行反演[A];第一届全国青年地质大会论文集[C];2013年

5 韩敏;郭伟;王金城;;径向基函数神经网络的全监督算法[A];中国仪器仪表学会第六届青年学术会议论文集[C];2004年

6 林楠;陈永良;路来君;;共轭梯度求解的Logistic回归模型与ROC曲线分析在矿产靶区预测中的应用[A];第十五届全国数学地质与地学信息学术研讨会论文集[C];2016年

7 毕竞;袁伟;;线性约束共轭梯度常模算法的研究[A];中国电子学会第十六届信息论学术年会论文集[C];2009年

8 黄敏超;张育林;陈启智;;共轭梯度反传算法及其在系统辨识中的应用[A];1995中国控制与决策学术年会论文集[C];1995年

9 张忠元;;一个共轭梯度方法全局收敛性的判别准则[A];第九届中国青年信息与管理学者大会论文集[C];2007年

10 李中华;魏鸣;肖艳姣;;关于单多普勒雷达资料的VVP反演方法的讨论[A];推进气象科技创新加快气象事业发展——中国气象学会2004年年会论文集（下册）[C];2004年

相关重要报纸文章 前1条

1 记者 朱华 通讯员 王握文 于冬阳 国文成;天河二号成世界超算双料冠军[N];长沙晚报;2014年

相关博士学位论文 前10条

1 李文钰;用于神经网络的带L_(1/2)正则项的共轭梯度学习方法[D];大连理工大学;2018年

2 马欢;电阻率法和激发极化法不同装置组合数据三维非线性共轭梯度反演并行算法研究[D];中国地质大学(北京);2015年

3 胡朝明;几类谱共轭梯度方法理论及数值行为研究[D];中南大学;2012年

4 张昆;改进的大地电磁场非线性共轭梯度三维反演及其并行计算研究[D];中国地质大学（北京）;2013年

5 姚胜伟;几类共轭梯度算法的研究[D];华东理工大学;2014年

6 林昌洪;大地电磁张量阻抗三维共轭梯度反演研究[D];中国地质大学（北京）;2009年

7 马明娟;一类共轭梯度方法及其收敛性[D];吉林大学;2009年

8 宛田宾;光散射断层成像技术的研究[D];中国科学技术大学;2007年

9 李艳灵;基于聚类的图像分割算法研究[D];华中科技大学;2009年

10 佟拓;海洋人工源频率域电磁法三维共轭梯度反演研究[D];中国地质大学（北京）;2012年

相关硕士学位论文 前10条

1 向燕菲;一类Krylov子空间方法的加速算法研究[D];电子科技大学;2019年

2 曾军平;AEMT干扰数据的压制及应用研究[D];东华理工大学;2019年

3 尹志益;基于修正共轭梯度迭代硬阈值的高效激光辐射对称性分析[D];广东工业大学;2018年

4 胡创业;大地电磁二维OCCAM-非线性共轭梯度反演研究[D];中国地质大学(北京);2016年

5 陈恩;WYL和HZ共轭梯度算法的改进和推广[D];重庆师范大学;2018年

6 刘奔;求解无约束优化问题的共轭梯度方法[D];重庆大学;2013年

7 蒲小丽;共轭梯度分解算法及其应用[D];南京航空航天大学;2012年

8 张杨;共轭梯度型方法的进一步研究与改进[D];重庆大学;2012年

9 王珏钰;非线性（无）约束问题的共轭梯度路径法[D];上海师范大学;2013年

10 崔曾如;基于最小二乘的三项共轭梯度方法[D];广西大学;2017年

本文编号：2719842