×

A survey of Shanks’ extrapolation methods and their applications. (English. Russian original) Zbl 1469.65011

Comput. Math. Math. Phys. 61, No. 5, 699-718 (2021); translation from Zh. Vychisl. Mat. Mat. Fiz. 61, No. 5, 723-743 (2021).
Summary: When a sequence or a series of scalars, vectors, matrices, tensors, is converging slowly to its limit, it can be transformed, by a sequence transformation, into a new sequence or a set of new sequences, which under some assumptions converges faster to the same limit. Such a transformation can even be applied to diverging sequences or series, thus providing its analytic continuation. Shanks’ transformation is a well known sequence transformation for accelerating the convergence of scalar sequences. In this survey, we explain its development, its various extensions, and its implementation. Several applications illustrate its effectiveness.

MSC:

65B10 Numerical summation of series
40A05 Convergence and divergence of series and sequences

Software:

SparseMatrix; EPSfun
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brezinski, C.; Redivo-Zaglia, M., Extrapolation Methods: Theory and Practice (1991), Amsterdam: North-Holland, Amsterdam · Zbl 0744.65004
[2] Delahaye, J. P., Sequence Transformations (1988), Berlin: Springer-Verlag, Berlin · Zbl 0652.65004 · doi:10.1007/978-3-642-61347-0
[3] G. I. Marchuk and, V. V. Shaidurov, Difference Methods and Their Extrapolations (1983), New York: Springer-Verlag, New York · Zbl 0511.65076 · doi:10.1007/978-1-4613-8224-9
[4] Sidi, A., Practical Extrapolation Methods: Theory and Applications (2003), Cambridge: Cambridge Univ. Press, Cambridge · Zbl 1041.65001 · doi:10.1017/CBO9780511546815
[5] Sidi, A., Vector Extrapolation Methods with Applications (2017), Philadelphia: SIAM, Philadelphia · Zbl 1383.65002 · doi:10.1137/1.9781611974966
[6] Weniger, E. J., Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series, Comput. Phys. Rep., 10, 189-371 (1989) · doi:10.1016/0167-7977(89)90011-7
[7] Wimp, J., Sequence Transformations and Their Applications (1981), New York: Academic, New York · Zbl 0566.47018
[8] Shanks, D., Nonlinear transformations of divergent and slowly convergent sequences, J. Math. Phys., 34, 1-42 (1955) · Zbl 0067.28602 · doi:10.1002/sapm19553411
[9] Graves-Morris, P. R.; Jenkins, C. D., Vector-valued rational interpolants III, Constr. Approx., 2, 263-289 (1986) · Zbl 0614.41016 · doi:10.1007/BF01893432
[10] D. Shanks, An Analogy between Transient and Mathematical Sequences and Some Nonlinear Sequence-to-Sequence Transforms Suggested by It (Naval Ordnance Laboratory, White Oak, 1949), Part I.
[11] Brezinski, C.; Crouzeix, M., Remarques sur le procédé \({{\Delta }^2}\), C. R. Acad. Sci. Paris A, 270, 896-898 (1970) · Zbl 0193.12101
[12] Brezinski, C.; Redivo-Zaglia, M., The genesis and early developments of Aitken’s process, Shanks’ transformation, the \(\varepsilon \), Numer. Algorithms, 80, 11-133 (2019) · Zbl 1477.65011 · doi:10.1007/s11075-018-0567-2
[13] Wynn, P., On a device for computing the \({{e}_m}({{S}_n})\), Math. Tables Aids Comput., 10, 91-96 (1956) · Zbl 0074.04601 · doi:10.2307/2002183
[14] Wynn, P., Singular rules for certain nonlinear algorithms, BIT, 3, 175-195 (1963) · Zbl 0123.11101 · doi:10.1007/BF01939985
[15] Baker, G. A.; Graves-Morris, P. R., Padé Approximants (1996), Cambridge: Cambridge University Press, Cambridge · Zbl 0923.41001 · doi:10.1017/CBO9780511530074
[16] Wynn, P., Acceleration techniques for iterated vector and matrix problems, Math. Comput., 16, 301-322 (1962) · Zbl 0105.10302 · doi:10.1090/S0025-5718-1962-0145647-X
[17] Salam, A., Non-commutative extrapolation algorithms, Numer. Algorithms, 7, 225-251 (1994) · Zbl 0812.65003 · doi:10.1007/BF02140685
[18] Brezinski, C.; Redivo-Zaglia, M., Matrix Shanks transformations, Electron. J. Linear Algebra, 35, 248-265 (2019) · Zbl 1431.65002 · doi:10.13001/1081-3810.3925
[19] P. R. Graves-Morris and C. D. Jenkins, “Generalized inverse vector-valued rational interpolation,” in Padé Approximation and Its Applications, Ed. by H. Werner and H. J. Bünger, Lecture Notes in Mathematics (Springer, Berlin, 1984), Vol. 1071, pp. 144-156. · Zbl 0538.41006
[20] McLeod, J. B., A note on the \(\varepsilon \), Computing, 7, 17-24 (1971) · Zbl 0219.65094 · doi:10.1007/BF02279938
[21] Artin, E., Geometric Algebra (1966), New York: Interscience, New York · Zbl 0642.51001
[22] Porteous, I. R., Topological Geometry (1981), Cambridge: Cambridge Univ. Press, Cambridge · Zbl 0446.15001 · doi:10.1017/CBO9780511623943
[23] Salam, A., An algebraic approach to the vector \(\varepsilon \), Numer. Algorithms, 11, 327-337 (1996) · Zbl 0852.65004 · doi:10.1007/BF02142505
[24] Brezinski, C., Généralisation de la transformation de Shanks, de la table de Padé et de l’\( \varepsilon \), Calcolo, 12, 317-360 (1975) · Zbl 0329.65006 · doi:10.1007/BF02575753
[25] Brezinski, C.; Redivo-Zaglia, M., The simplified topological \(\varepsilon \), SIAM J. Sci. Comput. A, 36, 2227-2247 (2014) · Zbl 1308.65006 · doi:10.1137/140957044
[26] Brezinski, C.; Redivo-Zaglia, M., The simplified topological \(\varepsilon \), Numer. Algorithms, 74, 1237-1260 (2017) · Zbl 1362.65004 · doi:10.1007/s11075-016-0238-0
[27] K. Jbilou, Thèse de 3ème cycle (Université des Sciences et Techniques de Lille, Lille, 1988).
[28] Jbilou, K.; Sadok, H., Some results about vector extrapolation methods and related fixed point iteration, J. Comput. Appl. Math., 36, 385-398 (1991) · Zbl 0746.65006 · doi:10.1016/0377-0427(91)90018-F
[29] Cabay, S.; Jackson, L. W., A polynomial extrapolation method for finding limits and antilimits of vector sequences, SIAM J. Numer. Anal., 13, 734-752 (1976) · Zbl 0359.65029 · doi:10.1137/0713060
[30] Kaniel, S.; Stein, J., Least-square acceleration of iterative methods for linear equations, J. Optim. Theory Appl., 14, 431-437 (1974) · Zbl 0272.65022 · doi:10.1007/BF00933309
[31] Mešina, M., Convergence acceleration for the iterative solution of the equations X = AX + f, Comput. Methods Appl. Mech. Eng., 10, 165-173 (1977) · Zbl 0344.65019 · doi:10.1016/0045-7825(77)90004-4
[32] Brezinski, C.; Redivo-Zaglia, M.; Saad, Y., Shanks sequence transformations and Anderson acceleration, SIAM Rev., 60, 646-669 (2018) · Zbl 1395.65001 · doi:10.1137/17M1120725
[33] C. Brezinski and M. Redivo-Zaglia, “EPSfun: A Matlab toolbox for the simplified topological \(\varepsilon \)-algorithm,” Netlib (2017), na44 package. http://www.netlib.org/numeralgo. · Zbl 1362.65004
[34] Le Ferrand, H., The quadratic convergence of the topological epsilon algorithm for systems of nonlinear equations, Numer. Algorithms, 3, 273-284 (1992) · Zbl 0787.65029 · doi:10.1007/BF02141936
[35] Steffensen, J. F., Remarks on iteration, Scand. Actuarial J., 1933, 64-72 (1933) · Zbl 0007.02601 · doi:10.1080/03461238.1933.10419209
[36] Sidi, A., A convergence study for reduced rank extrapolation on nonlinear systems, Numer. Algorithms, 84, 957-982 (2020) · Zbl 1442.65098 · doi:10.1007/s11075-019-00788-6
[37] Wynn, P., Gertrude Blanch Anniversary Volume (1967)
[38] Guilpin, C.; Gacougnolle, J.; Simon, Y., The \(\varepsilon \), Appl. Numer. Math., 48, 27-40 (2004) · Zbl 1036.65003 · doi:10.1016/S0168-9274(03)00104-1
[39] Brezinski, C., Extrapolation algorithms for filtering series of functions, and treating the Gibbs phenomenon, Numer. Algorithms, 36, 309-329 (2004) · Zbl 1071.42003 · doi:10.1007/s11075-004-2843-6
[40] Kaczmarz, S., Angenäherte Auflösung von Systemen linearer Gleichungen, Bull. Acad. Polon. Sci. A, 35, 355-357 (1937) · JFM 63.0524.02
[41] Gastinel, N., Linear Numerical Analysis (1970), New York: Academic, New York · Zbl 0221.65003
[42] Brezinski, C.; Redivo-Zaglia, M., Convergence acceleration of Kaczmarz’s method, J. Eng. Math., 93, 3-19 (2015) · Zbl 1360.65098 · doi:10.1007/s10665-013-9656-3
[43] Brezinski, C.; Redivo-Zaglia, M., Extrapolation methods for the numerical solution of nonlinear Fredholm integral equations, J. Integral Equations Appl., 31, 29-57 (2019) · Zbl 1416.65013 · doi:10.1216/JIE-2019-31-1-29
[44] Jbilou, K.; Sadok, H., Vector extrapolation methods: Applications and numerical comparison, J. Comput. Appl. Math., 122, 149-165 (2000) · Zbl 0974.65034 · doi:10.1016/S0377-0427(00)00357-5
[45] L.-H. Lim, “Singular values and eigenvalues of tensors: A variational approach,” in Proceedings of the 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (2005), pp. 129-132.
[46] Gautier, A.; Tudisco, F.; Hein, M., The Perron-Frobenius theorem for multi-homogeneous mappings, SIAM J. Matrix Anal. Appl., 40, 1179-1205 (2019) · Zbl 07122458 · doi:10.1137/18M1165037
[47] Davis, T. A.; Yifan, H., The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38, 1-25 (2011) · Zbl 1365.65123
[48] Cipolla, S.; Redivo-Zaglia, M.; Tudisco, F., Shifted and extrapolated power methods for tensor \({{\ell }^p}\), Electron. Trans. Numer. Anal., 53, 1-27 (2020) · Zbl 1433.65049 · doi:10.1553/etna_vol53s1
[49] Gleich, D. F.; Lim, L. H.; Yu, Y., Multilinear PageRank, SIAM J. Matrix Anal. Appl., 36, 1507-1541 (2015) · Zbl 1330.15029 · doi:10.1137/140985160
[50] Cipolla, S.; Redivo-Zaglia, M.; Tudisco, F., Extrapolation methods for fixed-point multilinear PageRank computations, Numer. Linear. Algebra. Appl., 27, e2280 (2020) · Zbl 1488.65106 · doi:10.1002/nla.2280
[51] Kolda, T. G.; Mayo, J. R., Shifted power method for computing tensor eigenpairs, SIAM J. Matrix Anal. Appl., 32, 1095-1124 (2011) · Zbl 1247.65048 · doi:10.1137/100801482
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.