Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Multistep $\varepsilon$ -algorithm, Shanks' transformation, and the Lotka-Volterra system by Hirota's method

Authors: Claude Brezinski, Yi He, Xing-Biao Hu, Michela Redivo-Zaglia and Jian-Qing Sun
Journal: Math. Comp. 81 (2012), 1527-1549
MSC (2010): Primary 65B05, 39A14, 37K10
Posted: October 19, 2011
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

1. A.C. Aitken, Determinants and Matrices, Oliver and Boyd, Edinburgh, 1939. MR 0000217 (1,35a)
2. 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.
3. 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.
4. Claude Brezinski, Accélération de suites à convergence logarithmique, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A727–A730 (French). MR 0305544 (46 #4674)
5. 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 0378341 (51 #14509)
6. C. Brezinski, A general extrapolation algorithm, Numer. Math. 35 (1980), no. 2, 175–187. MR 585245 (81j:65015), http://dx.doi.org/10.1007/BF01396314
7. 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 (90k:65012)
8. 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 (92m:41001)
9. C. Brezinski, Cross rules and non-abelian lattice equations for the discrete and confluent non-scalar 𝜀-algorithms, J. Phys. A 43 (2010), no. 20, 205201, 11. MR 2639912 (2011d:65438), http://dx.doi.org/10.1088/1751-8113/43/20/205201
10. 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
11. 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 (93d:65001)
12. 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 (91g:65010)
13. 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 (89a:65006), http://dx.doi.org/10.1137/0724080
14. T. Hȧvie, Generalized Neville type extrapolation schemes, BIT 19 (1979), no. 2, 204–213. MR 537780 (80f:65005), http://dx.doi.org/10.1007/BF01930850
15. 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.
16. Yi He, Xing-Biao Hu, and Hon-Wah Tam, A 𝑞-difference version of the 𝜀-algorithm, J. Phys. A 42 (2009), no. 9, 095202, 9. MR 2525530 (2010j:37111), http://dx.doi.org/10.1088/1751-8113/42/9/095202
17. Y. He, X.-B. Hu, H.-W. Tam, S. Tsujimoto, Convergence acceleration algorithms related to a general -transformation and its particular cases, submitted to Japan J. Indust. Appl. Math.
18. 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 (2005f:37137)
19. 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 (98i:35159), http://dx.doi.org/10.1088/0305-4470/30/10/034
20. 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 (2004a:39031), http://dx.doi.org/10.1088/0266-5611/18/6/309
21. 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 (2005e:39046), http://dx.doi.org/10.1088/0266-5611/20/2/015
22. Ana C. Matos and Marc Prévost, Acceleration property for the columns of the 𝐸-algorithm, Numer. Algorithms 2 (1992), no. 3-4, 393–408. MR 1184823 (94b:65008), http://dx.doi.org/10.1007/BF02139476
23. 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 0399720 (53 #3562)
24. 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 (2002h:42054), http://dx.doi.org/10.1023/A:1011897724524
25. A. Nagai and J. Satsuma, Discrete soliton equations and convergence acceleration algorithms, Phys. Lett. A 209 (1995), no. 5-6, 305–312. MR 1368590 (96h:65006), http://dx.doi.org/10.1016/0375-9601(95)00865-9
26. Atsushi Nagai, Tetsuji Tokihiro, and Junkichi Satsuma, The Toda molecule equation and the 𝜀-algorithm, Math. Comp. 67 (1998), no. 224, 1565–1575. MR 1484902 (99d:65010), http://dx.doi.org/10.1090/S0025-5718-98-00987-9
27. Y. Nakamura, ed., Applied Integrable Systems (in Japanese), Syokabo, Tokyo, 2000.
28. Yoshimasa Nakamura, Calculating Laplace transforms in terms of the Toda molecule, SIAM J. Sci. Comput. 20 (1998), no. 1, 306–317 (electronic). MR 1639142 (2000i:65215), http://dx.doi.org/10.1137/S106482759631408X
29. Kazuaki Narita, Soliton solution to extended Volterra equation, J. Phys. Soc. Japan 51 (1982), no. 5, 1682–1685. MR 668131 (84c:34116), http://dx.doi.org/10.1143/JPSJ.51.1682
30. 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 (2001b:37101)
31. 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 (93h:58077)
32. V. Papageorgiou, B. Grammaticos, and A. Ramani, Integrable lattices and convergence acceleration algorithms, Phys. Lett. A 179 (1993), no. 2, 111–115. MR 1230809 (94b:65009), http://dx.doi.org/10.1016/0375-9601(93)90658-M
33. 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 (97k:39013)
34. A. Salam, Extrapolation: Extension et Nouveaux Résultats, Thèse, Université des Sciences et Technologies de Lille, 1993.
35. A. Salam, On a generalization of the 𝜀-algorithm, J. Comput. Appl. Math. 46 (1993), no. 3, 455–464. MR 1223011 (94a:65002), http://dx.doi.org/10.1016/0377-0427(93)90041-9
36. Claus Schneider, Vereinfachte Rekursionen zur Richardson-Extrapolation in Spezialfällen, Numer. Math. 24 (1975), no. 2, 177–184 (German, with English summary). MR 0378342 (51 #14510)
37. 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.
38. Daniel Shanks, Non-linear transformations of divergent and slowly convergent sequences, J. Math. and Phys. 34 (1955), 1–42. MR 0068901 (16,961e)
39. Avram Sidi, Practical extrapolation methods, Cambridge Monographs on Applied and Computational Mathematics, vol. 10, Cambridge University Press, Cambridge, 2003. Theory and applications. MR 1994507 (2004e:65005)
40. W. W. Symes, The 𝑄𝑅 algorithm and scattering for the finite nonperiodic Toda lattice, Phys. D 4 (1981/82), no. 2, 275–280. MR 653781 (83h:58053), http://dx.doi.org/10.1016/0167-2789(82)90069-0
41. 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 (2001m:35307), http://dx.doi.org/10.1088/0266-5611/17/1/305
42. Robert Vein and Paul Dale, Determinants and their applications in mathematical physics, Applied Mathematical Sciences, vol. 134, Springer-Verlag, New York, 1999. MR 1654469 (99m:15005)
43. Guido Walz, Asymptotics and extrapolation, Mathematical Research, vol. 88, Akademie Verlag, Berlin, 1996. MR 1386191 (97j:65001)
44. E.J. Weniger, Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series, Comp. Phys. Reports, 10 (1989) 189-371.
45. Jet Wimp, Sequence transformations and their applications, Mathematics in Science and Engineering, vol. 154, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1981. MR 615250 (84e:65005)
46. P. Wynn, On a device for computing the 𝑒_{𝑚}(𝑆_{𝑛}) tranformation, Math. Tables Aids Comput. 10 (1956), 91–96. MR 0084056 (18,801e)
47. 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 0081979 (18,478c)
48. 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.
49. 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 0203963 (34 #3810)
50. P. Wynn, Upon systems of recursions which obtain among the quotients of the Padé table, Numer. Math. 8 (1966), 264–269. MR 0215499 (35 #6339)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|