# Â-and Î-stability of collocation Runge-Kutta methods

Guillaume Dujardin, Ingrid Lacroix-Violet

## ► To cite this version:

Guillaume Dujardin, Ingrid Lacroix-Violet. Â-and Î-stability of collocation Runge-Kutta methods. Applied Numerical Mathematics, 2024, 202, pp.158-172. 10.48550/arXiv.2304.09672. hal-04074151v2

HAL Id: hal-04074151

https://inria.hal.science/hal-04074151v2

Submitted on 10 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Â- AND Î-STABILITY OF RUNGE-KUTTA COLLOCATION METHODS

GUILLAUME DUJARDIN AND INGRID LACROIX-VIOLET

**ABSTRACT.** This paper deals with stability of classical Runge-Kutta collocation methods. When such methods are embedded in linearly implicit methods as developed in [13] and used in [14] for the time integration of nonlinear evolution PDEs, the stability of these methods has to be adapted to this context. For this reason, we develop in this paper several notions of stability, that we analyze. We provide sufficient conditions that can be checked algorithmically using just the collocation points of the method to ensure that these stability notions are fulfilled by a given Runge-Kutta collocation method. We also introduce examples and counterexamples used in [14] to highlight the necessity of these stability conditions in this context.

**AMS Classification.** 65L06, 65L20, 65L04, 65M70, 65M12, 65P40.

**Keywords.** Numerical analysis, Runge-Kutta methods, collocation methods, stability.

## 1. INTRODUCTION

This paper deals with stability of classical Runge-Kutta collocation methods. We introduce and analyze several notions of stability for such methods, that are, in particular, useful in the context of linearly implicit methods for the numerical integration of evolution PDEs. Indeed, the linearly implicit methods developed in [13, 14] embed a Runge-Kutta collocation method. Using additional unknowns and a collocation trick (such as in the relaxation method developed in [1] for the Schrödinger equation), they allow for the solution of a *linear* system at each time step, even if the original PDE is nonlinear. Moreover, these linearly implicit methods are shown in [14]) to have high order accuracy in time, provided they satisfy suitable stability conditions. The goal of this paper is to introduce these stability notions used in [14], to provide sufficient conditions on the coefficients of a Runge-Kutta collocation method to ensure them, and to provide the reader with examples and counterexamples. The numerical interest of the stability notions introduced in this paper is discussed and demonstrated *via* several numerical experiments using linearly implicit methods in the companion paper [14]. In contrast, to keep the presentation short, the present paper does *not* contain numerical experiments.

For solving dissipative problems such as the heat equation with such linearly implicit methods, the relevant notion of stability for Runge-Kutta collocation methods that we introduce is named Â-stability (see Definition 2.1 below). This stability notion is a generalization of the classical A-stability (which is recalled below in Section 2). For solving oscillatory problems such as the Schrödinger equation with such methods, the relevant notion of stability for Runge-Kutta collocation methods that we introduce is named Î-stability.

Of course, stability analysis of Runge-Kutta methods has a long history. Let us mention the A-stability introduced by Dahlquist [12], to ensure appropriate long-time behaviour (the letter A is short for the word “asymptotic”) of Runge-Kutta methods applied to non-expensive linear scalar equations, the B-stability introduced by Butcher [4] [2] for vector fields satisfying a one-sided Lipschitz condition, which generalizes asymptotic stability to nonlinear differential equations (see also [9]). The relations between these two notions is studied and summarized in [18] using the W-transform. The notions of A- and B-stability have been generalized to non-autonomous ODEs yielding the definitions of AN- and BN-stability [2]. For Runge-Kutta methods, the notion of BN-stability is essentially the same as that of algebraic stability [20]. The definition of algebraic stability involves a non-negative quadratic form
depending on the coefficients of the Runge–Kutta method at hand. It was discovered in [26] that if this quadratic form is zero, then the Runge–Kutta method is symplectic when applied to Hamiltonian equations. The interested reader may find a summary of stability notions for numerical methods for solving evolution ODEs in [5], including *G*-stability. Linear stability of Runge–Kutta methods has also been studied for ODE systems with nonconstant stiff part (see for example [6]). Stability properties of Runge–Kutta methods have also been studied outside the ODE context (see for example [27]). The purpose of this paper is to introduce, characterize and discuss similar stability notions, that are relevant in the context of using Runge–Kutta collocation methods as embedded methods in linearly implicit time stepping methods developped in [13, 14]. In particular, some of the results in this manuscript are *not* new and are identified as such, with references to the literature. These results are included for the reader’s convenience because they are useful in the context of the linearly implicit methods introduced in [13, 14]. Moreover, we provide here alternative ways to prove them, using the formalism and tools introduced in this paper.

In the context of integrating time-evolution systems arising from the spatial discretization of evolution PDEs, the relevant notions of stability for numerical methods depend on the PDE at hand, and, in particular, on whether that original PDE is parabolic, hyperbolic, or hamiltonian. This dates back, at least, to the seminal work of Crouzeix (see for example [7] for general ODEs involving operators and [8] for parabolic problems), and has a continued history in both linear and nonlinear contexts (see for example [10] for general rational approximations of analytic semigroups in Banach spaces, [24] for quasilinear parabolic problems, [16] for strong stability preserving high order methods for hyperbolic problems).

In this paper, we investigate notions of stability for Runge–Kutta collocation methods embedded in linearly implicit methods defined in the ODE setting in [13] and later extended to the semilinear PDE setting in [14]. We focus on the PDE case, and assume the linearly implicit method is applied to the (large) ODE system obtained after space discretization of the PDE at hand. We distinguish two main cases, depending on the unbounded linear differential operator of the PDE. First, when the linear operator is dissipative (roughly speaking, its spectrum is located in a left half plane of the complex plane and the real part of that spectrum is not bounded below), we introduce the notion of $\hat{A}$-stability. Second, when the linear operator is dispersive (roughly speaking, its spectrum is located in a vertical line of the complex plane and its imaginary part is not bounded), we introduce the notion of $\hat{I}$-stability. The relevance of these two stability notions for Runge–Kutta methods embedded in linearly implicit method for solving evolution PDEs is discussed and numerically illustrated in [14]. In particular, one can find examples (such as in Example 4.6) of $A$-stable methods that are not $\hat{A}$-stable. Such methods, when embedded in a linearly implicit method of the class introduced in [13], may fail to converge to the solution of a nonlinear partial differential equation, as illustrated numerically in [14] (Section 5.2.3). The goal of this paper is to provide sufficient conditions on the coefficients of the Runge–Kutta collocation method to ensure $\hat{A}$- and $\hat{I}$-stability.

The outline of this paper is as follows. In Section 2, we introduce several notions of stability for Runge–Kutta methods that are relevant in our context, and recall the basics about Runge–Kutta collocation methods. In Section 3.1, we indicate how one can compute the spectrum of the matrix of the coefficients of a Runge–Kutta collocation method (Lemma 3.1), and we derive some sufficient conditions to ensure the stability properties defined in the previous section (Lemmas 3.2 and 3.3). As an application of these criteria, we prove that Runge–Kutta collocation methods using Gauss points are $\hat{A}$-stable (Theorem 3.1). Moreover, using the Routh-Hurwitz algorithm, we provide a way for checking from only the collocation points of the Runge–Kutta method that our sufficient conditions are fulfilled, that guarantee the $\hat{A}$-stability of the method (see Section 3.4). We describe the influence of symmetry (with respect to $1/2$) of the collocation points on the stability of a Runge–Kutta collocation method in Section 3.5. We also investigate the stability of (forward) Runge–Kutta collocation methods with $s \le 4$ stages in Section 3.6. The last section of this paper (Section 4) is
devoted to the analysis of a few examples of Runge-Kutta collocation method with at most 5-stages
that are used numerically as examples or counterexamples in [14].

2. NOTIONS OF STABILITY OF RUNGE-KUTTA METHODS

2.1. **Several notions of stability.** Assume we are given a time interval $J \subset \mathbb{R}$, an open set $\Omega \subset \mathbb{R}^d$, a (smooth) function $f$ from $J \times \Omega$ to $\mathbb{R}^d$ and $(t_0, y_0) \in J \times \Omega$. For the time integration of the Cauchy problem

$$
(1) \qquad \begin{cases} y'(t) = f(t, y(t)) \\ y(t_0) = y_0 \end{cases},
$$

one may use a Runge–Kutta method with $s \in \mathbb{N}\setminus\{0\}$ stages, defined by $c_1, \dots, c_s \in \mathbb{R}$, $(a_{i,j})_{1\le i,j\le s} \in \mathbb{R}^s$ and $b_1, \dots, b_s \in \mathbb{R}$ defined by the following classical algorithm. Given some (small) time step $h > 0$, and starting from some $y^0 \in \Omega$ close to $y_0$, compute successively for $n \ge 0$ first $(y_{n,i})_{1\le i\le s} \in \Omega^s$ as the solution of the nonlinear system

$$
(2) \qquad y_{n,i} = y_n + h \sum_{j=1}^{s} a_{i,j} f(t_0 + (n+c_j)h, y_{n,j}), \quad (1 \le i \le s),
$$

and then $y_{n+1}$ using the explicit computation

$$
(3) \qquad y_{n+1} = y_n + h \sum_{i=1}^{s} b_i f(t_0 + (n+c_i)h, y_{n,i}).
$$

These methods have a long history, which started at the end of the 19th century [25], and have
been extensively studied in several contexts (see for example [19], [21] and references therein, as well
as for several other numerical methods) and order conditions as well as stability conditions are well
understood. Usually, the coefficients $(a_{i,j})_{1\le i,j\le s}$ are grouped in a square matrix denoted $A$, $b_1, \dots, b_s$
are grouped in a column vector denoted $b$ and $c_1, \dots, c_s$ are grouped in a column vector denoted $c$.
In particular, the *linear stability function* $R$ of these methods, defined for $\lambda \in \mathbb{C}$ by

