两类向量序列加速收敛方法比较

doi:10.12288/szjs.s2020-0704

数值计算与计算机应用 ›› 2021, Vol. 42 ›› Issue (4): 379-394.DOI: 10.12288/szjs.s2020-0704

• 论文 • 上一篇

两类向量序列加速收敛方法比较

秦子康¹, 安恒斌^2,3, 王新玉⁴

1. 中国工程物理研究院研究生院, 北京 100088;
2. 北京应用物理与计算数学研究所, 计算物理重点实验室, 北京 100094;
3. 中物院高性能数值模拟软件中心, 北京 100088;
4. 东北师范大学, 数学与统计学院, 长春 130024

收稿日期:2020-10-09 出版日期:2021-12-15 发布日期:2021-12-07
基金资助:
国家重点研发计划（2017YFA0603903）和国家自然科学基金（12171045，11671051）资助.

PDF ( 179 ) 引用

秦子康, 安恒斌, 王新玉. 两类向量序列加速收敛方法比较[J]. 数值计算与计算机应用, 2021, 42(4): 379-394.

Qin Zikang, An Hengbin, Wang Xinyu. COMPARISON OF TWO METHODS FOR ACCELERATING CONVERGENCE OF VECTOR SEQUENCES[J]. Journal on Numerica Methods and Computer Applications, 2021, 42(4): 379-394.

COMPARISON OF TWO METHODS FOR ACCELERATING CONVERGENCE OF VECTOR SEQUENCES

Qin Zikang¹, An Hengbin^2,3, Wang Xinyu⁴

1. Graduate School of CAEP, Beijing 100088, China;
2. Laboratory of Computational Physics, Institute of Applied Physics and Computational Mathematics, Beijing 100094, China;
3. CAEP Software Center for High Performance Numerical Simulation, Beijing 100088, China;
4. School of Mathematics and Statistics, Northeast Normal University, Changchun 130024, China

Received:2020-10-09 Online:2021-12-15 Published:2021-12-07

迭代方法是求解大规模线性和非线性问题的主要方法.由迭代方法产生的向量序列的收敛速度直接影响方法的应用效果.为了提高向量序列的收敛速度，可以采用向量序列的迭代加速算法.目前，针对向量序列加速收敛的算法主要包括两类：基于外插类的方法和基于Anderson加速的方法.外插类加速方法通过对于原序列进行变形，以获得新的向量序列，使新的向量序列的收敛速度比原序列更快.典型的外插类方法有最小多项式外插（MPE）方法，修正的最小多项式外插（MMPE）方法，降秩外插（RRE）方法，拓扑ε算法（TEA），向量ε算法（VEA）等.Anderson加速方法结合不动点迭代格式，利用迭代过程中残差序列的信息构造新的迭代序列.本文选取RRE方法作为外插类加速方法的代表，与Anderson加速方法进行比较，并重点通过几类典型应用进行测试和分析.结果表明，Anderson加速方法和RRE方法均可提高向量序列的收敛速度，并且Anderson加速方法比RRE方法更为稳定和有效.

关键词： 向量序列, 迭代加速, 不动点迭代, RRE, Anderson加速

The iterative algorithms are the main methods for solving large scale linear and nonlinear problems. The convergence rate of the vector sequences produced by an iterative method has direct influence on the application effectiveness. To improve the convergence rate of a vector sequence, an iterative acceleration algorithm may be employed. Currently, there are mainly two classes of iterative acceleration algorithms:One is the extrapolation methods and the other is Anderson acceleration method. In an extrapolation method, a new vector sequence is obtained by transforming the original vector sequence, such that the new vector sequence converges faster than the original sequence. The typical extrapolation algorithms include minimal polynomial extrapolation (MPE) algorithm, modified minimal polynomial extrapolation (MMPE) algorithm, reduced rank extrapolation (RRE) algorithm, topological ε-algorithm (TEA), and vector ε-algorithm (VEA). Anderson acceleration is designed for fixed point iteration, where the new sequence is constructed by employing the information of the history residual vectors. In this paper, RRE algorithm, which is chosen as a representative of the extrapolation algorithms, is compared with Anderson acceleration algorithm. The emphasis of the comparison is on the numerical tests and analysis for several typical applications. The results show that both of the algorithms can improve the convergence rate of the iterative sequence, and Anderson acceleration algorithm is more robust and efficient than RRE algorithm.

