Derivation of third order Runge–Kutta methods (ELDIRK) by embedding of lower order implicit time integration schemes for local and global error estimation

The mathematical modeling of several engineering problems requires the numerical solution of ordinary differential equations. Typical examples for a first order ordinary differential equation are the resulting heat equation discretized in space or inelastic constitutive equations, whilst structural dynamic problems lead to examples of second order ordinary differential equations, see e.g. [16, 33]. Choosing the appropriate integration method requires deciding on aspects such as the order of the integration scheme, stability properties and computational efficiency. A general class of algorithms is provided by so-called S-stage Runge–Kutta methods (RK-methods), where explicit and implicit schemes are distinguished, [5, 10, 19]. Due to the properties of A-stability, where the region of absolute stability is unbounded, see e.g. [19], and relatively low computational cost, the implicit Euler-method and the generalized trapezoidal-rule are most prominent integration schemes in structural mechanics, see e.g. [16, 33]. Also the second order Ellsiepen method [7], with the additional property of L-stability, proved to be very efficient for the laser beam simulation in additive manufacturing processes, see e.g. [28, 29].

A main focus of the paper is the derivation of reliable a posteriori local error estimates, which are essential for the two aims, Regarding the above mentioned first aim, to bound the local error, two concepts are distinguished for the calculation of a posteriori local error estimates: firstly, by means of higher order methods and secondly by means of extrapolation methods, see e.g. [19] on general information and [23] on applications for creep analysis with the finite element method. In line with the first concept, Fehlberg suggested a strategy for stepsize selection by so-called embedded Runge–Kutta methods, [11‐13]. The novelty of Fehlberg’s method is that the applied integration scheme is embedded by a second method with higher order, however, identical Runge–Kutta coefficients. As a consequence only one extra function calculation is required to estimate the local error of the embedded method. Thereupon, several embedded embedded Runge–Kutta schemes have been developed. For example Bogacki and Shampine [3] present a Runge–Kutta method of order three with four stages in order to embed a second-order method. A recent paper [14] investigates strong stability properties of embedded pairs of RK-methods, however, restricted to explicit methods.

A slightly different embedding compared to Fehlbergs explicit schemes has been given by Ellsiepen [7] with Butcher arrayThis array defines an embedded RK-method, subsequently denoted as RK(2)1-Ell, combining a method RK2-Ell (using \(\alpha \) below the horizontal line) of order 2 with embedded method RK1-Ell of order 1 (using \(\beta \)) [7]. Both methods have the same stage and, different to Fehlbergs explicit schemes, both methods are implicit. Exploiting both choices below the horizontal line has the consequence, that even for nonlinear problems no additional functional evaluation becomes necessary for local error estimation.

This paper intends to combine the advantage of Fehlsbergs embedding approach with only one additional functional evaluation to obtain a local error estimate, with the advantages of A-stability and relatively low computational cost of low order implicit methods. In order to avoid an additional solution of a system of equations we introduce a certain class of RK-methods labeled as ELDIRK. These methods are defined to have an explicit last stage in the general Butcher array of Diagonal Implicit Runge–Kutta (DIRK) methods, contrary to the class of EDIRK, where according to Kværnø et al. [18] the RK-methods have an explicit first stage in the general Butcher array

In addition to Mahnken [22], a general approach for the construction of third order ELDIRK-methods is presented by embedding some well known low order implicit time integration schemes. The proposed methodology is applied to embed the first order implicit Euler-method, the second order trapezoidal rule and the second order Ellsiepen method by a third order scheme. As main results, two extra function calculations are required in order to embed the implicit Euler-method and one extra function calculation is required for both, the trapezoidal-rule and Ellsiepen’s method, in order to obtain the third order properties. In this way, we will extend the Butcher array in Eq. (1) to obtain a new method RK3-Ell of order 3 in order to embed RK2-Ell of order 2 with only one additional function evaluation. As verified in the numerical examples in Sect. 7, the higher order properties for all new ELDIRK-methods with only one (and respectively two) additional function evaluation(s) are obtained for both linear as well as for nonlinear ordinary differential equations.