$$
(4) \qquad R(\lambda) = 1 + \lambda b^t (I - \lambda A)^{-1} 1,
$$

where *I* is the identity matrix of size *s* and *1* is the column vector of size *s* with all coefficients equal to 1, plays a crucial role in the analysis of most forms of stability for the methods. Indeed, in the scalar case *d* = 1, for the Dahlquist equation, which corresponds to (1) with *Ω* = *R* and *f*(*t*, *y*) = *ay* for some *a* ∈ *C*, the sequence produced by the Runge–Kutta method (2)–(3) satisfies for all *n* ∈ *N*, *y*<sup>*n*</sup> = (*R*(*ah*)<sup>*n*</sup>)*y*<sup>0</sup>. Observe that *R* is a rational function of *λ* and any of its poles in *C* is the inverse of a non-zero eigenvalue of the matrix *A*.

For the purpose of integrating systems of the form (1) arising from the space-discretization of
semilinear evolution PDEs using methods involving Runge–Kutta methods of the form (2)-(3) (see
[14]), and following [11], [17] and [3], we use the following eight notions of stability. We denote by
C− the set of complex numbers with non positive real part, and by iR the set of purely imaginary
numbers.

**Definition 2.1.** A Runge–Kutta method is said to be

* A-stable if for all $\lambda \in \mathbb{C}^-$, $|R(\lambda)| \le 1$.

• *I-stable* if for all $\lambda \in i\mathbb{R}$, $|R(\lambda)| \le 1$.

* AS-stable if the rational function $\lambda \mapsto \lambda b^t (I - \lambda A)^{-1}$ has only removable singularities in $\mathbb{C}^-$ and is bounded on $\mathbb{C}^-$.

* ASI-stable if for all $\lambda \in \mathbb{C}^-$, the matrix $(I - \lambda A)$ is invertible and $\lambda \mapsto (I - \lambda A)^{-1}$ is uniformly bounded on $\mathbb{C}^-$.

* *IS-stable* if the rational function $\lambda \mapsto \lambda b^t (I - \lambda A)^{-1}$ has only removable singularities in $i\mathbb{R}$ and is bounded on $i\mathbb{R}$.
* *ISI-stable* if for all $\lambda \in i\mathbb{R}$, the matrix $(I - \lambda A)$ is invertible and $\lambda \mapsto (I - \lambda A)^{-1}$ is uniformly bounded on $i\mathbb{R}$.

* *Â-stable* if it is A-stable, AS-stable and ASI-stable.

* *Î-stable* if it is I-stable, IS-stable and ISI-stable.

A few examples of Runge-Kutta methods and the analysis of their stability properties can be found in Section 4.

**Remark 2.1.** Observe that, from this definition, an A-stable Runge-Kutta method is also I-stable. Similarly, an AS-stable Runge-Kutta method is also IS-stable, and ASI-stable Runge-Kutta method is also ISI-stable. As a consequence, an Â-stable method is also Î-stable.

**Remark 2.2.** If b is in the range of A^t, then ASI-stability implies AS-stability using Lemma 4.4 of [3]. Similarly, ISI-stability implies IS-stability.

**2.2. Runge-Kutta collocation methods.** This paper deals with Runge-Kutta collocation methods in the sense of the following definition and the analysis of their stability properties in the sense of Definition 2.1.

**Definition 2.2 (collocation methods).** The Runge-Kutta method defined by A, b and c is said to be of collocation when $c_1, c_2, \dots, c_s$ are distinct real numbers and A and b satisfy for all $(i, j) \in \{1, \dots, s\}^2$,

$$ (5) \qquad a_{ij} = \int_0^{c_i} \ell_j(\tau) d\tau \quad \text{and} \quad b_i = \int_0^1 \ell_i(\tau) d\tau, $$

where $(\ell_i)_{1 \le i \le s}$ are the s Lagrange polynomials associated to $(c_1, \dots, c_s)$ defined by

$$ (6) \qquad \forall i \in \{1, \dots, s\}, \qquad \ell_i(\tau) = \prod_{\substack{j \ne i \\ j=1}}^{s} \frac{(\tau - c_j)}{(c_i - c_j)}. $$

We denote by $\pi$ the normalized polynomial of degree $s$, the zeros of which are $c_1, \dots, c_s$, i.e.

$$ (7) \qquad \pi = \prod_{i=1}^{s} (X - c_i). $$

Moreover, a Runge-Kutta collocation method is said to be forward when all $(c_i)_{1 \le i \le s}$ are non negative.

Order condition for Runge-Kutta collocation methods are well known (see e.g. [22]), and, amongst those methods, Gauss methods are known to have superconvergence in the sense that they have s stages and order 2s in the ODE setting [22]. These Runge-Kutta collocation methods appear as an essential tool of the high order linearly implicit methods derived for ODEs in [13] and used further for PDEs in [14]. Since all the coefficients of such methods are defined once the distinct s real numbers $c_1, \dots, c_s$ are chosen, their stability analysis (in the sense of Definition 2.1) can be reduced to the analysis of polynomials with one unknown (whose coefficients are polynomials in $c_1, \dots, c_s$), as we shall see in Section 3. One has for example the following lemma for the computation of $(a_{i,j})_{1 \le i,j \le s}$.

**Lemma 2.1 (Expression of A for Runge-Kutta collocation methods).** Let $s \ge 1$ be an integer, and $c_1, \dots, c_s$ be s distinct real numbers. The corresponding Runge-Kutta collocation method with matrix A defined in (5)-(6) satisfies

$$ (8) \qquad A = W_c \times V_c^{-1}, $$

where