Key words: vector sequence, iterative acceleration, fixed point iteration, RRE, Anderson acceleration

MR(2010)主题分类:

65B05
65F10

分享此文:

[1] Bottou L, Curtis F E, Nocedal J. Optimization methods for large-scale machine learning[J]. SIAM Review, 2018, 60(2):223-311.
[2] Boyd S. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2010, 3(1):1-122.
[3] Smith D A, Ford W F, Sidi A. Extrapolation methods for vector sequences[J]. SIAM Review, 1987, 29(2):199-233.
[4] Eyert V. A comparative study on methods for convergence acceleration of iterative vector sequences[J]. Journal of Computational Physics, 1996, 124(2):271-285.
[5] Jbilou K, H. S. Vector extrapolation methods. applications and numerical comparison[J]. Journal of Computational and Applied Mathematics, 2000, 122:149-165.
[6] Brezinski C, Cipolla S, Redivo-Zaglia M, Saad Y. Shanks and Anderson-type acceleration techniques for systems of nonlinear equations[J]. arXiv e-prints, 2020.
[7] Cabay S, L.W. J. A polynomial extrapolation method for finding limits and antilimits of vector sequences[J]. SIAM Journal on Numerical Analysis, 1976, 13(5):734-752.
[8] Brezinski C. Generalisations de la transformation de shanks, de la table de Pade et de l'ǫ-algorithme[J]. Calcolo, 1975, 12(4):317-360.
[9] Pugachev B P. Acceleration of the convergence of iterative processes and a method of solving systems of non-linear equations[J]. Ussr Computational Mathematics and Mathematical Physics, 1977, 17(5):199-207.
[10] Sidi A, Ford W F, Smith D A. Acceleration of convergence of vector sequences[J]. SIAM Journal on Numerical Analysis, 1986, 23(1):178-196.
[11] Kaniel S, Stein J. Least-square acceleration of iterative methods for linear equations[J]. Journal of Optimization Theory and Applications, 1974, 14(4):431-437.
[12] Eddy R. Extrapolating to the limit of a vector sequence[M], pages 387-396. Academic Press, New York, 1979.
[13] Mešina M. Convergence acceleration for the iterative solution of the equations X=AX + f[J]. Computer Methods in Applied Mechanics and Engineering, 1977, 10(2):165-173.
[14] Brezinski C, Redivozaglia M, Saad Y. Shanks sequence transformations and Anderson acceleration[J]. SIAM Review, 2018, 60(3):646-669.
[15] Brezinski C, Redivozaglia M. The simplified topological ε-algorithms:software and applications[J]. Numerical Algorithms, 2017, 74(4):1-24.
[16] Brezinski C, Redivozaglia M. The simplified topological ε-algorithms for accelerating sequences in a vector space[J]. SIAM Journal on Scientific Computing, 2014, 36(5):A2227-A2247.
[17] Wynn P. Acceleration techniques for iterated vector and matrix problems[J]. Mathematics of Computation, 1962, 16(79):301-322.
[18] Roberts D E. The vector epsilon algorithm:a residual approach[J]. Numerical Algorithms, 2002, 29:209-227.
[19] Steele J A, Dolovich A T. Toward the kernel of the vector epsilon algorithm[J]. International Journal for Numerical Methods in Engineering, 2015, 48(5):721-730.
[20] Sidi A. Vector extrapolation methods with applications[M]. SIAM, Philadelphia, 2017.
[21] Sidi A. SVD-MPE:an SVD-based vector extrapolation method of polynomial type[J]. Applied Mathematics, 2016, 7:1260-1278.
[22] Sidi A. Minimal polynomial and reduced rank extrapolation methods are related[J]. Advances in Computational Mathematics, 2017, 43(1):151-170.
[23] Kong Q, Jing Y F, Huang T Z, An H B. Acceleration of the scheduled relaxation Jacobi method:promising strategies for solving large, sparse linear systems[J]. Journal of Computational Physics, 2019, 397:108862.
[24] Evans C, Pollock S, Rebholz L G, Xiao M. A proof that Anderson acceleration improves the convergence rate in linearly converging fixed point methods (but not in those converging quadratically)[J]. SIAM Journal on Numerical Analysis, 2020, 58(1):788-810.
[25] Fang H R, Saad Y. Two classes of multisecant methods for nonlinear acceleration[J]. Numerical Linear Algebra with Applications, 2010, 16(3):197-221.
[26] Potra F, Engler H. A characterization of the behavior of the Anderson acceleration on linear problems[J]. Linear Algebra and its Applications, 2013, 438(3):1002-1011.
[27] Toth A, Ellis J A, Evans T M, Hamilton S P, Kelley C T, Pawlowski R P, Slattery S R. Local improvement results for Anderson acceleration with inaccurate function evaluations[J]. SIAM Journal on Scientific Computing, 2017, 39(5):S47-S65.
[28] Toth A, Kelley C. Convergence analysis for Anderson acceleration[J]. SIAM Journal on Numerical Analysis, 2015, 53(2):805-819.
[29] Walker H F. Anderson acceleration:algorithms and implementations[R]. Research Report MS-6-15-50, Worcester Polytechnic Institute Mathematical Sciences Department, 2011.
[30] Sidi A. Extrapolation vs. projection methods for linear systems of equations[J]. Journal of Computational and Applied Mathematics, 1987, 22(1):71-88.
[31] Sidi A. Review of two vector extrapolation methods of polynomial type with applications to large-scale problems[J]. Journal of Computational Science, 2012, 3(3):92-101.
[32] Duminil S, Sadok H, Silvester D. Fast solvers for discretized Navier-Stokes problems using vector extrapolation[J]. Numerical Algorithms, 2014, 66:89-104.
[33] Jbilou K, Reihel L, Sadok H. Vector extrapolation enhanced TSVD for linear discrete ill-posed problems[J]. Numerical Algorithms, 2009, 51(2):195-208.
[34] Awasthi N, Kalva S K, Pramanik M, Yalavarthy P K. Vector extrapolation methods for accelerating iterative reconstruction methods in limited-data photoacoustic tomography[J]. Journal of Biomedical Optics, 2018, 23(7):1-11.
[35] Anderson D G. Iterative procedures for nonlinear integral equations[J]. Journal of Association for Computing Machinery, 1965, 12(4):547-560.
[36] Yunnan Y. Anderson acceleration for seismic inversion[J]. arXiv, 2020.
[37] Walker H F, Ni P. Anderson acceleration for fixed-point iterations[J]. SIAM Journal on Numerical Analysis, 2011, 49(4):1715-1735.
[38] An H, Jia X, Walker H F. Anderson acceleration and application to the three-temputure energy equations[J]. Journal of Computational Physics, 2017, 347:1-19.
[39] Geist M, Scherrer B. Anderson Acceleration for Reinforcement Learning[C]. In European Workshop on Reinforcement Learning 14, 2018.
[40] Pasini M L. Convergence analysis of Anderson-type acceleration of Richardson's iteration[J]. Linear Algebra and its Applications, 2019, 26(4):e2241.
[41] Sidi A. Efficient implementation of minimal polynomial and reduced rank extrapolation methods[J]. Journal of Computational and Applied Mathematics, 1991, 36:305-337.
[42] Brezinski C, Redivozaglia M. Generalizations of Aitken's process for accelerating the convergence of sequences[J]. Computational and Applied Mathematics, 2007, 26(2):171-189.
[43] Shi W, Song S, Wu H, Hsu Y C, Wu C, Huang G. Regularized Anderson acceleration for off-policy deep reinforcement learning[J]. arXiv, 2019.
[44] Chan T F, Mathew T P. Domain decomposition algorithms[J]. Acta Numerica, 1994, 3:61-143.
[45] Duminil S, Sadok H, Szyld D B. Nonlinear Schwarz iterations with reduced rank extrapolation[J]. Applied Numerical Mathematics, 2015, 94:209-221.

[1]	王现辉, 乔慧. 一类含奇异积分核的高振荡积分数值估计[J]. 数值计算与计算机应用, 2017, 38(3): 215-224.

阅读次数

全文

摘要

两类向量序列加速收敛方法比较

COMPARISON OF TWO METHODS FOR ACCELERATING CONVERGENCE OF VECTOR SEQUENCES

扫码分享