An extension and analysis of the Shu-Osher representation of Runge-Kutta methods

Ferracina, L.; Spijker, M.

doi:10.1090/S0025-5718-04-01664-3

An extension and analysis of the Shu-Osher representation of Runge-Kutta methods
HTML articles powered by AMS MathViewer

by L. Ferracina and M. N. Spijker PDF

Math. Comp. 74 (2005), 201-219 Request permission

Abstract:

In the context of solving nonlinear partial differential equations, Shu and Osher introduced representations of explicit Runge-Kutta methods, which lead to stepsize conditions under which the numerical process is total-variation-diminishing (TVD). Much attention has been paid to these representations in the literature. In general, a Shu-Osher representation of a given Runge-Kutta method is not unique. Therefore, of special importance are representations of a given method which are best possible with regard to the stepsize condition that can be derived from them. Several basic questions are still open, notably regarding the following issues: (1) the formulation of a simple and general strategy for finding a best possible Shu-Osher representation for any given Runge-Kutta method; (2) the question of whether the TVD property of a given Runge-Kutta method can still be guaranteed when the stepsize condition, corresponding to a best possible Shu-Osher representation of the method, is violated; (3) the generalization of the Shu-Osher approach to general (possibly implicit) Runge-Kutta methods. In this paper we give an extension and analysis of the original Shu-Osher representation, by means of which the above questions can be settled. Moreover, we clarify analogous questions regarding properties which are referred to, in the literature, by the terms monotonicity and strong-stability-preserving (SSP).

References

Kevin Burrage, Efficiently implementable algebraically stable Runge-Kutta methods, SIAM J. Numer. Anal. 19 (1982), no. 2, 245–258. MR 650049, DOI 10.1137/0719015
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
K. Dekker and J. G. Verwer, Stability of Runge-Kutta methods for stiff nonlinear differential equations, CWI Monographs, vol. 2, North-Holland Publishing Co., Amsterdam, 1984. MR 774402
L. Ferracina and M.N. Spijker (2002): Stepsize restrictions for the total-variation-diminishing property in general Runge-Kutta methods, Report MI 2002-21 (2002), Mathematical Institute, University of Leiden. To appear in SIAM J. Numer. Anal.
A. Gerish and R. Weiner (2003): On the positivity of low order explicit Runge-Kutta schemes applied in splitting methods, Computers and Mathematics with Applications 45, 53–67.
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, Springer Series in Computational Mathematics, vol. 8, Springer-Verlag, Berlin, 1987. Nonstiff problems. MR 868663, DOI 10.1007/978-3-662-12607-3
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
I. Higueras (2002): On strong stability preserving time discretization methods, Report n.2 (2002), Departamento de Matemática e Informática, Universidad Pública de Navarra.
W. Hundsdorfer, S.J. Ruuth, and R.J. Spiteri (2003): Monotonicity-preserving linear multistep methods, SIAM J. Numer. Anal. 41, 605–623.
W. Hundsdorfer and J.G. Verwer (2003): Numerical solution of time-dependent advection-diffusion-reaction equations, Springer Ser. Comput. Math. 33, Springer-Verlag, Berlin.
J. F. B. M. Kraaijevanger, Contractivity of Runge-Kutta methods, BIT 31 (1991), no. 3, 482–528. MR 1127488, DOI 10.1007/BF01933264
Dietmar Kröner, Numerical schemes for conservation laws, Wiley-Teubner Series Advances in Numerical Mathematics, John Wiley & Sons, Ltd., Chichester; B. G. Teubner, Stuttgart, 1997. MR 1437144
Culbert B. Laney, Computational gasdynamics, Cambridge University Press, Cambridge, 1998. MR 1659254, DOI 10.1017/CBO9780511605604
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
K. W. Morton, Stability of finite difference approximations to a diffusion-convection equation, Internat. J. Numer. Methods Engrg. 15 (1980), no. 5, 677–683. MR 580354, DOI 10.1002/nme.1620150505
S.J. Ruuth and R.J. Spiteri (2002): Two barriers on strong-stability-preserving time discretization methods, J. Sci. Comput. 17, 211–220.
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 (2002): A survey of strong stability preserving high-order time discretizations, Collected Lectures on the Preservation of Stability under Discretization, D. Estep, S. Tavener Editors, SIAM (Philadelphia, PA), 51–65.
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
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
Eleuterio F. Toro, Riemann solvers and numerical methods for fluid dynamics, 2nd ed., Springer-Verlag, Berlin, 1999. A practical introduction. MR 1717819, DOI 10.1007/978-3-662-03915-1