Abstract
This paper reviews strong stability preserving discrete variable methods for differential systems. The strong stability preserving Runge–Kutta methods have been usually investigated in the literature on the subject, using the so-called Shu–Osher representation of these methods, as a convex combination of first-order steps by forward Euler method. In this paper, we revisit the analysis of strong stability preserving Runge–Kutta methods by reformulating these methods as a subclass of general linear methods for ordinary differential equations, and then using a characterization of monotone general linear methods, which was derived by Spijker in his seminal paper (SIAM J Numer Anal 45:1226–1245, 2007). Using this new approach, explicit and implicit strong stability preserving Runge–Kutta methods up to the order four are derived. These methods are equivalent to explicit and implicit RK methods obtained using Shu–Osher or generalized Shu–Osher representation. We also investigate strong stability preserving linear multistep methods using again monotonicity theory of Spijker.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
It is a purpose of this paper to systematically investigate strong stability preserving (SSP) Runge-Kutta (RK) methods and linear multistep methods (LMMs), for numerical solution of initial-value problems for ordinary differential equations (ODEs)
where the function \(f:{{\mathbb {R}}}\times {{\mathbb {R}}}^m\rightarrow {{\mathbb {R}}}^m\) is assumed to be sufficiently smooth. To define SSP property of numerical schemes, we assume that the discretization of (1.1) by the forward Euler method
\(n=1,2,\ldots ,N\), \(Nh=t_\textrm{end}-t_0\), \(t_n=t_0+nh\), satisfies the condition
\(n=1,2,\ldots ,N\), in some norm or semi-norm \(\Vert \cdot \Vert \), for all stepsizes h such that
We then search for methods, which preserve the monotonicity property (1.3) of the forward Euler method (1.2) under the restriction on the stepsize h, of the form
We discuss first explicit RK methods. Such methods, in Butcher representation, take the form
\(n=1,2,\ldots ,N\), and can be represented by the Butcher table
RK formulas (1.6) which satisfy (1.3) under the restriction (1.5) are called SSP RK methods, and the constant \({\mathcal {C}}\) is called SSP coefficient. To compare schemes with different number of stages s, we also define the effective SSP coefficient \({\mathcal {C}}_\textrm{eff}\) by
As discussed in [12, 14], the search for explicit SSP RK methods (1.6) is facilitated by SSP revealing representation of these methods as convex combinations of forward Euler steps. This so-called Shu–Osher representation proposed in [35], has the form
\(n=1,2,\ldots ,N\), where \(\alpha _{ij}\) are scalars such that
and \(\beta _{ij}\) are given by
The Shu–Osher representation of RK methods (1.6) is not unique, and the SSP coefficient of (1.7), which depends on the choice of \(\alpha _{ij}\), subject to (1.8), and the resulting \(\beta _{ij}\), can be characterized by the following result, essentially due to Shu and Osher [35] (see also [12, 14]).
Theorem 1.1
Assume that the forward Euler method (1.2) applied to (1.1) is strongly stable, i.e., the inequality (1.3) holds under the time step restriction (1.4). Assume also that \(\alpha _{ij}\ge 0\) and \(\beta _{ij}\ge 0\). Then, the solution \(\{y_n\}\) obtained by the RK method (1.6) or (1.7) satisfies the strong stability bound (1.3) under the time step restriction (1.5) with SSP coefficient \({\mathcal {C}}={\mathcal {C}}(\alpha ,\beta )\) given by
It is also possible to characterize SSP coefficient of (1.7) if some of the \(\beta _{ij}\) are negative, and we refer to the monograph [12] for such results.
A lot of work was devoted to finding explicit SSP RK methods with large SSP coefficients both by mathematical analysis, for low order methods, and numerical searches, for higher order schemes. Most of these numerical searches were based on formulation the appropriate optimization problems using Shu–Osher representation of RK methods, and the characterization of SSP coefficient formulated in Theorem 1.1.
In this paper, we will search for explicit and implicit SSP RK formulas using a different approach than that used in [12, 14], and which is based on monotonicity theory of general linear methods (GLMs) developed by Spijker [36]. In this approach we first reformulate RK methods in Butcher representation (1.6) as GLMs examined in [36], and then reformulate the appropriate optimization problems in terms of the abscissa vector \(\textbf{c}\), the coefficient matrix \(\textbf{A}\), and the weight vector \(\textbf{b}\).
The organization of this paper is as follows. In Sect. 2 we review generalized Shu–Osher representation introduced by Ferracina and Spijker [10], which can be used to investigate implicit SSP RK methods. The monotonicity theory for GLMs developed by Spijker [36] is reviewed in Sect. 3, and the resulting monotonicity theory for RK methods, as well as the formulation of appropriate minimization problems for computing explicit and implicit SSP RK methods, is described in Sect. 4. In Sect. 5, we analyze explicit and in Sect. 6, implicit SSP RK methods obtained by solving the minimization problems described in Sect. 4. We present examples of explicit SSP RK methods of order \(p=1\), of order \(p=2\) with \(s=2,3,\ldots ,10\) stages, of order \(p=3\) with \(s=3,4,\ldots ,10\) stages, and of order \(p=4\) with \(s=4,5,\ldots ,10\) stages, and implicit SSP RK methods up to the order \(p=4\). In Sect. 7, we analyze SSP LMMs, and examples of explicit and implicit SSP LMMs of order \(p=2\), \(p=3\), and \(p=4\), are presented in Sects. 8 and 9. Finally, in Sect. 10, some concluding remarks are given.
2 A Generalization of the Shu–Osher Representation of RK Methods
As discussed in Sect. 1, the SSP properties of explicit RK methods can be investigated using the Shu–Osher representation (1.9), and SSP coefficient of these methods is characterized in Theorem 1.1. It was proved in [14] that if implicit RK method has order \(p>1\), then the coefficients \(\alpha _{ij}\) of its Shu–Osher representation (1.9) cannot be all nonnegative. Hence, this representation cannot be used to find implicit SSP methods of order greater than one. SSP properties of implicit RK methods are usually investigated using a generalization of Shu–Osher representation introduced by Ferracina and Spijker [10] (see also [12, 18]). For RK methods with s stages, this representation takes the form
\(n=1,2,\ldots ,N\). Here, \(\lambda _{ij}\) and \(\mu _{ij}\) are real coefficients. Following [10], we introduce the matrices
and
The generalized Shu–Osher representation (2.1) of implicit RK method is not unique. Assuming that the coefficient matrices \(\textbf{L}\) and \(\textbf{M}\) are given and that the matrix \(\textbf{I}-\textbf{L}_0\) is nonsingular, the Butcher representation of RK method
can be computed from the formulas
where \(\textbf{I}\) is the identity matrix of dimension s, and \(\textbf{e}=[1,\ldots ,1]\in {{\mathbb {R}}}^s\). Similarly, if Butcher representation \((\textbf{c},\textbf{A},\textbf{b})\) of RK method is given, to compute the generalized Shu–Osher representation (2.1) we have to choose the coefficient matrices \(\textbf{L}_0\) and \(\textbf{L}_1\), and then compute the coefficient matrices \(\textbf{M}_0\) and \(\textbf{M}_1\) from the formulas
We have the following generalization of the Shu–Osher Theorem 1.1, which follows from the results of Ferracina and Spijker [11].
Theorem 2.1
Assume that the forward Euler method (1.2) applied to (1.1) is strongly stable, i.e., the inequality (1.3) holds under the time step restriction (1.4). Assume also that \(\textbf{I}-\textbf{L}_0\) is invertible and
Then, the solution \(\{y_n\}\) obtained by the implicit RK method (2.1) or (2.2) satisfies the strong stability bound (1.3) under the time step restriction (1.5) with SSP coefficient \({\mathcal {C}}={\mathcal {C}}(\textbf{A},\textbf{b},\textbf{L})\) given by
3 Monotonicity Theory for GLMs
Consider a class of GLMs of the form
\(n=1,2,\ldots ,N\), \(1\le \ell \le m\). In this formulation \(Y_i^{[n]}\), \(i=1,2,\ldots ,m\), are internal approximations or stages, which are used to compute external approximations \(y_i^{[n]}\), \(i=1,2,\ldots ,\ell \), which propagate from step to step. The formulation (3.1), which was considered by Spijker [36], is specified by the abscissa vector \(\textbf{c}=[c_1,\ldots ,c_m]^T\in {{\mathbb {R}}}^m\), and two coefficient matrices \(\textbf{T}=[t_{ij}]\in {{\mathbb {R}}}^{m\times m}\) and \(\textbf{S}=[s_{ij}]\in {{\mathbb {R}}}^{m\times \ell }\), where it is assumed, without loss of generality, that
This representation is not the most common one, and different representations of GLMs are discussed by Burrage [2], Butcher [3, 4, 6], Hairer et al. [15], Hairer and Wanner [16], Jackiewicz [24], and Wright [37].
Following the definition in [36], the GLM (3.1) is said to be monotonic if
where \(Y_i^{[n]}\) and \(y_j^{[n-1]}\) satisfy (3.1). Denote by \(\textbf{I}\) the identity matrix of dimension s, and, as in [36], let \(\big [\textbf{S}\mid \gamma \textbf{T}\big ]\), \(\gamma \in {{\mathbb {R}}}\), be the \(s\times (\ell +s)\) matrix whose first \(\ell \) columns are equal to \(\textbf{S}\), and the last s columns are equal to \(\gamma \textbf{T}\). Consider the condition
where the inequality in (3.4) should be interpreted componentwise. Then the following theorem, which characterizes the SSP coefficient of GLMs (3.1) can be deduced from the results of [36].
Theorem 3.1
Assume that the forward Euler method (1.2) applied to (1.1) is strongly stable, i.e., the inequality (1.3) holds under the time step restriction (1.4). Then the solution \(\{Y_i^{[n]}\}\) and \(\{y_i^{[n-1]}\}\) obtained by the GLM (3.1) satisfies (3.3) under the time step restriction (1.5) with SSP coefficient \({\mathcal {C}}={\mathcal {C}}(\textbf{T},\textbf{S})\) given by
It follows from this theorem that the coefficients of GLMs (3.1), and the corresponding SSP coefficient, can be computed by solving the minimization problem
with a very simple objective function \(F(\textbf{T},\textbf{S}):=-\gamma \), subject to the nonlinear inequality constrains (3.4), and to equality constrains
Here, \(\Phi _{p,q}(\textbf{T},\textbf{S})=0\) represents conditions for order p and stage order q. Such order and stage order conditions for GLMs, in different representations, were investigated in [3,4,5, 8, 15]. The approach based on solving the minimization problem (3.6), subject to constrains (3.4) and (3.7), was used in [7, 21,22,23] to investigate some classes of SSP GLMs up to the order \(p=4\). SSP GLMs were also investigated in [9, 19, 29]. SSP two-step RK methods were investigated in [27], and multistep RK methods in [1].
4 Monotonicity Theory for RK Methods
In this section, we apply the monotonicity theory of GLMs (3.1) presented in [36], and summarized in Theorem 3.1, to the special case of explicit RK methods in Butcher representation. It can be verified that the RK method (1.6) given by the abscissa vector \(\textbf{c}=[c_1,\ldots ,c_s]^T\in {{\mathbb {R}}}^s\), coefficient matrix \(\textbf{A}=[a_{ij}]\in {{\mathbb {R}}}^{s\times s}\), and weight vector \(\textbf{b}=[b_1,\ldots ,b_s]^T\in {{\mathbb {R}}}^s\), can be written as GLM (3.1) with \(m=s+1\), \(\ell =1\), and the coefficient matrices \(\textbf{T}\) and \(\textbf{S}\) defined by
where \(\textbf{e}=[1,\ldots ,1]^T\in {{\mathbb {R}}}^s\). Observe that for this representation the condition (3.2) is automatically satisfied. Putting \(y_1^{[n-1]}=y_{n-1}\) and \(y_1^{n]}=y_n\), the RK method (1.6) takes now the form
\(n=1,2,\ldots ,N\). For the representation (4.2), the monotonicity condition (3.3) takes the form
In particular, for \(i=s+1\), we have \(Y_{s+1}^{[n]}=y_n\), and the condition (4.3) implies the condition (1.3).
We will reformulate next the nonlinear inequality constrains (3.4), the characterization of SSP coefficient given by the condition (3.5) in Theorem 3.1, and the minimization problem (3.6) in terms of the coefficients \(\textbf{c}\), \(\textbf{A}\), and \(\textbf{b}\), of RK method (1.6). We have
and it follows that \(\det (\textbf{I}+\gamma \textbf{T})\ne 0\) if \(\textbf{A}\) is strictly lower triangular, which is the case for explicit RK methods, or if \(\textbf{A}\) is lower triangular with nonzero entries on the diagonal, which is the case for diagonally implicit RK methods. We have also
and it follows that
Since
we obtain
It follows from \(\det (\textbf{I}+\gamma \textbf{T})\ne 0\) and the above relation that the condition (3.4) is equivalent to
We summarize the above discussion in the following theorem.
Theorem 4.1
Assume that the forward Euler method (1.2) applied to (1.1) is strongly stable, i.e., the inequality (1.3) holds under the time step restriction (1.4). Then the solution \(\{Y_i^{[n]}\}\) and \(\{y_{n-1}\}\) obtained by the RK method (4.2) satisfies (4.3) (hence also (1.3)) under the time step restriction (1.5) with SSP coefficient \({\mathcal {C}}={\mathcal {C}}(\textbf{c},\textbf{A},\textbf{b})\) given by
It follows from this theorem that, similarly as for GLMs (3.1), the coefficients of RK methods (1.6) or (4.2), and the corresponding SSP coefficient, can be computed by solving the minimization problem
subject to the nonlinear inequality constrains (4.4), and the equality constrains
Here, \(\Phi _p(\textbf{c},\textbf{A},\textbf{b})=0\) stands for order conditions for RK methods up to the order p. Such conditions are discussed in the monographs [3, 4, 15].
5 Explicit SSP RK Methods
In this section, we analyze explicit SSP RK methods. Examples of such methods, up to the order \(p=4\) with \(s\le 10\) stages, are obtained by solving the minimization problem (4.6), subject to the inequality constrains (4.4), and the equality constrains (4.7).
5.1 Explicit SSP RK Methods of Order \(p=1\)
The explicit RK method of order \(p=1\) with \(s=1\) stages corresponds to the forward Euler method (1.2), for which \(\textbf{c}=0\), \(\textbf{A}=0\), \(\textbf{b}=1\),
For this method the condition \(\det (\textbf{I}+\gamma \textbf{T})\ne 0\) is automatically satisfied, and the inequalities (4.4) reduce to
This leads, as expected, to \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}=1\).
5.2 Explicit SSP RK Methods of Order \(p=2\)
In this section, we will search for explicit SSP RK methods of order \(p=2\) with \(s\ge 2\) stages. Solving the minimization problem (4.6) with inequality constrains (4.4) and equality constrains (4.7) corresponding to \(p=2\) leads to RK methods with
For these methods \({\mathcal {C}}=s-1\) and \({\mathcal {C}}_\textrm{eff}=(s-1)/s\). We have listed in Table 1 SSP coefficients \({\mathcal {C}}\) and \({\mathcal {C}}_\textrm{eff}\), intervals of absolute stability, and areas of regions of absolute stability for RK methods of order \(p=2\) with \(s=2,3,\ldots ,10\), stages. We have also plotted on Fig. 1 stability regions of these methods and on Fig. 2 scaled stability regions obtained by multiplying the points on the boundary of regions of absolute stability by p/s, where p is the order and s is the number of stages. These regions increase in size as s ranges from 2 to 10. On these figures stability regions of SSP RK method with \(p=s=2\) are plotted by a thick line.
5.3 Explicit SSP RK Methods of Order \(p=3\)
We will search for explicit SSP RK methods of order \(p=3\) with \(s=3,4,\ldots ,10\), stages. Solving the minimization problem (4.6) with constrains (4.4) and (4.7) corresponding to \(p=s=3\), we obtain the method whose Butcher representation is
and for which \({\mathcal {C}}=1\) and \({\mathcal {C}}_\textrm{eff}=1/3\). It can be verified that this method is equivalent to the Shu–Osher method SSPRK(3,3)
described in Theorem 2.3 in [12].
Solving the minimization problem (4.6) with constrains (4.4) and (4.7) corresponding to \(p=3\) and \(s=4\), we obtain the method whose Butcher representation is
For this method \({\mathcal {C}}=2\) and \({\mathcal {C}}_\textrm{eff}=1/2\).
The coefficients of methods obtained by solving the minimization problem (4.6) with constrains (4.4) and (4.7) corresponding to \(p=3\) and \(s=5,6,\ldots ,10\), are not listed here, but can be obtained from the authors. We have listed in Table 2 SSP coefficients \({\mathcal {C}}\) and \({\mathcal {C}}_\textrm{eff}\), interval of absolute stability, and areas of regions of absolute stability for RK methods of order \(p=3\) with \(s=3,4,\ldots ,10\), stages. We have also plotted on Fig. 3 stability regions of these methods and on Fig. 4 scaled stability regions obtained by multiplying the points on the boundary of regions of absolute stability by p/s, where p is the order and s is the number of stages. As for methods of order two these regions increase in size as s ranges from 3 to 10. On these figures stability regions of SSP RK method with \(p=s=3\) are plotted by a thick line.
5.4 Explicit SSP RK Methods of Order \(p=4\)
In this section we will search for explicit SSP RK methods of order \(p=4\) with \(s=4,5,\ldots ,10\), stages. It was proved in [13, 30] that explicit SSP RK methods with \(s=4\) stages do not exist, and this was also confirmed by our numerical searches. Solving the minimization problem (4.6) with constrains (4.4) and (4.7) corresponding to \(p=4\) and \(s=5\), we obtain the method with coefficients
For this method \({\mathcal {C}}=1.51\) and \({\mathcal {C}}_\textrm{eff}=0.30\). This methods is equivalent to SSPRK(5,4) scheme, whose Shu–Osher representation is listed in [12].
The coefficients of methods obtained by solving the minimization problem (4.6) with constrains (4.4) and (4.7) corresponding to \(p=4\) and \(s=6,7,8,9\), are not listed here, but can be obtained from the authors. The coefficients of method corresponding to \(p=4\) and \(s=10\) are given by
For this method \({\mathcal {C}}=6\) and \({\mathcal {C}}_\textrm{eff}=3/5\). This method is equivalent to the SSPRK(10,4) scheme, whose Shu–Osher representation is listed in [12]. We have listed in Table 3 SSP coefficients \({\mathcal {C}}\) and \({\mathcal {C}}_\textrm{eff}\), interval of absolute stability, and areas of regions of absolute stability for RK methods of order \(p=4\) with \(s=5,6,\ldots ,10\), stages. We have also plotted on Fig. 5 stability regions of these methods and on Fig. 6 scaled stability regions obtained by multiplying the points on the boundary of regions of absolute stability by p/s, where p is the order and s is the number of stages. We have also plotted on these figures by a thick line stability region of RK method with \(p=s=4\). As for methods of order two and three these regions increase in size as s ranges from 4 to 10.
6 Implicit SSP RK Methods
In this section, we analyze implicit SSP RK methods. Examples of such methods, up to the order \(p=4\), are obtained by solving the minimization problem (4.6), subject to the inequality constrains (4.4), and the equality constrains (4.7).
6.1 Implicit SSP RK Methods of Order \(p=1\)
The implicit RK method of order \(p=1\) with \(s=1\) stages corresponds to the backward Euler method
\(n=1,2,\ldots ,N\), for which \(\textbf{c}=1\), \(\textbf{A}=1\), \(\textbf{b}=1\),
For this method, the condition \(\det (\textbf{I}+\gamma \textbf{T})=1+\gamma \ne 0\) is satisfied for \(\gamma \ge 0\), and the inequalities (4.4) reduce to
These conditions lead to \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}=\infty \), compare [12, 28].
6.2 Implicit SSP RK Methods of Order \(p=2\)
In this section, we will search for implicit SSP RK methods of order \(p=2\) with \(s\ge 2\) stages. Solving the minimization problem (4.6) with inequality constrains (4.4) and equality constrains (4.7) corresponding to \(p=2\) leads to singly diagonally implicit RK methods with
For these methods \({\mathcal {C}}=2s\) and \({\mathcal {C}}_\textrm{eff}=2\). The stability function
of these methods takes the form \( R(z)=P(z)/Q(z), \) where P(z) and Q(z) are polynomials of degree s equal to
and
Here, \(\lambda =1/(2s)\) is the diagonal element of the coefficient matrix \(\textbf{A}\). It can be verified that the Nørsett polynomial E(y) defined by [16]
is identically equal to zero. This proves that all these methods are A-stable.
Choosing the matrix \(\textbf{L}\) to be equal to
the coefficient matrix \(\textbf{M}\) of the generalized Shu–Osher representation (2.1) takes the form
This representation was presented in [12]. As already observed, the generalized Shu–Osher representation is not unique, and for RK method of order \(p=2\) with \(s=2\) stages given by
Ferracina and Spijker [10] have chosen
which leads to
6.3 Implicit SSP RK Methods of Order \(p=3\)
In this section, we will search for implicit SSP RK methods of order \(p=3\) with \(s\ge 2\) stages. Solving the minimization problem (4.6) with inequality constrains (4.4) and equality constrains (4.7) corresponding to \(p=3\) leads to singly diagonally implicit RK methods with
For these methods \({\mathcal {C}}=s-1+\sqrt{s^2-1}\) and \({\mathcal {C}}_\textrm{eff}=(s-1+\sqrt{s^2-1})/s\).
Choosing the matrix \(\textbf{L}\) to be equal to
where
the coefficient matrix \(\textbf{M}\) of the generalized Shu–Osher representation (2.1) takes the form
where
and
This generalized Shu–Osher representation was presented in [12]. All these methods have bounded stability regions. These regions are plotted on Fig. 7 for \(p=3\) and \(s=2,3,\ldots ,10\), and the scaled stability regions, obtained by multiplying points on the boundary of these regions by p/s are plotted on Fig. 8. These regions increase in size as s ranges from 2 to 10.
6.4 Implicit SSP RK Methods of Order \(p=4\)
In this section, we will search for implicit SSP RK methods of order \(p=4\) with \(s\ge 3\) stages. Solving the minimization problem (4.6) with inequality constrains (4.4) and equality constrains (4.7) corresponding to \(p=4\) and \(s=3\) leads to diagonally implicit RK methods with coefficients given by
For this method \({\mathcal {C}}=2.05\) and \({\mathcal {C}}_\textrm{eff}=0.68\). The generalized Shu–Osher representation of this method is presented in [12].
Solving the minimization problem (4.6) with inequality constrains (4.4) and equality constrains (4.7) corresponding to \(p=4\) and \(s=4\) leads to diagonally implicit RK methods with coefficients given by
For this method \({\mathcal {C}}=4.42\) and \({\mathcal {C}}_\textrm{eff}=1.11\). The generalized Shu–Osher representation of this method is presented in [12].
We have also solved the minimization problem (4.6) with inequality constrains (4.4) and equality constrains (4.7) corresponding to \(p=4\) and \(s=5,6,\ldots ,10\). The coefficients of these methods in Butcher form are not listed here, but can be obtained from the authors, and the generalized Shu–Osher representations of these methods are presented in [12].
The stability regions of these SSP RK methods of order \(p=4\) with \(s=3,4,\ldots ,10\) stages are plotted on Fig. 9 and the scaled stability regions, obtained by multiplying points on the boundary of these regions by p/s are plotted on Fig. 10. Similarly as for SSP RK methods of order \(p=3\), these regions increase in size as s ranges from 3 to 10.
Coefficients of optimal implicit SSP RK methods up to order \(p=6\) are listed in [12].
7 Linear Multistep Methods
In this section, we will analyze LMMs specified by the coefficients
where
These methods are defined by
\(n=k,k+1,\ldots ,N\), \(Nh=t_\textrm{end}-t_0\), \(t_n=t_0+nh\), where \(y_0=y(t_0),y_1,\ldots ,y_{k-1}\) are the given starting values.
The first and second characteristic polynomials of LMM (7.1) are defined by
The LMM (7.1) is said to be zero-stable if no root of the first characteristic polynomial \(\rho (\xi )\) has modulus greater than one, and if every root with modulus one is simple.
The method (7.1) has order p if and only if the following order conditions are satisfied
compare [4, 6, 15, 17, 24, 31, 32]. The relations corresponding to \(p=1\),
are usually referred to as consistency conditions. These conditions can be written in the more compact form
If \(\beta _0=0\) the method (7.1) is explicit. For such methods the following result was formulated in [12], compare also [20, 34].
Theorem 7.1
Assume that the forward Euler method (1.2) applied to (1.1) is strongly stable, i.e., the inequality (1.3) holds under the time step restriction (1.4). Then, the solution \(y_n\) and obtained by the LMM (7.1) satisfies (1.3) under the time step restriction (1.5) with SSP coefficient \({\mathcal {C}}={\mathcal {C}}(\alpha ,\beta )\) given by
We have also the following bound on the SSP coefficients of explicit LMMs.
Theorem 7.2
(Lenferink [33]) The SSP coefficient \({\mathcal {C}}(\alpha ,\beta )\) of an k step explicit LMM (7.1) of order \(p>1\) satisfies the bound
In what follows we will investigate SSP properties of LMMs (7.1) by reformulating these methods as GLMs (3.1), and then using monotonicity theory of GLMs developed by Spijker [36]. Putting
the LMM (7.1) can be written as GLM (3.1) with \(m=k+1\), \(\ell =k\), abscissa vector \(\textbf{c}\) and coefficient matrices \(\textbf{S}\) and \(\textbf{T}\) defined by
where \(\textbf{0}\) is \(k\times k\) zero matrix, 0 is \(k\times 1\) zero vector, and \(\textbf{I}\) is \(k\times k\) identity matrix. Then, \(\det (\textbf{I}+\gamma \,\textbf{T})=1+\gamma \beta _0\ne 0\) for \(\gamma \ne -1/\beta _0\),
and it follows that the conditions (3.4) take the form
We summarize the above discussion in the following theorem.
Theorem 7.3
Assume that the forward Euler method (1.2) applied to (1.1) is strongly stable, i.e., the inequality (1.3) holds under the time step restriction (1.4). Then the solution \(y_n\) and obtained by the LMM (7.1) satisfies (1.3) under the time step restriction (1.5) with SSP coefficient \({\mathcal {C}}={\mathcal {C}}(\alpha ,\beta ,\beta _0)\) given by
We have also the following bound on SSP coefficient of implicit LMMs.
Theorem 7.4
([20, 34]) The SSP coefficient \({\mathcal {C}}(\alpha ,\beta ,\beta _0)\) of implicit LMM (7.1) of order \(p>1\) satisfies the bound
It follows from Theorem 7.3 that the coefficients \(\alpha \), \(\beta \), and \(\beta _0\) of LMM (7.1), and the corresponding SSP coefficient \({\mathcal {C}}(\alpha ,\beta ,\beta _0)\), can be computed by solving the minimization problem
subject to the nonlinear inequality constrains (7.5), and the equality constrains (7.2) corresponding to the order conditions up to the order p.
8 Explicit SSP LMMs
In this section, we investigate explicit SSP LMMs up to the order \(p=4\), i.e., methods (7.1) corresponding to \(\beta _0=0\). The explicit method with \(p=1\) and \(k=1\) corresponds to the forward Euler method, and was analyzed in Sect. 5.1. The explicit methods of order \(p=2\), \(p=3\), and \(p=4\), are analyzed in the sections below.
8.1 Explicit SSP LMMs of Order \(p=2\)
In this section, we will search for explicit LMMs of order \(p=2\) with \(k\ge 3\) stages. Solving the minimization problem (7.8) with inequality constrains (7.5) and equality constrains (7.2) corresponding to \(\beta _0=0\) and the order \(p=2\) leads to LMMs with coefficients given by
and SSP coefficient \({\mathcal {C}}_\textrm{eff}=(k-2)/(k-1)\). These methods were derived in [33], and were also reproduced in [12]. We have listed in Table 4 SSP coefficients \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}\), intervals of absolute stability, areas of regions of absolute stability and \(\max \{|r_j|, \ j=2,3,\ldots ,k\}\), where \(r_j\), \(j=2,3,\ldots ,k\), are roots of the first characteristic polynomial \(\rho (\xi )\), which are less than one, for LMMs of order \(p=2\) with \(k=3,4,\ldots ,10\), steps. The regions of absolute stability for these methods corresponding to \(k=3,4,\ldots ,10\), are plotted on Fig. 11. These regions increase in size as k ranges from 3 to 10. We have also plotted on this figure by a thick line the stability region of Adams–Bashforth methods of order \(p=2\). This method is defined by
\(n=2,3,\ldots ,N\), with given starting values \(y_0=y(t_0)\) and \(y_1\).
8.2 Explicit SSP LMMs of Order \(p=3\)
Solving the minimization problem (7.8) with inequality constrains (7.5) and equality constrains (7.2) corresponding to \(\beta _0=0\), \(p=3\), and \(k=4\), \(k=5\), and \(k=6\), lead to the methods
with optimal SSP coefficient \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}=1/3\),
with optimal SSP coefficient \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}=1/2\),
with SSP coefficient \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}\approx 0.5828\). The coefficients of (8.3) are listed in Matlab rational format. The methods (8.1), (8.2), and (8.3), are equivalent to SSPMS(4, 3), SSPMS(5, 3), and SSPMS\((6,3)_2\) formulas listed in [12]. The search for methods of order \(p=3\) and \(k>6\) leads to the method (8.3) corresponding to \(k=6\).
We have listed in Table 5 SSP coefficients \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}\), intervals of absolute stability, areas of regions of absolute stability and \(\max \{|r_j|, \ j=2,3,\ldots ,k\}\), where \(r_j\), \(j=2,3,\ldots ,k\), are roots of the first characteristic polynomial \(\rho (\xi )\), which are less than one, for LMMs of order \(p=3\) with \(k=4\), \(k=5\), and \(k\ge 6\), steps. The regions of absolute stability for these methods corresponding to \(k=4\), \(k=5\), and \(k\ge 6\), are plotted on Fig. 12. These regions increase in size as k ranges from 4 to 6. We have also plotted on this figure by a thick line the stability region of Adams–Bashforth methods of order \(p=3\). This method is defined by
\(n=3,4,\ldots ,N\), with given starting values \(y_0=y(t_0)\), \(y_1\), and \(y_2\).
8.3 Explicit SSP LMMs of Order \(p=4\)
Solving the minimization problem (7.8) with inequality constrains (7.5) and equality constrains (7.2) corresponding to \(\beta _0=0\), \(p=4\), and \(k=5\), leads to the method with rather small SSP coefficient and very small region of absolute stability. The coefficients of this method are not listed here. Solving this minimization problem corresponding to \(p=4\) and \(k=6\) we obtain the method, which in Matlab rational format takes the form
The SSP coefficient of this method is \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}\approx 0.1648\). This method is equivalent to SSPMS(4, 6) method, which was found numerically in [25, 26], and reproduced in [12].
We have listed in Table 6 SSP coefficients \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}\), intervals of absolute stability, areas of regions of absolute stability and \(\max \{|r_j|, \ j=2,3,\ldots ,k\}\), where \(r_j\), \(j=2,3,\ldots ,k\), are roots of the first characteristic polynomial \(\rho (\xi )\), which are less than one, for explicit LMMs of order \(p=4\) with \(k=5,6,\ldots ,10\), steps. The regions of absolute stability for these methods corresponding to \(k=5,6,\ldots ,10\), are plotted on Fig. 13. These regions increase in size as k ranges from 5 to 10. We have also plotted on this figure by a thick line the stability region of Adams–Bashforth methods of order \(p=4\). This method is defined by
\(n=4,5,\ldots ,N\), with given starting values \(y_0=y(t_0)\), \(y_1\), \(y_2\), and \(y_3\).
The SSP coefficients of explicit LMMs of order up tp \(p=15\) with up to \(k=50\) steps are listed in [12].
9 Implicit SSP LMMs
In this section, we investigate implicit SSP LMMs up to the order \(p=4\), i.e., methods (7.1) with \(\beta _0\ne 0\). The implicit method with \(p=1\) and \(k=1\) corresponds to the backward Euler method, and was analyzed in Sect. 6.1. The implicit methods of order \(p=2\), \(p=3\), and \(p=4\), are analyzed in the sections below.
9.1 Implicit SSP LMMs of Order \(p=2\)
Solving the minimization problem (7.8) with inequality constrains (7.5) and equality constrains (7.2) corresponding to \(\beta _0\ne 0\), \(p=2\), and \(k\ge 1\), leads to the trapezoidal method
\(n=1,2,\ldots ,N\). This method is A-stable. The coefficient matrices \(\textbf{S}\) and \(\textbf{T}\) of Spijker representation of this method are given by
and it can be verified that relations (7.5) for this method reduce to
This leads to the optimal SSP coefficient \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}=2\), compare Theorem 7.4.
The method (9.1) can be also written as implicit RK method with FSAL (First Same As Last) property, with coefficients
or
\(n=1,2,\ldots ,N\).
9.2 Implicit SSP LMMs of Order \(p=3\)
Solving the minimization problem (7.8) with inequality constrains (7.5) and equality constrains (7.2) corresponding to \(\beta _0\ne 0\), \(p=3\), and \(k\ge 2\), leads to the methods with coefficients
and optimal SSP coefficients
compare [34].
We have listed in Table 7 SSP coefficients \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}\), intervals of absolute stability, areas of regions of absolute stability and \(\max \{|r_j|, \ j=2,3,\ldots ,k\}\), where \(r_j\), \(j=2,3,\ldots ,k\), are roots of the first characteristic polynomial \(\rho (\xi )\), which are less than one, for implicit LMMs of order \(p=3\) with \(k=2,3,\ldots ,10\), steps. The regions of absolute stability for these methods corresponding to \(k=2,3,\ldots ,10\), are plotted on Fig. 14. These regions increase in size as k ranges from 2 to 10. We have also plotted on this figure by a thick line the stability region of Adams–Moulton methods of order \(p=3\). This method is defined by
\(n=2,3,\ldots ,N\), with given starting values \(y_0=y(t_0)\), and \(y_1\).
9.3 Implicit SSP LMMs of Order \(p=4\)
Solving the minimization problem (7.8) with inequality constrains (7.5) and equality constrains (7.2) corresponding to \(\beta _0\ne 0\), \(p=4\), and \(k=3\), leads to the method with coefficients
\(n=3,4,\ldots ,N\), with starting values \(y_0=y(t_0)\), \(y_1\), and \(y_2\). Solving the minimization problem (7.8) with inequality constrains (7.5) and equality constrains (7.2) corresponding to \(\beta _0\ne 0\), \(p=4\), and \(k\ge 4\), leads to the method with coefficients, which in Matlab rational format, are given by
The methods (9.2) and (9.3) are equivalent to the methods derived in [34]. We have listed in Table 8 SSP coefficients \({\mathcal {C}}={\mathcal {C}}_\textrm{eff}\), intervals of absolute stability, areas of regions of absolute stability and \(\max \{|r_j|, \ j=2,3,\ldots ,k\}\), where \(r_j\), \(j=2,3,\ldots ,k\), are roots of the first characteristic polynomial \(\rho (\xi )\), which are less than one, for implicit LMMs of order \(p=3\) with \(k=3\), and \(k\ge 4\), steps. The regions of absolute stability for these methods corresponding to \(k=3\), and \(k\ge 4\), are plotted on Fig. 15. These regions increase in size as k ranges from 3 to 4. We have also plotted on this figure by a thick line the stability region of Adams–Moulton methods of order \(p=4\). This method is defined by
\(n=3,4,\ldots ,N\), with given starting values \(y_0=y(t_0)\), \(y_1\), and \(y_2\).
The SSP coefficients of implicit LMMs of order up tp \(p=15\) with up to \(k=50\) steps are listed in [12].
10 Concluding Remarks
SSP properties of explicit or implicit RK methods are usually investigated using Shu–Osher or generalized Shu–Osher representations. In this paper, we discussed the construction of explicit and implicit SSP RK methods using a different point of view. This different approach is based of reformulating first RK methods as GLMs, and then using monotonicity theory of GLMs developed by Spijker [36] to construct explicit or implicit SSP RK methods. Both approaches, i.e., approach based on Shu–Osher or generalized Shu–Osher representation, or monotonicity theory of GLMs, lead to the same classes of explicit or implicit RK methods, but expressed in different representations (Shu–Osher, generalized Shu–Osher, or Butcher). The SSP LMMs are also investigated using monotonicity theory of GLMs.
Data availability statement
There are no available data associated with this paper.
References
Bresten, C., Gottlieb, S., Grant, Z., Higgs, D., Ketcheson, D., N\(\acute{\text{m}}\)eth, A.: Explicit strong stability preserving multistep Runge–Kutta methods. Math. Comput. 86, 747–769 (2017)
Burrage, K.: Parallel and Sequential Methods for Ordinary Differential Equations. Clarendon Press, Oxford (1995)
Butcher, J.C.: The Numerical Analysis of Ordinary Differential Equations. Wiley, New York (1987)
Butcher, J.C.: Numerical Methods for Ordinary Differential Equations. Wiley, New York (2003)
Butcher, J.C.: General linear methods. Acta Numer. 15, 157–256 (2006)
Butcher, J.C.: Numerical Methods for Ordinary Differential Equations, 2nd edn. Wiley, Chichester (2008)
Califano, G., Izzo, G., Jackiewicz, Z.: Strong stability preserving general linear methods with Runge–Kutta stability. J. Sci. Comput. 76, 943–968 (2018)
Cardone, A., Jackiewicz, Z., Verner, J.H., Welfert, B.: Order conditions for general linear methods. J. Comput. Appl. Math. 290, 44–64 (2015)
Constantinescu, E.M., Sandu, A.: Optimal explicit strong-stability-preserving general linear methods. SIAM J. Sci. Comput. 32, 3130–3150 (2010)
Ferracina, L., Spijker, M.N.: An extension and analysis of the Shu–Osher representation of Runge–Kutta methods. Math. Comput. 74, 201–219 (2004)
Ferracina, L., Spijker, M.N.: Stepsize restrictions for the total-variation-boundedness in general Runge–Kutta procedures. Appl. Numer. Math. 53, 265–279 (2005)
Gottlieb, S., Ketcheson, D.I., Shu, C.-W.: Strong Stability Preserving Runge–Kutta and Multistep Time Discretizations. World Scientific Publishing Co. Pte. Ltd., Hackensack (2011)
Gottlieb, S., Shu, C.-W.: Total variation diminishing Runge–Kutta schemes. Math. Comput. 67, 73–85 (1998)
Gottlieb, S., Shu, C.-W., Tadmor, E.: Strong stability-preserving high-order time discretization methods. SIAM Rev. 43, 89–112 (2001)
Hairer, E., Nørsett, S.P., Wanner, G.: Solving Ordinary Differential Equations I, Nonstiff Problems, Second Revised Edition. Springer, Berlin (1993)
Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II, Stiff and Differential-Algebraic Problems, Second Revised Edition. Springer, Berlin (1996)
Henrici, P.: Discrete Variable Methods in Ordinary Differential Equations. Wiley, New York (1962)
Higueras, I.: Representations of Runge–Kutta methods and strong stability preserving methods. SIAM J. Numer. Anal. 43, 924–948 (2005)
Horváth, Z., Podhaisky, H., Weiner, R.: Strong stability preserving explicit peer methods. J. Comput. Appl. Math. 296, 776–788 (2016)
Hundsdorfer, W., Ruuth, S.J.: On monotonicity and boundedness properties of linear multistep methods. Math. Comput. 75, 655–672 (2005)
Izzo, G., Jackiewicz, Z.: Strong stability preserving general linear methods. J. Sci. Comput. 65, 271–298 (2015)
Izzo, G., Jackiewicz, Z.: Strong stability preserving multistage integration methods. Math. Model. Anal. 20, 552–577 (2015)
Izzo, G., Jackiewicz, Z.: Strong stability preserving transformed DIMSIMs. J. Comput. Appl. Math. 343, 174–188 (2018)
Jackiewicz, Z.: General Linear Methods for Ordinary Differential Equations. Wiley, Hoboken (2009)
Ketcheson, D.I.: High order strong stability preserving time integrators and numerical wave propagation methods for hyperbolic PDEs. Ph.D. thesis, University of Washington (2009)
Ketcheson, D.I.: Computation of optimal monotonicity preserving general linear methods. Math. Comput. 78, 1497–1513 (2009)
Ketcheson, D.I., Gottlieb, S., Macdonald, C.B.: Strong stability preserving two-step Runge–Kutta methods. SIAM J. Numer. Anal. 49, 2618–2639 (2011)
Ketcheson, D.I., Macdonald, C.B., Gottlieb, S.: Optimal implicit strong stability preserving Runge–Kutta methods. Appl. Numer. Math. 59, 373–392 (2009)
Klinge, M., Weiner, R.: Strong stability preserving explicit peer methods for discontinuous Galerkin discretizations. J. Sci. Comput. 75, 1057–1078 (2018)
Kraaijevanger, J.F.B.M.: Contractivity of Runge–Kutta methods. BIT 31, 482–528 (1991)
Lambert, J.D.: Computational Methods in Ordinary Differential Equations. Wiley, Chichester (1973)
Lambert, J.D.: Numerical Methods for Ordinary Differential Equations. Wiley, Chichester (1991)
Lenferink, H.W.J.: Contractivity-preserving explicit linear multistep methods. Numer. Math. 55, 213–223 (1989)
Lenferink, H.W.J.: Contractivity-preserving implicit linear multistep methods. Math. Comput. 56, 177–199 (1991)
Shu, C.-W., Osher, S.: Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys. 77, 439–471 (1988)
Spijker, M.N.: Stepsize conditions for general monotonicity in numerical initial value problems. SIAM J. Numer. Anal. 45, 1226–1245 (2007)
Wright, W.: General linear methods with inherent Runge–Kutta stability. Ph.D. thesis, The University of Auckland, New Zealand (2002)
Acknowledgements
The work of the first author (GI) was supported by INdAM Research group GNCS.
Funding
Open access funding provided by Università degli Studi di Napoli Federico II within the CRUI-CARE Agreement.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
On behalf of all authors, the corresponding author states that there is no conflict of interest.
Additional information
Communicated by Ali Abdi.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Izzo, G., Jackiewicz, Z. Strong Stability Preserving Runge–Kutta and Linear Multistep Methods. Bull. Iran. Math. Soc. 48, 4029–4062 (2022). https://doi.org/10.1007/s41980-022-00731-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s41980-022-00731-x
Keywords
- Runge–Kutta methods
- Linear multistep methods
- General linear methods
- Monotonicity
- Strong stability preserving
- SSP coefficient
- Shu–Osher representation