Order barriers and characterizations for continuous mono-implicit Runge-Kutta schemes

Authors:
Paul Muir and Brynjulf Owren

Journal:
Math. Comp. **61** (1993), 675-699

MSC:
Primary 65L06; Secondary 34A50

MathSciNet review:
1195425

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The mono-implicit Runge-Kutta (MIRK) schemes, a subset of the family of implicit Runge-Kutta (IRK) schemes, were originally proposed for the numerical solution of initial value ODEs more than fifteen years ago. During the last decade, a considerable amount of attention has been given to the use of these schemes in the numerical solution of boundary value ODE problems, where their efficient implementation suggests that they may provide a worthwhile alternative to the widely used collocation schemes. Recent work in this area has seen the development of some software packages for boundary value ODEs based on these schemes. Unfortunately, these schemes lead to algorithms which provide only a discrete solution approximation at a set of mesh points over the problem interval, while the collocation schemes provide a natural continuous solution approximation. The availability of a continuous solution is important not only to the user of the software but also within the code itself, for example, in estimation of errors, defect control, mesh selection, and the provision of initial solution estimates for new meshes. An approach for the construction of a continuous solution approximation based on the MIRK schemes is suggested by recent work in the area of continuous extensions for explicit Runge-Kutta schemes for initial value ODEs. In this paper, we describe our work in the investigation of continuous versions of the MIRK schemes: (i) we give some lower bounds relating the stage order to the minimal number of stages for general continuous IRK schemes, (ii) we establish lower bounds on the number of stages needed to derive continuous MIRK schemes of orders 1 through 6, and (iii) we provide characterizations of these schemes having a minimal number of stages for each of these orders.