$$ (9) \qquad V_c = \begin{pmatrix} 1 & c_1^1 & \cdots & c_1^{s-1} \\ 1 & c_2^1 & \cdots & c_2^{s-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & c_s^1 & \cdots & c_s^{s-1} \end{pmatrix} \quad \text{and} \quad W_c = \begin{pmatrix} \frac{c_1^1}{1} & \frac{c_1^2}{2} & \cdots & \frac{c_1^s}{s} \\ \frac{c_2^1}{1} & \frac{c_2^2}{2} & \cdots & \frac{c_2^s}{s} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{c_s^1}{1} & \frac{c_s^2}{2} & \cdots & \frac{c_s^s}{s} \end{pmatrix}. $$
*Proof.* Since the s quadrature points $c_1, \cdots, c_s$ are distinct, the matrix A is well-defined by (5)-(6). Morover, we have for all polynomial function $f$ or degree at most $s-1$ that

$$ \forall i \in \{1, \cdots, s\}, \quad \sum_{j=1}^{s} a_{i,j} f(c_j) = \int_{0}^{c_i} f(\tau) d\tau. $$

In particular, for all $p \in \{1, \cdots, s\}$ and all $i \in \{1, \cdots, s\}$, for the function $f: \tau \mapsto \tau^{p-1}$, we obtain

$$ \sum_{j=1}^{s} a_{i,j} c_j^{p-1} = \frac{c_i^p}{p}. $$

This relation exactly states that $A \times V_c = W_c$. The inversibility of the Vandermonde matrix $V_c$ ensures that (8) holds. $\square$

### 3. STABILITY ANALYSIS OF RUNGE-KUTTA COLLOCATION METHODS

In this section, we consider a Runge-Kutta collocation method, the coefficients $(a_{i,j})_{1 \le i,j \le s}$ and $(b_i)_{1 \le i \le s}$ of which are derived using Definition 2.2 from the s distinct real numbers $c_1, \cdots, c_s$. Without loss of generality (using a permutation of the coefficients), we assume that $c_1 < \cdots < c_s$ are ordered this way.

#### 3.1. Computation of the characteristic polynomial of A in terms of $(c_i)_{1 \le i \le s}$.

**Lemma 3.1.** Let A be the matrix of a Runge-Kutta collocation method at the s distinct real points $(c_i)_{1 \le i \le s}$ with $c_1 < \cdots < c_s$. Let $\pi$ denote the polynomial defined in (7) in Definition 2.2. Denote by $\tau$ the linear mapping

$$ \tau: \left( \begin{array}{c} \mathbb{C}_s[X] \\ \sum_{k=0}^{s} a_k X^k \end{array} \right) \begin{array}{c} \longrightarrow \\ \longleftarrow \end{array} \left( \begin{array}{c} \mathbb{C}_s[X] \\ \sum_{k=0}^{s} k! a_k X^k \end{array} \right). $$

The characteristic polynomial $\chi_A$ of A is $\tau(\pi)/(s!)$.

**Remark 3.1.** For $P \in \mathbb{C}_s[X]$, we shall denote $\tau(P)$ or $\tau(P(X))$ its image by the mapping $\tau$ introduced in Lemma 3.1. Sometimes, we shall denote by $\tau(P)(\lambda)$ or $\tau(P(X))(\lambda)$ the evaluation of this image at $\lambda \in \mathbb{C}$.

*Proof.* Assume that all $c_i \neq 0$ for the time being. For a polynomial

$$ (10) \qquad P(X) = s\alpha_{s-1}X^{s-1} + \cdots + 2\alpha_1X + \alpha_0 \in \mathbb{C}_{s-1}[X], $$

we denote by $\nu(P)$ the column vector with component $i$ equal to $P(c_i)$. Introducing the diagonal matrix $D$ with entries $(1, 2, \cdots, s-1, s)$, this yields

$$ (11) \qquad \nu(P) = V_c D \begin{bmatrix} \alpha_0 \\ \vdots \\ \alpha_{s-1} \end{bmatrix}, $$

where $V_c$ is the square matrix defined in (9). Note that $V_c$ is invertible since all $c_i$ are distinct. We extend the definition of $\nu$ to $\mathbb{C}_s[X]$. Note however that (11) no longer holds for polynomials of degree $s$. Conversely, for $Y = (y_1, \cdots, y_s)^t \in \mathbb{C}^s$, we denote by $c(P)$ the coefficients in the canonical basis of $\mathbb{C}_{s-1}[X]$ of the only polynomial of degree at most $s-1$, the value of which at $c_i$ is $y_i$ for all $i \in \{1, \cdots, s\}$. This corresponds to expanding the polynomial $\sum_{i=1}^s y_i \ell_i(X)$ in the canonical basis of $\mathbb{C}_{s-1}[X]$, where $\ell_{i_1 \le i \le s}$ are the s Lagrange interpolation polynomials defined in (6) at points $(c_1, \cdots, c_s)$. We associate to a polynomial $P \in \mathbb{C}_{s-1}[X]$ of the form (10) its primitive $Q$ which vanishes at 0. We have

$$ (12) \qquad Q(X) = \alpha_{s-1}X^s + \cdots + \alpha_1X^2 + \alpha_0X. $$
For a polynomial $Q$ of this form, we define $c^1(Q)$ as the column vector with entry $i$ equal to $\alpha_{i-1}$ for all $i \in \{1, \dots, s\}$. Introducing the matrix

$$ (13) \qquad V = \begin{pmatrix} c_1 & c_1^2 & \cdots & c_1^s \\ c_2 & c_2^2 & \cdots & c_2^s \\ \vdots & \vdots & \ddots & \vdots \\ c_s & c_s^2 & \cdots & c_s^s \end{pmatrix}, $$

we have

$$ v(Q) = Vc^1(Q). $$

Moreover, since $P$ is a derivative of $Q$, we also have

$$ c(P) = Dc^1(Q). $$

For a general polynomial $P$ of the form (10), the associated polynomial $Q$ as in (12) satisfies

$$ v(Q) = Av(P). $$

For $\lambda \in \mathbb{C}$, we infer that

$$ \begin{aligned} (A - \lambda I)v(P) &= Av(P) - \lambda v(P) \\ &= v(Q) - \lambda V_c D c^1(Q) \\ &= Vc^1(Q) - \lambda V_c D c^1(Q) \\ &= (V - \lambda V_c D) c^1(Q) \\ &= (V - \lambda V_c D) D^{-1} V_c^{-1} v(P). \end{aligned} $$

Since this holds for all $P$, we infer that

$$ (14) \qquad \chi_A(\lambda) = \det(\lambda I - A) = \det(\lambda V_c D - V) \times \det(D^{-1} V_c^{-1}). $$

The second term in the product in the right-hand side of (14) does not depend on $\lambda$. Our first goal is to show that the first term in this product is proportional to $\tau(\pi)(\lambda)$. Observe that, setting

$$ (15) \qquad R_1 = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 1 & 0 & \cdots & 0 \end{pmatrix} \quad \text{and} \quad N = \begin{pmatrix} 0 & 2 & 0 & \cdots & 0 \\ 0 & 0 & 3 & \cdots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 0 \\ \vdots & \ddots & \ddots & \ddots & s \\ 0 & \cdots & \cdots & 0 & 0 \end{pmatrix}, $$

we have

$$ V_c D = V N + R_1. $$

Hence, using (14), $\chi_A$ is proportional to $\det(\lambda VN - V + \lambda R_1)$. Introducing the invertible matrix $M_\lambda = -I + \lambda N$, observe that

$$ (16) \qquad \lambda VN - V + \lambda R_1 = V(-I + \lambda N + \lambda V^{-1} R_1) = V(I + \lambda V^{-1} R_1 M_\lambda^{-1}) M_\lambda. $$

Since $\det V$ and $\det M_\lambda = (-1)^s$ do not depend on $\lambda$, we infer that $\chi_A$ is proportional to $\det(I + \lambda V^{-1} R_1 M_\lambda^{-1})$. Observe also that since we have the Dunford decomposition of $M_\lambda$, we have

$$ (-M_\lambda)^{-1} = (I - \lambda N)^{-1} = \sum_{k=0}^{s-1} (\lambda N)^k. $$

Since for all $k \in \{1, \dots, s-1\}$, the matrix $N^k = (n_{i,j}^k)_{1 \le i,j \le s}$ is a matrix with coefficients zero except for $(n^k)_{i,i+k} = \frac{(k+i)!}{(i)!}$ for $1 \le i \le s-k$, we infer that the first row of $M_\lambda^{-1}$ is equal to $(-1!, -2!\lambda, \dots, -(s-1)!\lambda^{s-2}, -s!\lambda^{s-1})$. This implies that $R_1 M_\lambda^{-1}$ is a matrix with all rows equal to $(-1!, -2!\lambda, \dots, -(s-1)!\lambda^{s-2}, -s!\lambda^{s-1})$. This is equivalent to saying that for all $j \in \{1, \dots, s\}$, the
column number $j$ of the matrix $R_1 M_{\lambda}^{-1}$ is equal to $-(j!)\lambda^{j-1}1$. This implies that the column number $j \in \{1, \dots, s\}$ of the matrix $V^{-1}R_1 M_{\lambda}^{-1}$ reads $-j!\lambda^{j-1}V^{-1}1$. Since the matrix $V^{-1}R_1 M_{\lambda}^{-1}$ has rank 1 due to the form of $R_1$, there exists some invertible matrix $B$ and some nontrivial $(\xi_1, \dots, \xi_s) \in \mathbb{C}^s$,

$$B^{-1}(V^{-1}R_1 M_{\lambda}^{-1})B = \begin{pmatrix} \xi_1 & 0 & \cdots & 0 \\ \xi_2 & 0 & \cdots & \vdots \\ \vdots & \vdots & \ddots & 0 \\ \xi_s & 0 & \cdots & 0 \end{pmatrix} := \Xi.$$

We infer that

$$\det(I + \lambda V^{-1} R_1 M_{\lambda}^{-1}) = \det(B(I + \lambda \Xi)B^{-1}) = (1 + \lambda \xi_1).$$

Using (16) and (14), we infer that $\chi_A(\lambda)$ is proportional to $1 + \lambda\xi_1$. Our second goal is to show that $(1 + \lambda\xi_1)$ is proportional to $\tau(\pi)(\lambda)$. Observe that $\xi_1 = \text{Tr}(\Xi) = \text{Tr}(V^{-1}R_1 M_{\lambda}^{-1})$. In order to compute $\xi_1 = \text{Tr}(V^{-1}R_1 M_{\lambda}^{-1})$, we compute the entry number $i$ of $-i!\lambda^{-1}V^{-1}1$ for $i \in \{1, \dots, s\}$. The unknown vector $X = (x_1, \dots, x_s) \in \mathbb{C}^s$ satisfies $VX = 1$ if and only if the polynomial $T(X) = x_s X^s + \cdots + x_1 X^1$ satisfies for all $j \in \{1, \dots, s\}$, $T(c_j) = 1$. Therefore, the polynomial $T(X) - 1 \in \mathbb{C}_s[X]$ is a multiple of $\pi = \prod_{i=1}^s (X - c_i)$ and therefore writes

$$T - 1 = e \prod_{i=1}^{s} (X - c_i),$$

for some $e \in \mathbb{C}$. Observe that $T(0) = 0$. Hence, $-1 = e \prod_{i=1}^s (-c_i)$. Hence, $e \neq 0$. Since,

$$\begin{align*} \lambda\xi_1 &= \lambda\text{Tr}(V^{-1}R_1 M_{\lambda}^{-1}) \\ &= -\sum_{i=1}^{s} i!\lambda^i (V^{-1}1)_i \\ &= -\sum_{i=1}^{s} i!x_i\lambda^i \\ &= \tau(-T)(\lambda), \end{align*}$$

we conclude that

$$\begin{align*} 1 + \lambda\xi_1 &= \tau(1 - T)(\lambda) \\ &= -e\tau(\pi)(\lambda). \end{align*}$$

Since $e \neq 0$, we conclude that $\chi_A$ is proportional to $\tau(\pi)$. Analysing the coefficient of degree $s$ ensures that $\chi_A = \tau(\pi)/(s!)$. This concludes the proof when all $c_i \neq 0$.

Now that the result is obtained when all the $c_i$ are nonzero, it holds for all $(c_i)_{1 \le i \le s} \in \mathbb{R}^s$ with $c_1 < \cdots < c_s$ (with at most one of them vanishing) by density, and because all the coefficients of $\tau(\pi)$ as well as all the coefficients of $\chi_A$ are continuous functions of $(c_1, \dots, c_s)$ over $\mathbb{R}^s$. $\square$

**Remark 3.2.** With the hypotheses and notations above, 0 is an eigenvalue of A if and only if there exists $j \in \{1, \dots, s\}$ such that $c_j = 0$. This is also equivalent to 0 being a root of $\tau(\pi)$.

**Remark 3.3.** Using Lemma 3.1, the eigenvalues of A are the zeros of $\tau(\pi)$. Observe also that

$$(17) \qquad \left\{ \frac{1}{z} \mid z \in \mathbb{C}^{-} \setminus \{0\} \right\} = \mathbb{C}^{-} \setminus \{0\}.$$

Therefore, in view of Definition 2.1, a necessary condition to have ASI stability is that $\tau(\pi)$ has no root in $\mathbb{C}^{-} \setminus \{0\}$. Similarly, observing that

$$(18) \qquad \left\{ \frac{1}{z} \mid z \in i\mathbb{R} \setminus \{0\} \right\} = i\mathbb{R} \setminus \{0\},$$

we obtain that a necessary condition to have ISI stability is that $\tau(\pi)$ has no root in $i\mathbb{R} \setminus \{0\}$.
### 3.2. Sufficient conditions to ensure $\hat{A}$-stability and $\hat{I}$-stability.
We prove that an $A$-stable Runge-Kutta collocation method such that $A$ has no eigenvalue in $\mathbb{C}^-$ is $\hat{A}$-stable. Thanks to Lemma 3.1, this is equivalent to proving that an $A$-stable Runge-Kutta collocation method such that $\tau(\pi)$ has no root in $\mathbb{C}^-$ is $\hat{A}$-stable.

**Lemma 3.2.** Assume that an $A$-stable Runge-Kutta collocation method is such that $\tau(\pi)$ has no root in $\mathbb{C}^-$. Then, it is $\hat{A}$-stable.

*Proof.* Let $c_1 < \dots < c_s$ be such that the Runge-Kutta collocation method with matrix $A$ is $A$-stable. Observe that

$$ \forall \lambda \in \mathbb{C} \setminus \{0\}, \quad (I - \lambda A) \text{ is invertible} \iff \left(A - \frac{1}{\lambda} I\right) \text{ is invertible.} $$

Since $\tau(\pi)$ has no zero in $\mathbb{C}^-$ by hypothesis, Lemma 3.1 ensures that the matrix $A$ has no eigenvalue in $\mathbb{C}^-$. In particular, for all $\lambda \in \mathbb{C}^- \setminus \{0\}$, $(A - \lambda I)$ is invertible. Observing that

$$ (19) \qquad \forall \lambda \in \mathbb{C} \setminus \{0\}, \quad (I - \lambda A)^{-1} = -\frac{1}{\lambda} \left(A - \frac{1}{\lambda} I\right)^{-1}. $$

This identity implies that we have

$$ (20) \qquad \lambda \mapsto (A - \lambda I)^{-1} \text{ is bounded over } \mathbb{C}^- \setminus \{0\} \quad \implies \quad \lambda \mapsto (I - \lambda A)^{-1} \text{ is bounded over } \mathbb{C}^- \setminus \{0\}. $$

Indeed, $\lambda \mapsto (I - \lambda A)^{-1}$ is always bounded in a complex neighbourhood of 0.

Observe that $(A - \lambda I)^{-1}$ is a matrix, the coefficients of which are rational functions of $\lambda$ of negative degrees. Therefore, since $A$ has no eigenvalue in $\mathbb{C}^-$, we infer that $\lambda \mapsto (A - \lambda I)^{-1}$ is bounded on $\mathbb{C}^-$. Therefore, using (20), we obtain that $\lambda \mapsto (I - \lambda A)^{-1}$ in bounded on $\mathbb{C}^-$. This implies that the method is ASI-stable. Since $A$ has no eigenvalue in $\mathbb{C}^-$, we infer that 0 is not an eigenvalue of $A$. Hence, using Lemma 3.1, the matrix $A$ is invertible. Using Remark 2.2, we infer that the method is also AS-stable using . Finally, the method is $A$, AS and ASI-stable. Hence, it is $\hat{A}$-stable. $\square$

A direct adaptation of the previous result yields the following lemma.

**Lemma 3.3.** Assume that an $I$-stable Runge-Kutta collocation method is such that $\tau(\pi)$ has no root in $i\mathbb{R}$. Then, it is $\hat{I}$-stable.

### 3.3. Stability of Runge-Kutta collocation methods with Gauss points.
We recall this result, established in [15] and [28] :

**Proposition 3.1.** An $s$ stages Runge-Kutta collocation method with $s$ Gauss points is $A$-stable.

*Proof.* Let us simply make the link between the proof of [28] and the notations introduced above. Using equation (9) in [28], the rational stability function $R$ introduced in (4) satisfies for $\Re(\lambda) > 0$

$$ (21) \qquad R(\lambda) = \frac{\int_{0}^{+\infty} e^{-\lambda\sigma} \pi(\sigma + 1) d\sigma}{\int_{0}^{+\infty} e^{-\lambda\sigma} \pi(\sigma) d\sigma}. $$

Using the fact that for all $k \in \mathbb{N}$, $\int_0^{+\infty} e^{-\lambda\sigma} \sigma^k d\sigma = k! / \lambda^{k+1}$, we infer that

$$ (22) \qquad R(\lambda) = \frac{\tau(\pi(X+1))(1/\lambda)}{\tau(\pi(X))(1/\lambda)}, $$

and this relation also holds for all $\lambda \in \mathbb{C} \setminus \{0\}$ such that $1/\lambda$ is not a zero of $\tau(\pi)$. When the $(c_i)_{1 \le i \le s}$ are Gauss points, one has

$$ (23) \qquad \pi(X) = \frac{d^s}{dX^s} (X(X-1))^s. $$
Following [28], we apply the Routh-Hurwitz algorithm to $\tau(\pi)$ in order to show that its roots have positive real parts. By a simple computation from (23), we have

$$ \begin{aligned} \pi(X) &= \frac{d^s}{dX^s} \left( X^s \sum_{k=0}^{s} \frac{s!}{k!(s-k)!} (-X)^k \right) \\ &= \sum_{k=0}^{s} \frac{s!}{k!(s-k)!} \frac{(s+k)!}{k!} (-X)^k. \end{aligned} $$

With the definition of $\tau(\pi)$ from Lemma 3.1, we infer that

$$ \tau(\pi)(\lambda) = s! \sum_{k=0}^{s} \frac{(s+k)!}{k!(s-k)!} (-\lambda)^k. $$

This corresponds to the polynomial in the appendix of [28] with $-\lambda$ here instead of $\mu$ there. In particular, using [28], we infer that all the roots of $\tau(\pi)$ have positive real parts.

Using (22), we infer that $R(\lambda)$ has no pole in $\mathbb{C}^-$. Therefore, $\lambda \mapsto R(\lambda)$ is an analytic function in an open set containing $\mathbb{C}^-$. Following [28], we have that $R(\lambda)$ has modulus bounded by one on the purely imaginary axis as well as on the left half circle at infinity (see also Section 3.5). Using the maximum principle for the analytic function $R$, we infer that $|R(\lambda)| \le 1$ in the closed left half plane $\mathbb{C}^-$. Therefore, the collocation method with Gauss points is $\mathcal{A}$-stable. $\square$

**Remark 3.4.** *Relations (21) (for $\Re(\lambda) > 0$) and (22) (for $\lambda \in \mathbb{C}\setminus\{0\}$) hold for all collocation methods. We will use this fact in Section 3.4 to derive an algorithm that allows to ensure that a given collocation method is $\hat{\mathcal{A}}$-stable.*

Using Lemma 3.2, this result can be improved as follows.

**Theorem 3.1.** *An $s$ stages Runge-Kutta collocation method with $s$ Gauss points is $\hat{\mathcal{A}}$-stable and $\hat{I}$-stable.*

*Proof.* Consider an $s$ stages Runge-Kutta collocation method with Gauss points. That method is $\mathcal{A}$-stable using Proposition 3.1, and the roots of $\tau(\pi)$ have positive real parts, as we have seen in the proof of Proposition 3.1. Using Lemma 3.2, we infer that the method is $\hat{\mathcal{A}}$-stable. It is also $\hat{I}$-stable by Remark 2.1. $\square$

**3.4. An algorithm to ensure that a given collocation method with $s$-stages is $\hat{\mathcal{A}}$-stable (hence $\hat{I}$-stable).** In this section, we describe sufficient conditions ensuring that a given Runge-Kutta collocation method is $\hat{\mathcal{A}}$-stable, and explain how these conditions can be checked algorithmically from the expression of the collocation points, using the Routh-Hurwitz criterion.

If a Runge-Kutta collocation method is given by $c_1 < c_2 < \dots < c_s$, then one can form the polynomial $\pi(X) = \prod_{i=1}^{s}(X - c_i)$ and the polynomial $\tau(\pi)$ using the definition of $\tau$ in Lemma 3.1. These computations can be carried out algorithmically from $c_1 < c_2 < \dots < c_s$. Using the fact that $\lambda \mapsto R(\lambda)$ is a rational function, the maximum principle implies that the method is $\mathcal{A}$-stable if and only if

* $\lambda \mapsto R(\lambda)$ has no pole in $\mathbb{C}^-$,

* $|R(\lambda)| \le 1$ for $\lambda \in i\mathbb{R}$ (and hence in the limit $|\lambda| \to +\infty$ in $\mathbb{C}^-$).

These two assumptions can be examined separately using algorithm that allow to localize the roots of polynomials as follows:

* For the first point above, if we assume that the collocation method is such that $\tau(\pi)$ has no root in $\mathbb{C}^-$, then, using (22), this first point holds. Moreover, this hypothesis on $\tau(\pi)$ can be checked algorithmically from the coefficients of $\tau(\pi)$ using the Routh-Hurwitz algorithm [23] (this is for example the case for Gauss points (see the proof of Theorem 3.1)).
• The second point can be checked by examining the real roots of $|R(ix)|^2 - 1$. Once again, this can be checked algorithmically from the coefficients of that polynomial, using the Routh-Hurwitz algorithm [23].

This provides sufficient algorithmic conditions to ensure that a given Runge-Kutta collocation method is A-stable. Indeed, for a Runge-Kutta collocation method satisfying the two points above, we have that it is A-stable. Moreover, since $\tau(\pi)$ has no pole in $\mathbb{C}^-$, the method satisfies that all $(c_i)_{1\le i\le s}$ are non-zero and the matrix A is invertible. In this case, using Lemma 3.2, we conclude that the method is $\hat{A}$-stable.

However, a method may be A-stable while $\tau(\pi)$ has zeros in $\mathbb{C}^-$, and that method may fail to be $\hat{A}$-stable (see Example 4.6 below).

The study of a few examples of Runge-Kutta methods can be found in Section 4.

### 3.5. Symmetry of the $(c_i)_{1\le i\le s}$ with respect to $1/2$ and stability.

**Proposition 3.2.** Assume the $s$ distinct coefficients $c_1 < \dots < c_s$ of a Runge-Kutta collocation method are symmetric with respect to $1/2$, i.e. for all $i \in \{1, \dots, s\}$, $c_i + c_{s+1-i} = 1$. The linear stability function $R$ of this method satisfies

$$ (24) \qquad \lim_{|\lambda| \to +\infty} |R(\lambda)| = 1, $$

and

$$ (25) \qquad \forall i \in i\mathbb{R}, \quad |R(\lambda)| = 1. $$

*Proof.* The result of Section 3.4 above holds independently of any symmetry condition on the collocation points $c_1, \dots, c_s$. However, when the points $c_1, \dots, c_s$ are symmetric with respect to $1/2$, we have

$$ \pi(X+1) = \prod_{i=1}^{s} (X+1-c_i) = \prod_{i=1}^{s} (X+c_i) = (-1)^s \prod_{i=1}^{s} (-X-c_i) = (-1)^s \pi(-X). $$

This implies that

$$ (26) \qquad \tau(\pi(X+1))(\lambda) = (-1)^s \tau(\pi(X))(-\lambda). $$

Hence, using (22), we infer

$$ |R(\lambda)| = \left| \frac{\tau(\pi(X+1))(1/\lambda)}{\tau(\pi(X))(1/\lambda)} \right| = \left| \frac{\tau(\pi(X+1))(1/\lambda)}{\tau(\pi(X+1))(-1/\lambda)} \right|. $$

This implies (24), as already noted by [28]. Expanding the polynomial with real coefficients $\tau(\pi(X))$ and writing it as $\tau(\pi(X))(\lambda) = \sum_{k=0}^{s} \alpha_k \lambda^k$, Relation (26) also implies that, for $x \in \mathbb{R}$,

$$ \begin{align*} \tau(\pi(X+1))(ix) &= (-1)^s \tau(\pi(X))(-ix) \\ &= (-1)^s \left( \sum_{\substack{k=0 \\ k \text{ even}}}^s \alpha_k (-ix)^k + \sum_{\substack{k=0 \\ k \text{ odd}}}^s \alpha_k (-ix)^k \right) \\ &= (-1)^s \left( \sum_{\substack{k=0 \\ k \text{ even}}}^s \alpha_k (ix)^k - \sum_{\substack{k=0 \\ k \text{ odd}}}^s \alpha_k (ix)^k \right) \\ &= (-1)^s \left( \sum_{\substack{k=0 \\ k \text{ even}}}^s \alpha_k \overline{(ix)^k} + \sum_{\substack{k=0 \\ k \text{ odd}}}^s \alpha_k \overline{(ix)^k} \right) \\ &= (-1)^s \overline{\tau(\pi(X))(ix)}. \end{align*} $$

In view of (22), this implies (25).

□
**Remark 3.5.** Using Proposition 3.2, a Runge-Kutta collocation method with symmetric points is I-stable.

**Remark 3.6.** A Runge-Kutta collocation method with symmetric points such that $\tau(\pi)$ has no roots in $\mathbb{R}$ is $\hat{I}$-stable. Indeed, using the remark above, such a method is I-stable. With Lemma 3.3, we infer that it is $\hat{I}$-stable.

**Remark 3.7.** Observe that a Runge-Kutta collocation method with symmetric points that is such that $\tau(\pi)$ has no poles in $\mathbb{C}^-$ is $\hat{A}$-stable. Indeed, using Proposition 3.2, the associated linear stability function $R$ satisfies (24) and (25). Moreover, the poles of $R$ in $\mathbb{C}^-$ are inverses of eigenvalues of $A$ in $\mathbb{C}^-\setminus\{0\}$. Since $\tau(\pi)$ has no root in $\mathbb{C}^-$, Lemma 3.1 ensures that $A$ has no such eigenvalue. In particular, $R$ is analytic in an open set containing $\mathbb{C}^-$. The maximum principle ensures that $|R(\lambda)| \le 1$ over $\mathbb{C}^-$. Hence, the method is $A$-stable. Using Lemma 3.2, we infer that it actually is $\hat{A}$-stable.

### 3.6. I- and A-stability of forward Runge-Kutta collocation methods with at most 4 stages.

3.6.1. *Statement of the result.* This section is devoted to the proof of the following theorem. The proof of this theorem relies on lemmas allowing to locate the eigenvalues of the matrix $A$ for forward Runge-Kutta collocation methods with at most 4 stages. The statements and proofs of these lemmas are provided in Section 3.6.2. These lemmas rely on the Routh-Hurwitz criterion for polynomials of degrees at most 4, which is recalled in Section 3.6.3.

**Theorem 3.2.** Consider a forward Runge-Kutta collocation method with $s = 1, s = 2, s = 3$ or $s = 4$ stages. If it is I-stable, then it is A-stable.

**Remark 3.8.** Under the hypothesis of Theorem 3.2, A-stability is equivalent to I-stability. Indeed, A-stability always implies I-stability (see Remark 2.1). On the other hand, Theorem 3.2 proves the converse implication.

**Remark 3.9.** This result shows that we can not construct an I-stable with 1, 2, 3 or 4 stages at non-negative collocation points that is both I-stable and not A-stable. In contrast, Example 4.7 shows that it is possible to construct I-stable yet not A-stable forward Runge-Kutta collocation methods with $s = 5$ stages.

*Proof.* Assume $s \in \{1, 2, 3, 4\}$ and the collocation points $(c_i)_{1 \le i \le s}$ are non-negative. Using either Lemma 3.4 (if $s = 1$), 3.5 (if $s = 2$), 3.6 (if $s = 3$) or 3.7 (if $s = 4$), we infer that $\text{sp}(A) \subset \{0\} \cup \{z \in \mathbb{C} \mid \Re(z) > 0\}$. In particular, the function $\lambda \mapsto (I - \lambda A)^{-1}$ is analytic over $\{z \in \mathbb{C} \mid \Re(z) < 0\}$. This implies that $\lambda \mapsto R(\lambda)$ (see (4)) is analytic over the same open set. Assume now that the Runge-Kutta collocation method is I-stable (see Definition 2.1). This means that

$$ \forall x \in \mathbb{R}, \quad |R(ix)| \le 1. $$

In particular, the rational function $R$ has no pole in $\{z \in \mathbb{C} \mid \Re(z) \le 0\}$. Using the maximum principle, we infer that $\lambda \mapsto |R(\lambda)|$ is bounded by 1 over this set $\{z \in \mathbb{C} \mid \Re(z) \le 0\}$. Hence, the method is A-stable. $\square$

### 3.6.2. Eigenvalues of a forward Runge-Kutta collocation method with $s \in \{1, 2, 3, 4\}$ stages.

**Lemma 3.4.** If $s = 1$ and $0 \le c_1$ is a given real number, then the corresponding 1-stage Runge-Kutta collocation method with matrix $A = (a_{i,j})_{1 \le i,j \le 3}$ satisfies

$$ \text{sp}(A) = \{c_1\} \subset \{z \in \mathbb{C} \mid \Re(z) \ge 0\}. $$

*Proof.* This is obvious using for example relation (8) of Lemma 2.1. $\square$
**Lemma 3.5.** If $s = 2$ and $0 < c_1 < c_2$ are two real numbers, then the corresponding 2-stages Runge-Kutta collocation method with matrix $A = (a_{i,j})_{1\le i,j\le 3}$ satisfies

$$ \mathrm{sp}(A) \subset \{z \in \mathbb{C} \mid \Re(z) > 0\}. $$

If $s = 2$ and $0 = c_1 < c_2$ are two real numbers, then the corresponding 3-stages Runge-Kutta collocation method with matrix $A = (a_{i,j})_{1\le i,j\le 3}$ satisfies

$$ \mathrm{sp}(A) \subset \{0\} \cup \{z \in \mathbb{C} \mid \Re(z) > 0\}. $$

*Proof.* Using for example relation (8) of Lemma 2.1, we have

$$ \chi_A(X) = X^2 - \frac{c_1 + c_2}{2} X + \frac{c_1 c_2}{2}. $$

If $c_1 = 0$ then the roots of $\chi_A$ are $0$ and $c_2/2 > 0$. If $c_1 > 0$, then $c_2 > 0$ and the roots of $\chi_A$ have positive real parts. $\square$

**Lemma 3.6.** If $s = 3$ and $0 < c_1 < c_2 < c_3$ are three real numbers, then the corresponding 3-stages Runge-Kutta collocation method with matrix $A = (a_{i,j})_{1\le i,j\le 3}$ satisfies

$$ \mathrm{sp}(A) \subset \{z \in \mathbb{C} \mid \Re(z) > 0\}. $$

If $s = 3$ and $0 = c_1 < c_2 < c_3$ are three real numbers, then the corresponding 3-stages Runge-Kutta collocation method with matrix $A = (a_{i,j})_{1\le i,j\le 3}$ satisfies

$$ \mathrm{sp}(A) \subset \{0\} \cup \{z \in \mathbb{C} \mid \Re(z) > 0\}. $$

*Proof.* Using (8) of Lemma 2.1, a direct computation ensures that the characteristic polynomial of A reads

$$ (27) \qquad \chi_A(X) = X^3 - \frac{1}{3}(c_1 + c_2 + c_3)X^2 + \frac{1}{6}(c_1c_3 + c_2c_3 + c_1c_2)X - \frac{1}{6}c_1c_2c_3. $$

In the first case $c_1 > 0$ (hence $c_3 > c_2 > c_1 > 0$), the Routh-Hurwitz criterion (Proposition 3.3) applied to the third order polynomial $\chi_A(-X)$ ensures that if

$$ (28) \qquad \frac{1}{3}(c_1 + c_2 + c_3)\frac{1}{6}(c_1c_3 + c_2c_3 + c_1c_2) - \frac{1}{6}c_1c_2c_3 > 0 $$

then all the roots of $\chi_A$ have positive real parts. Moreover, relation (28) is obvious by direct expansion of the left hand side using the fact that for all $i \in \{1, \dots, 3\}$, $c_i > 0$.

In the second case $c_1 = 0 < c_2 < c_3$, we have

$$ (29) \qquad \chi_A(X) = X \left( X^2 - \frac{c_2 + c_3}{3} X + \frac{c_2 c_3}{6} \right). $$

This ensures that all the roots of $\chi_A(X)/X$ have positive real parts. $\square$

**Lemma 3.7.** If $s = 4$ and $0 < c_1 < c_2 < c_3 < c_4$ are four real numbers, then the corresponding 4-stages Runge-Kutta collocation method with matrix $A = (a_{i,j})_{1\le i,j\le 4}$ satisfies

$$ \mathrm{sp}(A) \subset \{z \in \mathbb{C} \mid \Re(z) > 0\}. $$

If $s = 4$ and $0 = c_1 < c_2 < c_3 < c_4$ are four real numbers, then the corresponding 4-stages Runge-Kutta collocation method with matrix $A = (a_{i,j})_{1\le i,j\le 4}$ satisfies

$$ \mathrm{sp}(A) \subset \{0\} \cup \{z \in \mathbb{C} \mid \Re(z) > 0\}. $$

*Proof.* Using (8) of Lemma 2.1, a direct computation ensures that the characteristic polynomial of A reads

$$ (30) \qquad \chi_A(X) = X^4 - \frac{1}{4}\Sigma_1 X^3 + \frac{1}{12}\Sigma_2 X^2 - \frac{1}{24}\Sigma_3 X + \frac{1}{24}\Sigma_4, $$
where

$$
(31) \qquad \Sigma_1 = \sum_{i=1}^{4} c_i, \qquad \Sigma_2 = \sum_{1 \le i < j \le 4} c_i c_j, \qquad \Sigma_3 = \sum_{1 \le i < j < k \le 4} c_i c_j c_k, \qquad \Sigma_4 = c_1 c_2 c_3 c_4,
$$

are the elementary symmetric polynomials in $c_1, c_2, c_3, c_4$. Assume first that $c_1 > 0$. In this case, we have also $c_2, c_3, c_4 > 0$. In particular, with (31), we have for all $i \in \{1, \dots, 4\}$, $\Sigma_i > 0$. Therefore, by the Routh-Hurwitz criterion (Proposition 3.5 applied to $\chi_A(-X)$), if

$$
(32) \qquad \frac{\Sigma_1}{4} + \frac{\Sigma_2}{12} + \frac{\Sigma_3}{24} > \left(\frac{\Sigma_3}{24}\right)^2 + \left(\frac{\Sigma_1}{4}\right)^2 \frac{\Sigma_4}{24},
$$

then the fourth order polynomial $\chi_A$ has all its roots in the open right half plane $\{z \in \mathbb{C} \mid \Re(z) > 0\}$.
Observe that, in our case,

$$
\begin{align*}
\Sigma_1 \Sigma_2 \Sigma_3 - 2 (\Sigma_3)^2 - 3 (\Sigma_1)^2 \Sigma_4 = & \\
& + c_1^3 c_2^2 c_3 \quad + c_1^3 c_2^2 c_4 \quad + c_1^3 c_2 c_3^2 \quad + c_1^3 c_2 c_4^2 \quad + c_1^3 c_3 c_4^2 \quad + c_1^2 c_3^2 c_3 \\
& + c_1^2 c_2^3 c_4 \quad + c_1^2 c_2^2 c_3^2 \quad - 2 c_1^2 c_2^2 c_3 c_4 \quad + c_1^2 c_2^2 c_4^2 \quad + c_1^2 c_3^2 c_4^3 \quad - 2 c_1^2 c_2 c_3^2 c_4 \quad - 2 c_1^2 c_2 c_3 c_4^2 \\
& + c_1^2 c_2 c_3^3 c_4 \quad + c_1^2 c_3^2 c_4^3 \quad + c_1 c_2^2 c_3^2 c_4 \quad + c_1 c_2 c_3^2 c_4^3 \quad + c_1 c_3^2 c_4^3 \quad + c_1 c_2^2 c_3^3 c_4 \\
& - 2 c_1 c_2^2 c_3^2 c_4 \quad - 2 c_1 c_2^2 c_3 c_4^2 \quad + c_1 c_2^2 c_3^3 \quad - 2 c_1 c_2 c_3^2 c_4^2 \quad + c_1 c_3^2 c_4^2 \quad + c_1 c_3^2 c_4^3 \quad + c_2^3 c_3^2 c_4 \\
& + c_2^2 c_3^3 c_4 \quad + c_2^2 c_3^2 c_4^2 \quad + c_2^2 c_3 c_4^3 \quad + c_2 c_3^2 c_4^2 \quad + c_2 c_3^2 c_4^3
\end{align*}
$$

This symmetric polynomial is not non-negative over $\mathbb{R}^4$. However, it is positive over $(0, +\infty)^4$. Indeed, recalling that $0 < c_1 < c_2 < c_3 < c_4$, we have that the sum of the 3 blue (respectively green, yellow, purple, orange and brown) terms is positive. For example, for the orange terms,

$$
2c_1^2 c_2 c_3^2 c_4 = c_1^2 c_2 c_3^2 c_4 + c_1^2 c_2 c_3^2 c_4 < c_1^2 c_3^2 c_4 + c_1^2 c_3^2 c_4^2.
$$

Hence, $\Sigma_1\Sigma_2\Sigma_3 - 2(\Sigma_3)^2 - 3(\Sigma_1)^2\Sigma_4 > 0$. Using the Routh-Hurwitz criterion (Proposition 3.5), we infer that all the roots of $\chi_A$ have positive real parts in this case. Assume now that $c_1 = 0$. In this case, we have $0 < c_2 < c_3 < c_4$. Moreover,

$$
\chi_A(X) = X \left( X^3 - \frac{c_2 + c_3 + c_4}{4} X^2 + \frac{(c_2 c_3 + c_2 c_4 + c_3 c_4)}{12} X - \frac{c_2 c_3 c_4}{24} \right).
$$

Using the Routh-Hurwitz criterion for the third order polynomial $\chi_A(-X)/X$ (Proposition 3.3), we
have that, if

$$
(33) \qquad \frac{c_2 + c_3 + c_4}{4} \frac{(c_2 c_3 + c_2 c_4 + c_3 c_4)}{12} - \frac{c_2 c_3 c_4}{24} > 0,
$$

then all the roots of $\chi_A$ are in the closed right half plane $\{z \in \mathbb{C} \mid \Re(z) \ge 0\}$. Moreover, (33) is obvious by expanding the left hand side and using the positivity of $c_2, c_3$ and $c_4$. This proves the result. $\square$

3.6.3. The Routh-Hurwitz stability criterion for polynomials of order 3 and 4. The following two classical stability criterion are due to Routh and Hurwtiz [23].

**Proposition 3.3** (Routh-Hurwitz criterion for polynomials of order 3). Assume that $P = X^3 + a_2 X^2 + a_1 X + a_0$ is a given polynomial of order 3 with real coefficients. If $a_2 > 0$, $a_2 a_1 - a_0 > 0$ and $a_0 > 0$, then all the (complex) roots of $P$ have negative real parts.

**Proposition 3.4** (Routh-Hurwitz criterion for polynomials of order 4). Assume that $P = X^4 + a_3 X^3 + a_2 X^2 + a_1 X + a_0$ is a given polynomial of order 4 with real coefficients. If $a_3 > 0$, $a_3 a_2 - a_1 > 0$, $a_3 a_2 a_1 - a_1^2 - a_3^2 a_0 > 0$ and $a_0 > 0$, then all the (complex) roots of $P$ have negative real parts.

**Proposition 3.5** (alternative Routh-Hurwitz criterion for polynomials of order 4). Assume that $P = X^4 + a_3 X^3 + a_2 X^2 + a_1 X + a_0$ is a given polynomial of order 4 with real coefficients. If $a_3 > 0$, $a_1 > 0$, $a_3 a_2 a_1 - a_1^2 - a_3^2 a_0 > 0$ and $a_0 > 0$, then all the (complex) roots of $P$ have negative real parts.
## 4. EXAMPLES OF RUNGE-KUTTA COLLOCATION METHODS AND ANALYSIS OF THEIR STABILITY PROPERTIES

This section is devoted to the introduction of examples of forward Runge-Kutta collocation methods with $s = 2$, $s = 4$ and $s = 5$ stages and the analysis of their stability properties with respect to Definition 2.1. Most of these methods are used as underlying methods in the linearly implicit methods analyzed in [14]. In particular, some of them serve as examples in [14] to illustrate the necessity of all the stability criterions of Definition 2.1 for the convergence of the linearly implicit methods described and implemented there, when applied to systems of ODEs arising from the spatial discretization of evolution PDEs.

**4.1. Examples with $s = 2$ stages.** We consider a Runge-Kutta collocation method with $s = 2$ stages. Assuming $c_1 < c_2$, we have the Butcher tableau

$$ \begin{array}{c|cc} c_1 & \frac{c_1(c_1/2-c_2)}{c_1-c_2} & \frac{c_1^2/2}{c_1-c_2} \\ \hline c_2 & \frac{c_2^2/2}{c_2-c_1} & \frac{c_2(c_2/2-c_1)}{c_2-c_1} \\ \hline & \frac{1/2-c_2}{c_1-c_2} & \frac{1/2-c}{c_2-c_1} \end{array} $$

The stability function then reads

$$ R(\lambda) = 1 + \lambda \left( - \frac{(1/2-c_2)(2 \lambda c_1 c_2 - \lambda c_2^2 - 2 c_1 + 2 c_2)}{(c_1-c_2)^2 (c_1 c_2 \lambda^2 - \lambda c_1 - \lambda c_2 + 2)} - \frac{(1/2-c_1) \lambda c_2^2}{(c_2-c_1)(c_1-c_2)(c_1 c_2 \lambda^2 - \lambda c_1 - \lambda c_2 + 2)} \right. \\ \left. + \frac{(1/2-c_2) \lambda c_1^2}{(c_1-c_2)^2 (c_1 c_2 \lambda^2 - \lambda c_1 - \lambda c_2 + 2)} - \frac{(1/2-c_1)(\lambda c_1^2 - 2 \lambda c_1 c_2 - 2 c_1 + 2 c_2)}{(c_2-c_1)(c_1-c_2)(c_1 c_2 \lambda^2 - \lambda c_1 - \lambda c_2 + 2)} \right). $$

These facts are used in the next four examples.

**Example 4.1** (Runge-Kutta collocation method with $s = 2$ Gauss points). For Gauss points, the method reads

$$ (34) \qquad \left| \begin{array}{c} \frac{1}{2} - \frac{\sqrt{3}}{6} \\ \frac{1}{2} + \frac{\sqrt{3}}{6} \end{array} \right| \left| \begin{array}{ccc} \frac{1}{4} & \frac{1}{4} - \frac{\sqrt{3}}{6} & \\ \frac{1}{4} + \frac{\sqrt{3}}{6} & 1/4 & \\ \frac{1}{2} & \frac{1}{2} & \end{array} \right| $$

This method is $\hat{A}$-stable and hence $\hat{I}$-stable thanks to Theorem 3.1.

**Example 4.2** (Runge-Kutta collocation method with $s = 2$ stages that is $\hat{A}$-stable). For the points $(c_1, c_2) = (1/3, 2/3)$, the method reads,

$$ (35) \qquad \left| \begin{array}{ccc} \frac{1}{3} & \frac{1}{2} & -\frac{1}{6} \\ \frac{2}{3} & \frac{2}{3} & 0 \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \end{array} \right| $$

One can check that the spectrum of the matrix A consists in 2 complex conjugate eigenvalues $\frac{1}{4} \pm i\frac{\sqrt{7}}{12}$. This method has symmetric points with respect to $1/2$ and A has no eigenvalue in $\mathbb{C}^-$. Using Remark 3.7, we infer that it is $\hat{A}$-stable, hence $\hat{I}$-stable.

**Example 4.3** (Lobatto collocation method with $s = 2$ stages). The Runge-Kutta collocation method with $s = 2$ and $(c_1, c_2) = (0, 1)$ reads

$$ \left| \begin{array}{ccc} 0 & 0 & 0 \\ 1 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & 0 \end{array} \right| $$
It is A-stable. Indeed, in this case,

$$R(\lambda) = -\frac{\lambda + 2}{\lambda - 2},$$

and hence, for $\lambda \in \mathbb{C}^-$, $|R(\lambda)| \le 1$. Moreover, this method is ASI-stable. Indeed, we have

$$(I - \lambda A)^{-1} = \begin{pmatrix} 1 & 0 \\ \frac{\lambda}{2-\lambda} & \frac{2}{2-\lambda} \end{pmatrix},$$

and hence this matrix is bounded on $\mathbb{C}^-$. Finally, the method is AS-stable since

$$\lambda b^t (I - \lambda A)^{-1} = \begin{pmatrix} \frac{\lambda}{2-\lambda} & \frac{\lambda}{2-\lambda} \\ -2 & 3 \end{pmatrix},$$

which is bounded on $\mathbb{C}^-$. Hence, this method is Â-stable.

**Example 4.4** (Runge-Kutta collocation method with $s = 2$ stages, not A- nor I-stable). *The Butcher tableau of the Runge-Kutta collocation method with $s = 2$ and $(c_1, c_2) = (1/4, 1/3)$ reads*

$$\begin{array}{c|cc} \frac{1}{4} & \frac{5}{8} & -\frac{3}{8} \\ \hline \frac{1}{3} & \frac{2}{3} & -\frac{1}{3} \\ \hline & -2 & 3 \end{array}.$$

It is neither A-stable nor I-stable. Indeed, in this case,

$$R(\lambda) = \frac{6\lambda^2 + 17\lambda + 24}{\lambda^2 - 7\lambda + 24}.$$

## 4.2. Example with $s = 4$ stages.

**Example 4.5** (Lobatto collocation method with $s = 4$ uniform points). *The Butcher tableau of the Runge-Kutta collocation method with $s = 4$ and $(c_1, c_2, c_3, c_4) = (0, \frac{1}{3}, \frac{2}{3}, 1)$ reads:*

$$\begin{array}{c|cccc} 0 & 0 & 0 & 0 & 0 \\ \hline \frac{1}{3} & \frac{1}{8} & \frac{19}{72} & -\frac{5}{72} & \frac{1}{72} \\ \hline \frac{2}{3} & \frac{1}{9} & \frac{4}{9} & \frac{1}{9} & 0 \\ \hline \frac{1}{3} & \frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8} \\ \hline & \frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8} \end{array}.$$

