An Extended Multistep Shanks Transformation and Convergence Acceleration Algorithm with Their Convergence and Stability Analysis | Numerische Mathematik Skip to main content
Springer Nature Link
Log in

An Extended Multistep Shanks Transformation and Convergence Acceleration Algorithm with Their Convergence and Stability Analysis

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

The molecule solution of an extended discrete Lotka–Volterra equation is constructed, from which a new sequence transformation is proposed. A convergence acceleration algorithm for implementing this sequence transformation is found. It is shown that our new sequence transformation accelerates some kinds of linearly convergent sequences and factorially convergent sequences with good numerical stability. Some numerical examples are also presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aitken, A.C.: On Bernoullis numerical solution of algebraic equations. Proc. R. Soc. Edinb. 46, 289–305 (1926)

    MATH  Google Scholar 

  2. Aitken, A.C.: Determinants and Matrices. Oliver and Boyd, Edinburgh (1959)

    Google Scholar 

  3. Almkvist, G., Berndt, B.: Gauss, Landen, Ramanujan, the arithmetic-geometric mean, ellipses, \(\pi \), and the ladies diary. Am. Math. Mon. 95, 585–608 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  4. Babelon, O., Bernard, D., Talon, M.: Introduction to classical integrable systems. Cambridge University Press, Cambridge (2003)

  5. Baker, G.A., Graves-Morris, P.R.: Padé Approximants. Cambridge University Press, Cambridge (1996)

    Book  MATH  Google Scholar 

  6. Borwein, J.M., Borwein, P.B.: The arithmetic–geometric mean and fast computation of elementary functions. SIAM Rev. 26, 351–366 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bourbaki, N.: Éléments de mathématique. Fonctions d’une variable réelle (1961)

  8. Brezinski, C.: Conditions d’application et de convergence de proc d’ s d’ extrapolation. Numer. Math. 20, 64–79 (1972)

    Article  MathSciNet  Google Scholar 

  9. Brezinski, C.: Padé-type Approximation and General Orthogonal Polynomials. Birkhä user Verlag, Basel (1980)

    Book  MATH  Google Scholar 

  10. Brezinski, C.: A Bibliography on Continued Fractions, Padé Approximation. Sequence Transformation and Related Subjects. Prensas Universitarias de Zaragoza, Zaragoza (1991)

    Google Scholar 

  11. Brezinski, C.: Extrapolation algorithms and Padé approximations: A historical survey. Appl. Numer. Math. 20, 299–318 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  12. Brezinski, C.: Convergence acceleration during the 20th century. J. Comput. Appl. Math. 122, 1–21 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  13. Brezinski, C., He, Y., Hu, X.B., Redivo-Zaglia, M., Sun, J.Q.: Multistep \(\varepsilon \)-algorithm, Shanks’ transformation, and Lotka–Volterra system by Hirota’s method. Math. Comput. 81, 1527–1549 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  14. Brezinski, C., Redivo Zaglia, M.: Extrapolation Methods. Theory and Practice. North-Holland, Amsterdam (1991)

    MATH  Google Scholar 

  15. Brualdi, R.A., Schneider, H.: Determinantal identities: Gauss, Schur, Cauchy, Sylvester, Kronecker, Jacobi, Binet, Laplace, Muir, and Cayley. Linear Algebra Appl. 52/53, 769–791 (1983)

    MathSciNet  Google Scholar 

  16. Carstensen, C.: On a general epsilon algorithm. In: Ames, W.F., Brezinski, C. (eds.) Numerical and Applied Mathematics, Part II (Paris, 1988), pp. 437–441. IMACS Ann. Comput. Appl. Math., 1.2. Baltzer, Basel (1989)

  17. Chu, M.T.: Linear algebra algorithms as dynamical systems. Acta Numer. 17, 1–86 (2008)

    MathSciNet  MATH  Google Scholar 

  18. Garibotti, C.R., Grinstein, F.F.: Recent results relevant to the evaluation of infinite series. J. Comput. Appl. Math. 9, 193–200 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  19. He, Y., Hu, X.B., Sun, J.Q., Weniger, E.J.: Convergence acceleration algorithm via an equation related to the lattice Boussinesq equation. SIAM J. Sci. Comput. 33, 1234–1245 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. He, Y., Hu, X.B., Tam, H.W.: A q-difference version of the \(\varepsilon \)-algorithm. J. Phys. A 42, 5202–5210 (2009)

    MathSciNet  Google Scholar 

  21. Henrici, P.: The quotient-difference algorithm. In: National Bureau of Standards (ed.) Further Contributions to the Solution of Simultaneous Linear Equations and the Determination of Eigenvalues, Volume 49 of Applied Mathematics Series, pp. 23–46. US Government Printing Office (1958)

  22. Hirota, R.: Nonlinear partial difference equations. II. Discrete-time Toda equation. J. Phys. Soc. Japan 43, 2074–2078 (1977)

    Article  MathSciNet  Google Scholar 

  23. Hirota, R.: The Direct Method in Soliton Theory. Cambridge University Press, Cambridge(2004) (Translated by Nagai, A., Nimmo, J. and Gilson, C.)

  24. Hu, X.B., Bullough, R.K.: Backlund transformation and nonlinear superposition formula of an extended Lotka–Volterra equation. J. Phys. A 30, 3635–3641 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  25. Iwasaki, M., Nakamura, Y.: On the convergence of a solution of the discrete Lotka–Volterra system. Inverse Probl. 18, 1569–1578 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  26. Iwasaki, M., Nakamura, Y.: An application of the discrete Lotka–Volterra system with variable step-size to singular value computation. Inverse Probl. 20, 553–563 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  27. Jordan, C.: Calculus of Finite Differences. Chelsea Pub Co, New York (1965)

    MATH  Google Scholar 

  28. Nagai, A., Satsuma, J.: Satsuma Discrete soliton equations and convergence acceleration algorithms. Phys. Lett. A 209, 305–312 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  29. Nagai, A., Tokihiro, T., Satsuma, J.: The Toda molecule equation and the \(\varepsilon \)-algorithm. Math. Comput. 67, 1565–1575 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  30. Nakamura, Y. (ed.): Shokabo, Applied Integrable Systems. Tokyo (2000) (in Japanese)

  31. Nakamura, Y.: Algorithms associated with arithmetic, geometric and harmonic means and integrable systems. J. Comput. Appl. Math. 131, 161–174 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  32. Narita, K.: Soliton solution to extended Volterra equation. J. Phys. Soc. Japan 51, 1682–1685 (1982)

    Article  MathSciNet  Google Scholar 

  33. Olver, F.W., Lozier, D.W., Boisvert, R.F., Clark, C.W.: NIST Handbook of Mathematical Functions. Cambridge University Press, Cambridge (2010)

    MATH  Google Scholar 

  34. Osada, N.: Acceleration methods for slowly convergent sequences and their applications. PhD thesis, Nagoya University, Japan (1993)

  35. Grammaticos, B., Papageorgiou, V., Ramani, A.: Orthogonal polynomial approach to discrete Lax pairs for initial-boundary value problems of the QD algorithm. Lett. Math. Phys. 34, 91–101 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  36. Papageorgiou, V., Grammaticos, B., Ramani, A.: Integrable lattices and convergence acceleration algorithms. Phys. Lett. A 179, 111–115 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  37. Pennacchi, R.: Le trasformazioni razionali di una successione. Calcolo 5, 37–50 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  38. Rutishauser, H.: Der Quotienten-Differenzen-Algorithmus. Z. Angew. Math. Physik 5, 233–251 (1954)

  39. Sato M., Sato, Y.: Soliton equations as dynamical systems on infinite dimensional Grassmann manifold. In: Fujita, H., Lax, P.D., Strang, G., (eds.) Nonlinear Partial Differential Equations in Applied Science, vol. 81, pp. 259–271. North-Holland Math. Stud. (1981)

  40. Sidi, A.: Some properties of a generalization of the Richardson extrapolation process. J. Inst. Math. Appl. 24, 327–346 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  41. Sidi, A.: Acceleration of convergence of (generalized) Fourier series by the d-transformation. Ann. Numer. Math. 2, 381–406 (1995)

    MathSciNet  MATH  Google Scholar 

  42. Sidi, A.: Extension and completion of Wynn’s theory on convergence of columns of the epsilon table. J. Approx. Theory 86, 21–40 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  43. Sidi, A.: Further convergence and stability results for the generalized Richardson extrapolation process \(\text{ GREP }^{(1)}\) with an application to the \(\text{ D }^{(1)}\)-transformation for infinite integrals. J. Comput. Appl. Math. 112, 269–290 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  44. Sidi, A.: The Richardson extrapolation process with a harmonic sequence of collocation points. SIAM J. Numer. Anal. 37, 1729–1746 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  45. Sidi, A.: A convergence and stability study of the iterated Lubkin transformation and the \(\theta \)-algorithm. Math. Comput. 72, 419–434 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  46. Sidi, A.: Practical Extrapolation Methods: Theory and Applications. Cambridge University Press, Cambridge (2003)

    Book  Google Scholar 

  47. Sidi, A.: Survey of numerical stability issues in convergence acceleration. Appl. Numer. Math. 60, 1395–1410 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  48. Symes, W.W.: The QR algorithm and scattering for the finite nonperiodic Toda lattice. Phys. D. 4, 275–280 (1981/1982)

    Google Scholar 

  49. Temme, N.M.: Special Functions: An Introduction to the Classical Functions of Mathematical Physics. Wiley-Interscience, New York (1996)

    Book  MATH  Google Scholar 

  50. Tsujimoto, S., Nakamura, Y., Iwasaki, M.: The discrete Lotka–Volterra system computes singular values. Inverse Probl. 17, 53–58 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  51. Weniger, E.J.: Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series. Comput. Phys. Rep. 10, 189–371 (1989)

    Article  Google Scholar 

  52. Wimp, J.: Sequence Transformations and Their Applications. Academic Press, London (1981)

  53. Wynn, P.: On a device for computing the \(e_m(S_n)\) transformation. Math. Tables Aids Comput. 10, 91–96 (1956)

    Article  MathSciNet  MATH  Google Scholar 

  54. Wynn, P.: On the convergence and stability of the epsilon algorithm. SIAM J. Numer. Anal. 3, 91–122 (1966)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to express their sincere thanks to the referees for their pertinent and valuable comments. This work was partially supported by the National Natural Science Foundation of China (Grant No. 11071241, Grant No. 11201469), the knowledge innovation program of LSEC and the Institute of Computational Mathematics, AMSS, CAS, and the China Postdoctoral Science Foundation funded project (Grant No. 2012M510186).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Ocean University of China, Qingdao, 266100, People’s Republic of China

    Jian-Qing Sun

  2. LSEC, Institute of Computational Mathematics and Scientific Engineering Computing, AMSS, Chinese Academy of Sciences, P.O.Box 2719, Beijing, 100190, People’s Republic of China

    Xiang-Ke Chang & Xing-Biao Hu

  3. University of Chinese Academy of Sciences, Beijing, People’s Republic of China

    Xiang-Ke Chang

  4. Wuhan Institute of Physics and Mathematics, Chinese Academy of Sciences, Wuhan, 430071, People’s Republic of China

    Yi He

Authors
  1. Jian-Qing Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiang-Ke Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yi He
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xing-Biao Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jian-Qing Sun.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sun, JQ., Chang, XK., He, Y. et al. An Extended Multistep Shanks Transformation and Convergence Acceleration Algorithm with Their Convergence and Stability Analysis. Numer. Math. 125, 785–809 (2013). https://doi.org/10.1007/s00211-013-0549-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-013-0549-1

Mathematics Subject Classification

Search

Navigation