Multistep 𝜖–algorithm, Shanks’ transformation, and the Lotka–Volterra system by Hirota’s method

Brezinski, Claude; He, Yi; Hu, Xing-Biao; Redivo-Zaglia, Michela; Sun, Jian-Qing

doi:10.1090/S0025-5718-2011-02554-8

Multistep $\varepsilon$–algorithm, Shanks’ transformation, and the Lotka–Volterra system by Hirota’s method
HTML articles powered by AMS MathViewer

by Claude Brezinski, Yi He, Xing-Biao Hu, Michela Redivo-Zaglia and Jian-Qing Sun PDF

Math. Comp. 81 (2012), 1527-1549 Request permission

Abstract:

In this paper, we propose a multistep extension of the Shanks sequence transformation. It is defined as a ratio of determinants. Then, we show that this transformation can be recursively implemented by a multistep extension of the $\varepsilon$–algorithm of Wynn. Some of their properties are specified. Thereafter, the multistep $\varepsilon$–algorithm and the multistep Shanks transformation are proved to be related to an extended discrete Lotka–Volterra system. These results are obtained by using Hirota’s bilinear method, a procedure quite useful in the solution of nonlinear partial differential and difference equations.

References

A.C. Atiken, Determinants and Matrices, Oliver and Boyd, Edinburgh, 1939. MR 0000217
M.D. Benchiboun, Étude de Certaines Généralisations du $\Delta ^2$ d’Aitken et Comparaison de Procédés d’Accélération de la Convergence, Thèse de 3ème Cycle, Université des Sciences et Techniques de Lille, 1987.
C. Brezinski, Méthodes d’Accélération de la Convergence en Analyse Numérique, Thèse d’État, Université Scientifique et Médicale de Grenoble, 1971.
Claude Brezinski, Accélération de suites à convergence logarithmique, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A727–A730 (French). MR 305544
Claude Brezinski, Conditions d’application et de convergence de procédés d’extrapolation, Numer. Math. 20 (1972/73), 64–79 (French, with English summary). MR 378341, DOI 10.1007/BF01436643
C. Brezinski, A general extrapolation algorithm, Numer. Math. 35 (1980), no. 2, 175–187. MR 585245, DOI 10.1007/BF01396314
Claude Brezinski, Quasi-linear extrapolation processes, Numerical mathematics, Singapore 1988, Internat. Schriftenreihe Numer. Math., vol. 86, Birkhäuser, Basel, 1988, pp. 61–78. MR 1022946, DOI 10.1007/978-3-0348-6303-2_{5}
Claude Brezinski, Biorthogonality and its applications to numerical analysis, Monographs and Textbooks in Pure and Applied Mathematics, vol. 156, Marcel Dekker, Inc., New York, 1992. MR 1151616
C. Brezinski, Cross rules and non-abelian lattice equations for the discrete and confluent non-scalar $\epsilon$-algorithms, J. Phys. A 43 (2010), no. 20, 205201, 11. MR 2639912, DOI 10.1088/1751-8113/43/20/205201
C. Brezinski, Y. He, X.–B. Hu, J.–Q. Sun, H.–W. Tam, Confluent form of the multistep $\varepsilon$-algorithm, and the relevant integrable system, Stud. Appl. Math., 127 (2011), 191–209. DOI:10.1111/j.1467-9590.2011.00518.x
Claude Brezinski and Michela Redivo Zaglia, Extrapolation methods, Studies in Computational Mathematics, vol. 2, North-Holland Publishing Co., Amsterdam, 1991. Theory and practice; With 1 IBM-PC floppy disk (5.25 inch). MR 1140920
C. Carstensen, On a general epsilon algorithm, Numerical and applied mathematics, Part II (Paris, 1988) IMACS Ann. Comput. Appl. Math., vol. 1, Baltzer, Basel, 1989, pp. 437–441. MR 1066038
William F. Ford and Avram Sidi, An algorithm for a generalization of the Richardson extrapolation process, SIAM J. Numer. Anal. 24 (1987), no. 5, 1212–1232. MR 909075, DOI 10.1137/0724080
T. Hȧvie, Generalized Neville type extrapolation schemes, BIT 19 (1979), no. 2, 204–213. MR 537780, DOI 10.1007/BF01930850
Y. He, X.–B. Hu, J.–Q. Sun, E.J. Weniger, Convergence acceleration algorithm via an equation related to Boussinesq equation, SIAM J. Sci. Comput., 33 (2011), 1234–1245.
Yi He, Xing-Biao Hu, and Hon-Wah Tam, A $q$-difference version of the $\epsilon$-algorithm, J. Phys. A 42 (2009), no. 9, 095202, 9. MR 2525530, DOI 10.1088/1751-8113/42/9/095202
Y. He, X.–B. Hu, H.–W. Tam, S. Tsujimoto, Convergence acceleration algorithms related to a general $E$–transformation and its particular cases, submitted to Japan J. Indust. Appl. Math.
Ryogo Hirota, The direct method in soliton theory, Cambridge Tracts in Mathematics, vol. 155, Cambridge University Press, Cambridge, 2004. Translated from the 1992 Japanese original and edited by Atsushi Nagai, Jon Nimmo and Claire Gilson; With a foreword by Jarmo Hietarinta and Nimmo. MR 2085332, DOI 10.1017/CBO9780511543043
Xing-Biao Hu and R. K. Bullough, Bäcklund transformation and nonlinear superposition formula for an extended Lotka-Volterra equation, J. Phys. A 30 (1997), no. 10, 3635–3641. MR 1457967, DOI 10.1088/0305-4470/30/10/034
Masashi Iwasaki and Yoshimasa Nakamura, On the convergence of a solution of the discrete Lotka-Volterra system, Inverse Problems 18 (2002), no. 6, 1569–1578. MR 1955905, DOI 10.1088/0266-5611/18/6/309
Masashi Iwasaki and Yoshimasa Nakamura, An application of the discrete Lotka-Volterra system with variable step-size to singular value computation, Inverse Problems 20 (2004), no. 2, 553–563. MR 2065439, DOI 10.1088/0266-5611/20/2/015
Ana C. Matos and Marc Prévost, Acceleration property for the columns of the $E$-algorithm, Numer. Algorithms 2 (1992), no. 3-4, 393–408. MR 1184823, DOI 10.1007/BF02139476
Günter Meinardus and G. D. Taylor, Lower estimates for the error of best uniform approximation, J. Approximation Theory 16 (1976), no. 2, 150–161. MR 399720, DOI 10.1016/0021-9045(76)90044-7
Yukitaka Minesaki and Yoshimasa Nakamura, The discrete relativistic Toda molecule equation and a Padé approximation algorithm, Numer. Algorithms 27 (2001), no. 3, 219–235. MR 1858990, DOI 10.1023/A:1011897724524
A. Nagai and J. Satsuma, Discrete soliton equations and convergence acceleration algorithms, Phys. Lett. A 209 (1995), no. 5-6, 305–312. MR 1368590, DOI 10.1016/0375-9601(95)00865-9
Atsushi Nagai, Tetsuji Tokihiro, and Junkichi Satsuma, The Toda molecule equation and the $\epsilon$-algorithm, Math. Comp. 67 (1998), no. 224, 1565–1575. MR 1484902, DOI 10.1090/S0025-5718-98-00987-9
Y. Nakamura, ed., Applied Integrable Systems (in Japanese), Syokabo, Tokyo, 2000.
Yoshimasa Nakamura, Calculating Laplace transforms in terms of the Toda molecule, SIAM J. Sci. Comput. 20 (1998), no. 1, 306–317. MR 1639142, DOI 10.1137/S106482759631408X
Kazuaki Narita, Soliton solution to extended Volterra equation, J. Phys. Soc. Japan 51 (1982), no. 5, 1682–1685. MR 668131, DOI 10.1143/JPSJ.51.1682
Frank W. Nijhoff, Discrete Painlevé equations and symmetry reduction on the lattice, Discrete integrable geometry and physics (Vienna, 1996) Oxford Lecture Ser. Math. Appl., vol. 16, Oxford Univ. Press, New York, 1999, pp. 209–234. MR 1676599
F. W. Nijhoff, V. G. Papageorgiou, H. W. Capel, and G. R. W. Quispel, The lattice Gel′fand-Dikiĭ hierarchy, Inverse Problems 8 (1992), no. 4, 597–621. MR 1178232
V. Papageorgiou, B. Grammaticos, and A. Ramani, Integrable lattices and convergence acceleration algorithms, Phys. Lett. A 179 (1993), no. 2, 111–115. MR 1230809, DOI 10.1016/0375-9601(93)90658-M
V. Papageorgiou, B. Grammaticos, and A. Ramani, Integrable difference equations and numerical analysis algorithms, Symmetries and integrability of difference equations (Estérel, PQ, 1994) CRM Proc. Lecture Notes, vol. 9, Amer. Math. Soc., Providence, RI, 1996, pp. 269–280. MR 1416845, DOI 10.1090/crmp/009/25
A. Salam, Extrapolation: Extension et Nouveaux Résultats, Thèse, Université des Sciences et Technologies de Lille, 1993.
A. Salam, On a generalization of the $\epsilon$-algorithm, J. Comput. Appl. Math. 46 (1993), no. 3, 455–464. MR 1223011, DOI 10.1016/0377-0427(93)90041-9
Claus Schneider, Vereinfachte Rekursionen zur Richardson-Extrapolation in Spezialfällen, Numer. Math. 24 (1975), no. 2, 177–184 (German, with English summary). MR 378342, DOI 10.1007/BF01400966
D. Shanks, An analogy between transient and mathematical sequences and some nonlinear sequence–to–sequence transforms suggested by it. Part I, Memorandum 9994, Naval Ordnance Laboratory, White Oak, July 1949.
Daniel Shanks, Non-linear transformations of divergent and slowly convergent sequences, J. Math. and Phys. 34 (1955), 1–42. MR 68901, DOI 10.1002/sapm19553411
Avram Sidi, Practical extrapolation methods, Cambridge Monographs on Applied and Computational Mathematics, vol. 10, Cambridge University Press, Cambridge, 2003. Theory and applications. MR 1994507, DOI 10.1017/CBO9780511546815
W. W. Symes, The $QR$ algorithm and scattering for the finite nonperiodic Toda lattice, Phys. D 4 (1981/82), no. 2, 275–280. MR 653781, DOI 10.1016/0167-2789(82)90069-0
Satoshi Tsujimoto, Yoshimasa Nakamura, and Masashi Iwasaki, The discrete Lotka-Volterra system computes singular values, Inverse Problems 17 (2001), no. 1, 53–58. MR 1818491, DOI 10.1088/0266-5611/17/1/305
Robert Vein and Paul Dale, Determinants and their applications in mathematical physics, Applied Mathematical Sciences, vol. 134, Springer-Verlag, New York, 1999. MR 1654469
Guido Walz, Asymptotics and extrapolation, Mathematical Research, vol. 88, Akademie Verlag, Berlin, 1996. MR 1386191
E.J. Weniger, Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series, Comp. Phys. Reports, 10 (1989) 189–371.
Jet Wimp, Sequence transformations and their applications, Mathematics in Science and Engineering, vol. 154, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1981. MR 615250
P. Wynn, On a device for computing the $e_m(S_n)$ tranformation, Math. Tables Aids Comput. 10 (1956), 91–96. MR 84056, DOI 10.1090/S0025-5718-1956-0084056-6
P. Wynn, On a procrustean technique for the numerical transformation of slowly convergent sequences and series, Proc. Cambridge Philos. Soc. 52 (1956), 663–671. MR 81979
P. Wynn, Acceleration techniques in numerical analysis, with particular references to problems in one independent variable, in Proc. IFIP Congress 62, Munich, 27 Aug.-1 Sept. 1962, C.M. Popplewell ed., North–Holland, Amsterdam, 1962, pp. 149–156.
P. Wynn, An arsenal of Algol procedures for the evaluation of continued fractions and for effecting the epsilon algorithm, Rev. Française Traitement Information Chiffres 9 (1966), 327–362 (English, with French summary). MR 203963
P. Wynn, Upon systems of recursions which obtain among the quotients of the Padé table, Numer. Math. 8 (1966), 264–269. MR 215499, DOI 10.1007/BF02162562