**[1]**U. Ascher, J. Christiansen, and R. D. Russell,*Collocation software for boundary value ODE's*, ACM Trans. Math. Software**7**(1981), 209-222.**[2]**G. Bader and U. Ascher,*A new basis implementation for a mixed order boundary value ODE solver*, SIAM J. Sci. Statist. Comput.**8**(1987), no. 4, 483–500. MR**892301**, 10.1137/0908047**[3]**W. M. G. van Bokhoven,*Efficient higher order implicit one-step methods for integration of stiff differential equations*, BIT**20**(1980), no. 1, 34–43. MR**569974**, 10.1007/BF01933583**[4]**David L. Brown and Jens Lorenz,*A high-order method for stiff boundary value problems with turning points*, SIAM J. Sci. Statist. Comput.**8**(1987), no. 5, 790–805. MR**902743**, 10.1137/0908067**[5]**Kevin Burrage,*A special family of Runge-Kutta methods for solving stiff differential equations*, BIT**18**(1978), no. 1, 22–41. MR**0483458****[6]**K. Burrage, F. H. Chipman, and P. H. Muir,*Order results for mono-implicit Runge-Kutta methods*, SIAM J. Numer. Anal.**31**(1994), no. 3, 876–891. MR**1275118**, 10.1137/0731047**[7]**J. C. Butcher,*Coefficients for the study of Runge-Kutta integration processes*, J. Austral. Math. Soc.**3**(1963), 185–201. MR**0152129****[8]**J. C. Butcher,*Implicit Runge-Kutta processes*, Math. Comp.**18**(1964), 50–64. MR**0159424**, 10.1090/S0025-5718-1964-0159424-9**[9]**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****[10]**J. R. Cash,*Numerical integration of nonlinear two-point boundary value problems using iterated deferred corrections. I. A survey and comparison of some one-step formulae*, Comput. Math. Appl. Ser. A**12**(1986), no. 10, 1029–1048. MR**862027****[11]**J. R. Cash,*On the numerical integration of nonlinear two-point boundary value problems using iterated deferred corrections. II. The development and analysis of highly stable deferred correction formulae*, SIAM J. Numer. Anal.**25**(1988), no. 4, 862–882. MR**954789**, 10.1137/0725049**[12]**J. R. Cash and D. R. Moore,*A high order method for the numerical solution of two-point boundary value problems*, BIT**20**(1980), no. 1, 44–52. MR**569975**, 10.1007/BF01933584**[13]**J. R. Cash and A. Singhal,*Mono-implicit Runge-Kutta formulae for the numerical integration of stiff differential systems*, IMA J. Numer. Anal.**2**(1982), no. 2, 211–227. MR**668593**, 10.1093/imanum/2.2.211**[14]**J. R. Cash and A. Singhal,*High order methods for the numerical solution of two-point boundary value problems*, BIT**22**(1982), no. 2, 184–199. MR**672130**, 10.1007/BF01944476**[15]**J. R. Cash and M. H. Wright,*A deferred correction method for nonlinear two-point boundary value problems: implementation and numerical evaluation*, SIAM J. Sci. Statist. Comput.**12**(1991), no. 4, 971–989. MR**1102418**, 10.1137/0912052**[16]**G. Dahlquist and R. Jeltsch,*Generalized disks of contractivity for explicit and implicit Runge-Kutta methods*, Technical Report TRITA-NA-7906, The Royal Institute of Technology, Stockholm, 1979.**[17]**W. H. Enright, K. R. Jackson, S. P. Nørsett, and P. G. Thomsen,*Interpolants for Runge-Kutta formulas*, ACM Trans. Math. Software**12**(1986), no. 3, 193–218. MR**889066**, 10.1145/7921.7923**[18]**W. H. Enright and P. H. Muir,*Efficient classes of Runge-Kutta methods for two-point boundary value problems*, Computing**37**(1986), no. 4, 315–334 (English, with German summary). MR**869728**, 10.1007/BF02251090**[19]**-,*A mono-implicit Runge-Kutta type BVODE code with defect control*, SIAM J Sci. Statist. Comput. (submitted).**[20]**I. Gladwell, L. F. Shampine, L. S. Baca, and R. W. Brankin,*Practical aspects of interpolation in Runge-Kutta codes*, SIAM J. Sci. Statist. Comput.**8**(1987), no. 3, 322–341. MR**883774**, 10.1137/0908038**[21]**Suchitra Gupta,*An adaptive boundary value Runge-Kutta solver for first order boundary value problems*, SIAM J. Numer. Anal.**22**(1985), no. 1, 114–126. MR**772887**, 10.1137/0722008**[22]**Heinz-Otto Kreiss, N. K. Nichols, and David L. Brown,*Numerical methods for stiff two-point boundary value problems*, SIAM J. Numer. Anal.**23**(1986), no. 2, 325–368. MR**831622**, 10.1137/0723023**[23]**M. Lentini and V. Pereyra,*An adaptive finite difference solver for nonlinear two-point boundary problems with mild boundary layers*, SIAM J. Numer. Anal.**14**(1977), no. 1, 94–111. Papers on the numerical solution of two-point boundary-value problems (NSF-CBMS Regional Res. Conf., Texas Tech Univ., Lubbock, Tex., 1975). MR**0455420****[24]**S. P. Nørsett,*Semi-explicit Runge-Kutta methods*, Mathematics and Computation No. 6/74, University of Trondheim, 1974.**[25]**S. P. Nørsett and G. Wanner,*Perturbed collocation and Runge-Kutta methods*, Numer. Math.**38**(1981/82), no. 2, 193–208. MR**638444**, 10.1007/BF01397089**[26]**Brynjulf Owren and Marino Zennaro,*Order barriers for continuous explicit Runge-Kutta methods*, Math. Comp.**56**(1991), no. 194, 645–661. MR**1068811**, 10.1090/S0025-5718-1991-1068811-2**[27]**Brynjulf Owren and Marino Zennaro,*Derivation of efficient, continuous, explicit Runge-Kutta methods*, SIAM J. Sci. Statist. Comput.**13**(1992), no. 6, 1488–1501. MR**1185658**, 10.1137/0913084**[28]**Steven Pruess,*Interpolation schemes for collocation solutions of two-point boundary value problems*, SIAM J. Sci. Statist. Comput.**7**(1986), no. 1, 322–333. MR**819474**, 10.1137/0907021**[29]**J. Verner,*Differentiable interpolants for high-order Runge-Kutta methods*, Technical Report 1990-9, Queen's University, 1990.**[30]**Richard Weiss,*The application of implicit Runge-Kutta and collection methods to boundary-value problems*, Math. Comp.**28**(1974), 449–464. MR**0341881**, 10.1090/S0025-5718-1974-0341881-2**[31]**M. Zennaro,*Natural continuous extensions of Runge-Kutta methods*, Math. Comp.**46**(1986), no. 173, 119–133. MR**815835**, 10.1090/S0025-5718-1986-0815835-1**[32]**Marino Zennaro,*Natural Runge-Kutta and projection methods*, Numer. Math.**53**(1988), no. 4, 423–438. MR**951323**, 10.1007/BF01396327

Retrieve articles in *Mathematics of Computation*
with MSC:
65L06,
34A50

Retrieve articles in all journals with MSC: 65L06, 34A50

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1993-1195425-8

Keywords:
Runge-Kutta methods,
boundary value ODEs,
continuous extensions

Article copyright:
© Copyright 1993
American Mathematical Society