Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Boundedness and strong stability of Runge-Kutta methods


Authors: W. Hundsdorfer and M. N. Spijker
Journal: Math. Comp. 80 (2011), 863-886
MSC (2010): Primary 65L05, 65L06, 65L20, 65M20
DOI: https://doi.org/10.1090/S0025-5718-2010-02422-6
Published electronically: September 21, 2010
MathSciNet review: 2772099
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In the literature, much attention has been paid to Runge-Kutta methods (RKMs) satisfying special nonlinear stability requirements indicated by the terms total-variation-diminishing (TVD), strong stability preserving (SSP) and monotonicity. Stepsize conditions, guaranteeing these properties, were derived by Shu and Osher [J. Comput. Phys., 77 (1988) pp. 439-471] and in numerous subsequent papers. These special stability requirements imply essential boundedness properties for the numerical methods, among which the property of being total-variation-bounded. Unfortunately, for many RKMs, the above special requirements are violated, so that one cannot conclude in this way that the methods are (total-variation) bounded.

In this paper, we study stepsize-conditions for boundedness directly, rather than via the detour of the above special stability properties. We focus on stepsize-conditions which are optimal, in that they are not unnecessarily restrictive. We find that, in situations where the special stability properties mentioned above are violated, boundedness can be present only within a class of very special RKMs.

As a by-product, our analysis sheds new light on the known theory of monotonicity for RKMs. We obtain separate results for internal and external monotonicity, as well as a new proof of the fundamental relation between monotonicity and Kraaijevanger's coefficient. This proof distinguishes itself from older ones in that it is shorter and more transparent, while it requires simpler assumptions on the RKMs under consideration.


