Boundedness and strong stability of Runge-Kutta methods

Hundsdorfer, W.; Spijker, M. N.

doi:10.1090/S0025-5718-2010-02422-6

Boundedness and strong stability of Runge-Kutta methods
HTML articles powered by AMS MathViewer

by W. Hundsdorfer and M. N. Spijker PDF

Math. Comp. 80 (2011), 863-886 Request permission

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

J. C. Butcher, The numerical analysis of ordinary differential equations, A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1987. Runge\mhy Kutta and general linear methods. MR 878564
J. C. Butcher, Numerical methods for ordinary differential equations, John Wiley & Sons, Ltd., Chichester, 2003. MR 1993957, DOI 10.1002/0470868279
Germund Dahlquist and Rolf Jeltsch, Reducibility and contractivity of Runge-Kutta methods revisited, BIT 46 (2006), no. 3, 567–587. MR 2265575, DOI 10.1007/s10543-006-0079-7
L. Ferracina and M. N. Spijker, Stepsize restrictions for the total-variation-diminishing property in general Runge-Kutta methods, SIAM J. Numer. Anal. 42 (2004), no. 3, 1073–1093. MR 2113676, DOI 10.1137/S0036142902415584
L. Ferracina and M. N. Spijker, An extension and analysis of the Shu-Osher representation of Runge-Kutta methods, Math. Comp. 74 (2005), no. 249, 201–219. MR 2085408, DOI 10.1090/S0025-5718-04-01664-3
L. Ferracina and M. N. Spijker, Stepsize restrictions for total-variation-boundedness in general Runge-Kutta procedures, Appl. Numer. Math. 53 (2005), no. 2-4, 265–279. MR 2128526, DOI 10.1016/j.apnum.2004.08.024
L. Ferracina and M. N. Spijker, Strong stability of singly-diagonally-implicit Runge-Kutta methods, Appl. Numer. Math. 58 (2008), no. 11, 1675–1686. MR 2458475, DOI 10.1016/j.apnum.2007.10.004
Sigal Gottlieb, On high order strong stability preserving Runge-Kutta and multi step time discretizations, J. Sci. Comput. 25 (2005), no. 1-2, 105–128. MR 2231945, DOI 10.1007/s10915-004-4635-5
Sigal Gottlieb, David I. Ketcheson, and Chi-Wang Shu, High order strong stability preserving time discretizations, J. Sci. Comput. 38 (2009), no. 3, 251–289. MR 2475652, DOI 10.1007/s10915-008-9239-z
Sigal Gottlieb and Chi-Wang Shu, Total variation diminishing Runge-Kutta schemes, Math. Comp. 67 (1998), no. 221, 73–85. MR 1443118, DOI 10.1090/S0025-5718-98-00913-2
Sigal Gottlieb, Chi-Wang Shu, and Eitan Tadmor, Strong stability-preserving high-order time discretization methods, SIAM Rev. 43 (2001), no. 1, 89–112. MR 1854647, DOI 10.1137/S003614450036757X
E. Hairer, S. P. Nørsett, and G. Wanner, Solving ordinary differential equations. I, 2nd ed., Springer Series in Computational Mathematics, vol. 8, Springer-Verlag, Berlin, 1993. Nonstiff problems. MR 1227985
E. Hairer and G. Wanner, Solving ordinary differential equations. II, 2nd ed., Springer Series in Computational Mathematics, vol. 14, Springer-Verlag, Berlin, 1996. Stiff and differential-algebraic problems. MR 1439506, DOI 10.1007/978-3-642-05221-7
Ami Harten, High resolution schemes for hyperbolic conservation laws, J. Comput. Phys. 49 (1983), no. 3, 357–393. MR 701178, DOI 10.1016/0021-9991(83)90136-5
Inmaculada Higueras, On strong stability preserving time discretization methods, J. Sci. Comput. 21 (2004), no. 2, 193–223. MR 2069949, DOI 10.1023/B:JOMP.0000030075.59237.61
Inmaculada Higueras, Representations of Runge-Kutta methods and strong stability preserving methods, SIAM J. Numer. Anal. 43 (2005), no. 3, 924–948. MR 2177549, DOI 10.1137/S0036142903427068
Inmaculada Higueras, Strong stability for additive Runge-Kutta methods, SIAM J. Numer. Anal. 44 (2006), no. 4, 1735–1758. MR 2257125, DOI 10.1137/040612968
Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1990. Corrected reprint of the 1985 original. MR 1084815
Zoltán Horváth, Positivity of Runge-Kutta and diagonally split Runge-Kutta methods, Appl. Numer. Math. 28 (1998), no. 2-4, 309–326. Eighth Conference on the Numerical Treatment of Differential Equations (Alexisbad, 1997). MR 1655167, DOI 10.1016/S0168-9274(98)00050-6
W. Hundsdorfer, A. Mozartova, and M. N. Spijker, Stepsize conditions for boundedness in numerical initial value problems, SIAM J. Numer. Anal. 47 (2009), no. 5, 3797–3819. MR 2576521, DOI 10.1137/090745842
Willem Hundsdorfer and Jan Verwer, Numerical solution of time-dependent advection-diffusion-reaction equations, Springer Series in Computational Mathematics, vol. 33, Springer-Verlag, Berlin, 2003. MR 2002152, DOI 10.1007/978-3-662-09017-6
D.I. Ketcheson, An algebraic characterization of strong stability preserving Runge-Kutta schemes, Undergraduate Thesis, Brigham Young University, Provo, Utah, USA, 2004.
David I. Ketcheson, Colin B. Macdonald, and Sigal Gottlieb, Optimal implicit strong stability preserving Runge-Kutta methods, Appl. Numer. Math. 59 (2009), no. 2, 373–392. MR 2484928, DOI 10.1016/j.apnum.2008.03.034
J. F. B. M. Kraaijevanger, Contractivity of Runge-Kutta methods, BIT 31 (1991), no. 3, 482–528. MR 1127488, DOI 10.1007/BF01933264
Randall J. LeVeque, Finite volume methods for hyperbolic problems, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2002. MR 1925043, DOI 10.1017/CBO9780511791253
Steven J. Ruuth, Global optimization of explicit strong-stability-preserving Runge-Kutta methods, Math. Comp. 75 (2006), no. 253, 183–207. MR 2176394, DOI 10.1090/S0025-5718-05-01772-2
Chi-Wang Shu, Total-variation-diminishing time discretizations, SIAM J. Sci. Statist. Comput. 9 (1988), no. 6, 1073–1084. MR 963855, DOI 10.1137/0909073
C.-W. Shu, A survey of strong stability preserving high order time discretizations, Collected lectures on the preservation of stability under discretization (Fort Collins, CO, 2001) SIAM, Philadelphia, PA, 2002, pp. 51–65. MR 2026663
Chi-Wang Shu and Stanley Osher, Efficient implementation of essentially nonoscillatory shock-capturing schemes, J. Comput. Phys. 77 (1988), no. 2, 439–471. MR 954915, DOI 10.1016/0021-9991(88)90177-5
M. N. Spijker, Contractivity in the numerical solution of initial value problems, Numer. Math. 42 (1983), no. 3, 271–290. MR 723625, DOI 10.1007/BF01389573
M. N. Spijker, Monotonicity and boundedness in implicit Runge-Kutta methods, Numer. Math. 50 (1986), no. 1, 97–109. MR 864307, DOI 10.1007/BF01389670
M. N. Spijker, Stepsize conditions for general monotonicity in numerical initial value problems, SIAM J. Numer. Anal. 45 (2007), no. 3, 1226–1245. MR 2318810, DOI 10.1137/060661739
Raymond J. Spiteri and Steven J. Ruuth, A new class of optimal high-order strong-stability-preserving time discretization methods, SIAM J. Numer. Anal. 40 (2002), no. 2, 469–491. MR 1921666, DOI 10.1137/S0036142901389025