In particular we have, using (4),

$$R(\lambda) = \frac{-\lambda^3 - 11 \lambda^2 - 54 \lambda - 108}{\lambda^3 - 11 \lambda^2 + 54 \lambda - 108}.$$

Since the points of this method are symmetric with respect to $1/2$ and $\tau(\pi)$ has no root in $\mathbb{C}^-$, we infer (using Remark 3.7) that this method is Â-stable.

## 4.3. Examples of Runge-Kutta collocation methods with $s = 5$ stages.

4.3.1. An example of A-stable and AS-stable method which is not ASI-stable. It may happen that a Runge-Kutta collocation method is A-stable and AS-stable, yet not ASI-stable, when, for example, $\tau(\pi(X))$ and $\tau(\pi(X + 1))$ share the same roots in $\mathbb{C}^-$. In this case, $R(\lambda)$ may be smooth and with modulus bounded by 1 in $\mathbb{C}^-$, $\lambda \mapsto \lambda b^t(I - \lambda A)^{-1}$ be bounded in $\mathbb{C}^-$, while $\lambda \mapsto (I - \lambda A)^{-1}$ is not bounded in $\mathbb{C}^-$. This is for example the case for the following 5-stages method.

**Example 4.6** (An example of A-stable and AS-stable method which is not ASI-stable). *Take $c_1 = 1/4$, $c_3 = 1/2$, $c_5 = 3/4$,*