Two different types of embedded RK-methods are distinguished in the literature. The original embedded RK-method explained above will subsequently be termed standard embedded RK-method. For its variation, the roles of embedded and improved solutions are simply reversed, see [19, p. 108], and therefore this method will subsequently be denoted as reversed embedded RK-method.

Regarding the above mentioned second aim of local error estimates, to contribute to an estimate of the global error, we follow closely the procedure recently presented in [22]. Here, we consider an estimate for the global error measure obtained from a quantity of interest, for both, the standard embedded and the reversed embedded RK-method. This strategy avoids the solution of a dual problem as performed e.g. in [25]. The dual problem runs backwards in time [2, 17, 21, 31], which due to additional storage requirements might become a serious drawback when applied e.g. to FEM or respectively to FDM simulations. Moreover, in [22], we perform a linearisation of the quantity of interest, related to both embedded RK-methods, in order to investigate the corresponding effectivity indices with the following main results: The error estimate for the standard RK-method approaches \( I_\mathrm{\tiny eff}= \kappa \) in the limit. Here \(\kappa \) is a constant, which can be above or below one, meaning, the error can be over- or underestimated. The effectivity index for the reversed RK-method approaches \( I_\mathrm{\tiny eff}= 1\) in the limit, meaning that this error estimate is asymptotically exact. In this work, these results are verified numerically, for all new RK-schemes developed in this paper.

The structure of the paper is as follows: Sect. 2 summarises some preliminaries on numerical time integration of systems of ordinary equations with RK-methods including a posteriori error estimation. Here also, the class of ELDIRK-methods is introduced. Moreover, we will recall the order conditions from [4, 6] to guarantee a certain convergence order of an RK-method. In Sects. 3 and 4 we present a general approach for the construction of second order embedding ELDIRK-methods and third order embedding ELDIRK-methods, respectively. The methodology is applied to three prominent low order implicit integration schemes, that is the implicit Euler-method, the generalized trapezoidal-rule and Ellsiepen’s method. In this way, for each of the methods we obtain an extended Butcher tableau. Section 5 provides a brief revision of goal oriented error measures introduced in [22], and the asymptotic behaviour of error estimates for the standard embedded and the reversed embedded RK-methods. Two numerical examples in Sect. 6 are concerned with a parachute with viscous damping and a two-dimensional laser beam simulation. Here, we illustrate the higher order convergence behaviour for equidistant step sizes of the proposed new Runge–Kutta methods. Finally, a summary of the main results of this paper and an outlook for future work are given in Sect. 7.

This section intends to provide a brief summary of goal oriented global temporal error measures introduced in [22], and its asymptotic behaviour for standard embedded RK(r)q in Eq. (12) and for reversed embedded RK(q)r in Eq. (13)

Global temporal error estimation can be achieved within a mathematically sound way by means of two functionals as originally proposed for partial differential equations, see e.g. [2, 8, 27, 30, 36]: Firstly, a weak form for temporal discretization of the underlying initial value problem (IVP), and, secondly, a quantity of interest (QoI) or goal function, respectively, which enables to measure the related global error. For the temporal discretization, the former can be obtained as a weak Petrov-Galerkin formulation. Here the concept of the finite element method for space discretizations is adapted to the time domain, originally introduced in [1, 15, 26]. To this end the underlying differential equation (2) is reformulated into a corresponding weak form by a premultiplication with a test function and an integration over the time domain \(I\). The solution functions as well as the test functions are then approximated by means of appropriate interpolations. Conventionally, discontinuous Galerkin (dG) and continuous Galerkin (cG) methods are distinguished, see e.g. [8]. Eventually, the weak form enables to derive RK-schemes which result into the Butcher array (7). A simple example is e.g. given in [35] for the backward (implicit) Euler scheme. Regarding the mathematical details for derivation of a general explicit \(S\)-stage RK-method on the basis of a weak form the interested reader is referred e.g. to Muñoz-Matute et al. [25]. The QoI approach offers a great flexibility on global error estimation, since the goal function is a user specified quantity, see e.g. [17, 21].

In this section, a global error estimate is obtained directly from a quantity of interest, for both, the standard embedded and the reversed embedded RK-method by means of the functional representation for the weak form. This strategy avoids the solution of a dual problem as performed e.g. in [25]. The dual problem runs backwards in time [2, 17, 21, 31], which due to additional storage requirements might become a serious drawback when applied e.g. to FEM or respectively to FDM simulations.

