In the stability theory of one-step or multistep methods for initial value problems, one is often interested in various geometric properties of the stability region \({\mathcal {S}}\subset {\mathbb {C}}\) of the method. In this work, we study the shape of the stability region of linear multistep methods (LMMs) or multiderivative multistep methods (also known as generalized LMMs) as follows.
Suppose we are given
a)
a stability region \({\mathcal {S}}\) or
b)
a family of stability regions \({\mathcal {S}}_{\beta }\) parametrized by some \(\beta \in \mathbb {R}^{d}\)
and a family of subsets of
\({\mathbb {C}}\), denoted by
\({\mathfrak {F}}\). Due to their relevance in applications, we will consider the following three classes:
-
\({\mathfrak {F}}={\mathfrak {F}}^{\text { sect}}_{\alpha }\) is the family of infinite sectors in the left half of \({\mathbb {C}}\), with vertex at the origin, symmetric about the negative real axis, and parametrized by the sector angle α ∈ (0,π/2).
-
\({\mathfrak {F}}={\mathfrak {F}}^{\text { disk}}_{r}\) is the family of disks in the left half of \({\mathbb {C}}\), symmetric with respect to the real axis, touching the imaginary axis, and parametrized by the disk radius r > 0.
-
\({\mathfrak {F}}={\mathfrak {F}}^{\text { para}}_{m}\) is the family of parabolas in the left half of \({\mathbb {C}}\), symmetric with respect to the real axis, touching the imaginary axis, and parametrized by some m > 0.
Our goal is to find the set
\(H\in {\mathfrak {F}}\) with the largest parameter (
α,
r, or
m) such that
-
\(H\subset {\mathcal {S}}\) in case a;
-
\(H\subset {\mathcal {S}}_{\beta _{\text {opt}}}\) for some stability region in the family in case b, but \(H\not \subset {\mathcal {S}}_{\beta }\) for β≠βopt.
We will present some tools to handle these shape optimization questions and, as an illustration, exactly solve some of them by using
Mathematica version 11 in the BDF (backward differentiation formula) and Enright families (as LMMs and multiderivative multistep methods, respectively), and in an infinite family of IMEX methods with
d = 2 parameters.
1.1 Motivation and main results
When solving stiff ordinary differential equations, one desirable property of the numerical method is
A-stability: a method is
A-stable if the closed left half-plane
\(\{z\in {\mathbb {C}} : \text {Re}(z)\le 0\}\) belongs to
\({\mathcal {S}}\). Many useful methods are not
A-stable, still,
\({\mathcal {S}}\) contains a sufficiently large infinite sector in the left half-plane with vertex at the origin and symmetric about the negative real axis. This leads to the notion of
A(
α)-stability: a method is
A(
α)-stable with some 0 <
α <
π/2 if
$$ \{z\in{\mathbb{C}}\setminus\{0\} : |\arg(-z)|\le \alpha\} \subset {\mathcal{S}}, $$
(1)
where the argument of a non-zero complex number satisfies −
π < arg ≤
π. The largest 0 <
α <
π/2 such that (
1) holds is referred to as the stability angle of the method [
17]. Various other stability concepts—such as
A(0)-stability,
A0-stability,
\(\overset {\circ }{\text {A}}\)-stability, stiff stability, or asymptotic
A(
α)-stability—have also been defined, and theorems are devised to test whether a given multistep method is stable in one of the above senses (see, for example, [
3,
9,
11,
20‐
23,
26,
34,
40]). There are various techniques to test
A(
α)-stability for a given
α value. In [
3], for example, the sector on the left-hand side of (
1) is decomposed into an infinite union of disks, and a bijection between each disk and the left half-plane is established via fractional linear transformations to employ a Routh–Hurwitz-type criterion. Another way of studying
A(
α)-stability is to consider the root locus curve (RLC) of the multistep method [
17]. Based on the RLC and some theorems from complex analysis, [
38] presents a criterion for a LMM to be
A(
α)-stable for a given
α; the stability angle is then obtained as the solution of an optimization problem involving Chebyshev polynomials. The procedure in [
38] is formulated only for LMMs but not for multiderivative multistep methods.
The first goal of the present work is to describe an elementary approach to exactly determine the stability angle of a LMM or multiderivative multistep method: by eliminating the complex exponential function from the RLC and using a tangency condition, a system of polynomial equations in two variables is set up whose solution yields the stability angle. This process is easily implemented in computer algebra systems. As an illustration, we consider two finite families: the BDF methods [
13,
17,
38] as LMMs and the second-derivative multistep methods of Enright [
6,
10,
17]. With
\(\alpha _{k}^{\text {BDF}}\) denoting the stability angle of the
k-step BDF method for 3 ≤
k ≤ 6, we show that
\(\tan \left (\alpha _{k}^{\text {BDF}}\right )\) is an unexpectedly simple algebraic number, having degree 2 for
k ∈{3,4,6} and degree 4 for
k = 5 (see Table
1). For the
k-step Enright methods with 3 ≤
k ≤ 7, the corresponding constants
\(\tan \left (\alpha _{k}^{\text {Enr}}\right )\) (with approximate values listed in Table
2) are much more complicated algebraic numbers of increasing degree (starting with 22). As far as we know, exact values
α ∈ (0,
π/2) for the stability angles of multistep methods were not presented earlier in the literature.
Table 1
The exact stability angles \(\alpha _{k}^{\text {BDF}}=\frac {180}{\pi }\arctan \left (c_{k}^{\text {BDF}}\right )\) of the BDF methods expressed in degrees
3 | \(\frac {329 \sqrt {\frac {7}{5}}}{27}\) | 86.032366860211647332∘ |
4 | \(\frac {699 \sqrt {\frac {3}{2}}}{256}\) | 73.351670474578482110∘ |
5 | \(\frac {1326107429}{25} \sqrt {\frac {62}{53860574450525125 + 1194498034900685 \sqrt {2033}}}\) | 51.839755836049910391∘ |
6 | \(\frac {45503}{10125 \sqrt {195}}\) | 17.839777792245700101∘ |
Table 2
Stability angles \(\alpha _{k}^{\text {Enr}}=\frac {180}{\pi }\arctan \left (c_{k}^{\text {Enr}}\right )\) of the Enright methods expressed in degrees
3 | 27.056933440109472532101963 | 87.8833627693413031369003498∘ |
4 | 7.1406622283653916403051061 | 82.0279713768712835947479188∘ |
5 | 3.2907685080317853840110455 | 73.0970020659749082763655203∘ |
6 | 1.7285146253131256601603521 | 59.9492702555400766770433070∘ |
7 | 0.7703217281441388675578954 | 37.6078417405752150238159031∘ |
The stability radius of a multistep method is the largest number
r > 0 such that the inclusion
$$ \{z\in\mathbb{C} : |z+r|\le r\} \subset {\mathcal{S}} $$
holds. The stability radius plays an important role when analyzing the boundedness properties of multistep methods. For example, it has been proved [
42, Theorem 3.1] that this radius is the largest step-size coefficient for linear boundedness of a LMM satisfying some natural assumptions.
The second goal of the present work is to compute the stability radius for some multistep methods. We will achieve this by using again the algebraic form of the RLCs. Table
3 contains the exact values in the BDF family for 3 ≤
k ≤ 6.
Table 3
The exact stability radii \(r_{k}^{\text { BDF}}\) of the BDF methods
3 | \(\left (17+8 \sqrt {10}\right )/6\) | 7.049703546891172 |
4 | {18432, 2172,− 100855,− 114975} | 2.727199466336645 |
5 | {2944512000, 260854387200, 679386763440, | |
| 266052478296,− 1280160594125,− 1354065829875} | 1.357947301777465 |
6 | {141717600000, 558150393600, 1112790780640, | |
| 948530730784,− 119637602525,− 488414721375} | 0.559931687924882 |
The RLC, as the graph of a
\([0,2\pi ]\to \mathbb {C}\) function (or a union of such functions for generalized LMMs), yields information about the boundary of the stability region,
\(\partial {\mathcal {S}}\). It is known, however, that in general the RLC does not coincide with
\(\partial {\mathcal {S}}\) (see Fig.
3). This does not pose a problem when a fixed multistep method is considered—one can evaluate the roots of the characteristic polynomial at finitely many test points sampled from different components of
\({\mathbb {C}}\) determined by the RLC to see which component belongs to
\({\mathcal {S}}\) and which one to
\({\mathbb {C}}\setminus {\mathcal {S}}\). But when working with parametric families of multistep methods, the precise identification of the stability region boundaries or components can become challenging with the RLC method. One can overcome this difficulty for example by invoking a reduction process, the Schur–Cohn reduction, formulated in, e.g., [
37]. Instead of using auxiliary fractional linear transformations and applying Routh–Hurwitz-type criteria [
28,
36] as mentioned above, these Schur–Cohn-type theorems in [
37] are directly tailored to the context of multistep methods to locate the roots of the characteristic polynomials with respect to the unit disk.
The third goal of the present work is to demonstrate the effectiveness of the Schur–Cohn reduction when we solve two optimization case studies in a family of implicit-explicit (IMEX) multistep methods taken from [
18]. On the one hand, we find the method in the IMEX family that has the largest stability angle, that is, the method whose stability region contains the largest sector (see our Theorem 5.3). On the other hand, we illustrate the versatility of the reduction technique by also finding the method whose stability region contains the largest parabola (see Theorem 6.1); the inclusion of a parabola-shaped region in
\({\mathcal {S}}\) is relevant when studying semi-discretizations of certain partial differential equations (PDEs) of advection-reaction-diffusion type [
5,
18,
28]. The chosen IMEX family is described by two real parameters, and the corresponding characteristic polynomial is cubic. The Schur–Cohn reduction process recursively decreases the degree of the characteristic polynomial, so instead of analyzing the roots of high-degree polynomials, we finally need to check polynomial inequalities in the parameters present in the coefficients of the original polynomial. Besides the two real parameters, two complex variables are involved in our calculations—the non-trivial interplay between these six real variables determines the optimum in both cases. We emphasize that we solve the optimization problem exactly, and RLCs are not relied on in the rigorous part of the proofs (only when setting up conjectures about the optimal values).
1.2 Structure of the paper
In Section
2.1, we introduce some notation. In Sections
2.2–
2.3, we review the Schur–Cohn reduction and the definition of the stability region of a multistep method. In Sections
2.4–
2.5, the definition of the root locus curve is recalled in two special cases: for linear multistep methods and for second-derivative multistep methods. Here, we consider the BDF and Enright families as concrete examples.
Regarding the new results, a simple algebraic technique is described in Section
3.1 to exactly compute the stability angle of a linear multistep or multiderivative multistep method. Stability angles for the BDF and Enright families are tabulated in Sections
3.2–
3.3. In Section
4, we exactly compute the stability radii in the BDF family by using the same approach. In Section
5, we first describe a two-parameter family of IMEX multistep methods, in which we determine the unique method with the largest stability angle, then, in Section
6, the unique method whose stability region contains the largest parabola. The techniques in Sections
5–
6 do not rely on root locus curves but use the Schur–Cohn reduction instead; the full proofs are deferred to Appendices
A and
B.