$$c_2 = \frac{1}{2} - \frac{\sqrt{7}}{14},$$
and $c_4 = 1 - c_2$. The value of $c_2$ is chosen as a solution to

$$14c_2^2 - 14c_2 + 3 = 0,$$

so that the greatest common divisor of $\tau(\pi(X))$ and $\tau(\pi(X+1))$ is not 1. Indeed, the five roots of $\tau(\pi(X))$ are simple and consist in $i\alpha$, $-i\alpha$, a positive real number and two other conjugated complex numbers of positive real part, where

$$\alpha = \frac{3\sqrt{7}}{56}.$$

Moreover, $i\alpha$ and $-i\alpha$ are also roots of $\tau(\pi(X+1))$. In particular, using (22), $\lambda \mapsto R(\lambda)$ is an analytic function in an open set containing $\mathbb{C}^-$. Thanks to Section 3.5, the fact that the points are symmetric with respect to $1/2$ implies that $\lim_{|\lambda| \to +\infty} |R(\lambda)| = 1$ and $|R(\lambda)| = 1$ for $\lambda \in i\mathbb{R}$. The maximum principle implies that $|R(\lambda)| \le 1$ for $\lambda \in \mathbb{C}^-$. Hence the method is A-stable. However, since $i\alpha$ and $-i\alpha$ are eigenvalues of A, we have