References [Enhancements On Off] (What's this?)

  • 1. J.C. Butcher, The numerical analysis of ordinary differential equations, John Wiley, Chichester, UK, 1987. MR 878564 (88d:65002)
  • 2. J.C. Butcher, Numerical methods for ordinary differential equations, John Wiley, Chichester, UK, 2003. MR 1993957 (2004e:65069)
  • 3. G. Dahlquist, R. Jeltsch, Reducibility and contractivity of Runge-Kutta methods revisited, BIT 46 (2006), 567-587. MR 2265575 (2007h:65068)
  • 4. L. Ferracina, M.N. Spijker, Stepsize restrictions for the total-variation-diminishing property in general Runge-Kutta methods, SIAM J. Numer. Anal. 42 (2004), 1073-1093. MR 2113676 (2005k:65126)
  • 5. L. Ferracina, M.N. Spijker, An extension and analysis of the Shu-Osher representation of Runge-Kutta methods, Math. Comp. 74 (2005), 201-219. MR 2085408 (2005g:65110)
  • 6. L. Ferracina, M.N. Spijker, Stepsize restriction for total-variation-boundedness in general Runge-Kutta procedures, Appl. Num. Math. 53 (2005), 265-279. MR 2128526 (2005k:65127)
  • 7. L. Ferracina, M.N. Spijker, Strong stability of singly-diagonally-implicit Runge-Kutta methods, Appl. Num. Math. 58 (2008), 1675-1686. MR 2458475 (2009i:65114)
  • 8. S. Gottlieb, On high order strong stability preserving Runge-Kutta and multistep time discretizations, Journ. Scientif. Computing 25 (2005), 105-128. MR 2231945 (2007f:65029)
  • 9. S. Gottlieb, D.I. Ketcheson, C.-W. Shu, High order strong stability preserving time discretizations, Journ. Scientif. Computing 38 (2009), 251-289. MR 2475652 (2010b:65161)
  • 10. S. Gottlieb, C.-W. Shu, Total-variation-diminishing Runge-Kutta schemes, Math. Comp. 67 (1998), 73-85. MR 1443118 (98c:65122)
  • 11. S. Gottlieb, C.-W. Shu, E. Tadmor, Strong stability-preserving high-order time discretization methods, SIAM Review 43 (2001), 89-112. MR 1854647 (2002f:65132)
  • 12. E. Hairer, S.P. Nørsett, G. Wanner, Solving ordinary differential equations. I. Nonstiff problems, Springer-Verlag, Berlin, 1993. MR 1227985 (94c:65005)
  • 13. E. Hairer, G. Wanner, Solving ordinary differential equations. II. Stiff and differential-algebraic problems, Springer-Verlag, Berlins, 1996. MR 1439506 (97m:65007)
  • 14. A. Harten, High resolution schemes for hyperbolic conservation laws, J. Comput. Phys. 49 (1983), 357-393. MR 701178 (84g:65115)
  • 15. I. Higueras, On strong stability preserving time discretization methods, Journ. Scientif. Computing 21 (2004), 193-223. MR 2069949 (2005d:65112)
  • 16. I. Higueras, Representations of Runge-Kutta methods and strong stability preserving methods, SIAM J. Numer. Anal. 43 (2005), 924-948. MR 2177549 (2006j:65184)
  • 17. I. Higueras, Strong stability for additive Runge-Kutta methods, SIAM J. Numer. Anal. 44 (2006), 1735-1758. MR 2257125 (2008c:65164)
  • 18. R.A. Horn, C.R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1998. MR 1084815 (91i:15001)
  • 19. Z. Horváth, Positivity of Runge-Kutta and diagonally split Runge-Kutta methods, Appl. Num. Math. 28 (1998), 309-326. MR 1655167 (99i:65073)
  • 20. W. Hundsdorfer, A. Mozartova, M.N. Spijker, Stepsize conditions for boundedness in numerical initial value problems, SIAM J. Numer. Anal. 47 (2009), 3797-3819. MR 2576521
  • 21. W. Hundsdorfer, J.G. Verwer, Numerical solution of time-dependent advection-diffusion-reaction equations, Springer-Verlag, Berlin, 2003. MR 2002152 (2004g:65001)
  • 22. D.I. Ketcheson, An algebraic characterization of strong stability preserving Runge-Kutta schemes, Undergraduate Thesis, Brigham Young University, Provo, Utah, USA, 2004.
  • 23. D.I. Ketcheson, C.B. Macdonald, S. Gottlieb, Optimal implicit strong stability preserving Runge-Kutta methods, Appl. Num. Math. 59 (2009), 373-392. MR 2484928 (2010a:65113)
  • 24. J.F.B.M. Kraaijevanger, Contractivity of Runge-Kutta methods, BIT 31 (1991), 482-528. MR 1127488 (92i:65120)
  • 25. R.J. LeVeque, Finite volume methods for hyperbolic problems, Cambridge University Press, Cambridge, 2002. MR 1925043 (2003h:65001)
  • 26. S.J. Ruuth, Global optimization of explicit strong-stability-preserving Runge-Kutta methods, Math. Comp. 75 (2006), 183-207. MR 2176394 (2006k:65180)
  • 27. C.-W. Shu, Total-variation-diminishing time discretizations, SIAM J. Sci. Statist. Comput., 9 (1988), 1073-1084. MR 963855 (90a:65196)
  • 28. C.-W. Shu, A survey of strong stability preserving high-order time discretizations, Collected lectures on the preservation of stability under discretization, D. Estep and S. Tavener eds., SIAM, Philadelphia, 2002, pp. 51-65. MR 2026663
  • 29. C.-W. Shu, S. Osher, Efficient implementation of essentially nonoscillatory shock-capturing schemes, J. Comput. Phys. 77 (1988), 439-471. MR 954915 (89g:65113)
  • 30. M.N. Spijker, Contractivity in the numerical solution of initial value problems, Numer. Math. 42 (1983), 271-290. MR 723625 (85b:65067)
  • 31. M.N. Spijker, Monotonicity and boundedness in implicit Runge-Kutta methods, Numer. Math. 50 (1986), 97-109. MR 864307 (88a:65076)
  • 32. M.N. Spijker, Stepsize conditions for general monotonicity in numerical initial value problems, SIAM J. Numer. Anal. 45 (2007), 1226-1245. MR 2318810 (2008e:65199)
  • 33. R.J. Spiteri, S.J. Ruuth, A new class of optimal high-order strong-stability-preserving time discretization methods, SIAM J. Numer. Anal. 40 (2002), 469-491. MR 1921666 (2003g:65083)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65L05, 65L06, 65L20, 65M20

Retrieve articles in all journals with MSC (2010): 65L05, 65L06, 65L20, 65M20


Additional Information

W. Hundsdorfer
Affiliation: Center for Mathematics and Computer Sciences, P.O. Box 94079, NL-1090-GB Amsterdam, Nederland
Email: willem.hundsdorfer@cwi.nl

M. N. Spijker
Affiliation: Mathematical Institute, Leiden University, P.O. Box 9512, NL-2300-RA Leiden, Nederland
Email: spijker@math.leidenuniv.nl

DOI: https://doi.org/10.1090/S0025-5718-2010-02422-6
Keywords: Initial value problem, method of lines (MOL), ordinary differential equation (ODE), Runge-Kutta method (RKM), total-variation-diminishing (TVD), strong-stability-preserving (SSP), monotonicity, total-variation-bounded (TVB), boundedness.
Received by editor(s): September 28, 2009
Received by editor(s) in revised form: February 16, 2010
Published electronically: September 21, 2010
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society