Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
Published electronically: October 19, 2011
MathSciNet review: 2904589
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 [Enhancements On Off] (What's this?)

  • 1. A.C. Aitken, Determinants and Matrices, Oliver and Boyd, Edinburgh and London, 1939. MR 00000217 (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. C. Brezinski, Accélération de suites à convergence logarithmique, C. R. Acad. Sci. Paris, Sér. A, 273 (1971) 727-730. MR 0305544 (46:4674)
  • 5. C. Brezinski, Conditions d'application et de convergence de procédés d'extrapolation, Numer. Math., 20 (1972) 64-79. MR 0378341 (51:14509)
  • 6. C. Brezinski, A general extrapolation algorithm, Numer. Math., 35 (1980) 175-187. MR 585245 (81j:65015)
  • 7. C. Brezinski, Quasi-linear extrapolation processes, in Numerical Mathematics. Singapore 1988, R.P. Agarwal et al. eds., ISNM vol. 86, Birkhäuser, Basel, 1988, pp. 61-78. MR 1022946 (90k:65012)
  • 8. C. Brezinski, Biorthogonality and its Applications of Numerical Analysis, Marcel Dekker, New York, 1992. MR 1151616 (92m:41001)
  • 9. C. Brezinski, Cross rules and non-Abelian lattice equations for the discrete and confluent non-scalar epsilon-algorithms, J. Phys. A: Math. Theor., 43 (2010) 205201. MR 2639912 (2011d:65438)
  • 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. C. Brezinski, M. Redivo-Zaglia, Extrapolation Methods. Theory and Practice, North-Holland, Amsterdam, 1991. MR 1140920 (93d:65001)
  • 12. C. Carstensen, On a general epsilon algorithm, in Numerical and Applied Mathematics,
    C. Brezinski ed., Baltzer, Basel, 1989, pp. 437-441. MR 1066038 (91g:65010)
  • 13. W. F. Ford, A. Sidi, An algorithm for a generalization of the Richardson extrapolation process, SIAM J. Numer. Anal., 24 (1987) 1212-1232. MR 909075 (89a:65006)
  • 14. T. Håvie, Generalized Neville type extrapolation schemes, BIT, 19 (1979) 204-213. MR 537780 (80f:65005)
  • 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. Y. He, X.-B. Hu, H.-W. Tam, A $ q$-difference version of the $ \varepsilon $-algorithm, J. Phys. A: Math. Theor., 42 (2009) 095202. MR 2525530 (2010j:37111)
  • 17. 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.
  • 18. R. Hirota, The Direct Method in Soliton Theory, Cambridge University Press, Cambridge, 1992. MR 2085332 (2005f:37137)
  • 19. X.-B. Hu, R.K. Bullough, Bäcklund transformation and nonlinear superposition formula of an extended Lotka-Volterra equation, J. Phys. A: Math. Gen., 30 (1997) 3635-3641. MR 1457967 (98i:35159)
  • 20. M. Iwasaki, Y. Nakamura, On the convergence of a solution of the discrete Lotka-Volterra system, Inverse Problem, 18 (2002) 1569-1578. MR 1955905 (2004a:39031)
  • 21. M. Iwasaki, Y. Nakamura, An application of the discrete Lotka-Volterra system with variable step-size to singular value computation, Inverse Problems 20 (2004) 553-563. MR 2065439 (2005e:39046)
  • 22. A. Matos, M. Prévost, Acceleration property for the columns of the $ E$-algorithm, Numer. Algorithms, 2 (1992) 393-408. MR 1184823 (94b:65008)
  • 23. G. Meinardus, G.D. Taylor, Lower estimates for the error of the best uniform approximation, J. Approx. Theory, 16 (1976) 150-161. MR 0399720 (53:3562)
  • 24. Y. Minesaki, Y. Nakamura, The discrete relativistic Toda molecule equation and a Padé approximation algorithm, Numer. Algorithms, 27 (2001) 219- 235. MR 1858990 (2002h:42054)
  • 25. A. Nagai, J. Satsuma, Discrete soliton equations and convergence acceleration algorithms, Phys. Letters A, 209 (1995) 305-312. MR 1368590 (96h:65006)
  • 26. A. Nagai, T. Tokihiro, J. Satsuma, The Toda molecule equation and the $ \varepsilon $-algorithm, Math. Comput., 67 (1998) 1565-1575. MR 1484902 (99d:65010)
  • 27. Y. Nakamura, ed., Applied Integrable Systems (in Japanese), Syokabo, Tokyo, 2000.
  • 28. Y. Nakamura, Calculating Laplace transforms in terms of the Toda molecule, SIAM J. Sci. Comput. 20 (1999) 306-317. MR 1639142 (2000i:65215)
  • 29. K. Narita, Soliton solution to extended Volterra equation, J. Phys. Soc. Japan, 51 (1982) 1682-1685. MR 668131 (84c:34116)
  • 30. F.W. Nijhoff, Discrete Painlevé equations and symmetry reductions on the lattice, in Discrete Integrable Geometry and Physics, A. Bobenko and R. Seiler eds., Clarendon Press, Oxford, 1999, pp. 209-234. MR 1676599 (2001b:37101)
  • 31. F.W. Nijhoff, V.G. Papageorgiou, H.W. Capel, G.R.W. Quispel, The lattice Gel'fand-Dikii hierarchy, Inverse Problems. 8(4), (1992) 597-621. MR 1178232 (93h:58077)
  • 32. V. Papageorgiou, B. Grammaticos, A. Ramani, Integrable lattices and convergence acceleration algorithms, Phys. Letters A, 179 (1993) 111-115. MR 1230809 (94b:65009)
  • 33. V. Papageorgiou, B. Grammaticos, A. Ramani, Integrable difference equations and numerical analysis algorithms, in Symmetries and Integrability of Difference Equations, D. Levi et al. eds., CRM Proceedings and Lecture Notes, vol. 9, AMS, Providence, 1996, pp. 269-279. 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 $ \varepsilon $-algorithm, J. Comput. Appl. Math., 46 (1993) 455-464. MR 1223011 (94a:65002)
  • 36. C. Schneider, Vereinfachte Rekursionen zur Richardson-Extrapolation in Spezialfällen, Numer. Math., 24 (1975) 177-184. 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. D. Shanks, Non linear transformations of divergent and slowly convergent sequences, J. Math. Phys., 34 (1955) 1-42. MR 0068901 (16:961e)
  • 39. A. Sidi, Practical Extrapolation Methods. Theory and Applications, Cambridge University Press, Cambridge, 2003. MR 1994507 (2004e:65005)
  • 40. W.W. Symes, The $ QR$ algorithm and scattering for the nonperiodic Toda lattice, Physica 4D (1982) 275-280. MR 653781 (83h:58053)
  • 41. S. Tsujimoto, Y. Nakamura, M. Iwasaki, The discrete Lotka-Volterra system computes singular values, Inverse Problems 17 (2001) 53-58. MR 1818491 (2001m:35307)
  • 42. R. Vein, P. Dale, Determinants and Their Applications in Mathematical Physics, Springer-Verlag, New York, 1999. MR 1654469 (99m:15005)
  • 43. G. Walz, Asymptotics and Extrapolation, 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. J. Wimp, Sequence Transformations and Their Applications, Academic Press, New York, 1981. MR 615250 (84e:65005)
  • 46. P. Wynn, On a device for computing the $ e_{m}(S_{n})$ transformation, MTAC, 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 Phil. 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, Chiffres, 4 (1966) 327-362. 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)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65B05, 39A14, 37K10

Retrieve articles in all journals with MSC (2010): 65B05, 39A14, 37K10

Additional Information

Claude Brezinski
Affiliation: Laboratoire Paul Painlevé, UMR CNRS 8524, UFR de Mathématiques Pures et Appliquées, Université des Sciences et Technologies de Lille, France

Yi He
Affiliation: LSEC, Institute of Computational Mathematics and Scientific Engineering Computing, AMSS, Chinese Academy of Sciences, and Graduate School of the Chinese Academy of Sciences, Beijing, People’s Republic of China

Xing-Biao Hu
Affiliation: LSEC, Institute of Computational Mathematics and Scientific Engineering Computing, AMSS, Chinese Academy of Sciences, Beijing, People’s Republic of China

Michela Redivo-Zaglia
Affiliation: Università degli Studi di Padova, Dipartimento di Matematica Pura ed Applicata, Italy

Jian-Qing Sun
Affiliation: LSEC, Institute of Computational Mathematics and Scientific Engineering Computing, AMSS, Chinese Academy of Sciences, and Graduate School of the Chinese Academy of Sciences, Beijing, People’s Republic of China

Keywords: Convergence acceleration algorithm, $𝜖$–algorithm, Shanks’ transformation, Lotka–Volterra system
Received by editor(s): December 21, 2010
Received by editor(s) in revised form: March 14, 2011
Published electronically: October 19, 2011
Article copyright: © Copyright 2011 American Mathematical Society

American Mathematical Society