$$\|(I - \lambda A)^{-1}\|_{\lambda \to -i\alpha^{-1}} + \infty \quad \text{and} \quad \|(I - \lambda A)^{-1}\|_{\lambda \to i\alpha^{-1}} + \infty,$$

so that the method is not ASI-stable. The boundedness of $\lambda \mapsto \lambda b^t (I - \lambda A)^{-1}$ over $\mathbb{C}^-$ follows from the fact that this smooth function is bounded at infinity (degree at most $-4$ in $\lambda$) and in the neighborhood $\pm i/\alpha$ since $b$ is orthogonal to the eigenvectors of A associated with $\pm i\alpha$. Therefore the method is AS-stable.

The full Butcher tableau of this method is

$$\begin{array}{c|c|c|c|c}
\frac{1}{4} & \frac{3259}{1440} & -\frac{1421}{720} - \frac{21\sqrt{7}}{64} & \frac{163}{120} & -\frac{1421}{720} + \frac{21\sqrt{7}}{64} & \frac{829}{1440} \\
\frac{1}{2} - \frac{\sqrt{7}}{14} & \frac{\kappa_2^2(281\sqrt{7}+1120)}{15435} & -\frac{343}{180} - \frac{107\sqrt{7}}{315} & \frac{\kappa_2^2(106\sqrt{7}+455)}{10290} & -\frac{\kappa_2^2(97\sqrt{7}+770)}{17640} & \frac{\kappa_2^2(71\sqrt{7}+280)}{15435} \\
\frac{1}{2} & \frac{203}{90} & -\frac{343}{180} - \frac{7\sqrt{7}}{24} & \frac{22}{15} & -\frac{343}{180} + \frac{7\sqrt{7}}{24} & \frac{53}{90} \\
\frac{1}{2} + \frac{\sqrt{7}}{14} & -\frac{\kappa_+^2(281\sqrt{7}-1120)}{15435} & \frac{\kappa_+^2(97\sqrt{7}-770)}{17640} & -\frac{\kappa_+^2(106\sqrt{7}-455)}{10290} & -\frac{343}{180} + \frac{107\sqrt{7}}{315} & -\frac{\kappa_+^2(71\sqrt{7}-280)}{15435} \\
\frac{3}{4} & \frac{363}{160} & -\frac{147}{80} - \frac{21\sqrt{7}}{64} & \frac{63}{40} & -\frac{147}{80} + \frac{21\sqrt{7}}{64} & \frac{93}{160} \\
\hline
& \frac{128}{45} & \frac{-343}{90} & \frac{44}{15} & \frac{-343}{90} & \frac{128}{45}
\end{array}$$