In the following, numerical results of the algorithms summarized in Table  3, the embedded implicit Euler method RK(3)2-Eul, the embedded trapezoidal rule RK(3)2-Trap and the embedded Ellsiepen method RK(3)2-Ell are presented for two test problems: Firstly, a parachute with viscous damping and, secondly, a laser beam simulation with the finite difference method. Results are presented for equidistant step lengths as well as for non-equidistant step lengths based on adaptive time-step control. We will also verify the expected order properties of the new third order ELDIRK methods RK3-Eul, RK3-Trap and RK3-Ell, and we will present results for the reversed embedded Runge–Kutta methods, denoted as RK(2)3-Eul, RK(2)3-Trap and RK(2)3-Ell. Thereby, the nonlinear equations resulting from the implicit RK-schemes are solved with a Newton method, as explained in [22].

For comparison, we present also results for the embedded RK-method of Ellsiepen according to Eq. (1) [7], denoted as RK(2)1-Ell. As explained before, both RK1-Ell and RK2-Ell are implicit, however, the Newton method iterates on the same slopes \(\underline{\textrm{k}}_{j}\), which satisfy a residual obtained from Eq. (5.2). In analogy to previous notations, RK(1)2-Ell denotes the corresponding reversed RK-method.

For both, standard embedded RK(r)q and reversed embedded RK(q)r the error measure in Eq. (51.2) is investigated. Thus, by means of the notation \(\cdot _N:= \cdot (t_N)\) and a 2-norm, for standard embedded RK(r)q the following three global error functions are introduced:with global error estimate \({\underline{\mathrm{{\eta }}}}_N^{{{r}},{{q}}} \) according to Eq. (46.3). We will verify the result \( \lim \nolimits _{\tau \rightarrow 0} I_\mathrm{\tiny eff}^{{{q}}}= \kappa \) in Eq. (54). For reversed embedded RK(q)r the following three global error functions are introduced:with global error estimate \({\underline{\mathrm{{\eta }}}}_N^{{{q}},{{r}}} \) according to Eq. (55.3). We will verify the result \( \lim \nolimits _{\tau \rightarrow 0} \left| I_\mathrm{\tiny eff}^{{{q}},{{r}}} \right| = 1 \) in Eq. (59). As an alternative to the above time point goal function, results for a time integrated goal function are presented in [22].

In this paper we have proposed a general approach to embed low order implicit time integration methods into third order Runge–Kutta schemes. In order to obtain a systematic representation for the higher order methods, we introduce the notion of ELDIRK-methods. These are defined to have an explicit last stage in the general Butcher tableau, contrary to the class of EDIRK methods, which according to Kværnø et al. [18] have an explicit first stage in the general Butcher array. The consequence is, that there is no need to solve an additional nonlinear system of equations for the ELDIRK-method compared to the embedded schemes. This feature holds for linear as well as for nonlinear ordinary differential equations.

The approach has been applied to three prominent low order implicit methods, that is, the implicit Euler-method, the trapezoidal-rule and the Ellsiepen method. In this way, for each of the methods we obtain an extended Butcher tableau.

The new embedded standard RK-methods, RK(3)2-Eul, RK(3)2-Trap and RK(3)2-Ell and the reversed methods RK(2)3-Eul, RK(2)3-Trap and RK(2)3-Ell have been tested extensively in two numerical examples: Firstly, a parachute with viscous damping and, secondly, two-dimensional temperature evolution due to laser beam movement, and they have been compared to the RK(2)1 method of Ellsiepen [7], Eq. (1) in this work. For both examples it has been verified, that with only two additional function evaluations for RK1-Eul, the ELDIRK-method RK3-Eul attains the third order properties. Similarly, third order properties are obtained for the new ELDIRK-methods RK3-Trap and respectively for RK3-Ell with only one additional function evaluation for RK2-Trap and respectively for RK2-Ell. We point out, that this behaviour holds also for nonlinear IVPs.

Concerning further extensions, being only half implicit, a stability analysis of all new ELDIRK-methods is of interest. Also, strategies to control the global error, see e.g. [21], should be considered for embedded RK-methods, based on the proposed global error measures of [22] and recalled in this work.