where $\kappa_{\pm} = 7 \pm \sqrt{7}$.

4.3.2. A Runge-Kutta collocation method with $s = 5$ stages which is I- but not A-stable. We proved Theorem 3.2 in Section 3.6, which states that forward Runge-Kutta collocation methods with at most 4 stages that are I-stable are also A-stable. The example below shows that this is no longer the case for forward Runge-Kutta collocation methods with at least 5 stages: There exists a (forward) Runge-Kutta collocation method with $s = 5$ stages which is I-stable yet not A-stable.

**Example 4.7** (A Runge-Kutta collocation method with $s = 5$ stages which is I- but not A-stable). We consider the 5-stages Runge-Kutta collocation method defined by its Butcher tableau

$$\begin{array}{c|c|c|c|c}
\frac{1}{4} & \frac{4453}{2400} & -\frac{4347}{1600} & \frac{221}{120} & -\frac{1917}{1600} & \frac{1123}{2400} \\
\frac{1}{3} & \frac{3824}{2025} & -\frac{133}{50} & \frac{742}{405} & -\frac{179}{150} & \frac{944}{2025} \\
\frac{1}{2} & \frac{281}{150} & -\frac{513}{200} & \frac{29}{15} & -\frac{243}{200} & \frac{71}{150} \\
\frac{2}{3} & \frac{3808}{2025} & -\frac{194}{75} & \frac{824}{405} & -\frac{28}{25} & \frac{928}{2025} \\
\frac{3}{4} & \frac{1503}{800} & -\frac{4131}{1600} & \frac{81}{40} & -\frac{1701}{1600} & \frac{393}{800} \\
\hline
& \frac{176}{75} & -\frac{189}{50} & \frac{58}{15} & -\frac{189}{50} & \frac{176}{75}
\end{array}$$

This method is I-stable but not A-stable. Indeed, since the points $(c_i)_{1 \le i \le 5}$ are symmetric with respect to $1/2$, we have, using Remark 3.5 that this method is I-stable. Note that, since the matrix A has no eigenvalue on the purely imaginary axis, this method is moreover $\hat{I}$-stable, thanks to Remark 3.6. Moreover, the characteristic polynomial of A, given by $34560X^5 - 17280X^4 + 4164X^3 - 642X^2 + 71X - 6$, has 5 simple complex roots including two complex conjugates with a negative real part (approximately
$\delta_{\pm} \approx -0.0008959473813 \pm 0.1432367668i$. In this case $\lambda = 1/\delta_+$ and $\lambda = 1/\delta_-$ are poles of $R(\lambda)$, with negative real part so that the method is not $A$-stable.

5. CONCLUSION

This paper deals with stability of classical Runge–Kutta collocation methods. For the purpose of providing stability of linearly implicit methods as developed in [13] and used in [14], when applied to nonlinear evolution PDEs, we introduce and analyze several notions of stability. These notions are grouped in the definition of $\hat{A}$- and $\hat{I}$-stability (see Definition 2.1). We provide sufficient conditions that can be checked algorithmically to ensure that these stability notions are fulfilled by a given Runge–Kutta collocation method. In particular, we prove that an $A$-stable Runge–Kutta collocation method such that some polynomial $\tau(\pi)$ has no root in $\mathbb{C}^-$ is $\hat{A}$-stable (see Lemma 3.2). Since $\tau(\pi)$ can be computed from the $s$ collocation points $c_1, \cdots, c_s$, and since the fact that it has no root in $\mathbb{C}^-$ can be checked using the Routh–Hurwitz algorithm, we derive an algorithmically checkable sufficient condition to ensure that a given $A$-stable Runge–Kutta collocation method is $\hat{A}$-stable.

We also investigate the relations between $\hat{A}$- and $\hat{I}$-stability and show that a forward Runge–Kutta collocation method with $s = 5$ stages may be $I$-stable even if not $A$-stable (see Example 4.7), while all forward Runge–Kutta collocation methods with at most 4 stages that are $I$-stable are necessarily $A$-stable (Theorem 3.2). We also investigate the influence of the symmetry of the collocation points with respect to $1/2$ (see Section 3.5). A last consequence of our analysis is that Runge–Kutta collocation methods at Gauss points are $\hat{A}$- (hence $\hat{I}$-) stable (see Theorem 3.1).

ACKNOWLEDGMENTS

This work was partially supported by the Labex CEMPI (ANR-11-LABX-0007-01).

REFERENCES

[1] C. Besse. A relaxation scheme for the nonlinear Schrödinger equation. SIAM J. Numer. Anal., 42(3):934-952 (electronic), 2004.

[2] K. Burrage and J. C. Butcher. Stability criteria for implicit Runge-Kutta methods. SIAM J. Numer. Anal., 16(1):46-57, 1979.

[3] K. Burrage, W. H. Hundsdorfer, and J. G. Verwer. A study of B-convergence of Runge-Kutta methods. Computing, 36(1-2):17-34, 1986.

[4] J. C. Butcher. A stability property of implicit Runge-Kutta methods. BIT Numerical Mathematics, 15:358-361, 1975.

[5] J. C. Butcher. Thirty years of G-stability. BIT, 46(3):479-489, 2006.

[6] M. Calvo, S. González-Pinto, and J. I. Montijano. Runge-Kutta methods for the numerical solution of stiff semilinear systems. BIT, 40(4):611-639, 2000.

[7] M. Crouzeix. Sur l'approximation des équations différentielles opérationnelles linéaires par des méthodes de Runge-Kutta. PhD thesis, Université de Paris VI Thèse, 1975.

[8] M. Crouzeix. Sur les méthodes de Runge-Kutta pour l'approximation des problemes d'évolution. In R. Glowinski and J. L. Lions, editors, Computing Methods in Applied Sciences and Engineering, pages 206-223, Berlin, Heidelberg, 1976. Springer Berlin Heidelberg.

[9] M. Crouzeix. Sur la B-stabilité des méthodes de Runge-Kutta. Numer. Math., 32(1):75-82, 1979.

[10] M. Crouzeix, S. Larsson, S. Piskarëv, and V. Thomée. The stability of rational approximations of analytic semigroups. BIT, 33(1):74-84, 1993.

[11] M. Crouzeix and P.-A. Raviart. Méthodes de Runge-Kutta. Unpublished lecture notes, Université de Rennes, 1980.

[12] G. G. Dahlquist. A special stability problem for linear multistep methods. Nordisk Tidskr. Informationsbehandling (BIT), 3:27-43, 1963.

[13] G. Dujardin and I. Lacroix-Violet. High order linearly implicit methods for evolution equations. ESAIM: Mathematical Modelling and Numerical Analysis, Apr. 2022.
[14] G. Dujardin and I. Lacroix-Violet. High order linearly implicit methods for semilinear evolution pdes. preprint, 2023.

[15] B. L. Ehle. High order A-stable methods for the numerical solution of systems of D.E.'s. *Nordisk Tidskr. Informationsbehandling (BIT)*, 8:276-278, 1968.

[16] S. Gottlieb, C.-W. Shu, and E. Tadmor. Strong stability-preserving high-order time discretization methods. *SIAM Review*, 43(1):89-112, 2001.

[17] E. Hairer. Constructive characterization of A-stable approximations to exp(z) and its connection with algebraically stable Runge-Kutta methods. *Numer. Math.*, 39(2):247-258, 1982.

[18] E. Hairer. *a- and b-stability for runge-kutta methods - characterizations and equivalence*. *Numerische Mathematik*, 48:383-390, 1986.

[19] E. Hairer, S. Norsett, and G. Wanner. *Solving Ordinary Differential Equations I: Nonstiff Problems*, volume 8. Springer, 01 1993.

[20] E. Hairer and G. Wanner. Algebraically stable and implementable runge-kutta methods of high order. *SIAM Journal on Numerical Analysis*, 18(6):1098-1108, 1981.

[21] E. Hairer and G. Wanner. *Solving Ordinary Differential Equations II. Stiff and Differential-Algebraic Problems*, volume 14. Springer Verlag Series in Comput. Math., 01 1996.

[22] E. Hairer, G. Wanner, and L. C. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Springer Series in Computational Mathematics 31. Springer Berlin Heidelberg, 2nd ed edition, 2002.

[23] A. Hurwitz. Ueber die Bedingungen, unter welchen eine Gleichung nur Wurzeln mit negativen reellen Theilen besitzt. *Math. Ann.*, 46(2):273-284, 1895.

[24] C. Lubich and A. Ostermann. Runge-Kutta approximation of quasi-linear parabolic equations. *Math. Comp.*, 64(210):601-627, 1995.

[25] C. Runge. Ueber die numerische auflösung von differentialgleichungen. *Mathematische Annalen*, 46:167-178, 1895.

[26] J. M. Sanz-Serna. Runge-Kutta schemes for Hamiltonian systems. *BIT*, 28(4):877-883, 1988.

[27] M. Song and M. Z. Liu. Numerical stability and oscillation of the Runge-Kutta methods for equation $x'(t) = ax(t) + a_0x(M[\frac{t+N}{M}])$. *Adv. Difference Equ.*, pages 2012:146, 13, 2012.

[28] K. Wright. Some relationships between implicit Runge-Kutta, collocation Lanczos $\tau$ methods, and their stability properties. *Nordisk Tidskr. Informationsbehandling (BIT)*, 10:217-227, 1970.

(G. Dujardin) UNIV. LILLE, INRIA, CNRS, UMR 8524 - LABORATOIRE PAUL PAINLEVÉ, F-59000 LILLE, FRANCE, **guillaume.dujardin@inria.fr**

(I. Lacroix-Violet) **UNIVERSITÉ DE LORRAINE**, CNRS, IECL, F-54000 NANCY, FRANCE
**ingrid.lacroix@univ-lorraine.fr**