The discrete gradient methods are integrators designed to preserve invariants of ordinary differential equations. From a formal series expansion of a subclass of these methods, we derive conditions for arbitrarily high order. We derive specific results for the average vector field discrete gradient, from which we get P-series methods in the general case, and B-series methods for canonical Hamiltonian systems. Higher order schemes are presented, and their applications are demonstrated on the Hénon–Heiles system and a Lotka–Volterra system, and on both the training and integration of a pendulum system learned from data by a neural network.
Hinweise
Communicated by Christian Lubich.
The research was supported by the Research Council of Norway, through the projects SPIRIT (No. 231632) and BigDataMine (No. 309691).
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Energy preservation and discrete gradient methods
For an ordinary differential equation (ODE)
$$\begin{aligned} \dot{x} = f(x), \quad x \in \mathbb {R}^d, \quad f : \mathbb {R}^d \rightarrow \mathbb {R}^d, \end{aligned}$$
(1)
a first integral, or invariant, is a function \(H : \mathbb {R}^d \rightarrow \mathbb {R}\) such that \(H(x(t)) = H(x(t_0))\) along the solution curves of (1). If we can write
where \(S(x) : \mathbb {R}^{d \times d} \rightarrow \mathbb {R}^d\) is a skew-symmetric matrix, then (1) preserves H: this follows from the skew-symmetry of S(x), which yields
The converse is also true: McLachlan et al. showed in [30] that, whenever (1) has a first integral H, there exists a skew-symmetric matrix S(x), bounded near every non-degenerate critical point of H, such that (1) can be written on what is called the skew-gradient form:
will satisfy (2) for any non-vanishing function \(g : \mathbb {R}^d \rightarrow \mathbb {R}^d\). Many ODEs with first integrals have a well-known skew-gradient form (4). This includes Poisson systems, and the important class consisting of canonical Hamiltonian ODEs. For the latter, S will be constant, so that we may write
$$\begin{aligned} \dot{x} = S \nabla H(x). \end{aligned}$$
(6)
A numerical integrator preserving a first integral H exactly is called an integral-preserving, or energy-preserving, method. Starting in the late 1970s, a few energy-preserving methods were proposed which relied on some discrete analogue of the property (3), see e.g. [9, 23, 25, 26]. Most prominent among these is the class of methods called discrete gradient methods, defined formally by Gonzalez in [18] and given their current name in [30].
Given the first integral H, a discrete gradient \(\overline{\nabla } H : \mathbb {R}^d \times \mathbb {R}^d \rightarrow \mathbb {R}^d\) is a function satisfying the conditions
for all \(x,y\in \mathbb {R}^d\). Introducing also the discrete approximation \(\overline{S}(x,y,h)\) to S(x), skew-symmetric and satisfying \(\overline{S}(x,x,0) = S(x)\), the corresponding discrete gradient method is given by
We say that (9) is consistent to the skew-gradient system (4), since \(\overline{S}(x,\hat{x},h)\) is a consistent approximation of S(x) and \(\overline{\nabla }H(x,\hat{x})\) is a consistent approximation of \(\nabla H(x)\).
Anzeige
If \(d\ge 2\), there are in general infinitely many functions satisfying (7)–(8). Many explicit definitions of concrete discrete gradients have been suggested, and we will discuss the most prominent among them in Sect. 2.1. One of these is the average vector field (AVF) discrete gradient, first introduced in [22] and sometimes called the mean value discrete gradient [30]. For a given H, it is given by the average of \(\nabla H\) on the segment \([x,y]\):
When applied to the constant S system (6), the discrete gradient method with \(\overline{S}(x,y,h) = S\) and \(\overline{\nabla }H = \overline{\nabla }_{\text {AVF}} H\) coincides with the scheme
This is sometimes viewed as a method by itself, applicable to any system (1), in which case it is called the average vector field (AVF) method [37]. This was shown in [6] to be a B-series method.
As pointed out in [30], the discrete gradient is restricted by its definition to be at best a second order approximation to point values of \(\nabla {H}\). In much of the literature on discrete gradient methods, see e.g. [18, 21], the approximation \(\overline{S}\) is defined as being independent of h. In that case, the discrete gradient scheme (9) can at best guarantee second order convergence towards the exact solution. Over the last two decades, there have been published some notable papers on higher order discrete gradient methods. McLaren and Quispel were first out with their bootstrapping technique derived in [31, 32]. Given any discrete gradient \(\overline{\nabla }H\) and an approximation to S(x) given by \(\overline{S}(x,y,h)\), they compare the Taylor expansion of the corresponding discrete gradient scheme to that of the exact solution, and thus find a new approximation \(\tilde{S}(x,y,h)\) to S(x) which yields higher order. This quickly becomes a very involved procedure, but by using a symmetric discrete gradient, they derive fourth order methods. A downside of this method is that the schemes of order higher than two require the calculation of tensors of order three or higher at every time step.
A fourth order generalization of the AVF method is proposed by the same authors in [37]. This can be viewed as a fourth-order discrete gradient method for all skew-gradient systems where S is constant. Also worth mentioning in this setting is the collocation-like method introduced by Hairer [20] and then generalized to Poisson systems by Cohen and Hairer [10]. This is a multi-stage extension of the AVF discrete gradient method. To get higher than second order, more than one stage is required. In that case the method is not a discrete gradient method, although it is energy-preserving.
Norton et al. show in [35] that linear projection methods can be viewed as a class of discrete gradient methods for skew-gradient systems with S(x) given by the default formula (5). In connection to this, Norton and Quispel suggest in [36] the class of approximations to (5) given by
where \(\tilde{f}(x,y,h)\) is a consistent approximation to f(x), and \(\tilde{g}(x,y,h), \hat{g}(x,y,h)\) and \(\breve{g}(x,y,h)\) are all consistent approximations to \(\nabla H(x)\). The corresponding discrete gradient method then inherits the order of the method \(\hat{x}= x + h \tilde{f}(x,\hat{x},h)\).
Anzeige
The use of the discrete gradient method expands beyond the numerical integration of ODEs. It can be applied to the time-integration of partial differential equations (PDEs) which has constants of motion, guaranteeing preservation of a discrete approximation of an integral [5, 14, 16]. Higher-order methods have been studied in this context, but then only schemes that are expanding on the AVF method [3, 24]. Furthermore, building on the recently introduced Hamiltonian neural networks [8, 19], Matsubara et al. have shown how discrete gradients can be used to learn energy-preserving systems from data [27]. Since the energy is given by a neural network, none of the higher-order methods reviewed above are applicable in that case, and the authors suggest to use multi-step methods to get higher than second order.
To the best of our knowledge, no one has so far suggested higher than fourth order discrete gradient methods for a general skew-gradient system (4). Furthermore, for this general case, all discrete gradient methods suggested of higher than second order involve tensors of order three or higher. In this paper we present general theory for achieving methods of arbitrary order, using any discrete gradient and not depending on tensors of order higher than two. Largely inspired by the above mentioned references, especially [31, 32, 37], we present here a general form giving a class of approximations \(\overline{S}(x,y,h)\) to any S(x) in (4), with corresponding conditions for achieving an arbitrary order of the discrete gradient method (9). We do this step by step. In the next section, we derive some useful properties of a general discrete gradient and discuss the most common specific discrete gradients. Then we consider the AVF method and use order theory for B-series methods to obtain a generalization of this, with corresponding order conditions. In Sect. 4, we build on this to develop higher order discrete gradient methods for a general skew-gradient system, using the AVF discrete gradient. Then, in Sect. 5, we generalize this further to allow for a free choice of the discrete gradient, thus arriving at the general form \(\overline{S}(x,y,h)\) mentioned above, and a formal series expansion of the corresponding discrete gradient methods. Throughout the paper, we present several examples of higher order schemes for the different cases. In the final section, we apply some of these schemes to numerical examples: the Hénon–Heiles system with a constant S, a Lotka–Volterra system with a non-constant S, and a pendulum system learned by a neural network.
2 A preliminary analysis of discrete gradients
To simplify notation in the following derivations, we define \(g:=\nabla H\). Furthermore, we suppress the first argument of \(\overline{\nabla }H\) and define \(\bar{g}(y) := \overline{\nabla }H(x,y)\). We use Einstein summation convention, with a comma in the subscript to differentiate between components of covectors and derivatives. That is, we write \(\bar{g}(y)^i_{,j} := \frac{\partial \bar{g}(y)^i}{\partial y^j}\), \(\bar{g}(y)_{i,j} := \frac{\partial \bar{g}(y)_i}{\partial y^j}\) and so forth. Taylor expanding \(\bar{g}(y)\) around x, we get
By the consistency criterion (8), we have \(\bar{g}(x) = g(x)\). However, if we require the discrete gradient to be a differentiable function in its second argument, (8) follows directly from (7). To see this, we write (7) as
The case \(y= x\) immediately gives \(g(x)_j = \bar{g}(x)_j\), or (8). Assuming further that \(\overline{\nabla }H \in C^2(\mathbb {R}^d \times \mathbb {R}^d,\mathbb {R}^d)\), we can differentiate once more to get
where \(D^2 H :=D\nabla H\) denotes the Hessian of H, and \(D_{2} \overline{\nabla }H\) denotes the Jacobian of \(\overline{\nabla }H\) with respect to its second argument.
Lemma 1
If the discrete gradient \(\overline{\nabla }H\) is symmetric, i.e. \(\overline{\nabla }H(x,y) = \overline{\nabla }H(y,x)\) for all \(x, y \in \mathbb {R}^d\), then
Thus, for \(y= x\) we get \(\bar{g}(x)_{k,j} = \bar{g}(x)_{j,k}\), or \((D_{2} \overline{\nabla }H(x,x))^\text {T} = D_{2} \overline{\nabla }H(x,x)\). Inserting that in (18), we obtain (19).
Definition 1
Given a discrete gradient \(\overline{\nabla }H \in C^1(\mathbb {R}^d \times \mathbb {R}^d,\mathbb {R}^d)\), we define the function \(Q : \mathbb {R}^d \times \mathbb {R}^d \rightarrow \mathbb {R}^{d\times d}\) by
Note that Q(x, y) is a skew-symmetric matrix. From (18), we see that \(Q(x,x) = \frac{1}{2}D^2 H(x) - D_2\overline{\nabla }H(x,x)\). The following result is crucial for the the main result of this paper: the development of a general theory for higher order discrete gradient methods.
Lemma 2
For a discrete gradient \(\overline{\nabla }H \in C^{p}(\mathbb {R}^d \times \mathbb {R}^d,\mathbb {R})\) and the corresponding Q given by (20),
Differentiating (17) \(\kappa -1\) times by \(y\) and setting \(y= x\), we find that the \(\kappa \)th derivatives of g(x) can be expressed by the \(\kappa \)th derivatives of \(\bar{g}(x)\) through the relation
While introducing the discrete gradient methods in [18], Gonzalez also gave an example of a discrete gradient satisfying (7)–(8): the midpoint discrete gradient is given by
Even when H is analytic, this discrete gradient is often not; the second order partial derivatives are in general singular in \(y=x\). For that reason, it is not suited for achieving higher order methods by the techniques we consider in this paper.
The Itoh–Abe discrete gradient method, introduced in [23], notably does not require evaluation of the gradient. The corresponding discrete gradient, which has also been called the coordinate increment discrete gradient [30], is defined by
While the other discrete gradients we consider in this paper are symmetric and thus second order approximations to \(\nabla H\), the Itoh–Abe discrete gradient is only of first order. However, a second order discrete gradient, which we call the symmetrized Itoh–Abe (SIA) discrete gradient, is given by
Furihata presented the discrete variational derivative method for a class of PDEs in [16], a method which has been developed further by Furihata, Matsuo and co-authors in a series of papers, e.g. [29, 38], as well as the monograph [17]. As shown in [14], these schemes can also be obtained by semi-discretizing the PDE in space and then applying a discrete gradient method on the resulting system of ODEs. We give here the definition of the specific discrete gradient that gives the schemes of Furihata and co-author, defined for a class of invariants that includes all polynomial functions:
The discrete gradient introduced by Matsubara and co-authors in [27] shares some relation to the Furihata discrete gradient, in that they are both relying on a discrete analogue to the product rule for derivatives. But the former discrete gradient, obtained by what the authors call the automatic discrete differentiation algorithm, more importantly depends on an analogue to the chain rule. By using this algorithm instead of standard automatic differentiation in a neural network that learns a dynamical system from data, the discrete gradient is obtained together with the preserved energy. Thus the learned system can be integrated in an energy-preserving manner, which distinguishes the approach of Matsubara et al. from comparable studies [8, 19, 39].
Lastly we consider the AVF discrete gradient (10), which has several noteworthy characteristics.
Lemma 3
The Q(x, y) corresponding to the AVF discrete gradient is the zero matrix, since \((D_{2} \overline{\nabla }_{\text {AVF}} H (x,y))^\text {T} = D_{2} \overline{\nabla }_{\text {AVF}} H(x,y)\).
Proof
For \(\bar{g}(y) :=\overline{\nabla }_{\text {AVF}} H(x,y)\), we have
for some \(\tilde{H} : \mathbb {R}^d \times \mathbb {R}^d \rightarrow \mathbb {R}\) and all \(x, y \in \mathbb {R}^d\).
Any other discrete gradient will have these properties only for functions H for which it coincides with the AVF discrete gradient:
Proposition 1
The AVF discrete gradient is the unique discrete gradient satisfying \((D_{2} \overline{\nabla }H (x,y))^\text {T} = D_{2} \overline{\nabla }H(x,y)\) for all H, x and y, and it has the formal expansion
Assume that \(\nabla H\) is an analytic function. As in the proof of Lemma 2, let \(I = \left\{ i_1,i_2,\dots ,i_\kappa \right\} \) be an ordered set of \(\kappa \) indices, and let \(I_m\) be I with the \(m^{\text {th}}\) element excluded. If \(\bar{g}(y)_{i,j} = \bar{g}(y)_{j,i}\) for all i, j, then also
$$\begin{aligned} \bar{g}(y)_{i,I} = \bar{g}(y)_{i_m,\left\{ i,I_m\right\} } \quad \text { for all } i,I,m. \end{aligned}$$
(27)
Inserting (27) in (21) we get \(g^{(\kappa )}(x) = (1+\kappa ) \bar{g}^{(\kappa )}(x)\). Then inserting this for \(\bar{g}^{(\kappa )}(x)\) in (14), we get (26), which uniquely defines the AVF discrete gradient.
A consequence of the above result is that the AVF discrete gradient is the unique discrete gradient for which the scheme (9) with \(\overline{S}(x,\hat{x},h)=S\) is a B-series method when applied to the system (6).
As we see from the above definitions and discussion, each of the discrete gradients have their advantages and disadvantages. Gonzalez’ midpoint discrete gradient is easily calculated from the energy H and the gradient \(\nabla H\), but it is in general only once differentiable. The Itoh–Abe and Furihata discrete gradient methods do not require knowledge of the gradient, but the former is only a first order method and the latter is only defined for H of the form (24). The AVF discrete gradient is the unique discrete gradient whose series expansion is given by the differentials of the gradient. It does however require an integral to be calculated. The discrete gradient of Matsubara and co-authors has a different area of use than the others: it is only defined when H is a neural network. In that case neither Gonzelez’ midpoint, the AVF or the Furihata discrete gradients can be obtained.
In the next section we consider the specific case where the AVF discrete gradient is chosen and S is constant, so that we can build on established results for B-series methods to develop new theory.
3 A generalization of the AVF method
Let us recall the concept of B-series. Referring to the definitions in [21, Section III.1], we let T be the set of rooted trees, built recursively from starting with and letting \(\tau = [\tau _1,\ldots ,\tau _m]\) be the tree obtained by grafting the roots of the trees \(\tau _1,\ldots ,\tau _m\) to a new root. Furthermore, \(F(\tau )\) is the elementary differential associated with the tree \(\tau \), defined by and
where the integers \(\mu _1, \mu _2, \ldots \) count equal trees among \(\tau _1,\ldots ,\tau _m\). Then, if \(\phi : T \cup \lbrace \emptyset \rbrace \rightarrow \mathbb {R}\) is an arbitrary map, a B-series is a formal series
where each \(z_{njk} :=z_{njk}(x,\hat{x},h) = B(\phi _{njk},x)\) can be written as a B-series with \(\phi (\emptyset ) = 1\).
Theorem 1
When applied to (1) with \(f(x) = S\nabla H(x)\), where S is a constant skew-symmetric matrix, the scheme (31) preserves H, in that \(H(\hat{x}) = H(x)\).
$$\begin{aligned} \overline{S}(x,\hat{x},h) = S + \sum _{n=2}^{p-1} h^n \sum _{j} b_{nj} \left( \prod _{k=1}^n S D^2H(z_{njk}) + (-1)^n \prod _{k=1}^n S D^2H(z_{nj(n-k+1)}) \right) S. \end{aligned}$$
We have
$$\begin{aligned} \left( \prod _{k=1}^n \right.&\left. S D^2H(z_{njk}) \cdot S + (-1)^n \prod _{k=1}^n S D^2H(z_{nj(n-k+1)} ) \cdot S \right) ^T \\&= S^T \prod _{k=1}^n \big (D^2H(z_{nj(n-k+1)})^T S^T\big ) + (-1)^n S^T \prod _{k=1}^n \big (D^2H(z_{njk})^T S^T\big ) \\&= (-1)^{i+1} S \prod _{k=1}^n D^2H(z_{nj(n-k+1)}) S - S \prod _{k=1}^n D^2H(z_{njk}) S \\&= - \left( \prod _{k=1}^n S D^2H(z_{njk}) \cdot S + (-1)^n \prod _{k=1}^n S D^2H(z_{nj(n-k+1)} ) \cdot S \right) , \end{aligned}$$
and thus \(\overline{S}(x,\hat{x},h)\) is a skew-symmetric matrix.
Before considering the order conditions of the generalized AVF method, let us recall a couple of results from the literature on B-series.
Lemma 4
([21, Lemma III.1.9]) Let B(a, x) be a B-series with \(a(\emptyset ) = 1\). Then \(h f(B(a,x)) = B(a',x)\) is also a B-series, with \(a'(\emptyset ) = 0\), and otherwise
([34, Theorem 2.2]) Let B(a, x) and B(b, x) be two B-series with \(a(\emptyset ) = 1\) and \(b(\emptyset ) = 0\). Then \(h f'(B(a,x))B(b,x) = B(a\times b,x)\), i.e. a B-series, with and otherwise
Proposition 1 in [6] states that the standard AVF method is a B-series method. We build on the proof of that proposition to prove the following result.
Proposition 2
The generalized AVF method (31) is a B-series method.
Proof
First we define \(\hat{e} : T \cup \lbrace \emptyset \rbrace \rightarrow \mathbb {R}\) by \(\hat{e}(\emptyset ) = 1\) and \(\hat{e}(\tau ) = 0\) for all \(\tau \ne \emptyset \). Then, assuming that the solution \(\hat{x}\) of (31) can be written as the B-series \(\hat{x}= B(\Phi ,x)\), we find the B-series
Comparing the B-series of the exact solution and the B-series of the solution of (31), and noting that the elementary differentials are independent, we immediately get the following result.
Theorem 2
The generalized AVF method (31) is of order p if and only if
where \(\Phi \) is given by (33) and \(\gamma \) is given by (30).
Table 1
Elementary differentials and their coefficients in the B-series of the solution of (31), up to fourth order
\(|\tau |\)
\(F(\tau )^i\)
\(\tau \)
\(\sigma (\tau )\)
\(\gamma (\tau )\)
\(\Phi (\tau )\)
1
\(f^i\)
1
1
1
2
\(f^i_jf^j\)
1
2
\(\frac{1}{2}\)
3
\(f^i_{jk}f^jf^k\)
2
3
\(\frac{1}{3}\)
\(f^i_jf^j_kf^k\)
1
6
\(\frac{1}{4}+2\sum _j b_{2j}\)
4
\(f^i_{jkl}f^jf^kf^l\)
6
4
\(\frac{1}{4}\)
\(f^i_{jk}f^jf^k_lf^l\)
1
8
\(f^i_{j}f^j_{kl}f^kf^l\)
2
12
\(f^i_{j}f^j_{k}f^k_lf^l\)
1
24
\(\frac{1}{8}+2\sum _j b_{2j}\)
The terms \(\Phi (\tau )\) can be found from (33) by applying Lemma 5 recursively, as illustrated by the following example.
Example 1
Consider , and assume we have found \(\Phi \) for all trees up to and including order four already, as given in Table 1. We have
Then we calculate
where we have used in the second equality that . Similarly we find . Furthermore,
and . Hence,
Now, if we assume the order condition (34) to be satisfied for all trees up to and including order four, we can replace \(\sum _j b_{2j} = -\frac{1}{24}\) and in the above expression, use that , and get that (34) is satisfied for if and only if
(35)
3.1 Construction of higher order schemes
As the size of the trees grows, finding \(\Phi (\tau )\) from (33) can become quite a cumbersome operation. Furthermore, we observe from Table 1 that there are some equivalent order conditions for different trees. Before presenting more convenient techniques for finding order conditions for the generalized AVF method, let us define some more concepts related to B-series and trees.
First, recall that the Butcher product of two trees \(u = [u_1,\ldots ,u_m]\) and \(v = [v_1,\ldots ,v_n]\) is given by \(u \circ v = [u_1,u_2,\ldots ,u_m,v]\). This operation is neither associative nor commutative, and in contrast to the practice in [21], we here take the product of several factors without parentheses to mean evaluation from right to left:
Given a forest \(\mu = (\tau _1,\ldots ,\tau _m)\), the tree obtained by grafting the roots of every tree in \(\mu \) to a new root is denoted by \([\mu ] = [\tau _1,\ldots ,\tau _m]\). Moreover, \(\mu ^{-1}(\tau )\) denotes the forest such that \([\mu ^{-1}(\tau )] = \tau \). We extend the maps \(\phi : T \cup \lbrace \emptyset \rbrace \rightarrow \mathbb {R}\) and \(\gamma : T \cup \lbrace \emptyset \rbrace \rightarrow \mathbb {R}\) to forests by the letting \(\phi (\mu ) = \prod _{i=1}^m \phi (\tau _i)\) and \(\gamma (\mu ) = \prod _{i=1}^m \gamma (\tau _i)\) for \(\mu = (\tau _1,\ldots ,\tau _m)\).
Consider now a tree \(\tau \) consisting of \(|\tau |\) nodes. We may number every tree from 1 to \(|\tau |\), starting at the root and going from left to right on the increasing levels above. For a given node \(i \in \lbrace 1,\ldots ,|\tau |\rbrace \) on level \(n+1\), there exists a unique set of forests \(\hat{\tau }^i = \lbrace \mu ^i_1,\ldots ,\mu ^i_{n+1}\rbrace \) such that
Inserting this and the corresponding result for \((\phi _{njn} \times \cdots \times \phi _{nj1} \times \theta )(\tau )\) in (33), we get (37).
In [7, 15], conditions are derived for a B-series method to be energy preserving when applied to the system (6). In [37], while giving the AVF method as one such method, Quispel and McLaren present a general form of what they call energy-preserving linear combinations of rooted trees:
Here we give their result as a lemma, which is proved later by the proof of the more general Theorem 5.
Lemma 6
Let \(\mu _1, \ldots , \mu _n\) be n arbitrary forests. Then, if \(f(x)=S\nabla H(x)\) for some skew-symmetric constant matrix S, we have that \(F(\omega )(x) \cdot \nabla H(x) = 0\) for
There is a connection between (36) and Lemma 6 such that instead of order conditions for every tree, we can calculate order conditions for every energy-preserving linear combination. To see this we start by collecting the leaf nodes, i.e. nodes with no children, of the tree \(\tau \) in a set \(I_l\) and the other nodes in the set \(I_n\). If node \(i \in I_n\), we may then use the relation
to find \(\Lambda (\hat{\tau }^i)\) from the previously calculated \(\Lambda \) for a smaller tree. Then if lower order conditions are satisfied, we have numerical values for these \(\Lambda \). The leaf nodes on the other hand, with their corresponding \(\hat{\tau }^i = \lbrace \mu _1^i,\ldots ,\mu _n^i,\emptyset \rbrace \), gives an energy-preserving linear combination (38) which \(\tau \) belongs to. If i is on level two, this combination is simply \(\tau -\tau =0\), and accordingly \(\Lambda \) is not calculated for these nodes in (36). Moreover, leaves on the same level have identical \(\hat{\tau }^i\). Thus, a tree with leaves on m different levels above level two will belong to at most m non-zero energy-preserving linear combinations (38). For each of these combinations there is a corresponding order condition, with the left hand side given by (37). The right hand side can be found by considering the individual trees.
If we assume the conditions for order \(<p\) to be satisfied, we may replace (34) by
where \(|\mu |\) denotes the number of trees in the forest \(\mu \). Note that \(\Lambda (\lbrace \emptyset \rbrace ) = 1\) and hence \(\Lambda (\hat{\tau }^1) = \theta (\tau )\). Then we can calculate the numerical value for the right hand side and, if \(\tau \) has leaves on only one level \(>2\), find an order condition for both \(\tau \) and the other tree in the combination (38). This warrants an example.
Example 2
Consider again the tree , which is part of the energy-preserving linear combination Ignoring the two nodes on level 2, there are three nodes to calculate \(\Lambda \) for: \(i=1, i=4\) and \(i=5\). We find
and we have the order condition (35) for the linear combination .
If there are leaves on \(r>1\) different levels above level two, things get slightly more complicated. Then we get r different terms on the left hand side of (39) and we need to consider the order condition for \(\tau \) and the r trees it forms energy-preserving linear combinations with, so that we get an equation for every energy-preserving combination of these trees, also those not including \(\tau \). This is illustrated by the following example.
Example 3
The tree forms energy-preserving combinations with both and . Thus we have to calculate (39) for all three trees to find order conditions for the corresponding linear combinations. Starting with , which has three nodes above level two, two leaves and one non-leaf, we get
Combining (40), (41) and (42), we get the equivalent system of equations
(43)
(44)
(45)
where the choice of \(\alpha \in \mathbb {R}\) is arbitrary. The order conditions (43)–(45) can be associated to the linear combinations \(, \) and , respectively.
Table 2
Energy-preserving linear combinations of elementary differentials, and their associated order conditions for the scheme (31), up to sixth order. The coefficients \(\alpha _1, \alpha _2 \in \mathbb {R}\) are arbitrary
\(|\tau |\)
\(\omega \)
Order condition
1
–
2
–
–
3
\(\sum _j b_{2j} = -\frac{1}{24}\)
4
5
\(\sum _j b_{4j}=\frac{1}{240}\)
6
By considering the order conditions in Table 2, we find a fifth order scheme of the form (31) given by
(46)
where
$$\begin{aligned} z_1 = x + \frac{2}{5} h f(x), \qquad z_2 = x + \frac{17+\sqrt{17}}{30} h f(z_1), \qquad z_3 = x + \frac{17-\sqrt{17}}{30} h f(z_1). \end{aligned}$$
A symmetric sixth order scheme is given by
$$\begin{aligned} \frac{\hat{x}-x}{h}= & {} \, \bigg (I - \frac{13}{360} h^2 f'\big (\bar{x}+\frac{\sqrt{13}}{26} h f(\bar{x}-\frac{3\sqrt{13}}{26} h f(\bar{x}))\big ) f'\big (\bar{x}-\frac{\sqrt{13}}{26} h f(\bar{x}+\frac{3\sqrt{13}}{26} h f(\bar{x}))\big ) \nonumber \\&- \,\frac{13}{360} h^2 f'\big (\bar{x}-\frac{\sqrt{13}}{26} h f(\bar{x}+\frac{3\sqrt{13}}{26} h f(\bar{x}))\big ) f'\big (\bar{x}+\frac{\sqrt{13}}{26} h f(\bar{x}-\frac{3\sqrt{13}}{26} h f(\bar{x}))\big ) \nonumber \\&- \,\frac{1}{180} h^2 f'(x) f'(x) - \frac{1}{180} h^2 f'(\hat{x}) f'(\hat{x}) \nonumber \\&+\, \frac{1}{720}h^3 f'(\bar{x}-\frac{1}{2}hf(\bar{x})) f'(\bar{x}) f'(\bar{x}+\frac{1}{2}hf(\bar{x})) \nonumber \\&- \, \frac{1}{720}h^3 f'(\bar{x}+\frac{1}{2}hf(\bar{x})) f'(\bar{x}) f'(\bar{x}-\frac{1}{2}hf(\bar{x})) \nonumber \\&+\, \frac{1}{120} h^4 f'(\bar{x}) f'(\bar{x}) f'(\bar{x}) f'(\bar{x}) \bigg ) \int _0^1 f((1-\xi )x + \xi \hat{x}) \, \mathrm {d}\xi , \end{aligned}$$
(47)
where \(\bar{x}= \frac{x+\hat{x}}{2}\). If we wish to calculate the matrix in front of the integral explicitly, we have a non-symmetric sixth order scheme given by
$$\begin{aligned} \begin{aligned} z_1&= x + \frac{1}{4} h f(x) + \frac{3}{4} h f\big (x+\frac{2}{3} h f(x + \frac{1}{3}h f(x))\big ), \quad z_2 = x + \frac{1}{2} h f(x),\\ z_3&= x + h f(z_2), \quad z_4 = \frac{1}{2}(x+z_3) - \frac{3\sqrt{13}}{26} h f(z_2),\\ z_5&= \frac{1}{2}(x+z_3) + \frac{3\sqrt{13}}{26} h f(z_2), \\ z_6&= \frac{1}{2}(x+z_1) + \frac{\sqrt{13}}{26} h f(z_4), \quad z_7 = \frac{1}{2}(x+z_1) - \frac{\sqrt{13}}{26} h f(z_5). \end{aligned} \end{aligned}$$
4 AVF discrete gradient methods for general skew-gradient systems
We will now build on the results of the previous section by generalizing the results to the situation where S(x) in the skew-gradient system (4) is not necessarily constant. Consider therefore now an ODE of the form (4), and set again \(g :=\nabla H\). By Taylor expansion of x around \(t=t_0\) we get
$$\begin{aligned} x(t_0+h)&= \, x + h S g + \frac{h^2}{2}(S' g S g + S g' S g) + \frac{h^3}{6}(S'' g (S g, S g) + 2 S' g' (S g, S g) \\&+ S g'' (S g, S g) + S' g S' g S g + S' g S g' S g\\&+ S g' S' g S g + S g' S g' S g) + \mathcal {O}(h^4), \end{aligned}$$
where \(x:=x(t_0)\), and S, g and their derivatives are evaluated in x. Introducing the notation \(f^\circ :=S' g\) and \(f^\bullet :=S g'\), we can write this in the abbreviated form
$$\begin{aligned} x(t_0+h)= & {} \, x + h f + \frac{h^2}{2}(f^\circ f + f^\bullet f) + \frac{h^3}{6}(f^{\circ \circ } (f, f) + 2 f^{\circ \bullet } (f, f) + f^{\bullet \bullet } (f, f) \nonumber \\&+ f^{\circ } f^{\circ } f + f^{\circ } f^{\bullet } f + f^{\bullet } f^{\circ } f + f^{\bullet } f^{\bullet } f) + \mathcal {O}(h^4). \end{aligned}$$
(49)
4.1 Skew-gradient systems and P-series
A P-series is given by
(50)
where TP is the set of rooted bi-colored trees and and are the subsets of TP whose roots are black and white, respectively [21, Section III.2]. The bi-colored trees are built recursively; starting with and , we let be the tree you get by grafting the roots of \(\tau _1,\ldots ,\tau _m\) to a black root and the tree you get by grafting \(\tau _1,\ldots ,\tau _m\) to a white root. No subscript, i.e. \(\tau = [\tau _1,\ldots ,\tau _m]\), means grafting to a black root.
can be written as \((x(t_0+h),y(t_0+h)) = P(1/\gamma ,(x_0,y_0))\), where the coefficient \(\gamma \) is given by and (30). As noted in [10], setting \(f(x,y) :=S(y) \nabla H(x)\), the skew-gradient system (4) can be written as (51) with \(g=f\). When \(g=f\), all coefficients and the elementary differentials \(F(\tau )\) in (50) are given independently of the color of the root. Thus for the system (4), it suffices to consider
(52)
and we have that the exact solution of (4) can be written as \(x(t_0+h) = P(1/\gamma ,x_0)\). Breaking slightly with convention, we define a P-series to be the single row version (52) in the remainder of this paper. Denoting black-rooted subtrees by \(\tau _i\) and white-rooted subtrees by \(\bar{\tau }_i\), the elementary differentials \(F(\tau )\) for the skew-gradient system are given recursively by , and
for both and . The bi-colored trees in and their corresponding elementary differentials F are given up to order three in Table 3. The number of trees grows very quickly with the order; see https://oeis.org/A000151.
Table 3
Bi-colored trees and their elementary differentials up to third order
\(|\tau |\)
\(F(\tau )^i\)
\(F(\tau )\)
\(\tau \)
\(\alpha (\tau )\)
\(\gamma (\tau )\)
\(\sigma (\tau )\)
1
\(S^i_j g^j\)
f
1
1
1
2
\(S^i_{jk} g^j S^{k}_l g^l\)
\(f^\circ f\)
1
2
1
\(S^i_j g^j_{k} S^{k}_l g^l\)
\(f^\bullet f\)
1
2
1
3
\(S^{i}_{j k m} g^{j} S^{k}_l g^l S^{m}_n g^n\)
\(f^{\circ \circ } (f,f)\)
1
3
2
\(S^{i}_{jk} g^j_{m} S^{k}_l g^l S^{m}_n g^n\)
\(f^{\circ \bullet } (f,f)\)
2
3
1
\(S^{i}_j g^j_{k m} S^{k}_l g^l S^{m}_n g^n\)
\(f^{\bullet \bullet } (f,f)\)
1
3
2
\(S^{i}_{jk} g^{j} S^{k}_{lm} g^l S^{m}_n g^n\)
\(f^{\circ } f^{\circ } f\)
1
6
1
\(S^{i}_j g^j_{k} S^{k}_{lm} g^{l} S^{m}_n g^n\)
\(f^{\bullet } f^{\circ } f\)
1
6
1
\(S^{i}_{jk} g^{j} S^{k}_l g^{l}_m S^{m}_n g^n\)
\(f^{\circ } f^{\bullet } f\)
1
6
1
\(S^{i}_j g^j_{k} S^{k}_l g^l_{m} S^{m}_n g^n\)
\(f^{\bullet } f^{\bullet } f\)
1
6
1
The following lemma is Lemma III.2.2 in [21] amended to fit our setting.
Lemma 7
Let P(a, x) and P(b, x) be two P-series with \(a(\emptyset ) = b(\emptyset ) = 1\). Then
$$\begin{aligned} h S(P(a,x)) \nabla H(P(b,x)) = P(a \vee b,x), \end{aligned}$$
As in the proof of Proposition 2, we define \(\hat{e}\) by \(\hat{e}(\emptyset ) = 1\) and \(\hat{e}(\tau ) = 0\) for all \(\tau \ne \emptyset \). Now, assume that the solution \(\hat{x}\) of (54) can be written as the P-series \(\hat{x}= P(\Phi ,x)\). Then, using Lemma 7, we find the P-series
Note that \(\left\{ \emptyset \right\} \) counts as both a black-rooted and a white-rooted tree. Hence we have e.g.
where we also use that .
We now present a subclass of the AVF discrete gradient method, for which we will find order conditions using Lemma 7 and Lemma 8. This subclass is every AVF discrete gradient method for which the approximation of S(x) can be written in the form
each \(z_{njk} :=z_{njk}(x,\hat{x},h) = P(\phi _{njk},x)\) and each \(\bar{z}_{njk} :=\bar{z}_{njk}(x,\hat{x},h) = P(\psi _{njk},x)\) can be written as a P-series with \(\phi _{njk}(\emptyset ) = \psi _{njk}(\emptyset ) = 1\) for all n, j, k. We require that \(\sum _j b_{0j} = \frac{1}{2}\), which ensures that (56) is a consistent approximation of S(x).
Theorem 3
The discrete gradient scheme (9) with the AVF discrete gradient (10) and the approximation of S(x) given by (56) is a P-series method.
Proof
Generalizing the argument in the proof of Proposition 4, we find the P-series
$$\begin{aligned} h \, S\big (P(a,x)\big ) \int _0^1 \nabla H ((1-\xi )x + \xi \hat{x}) \, \mathrm {d}\xi&= P \bigg ( \int _0^1 \big (a \vee \big ((1-\xi )\hat{e}+\xi \Phi \big ) \big ) \, \mathrm {d}\xi , \, x \bigg ), \end{aligned}$$
where \(\bar{\theta }(a) :=\int _0^1 \big (a \vee \big ((1-\xi )\hat{e}+\xi \Phi \big ) \big ) \, \mathrm {d}\xi = \int _0^1 \big (a \vee \xi \Phi \big ) \big ) \, \mathrm {d}\xi \), so that \(\bar{\theta }(a)(\emptyset ) = 0, \), and
Thus we may write the solution \(\hat{x}\) found from applying the scheme (9) with the AVF discrete gradient (10) and \(\overline{S}(x,\hat{x},h)\) given by (56) as
The AVF discrete gradient method with \(\overline{S}\) given by (56) is of order p if and only if
$$\begin{aligned} \Phi (\tau ) = \frac{1}{\gamma (\tau )} \quad \text { for } |\tau |\le p. \end{aligned}$$
(60)
The values \(\Phi (\tau )\) can be found from (59) using (55) recursively and then (57). However, a more convenient approach is derived in the next subsection.
4.2 Order conditions
This subsection is devoted to generalizations of the results in Sect. 3.1 to the cases where S(x) is not necessarily constant. To that end, for a tree , we cut off all branches between black and white nodes and denote the mono-colored tree we are left with by \(\tau ^{b}\). We number the nodes in that tree as before, from 1 to \(|\tau ^{b}|\), and reattach the cut-off parts to the tree to get \(\tau \) again. Let \(\mu \) denote a forest of black-rooted trees and \(\eta \) a forest of white-rooted trees. Then, for a given node \(i \in [1,\ldots ,|\tau ^{b}|]\) on level \(n+1\), there exists a unique set of forests \(\hat{\tau }^i = \lbrace (\mu ^i_1,\eta ^i_1),\ldots ,(\mu ^i_{n+1},\eta ^i_{n+1})\rbrace \) such that
Inserting this and the corresponding result for \(((\psi _{nj(n+1)}, \phi _{njn}) \times \cdots \times (\psi _{nj2}, \phi _{nj1}) \times \bar{\theta }(\psi _{nj1}))(\tau )\) in (59), we get (62).
Note that if \(\tau \) only has black nodes, we have \(\Lambda (\hat{\tau }^1) = \theta (\tau ) \sum _j b_{0j} (\psi _{0j1}(\emptyset )+\psi _{0j1}(\emptyset )) = \theta (\tau )\), and also \(\Lambda (\hat{\tau }^i) = 0\) for all nodes i on level 2. Thus (61) simplifies to (36).
Like for the constant S case, the order conditions can be given for energy-preserving linear combinations of elementary differentials instead for each elementary differential. In the following generalization of Lemma 6, we state that the energy-preserving linear combinations of bi-colored rooted trees are given by
Theorem 5
Let \(\mu _1, \mu _2, \ldots , \mu _n\) be arbitrary forests of black-rooted trees and \(\eta _1, \eta _2, \ldots , \eta _{n+1}\) arbitrary forests of white-rooted trees. Given \(f(x)=S(x)\nabla H(x)\), where S(x) is a skew-symmetric matrix, and elementary differentials defined by (53), the linear combinations of trees given by
are energy-preserving in the sense that \(F(\omega )(x) \cdot \nabla H(x) = 0\).
Proof
For any forest of black-rooted trees \(\mu _j\), we have \(F([\mu _j]\circ [\emptyset ]) = S B_j S\nabla H\) for some symmetric matrix \(B_j\), suppressing the argument x. Similarly, for a forest of white-rooted trees \(\eta _j\), we have \(F([\eta _j]) = W_j\nabla H\) for some skew-symmetric matrix \(W_j\). Note that the empty forest is considered both a black-rooted and a white-rooted forest, and accordingly we have and . For these matrices \(B_j\) and \(W_j\) corresponding to the forests \(\mu _j\) and \(\eta _j\), we get
Thus \(F(\omega )(x)\) is a skew-symmetric matrix times \(\nabla H(x)\), and the statement in the above theorem follows directly.
For bi-colored trees, we define a node on the tree \(\tau \) to be a leaf if it is a leaf on the corresponding cut tree \(\tau ^{b}\) by the definition of leaves given in the previous section. We let \(I_l\) be the set of leaves and \(I_n\) the set of non-leaf nodes which are also in \(\tau ^{b}\), so that \(I_l \cup I_n = [ 1,\ldots ,|\tau ^{b}|]\). In contrast to the case with mono-colored trees, a leaf i on level one or two of a bi-colored tree may give rise to a non-zero energy-preserving linear combination; it does so if and only if \(\eta ^i_{k} \ne \emptyset \) for any \(k = 1,2\). Accordingly, \(\Lambda (\hat{\tau }^i)\) is calculated in (61) also when \(n=0,1\). Furthermore, two leaves i and j on the same level will belong to two different energy-preserving combinations if \(\eta ^i_{n+1} \ne \eta ^j_{n+1}\). Therefore we now simply state that a tree with r leaves, also including the lower two levels, belong to at most r non-zero linear combinations. We thus get r terms on the left hand side of
which is equivalent to (60) if we assume the conditions for lower order to be satisfied.
Example 4
Consider the tree , which is part of the energy-preserving linear combination . Assume that the order conditions up to and including order three are all satisfied. The cut tree has three nodes of which two are leaves. Node number 2 is a leaf on level 2 with \(\eta ^2_1 = \eta ^2_2 = \emptyset \), and thus gives \(\Lambda (\hat{\tau }^2)=0\). We find for the other two,
Even though the number of black-rooted bi-colored trees grows very quickly, e.g. to 26 for \(|\tau |=4\) and 107 for \(|\tau |=5\), finding and satisfying the order conditions is not as daunting a task as it might first appear. First of all, it suffices to find order conditions for the non-zero linear combinations given by (63). Moreover, a couple key observations simplifies the process further:
The large number of trees \(\tau \) for which , i.e. trees with no black nodes on level 2, are all energy-preserving. They can be written \(\tau = [\eta _1^1]\), and their order condition is given by
For trees that are identical except for the colors of the descendants of white nodes, it suffices to calculate one order condition. E.g. for we have the order condition , where each of the gray nodes may be black or white. To satisfy these conditions, it is natural to require that \(\bar{z}_{0j1}\) in (56) is a B-series up to order \(p-1\).
From the order conditions displayed in Table 4 we find that one second order scheme is given by (9) using the AVF discrete gradient (10) and an explicit skew-symmetric approximation of S given by \(\overline{S}(x,\cdot ,h) = S(x + \frac{1}{2} h f(x))\). A third order scheme is obtained if we instead use the skew-symmetric approximation of S explicitly given by
where \(z_1 = x + \frac{1}{3} h f(x), z_2 = x + \frac{2}{3} h f(z_1)\).
Table 4
Linear combinations \(\omega \) of bi-colored black-rooted trees corresponding to energy-preserving elementary differentials of \(f(x) = S(x)\nabla H(x)\), where S(x) is a skew-symmetric matrix, as well as their associated order conditions for the discrete gradient method (9) with the AVF discrete gradient (10) and \(\overline{S}(x,\hat{x},h)\) given by (56)
\(|\tau |\)
\(\omega \)
Order condition
1
\(2 \sum _j b_{0j} = 1\)
2
3
\(\sum _j b_{2j} = -\frac{1}{24}\)
4
A symmetric fourth order scheme is given by (9) using the AVF discrete gradient (10) and the skew-symmetric approximation of S
where \(\bar{x}= \frac{x+\hat{x}}{2}\). Another fourth order scheme is obtained if we instead use the explicit skew-symmetric approximation of S found by
$$\begin{aligned} z_1&= x + \frac{1}{2} h f(x), z_3 = x + h f(z_2), \quad z_5 = \frac{1}{3}(x+z_1+z_2) + \frac{1}{12} (-z_3+z_4),\\ z_2&= x + h f(z_1), z_4 = x + h f(z_3), \quad z_6 = \frac{\sqrt{3}}{36}(7 x-2 z_1-4z_2+z_3-2z_4). \end{aligned}$$
5 Order conditions for general discrete gradient methods
We will now generalize the results of the two previous sections to discrete gradient methods with a general discrete gradient, as defined by (7)–(8). To that end, we introduce two new series in the vein of B- and P-series, as well as related tree structures.
5.1 The constant S case
Consider mono-colored rooted trees whose nodes can have two different shapes: the circle shape of the nodes in trees of B-series, but also a triangle shape. Let TG be the set of such trees whose leaves are always circles. That is, from the first tree , every tree \(\tau \in TG\) can be built recursively through
which denotes the grafting of the trees \(\tau _1,\ldots ,\tau _m\) to a root or , respectively. The elementary differentials \(F(\tau )\) corresponding to a tree \(\tau \in TG\) are likewise defined recursively by and
We can then define a generalization of B-series which includes these elementary differentials.
where \(\phi : TG \cup \lbrace \emptyset \rbrace \rightarrow \mathbb {R}\) is an arbitrary mapping, and the symmetry coefficient \(\sigma \) is given by (28).
The G-series of the exact solution is given by \(x(t_0+h) = G(\xi ,x(t_0))\), with
For use in the remainder of this paper, we generalize the Butcher product by the definition
Furthermore, we let \(|\tau |\) denote the total number of nodes in \(\tau \), and the number of nodes of type . Let SG be the set of tall trees in TG; that is, the set of trees with only one node on each level. For a tree \(\tau \in TG\), number every tree from 1 to \(|\tau |\), as before. For any node i on level \(n+1\), we define the stem \(s^i \in SG\) to be the tall tree consisting of the nodes connecting the root to node i, including the root and node i. Denote the \(j^\text {th}\) node of \(s^i\) by \(s^i_j\), so that \(s^i_1\) is the root and \(s^i_{n+1} = i\). Then we have a unique set of forests \(\hat{\tau }^i = \lbrace \mu ^i_1,\ldots ,\mu ^i_{n+1}\rbrace \) such that
The following lemma is a generalization of Lemma 5 to G-series. Its proof is very similar to the proof of [34, Theorem 2.2], and hence omitted.
Lemma 9
Let G(a, x) and G(b, x) be two G-series with \(a(\emptyset ) = 1\) and \(b(\emptyset ) = 0\). Then the G-series \(h S D^2 H(G(a,x))G(b,x) = G(a\times b,x)\) is given by and otherwise
Moreover, \(h S Q(x,G(a,x))G(b,x) = G(a\otimes b,x)\), with and otherwise
To every stem \(s\in SG\) of height \(n+1 = |s |\), we associate coefficients \(b_{sj}\) and \(\phi _{sjk}\). Letting \(s_k\) be the \(k^{\text {th}}\) node of s, we define the function
Then we have \(h S R(\phi _{sjk},x) G(b,x) = G(\phi _{sjk} \diamond b)\), with and
with \(\phi _{sjk}(\emptyset ) = 1\) for every s, j, k, and with .
Lemma 10
The discrete gradient method (9) with \(\overline{S}(x,\hat{x},h)\) given by (70) and \(\overline{\nabla }H \in C^\infty (\mathbb {R}^d\times \mathbb {R}^d,\mathbb {R}^d)\) is a G-series method when applied to a constant S skew-gradient system (6).
Proof
Assume that the solution \(\hat{x}\) of (9) with \(\overline{S}(x,\hat{x},h)\) given by (70) can be written as the G-series \(\hat{x}= G(\Phi ,x)\). Then, using Lemma 2 and \(\overline{\nabla }H(x,x) = \nabla H(x)\),
$$\begin{aligned} h S \overline{\nabla }H(x,\hat{x}) =&\, h S \sum _{m=0}^\infty \frac{1}{m!}D_2^{m} \overline{\nabla }H(x,x)(G(\Phi ,x)-x)^m \\ =&\, h S \sum _{m=0}^\infty \frac{1}{(m+1)!}D^m\nabla H(x)(G(\Phi ,x)-x)^m \\&- h S \sum _{m=1}^\infty \frac{2m}{(m+1)!} D_2^{m-1} Q(x,x) (G(\Phi ,x)-x)^m. \end{aligned}$$
Arguing as in the proof of Lemma III.1.9 in [21], we get \(h \, S \, \overline{\nabla }H(x,\hat{x}) = G(\theta ,x)\), with \(\theta (\emptyset ) = 0, \), and
(71)
Then we can write (9) with \(\overline{S}(x,\hat{x},h)\) given by (70) as
with
(72)
Theorem 6
The discrete gradient method (9) with \(\overline{S}(x,\hat{x},h)\) given by (70) and \(\overline{\nabla }H \in C^{\infty }(\mathbb {R}^d\times \mathbb {R}^d,\mathbb {R}^d)\) is of order p if and only if
where \(\Phi \) is given by (72) and the \(\xi \) is given by (69).
We remark that \(\overline{\nabla }H \in C^{\infty }(\mathbb {R}^d\times \mathbb {R}^d,\mathbb {R}^d)\) is a necessary condition for the method to be a G-series method for all S and H, but not for its order; \(\overline{\nabla }H \in C^{p-1}(\mathbb {R}^d\times \mathbb {R}^d,\mathbb {R}^d)\) is sufficient for the scheme to be of order p. The following proposition is presented without its proof, which follows along the lines of the proof of Proposition 3.
where \(\hat{e}(\emptyset ) = 1\) and \(\hat{e}(\tau ) = 0\) for all \(\tau \ne \emptyset , \theta \) is given by (71), and
(75)
with \(\hat{s}^i\) given by \(\hat{s}^i_k = s^i_{n-k+1}\) for \(k=1,\ldots ,n\), and \(\hat{s}^i_{n+1} = s^i_{n+1}\).
As for the AVF method, one does not need to find the order conditions for every tree; it suffices to find the order condition for each energy-preserving linear combination of the form
(76)
The above does not give every energy-preserving linear combination of the elementary differentials of G-series; it gives the combinations one gets in the scheme (9) with \(\overline{S}(x,\hat{x},h)\) given by (70). Now, let again \(I_l\) and \(I_n\) denote the sets of leaf nodes and non-leaf nodes, respectively. If we assume the conditions for order \(< p\) to be satisfied, we have an equivalent order condition to (73) by
to calculate \(\Lambda (\hat{\tau }^i)\) for \(i \in I_n\). Here \(\bar{s}^i\) is \(s^i\) with \(s^i_{n+1}\) replaced by , and \(\hat{\theta }(\emptyset ) = 0, \), and
(78)
Note that \(\Lambda (\hat{\tau }^1,s^1) = \hat{\theta }(\tau )\).
Table 5
Energy-preserving linear combinations of the form (76) and their associated order conditions for the discrete gradient method (9) with \(\overline{S}(x,\hat{x},h)\) given by (70)
\(|\tau |\)
\(\omega \)
s
Order condition
1
\(\sum _j b_{sj} = \frac{1}{2}\)
2
\(\sum _j b_{sj} = \frac{1}{2}\)
3
\(\sum _j b_{sj} = \frac{1}{2}\)
\(\sum _{j} b_{sj} -\sum _{j} b_{\bar{s}j} = 0\)
\(\sum _j b_{sj} = -\frac{1}{24}\)
4
\(\sum _{j} b_{sj} = \frac{1}{2}\)
\(\sum _{j} b_{sj} -\sum _{j} b_{\bar{s}j} = 0\)
\(\sum _{j} b_{sj} - \sum _{j} b_{\bar{s}j} = 0\)
\(\sum _{j} b_{sj} = 0 \)
From the order conditions in Table 5, we can find an \(\overline{S}(x,\hat{x},h)\) so that (9) becomes a fourth order scheme for any \(\overline{\nabla }H \in C^{3}(\mathbb {R}^d\times \mathbb {R}^d,\mathbb {R}^d)\). For instance, the stem has the related order conditions \(\sum _j b_{sj} = \frac{1}{2}\) and , which sets the requirements for the term
$$\begin{aligned} h^2 \sum _{j} b_{sj} (S Q(x,z_{1j}) S Q(x,z_{2j})+S Q(x,z_{2j}) S Q(x,z_{1j})) S. \end{aligned}$$
Choosing \(b_{s1} = \frac{1}{2}\) and \(z_{11} = z_{21} = x+\frac{2}{3}h f(x)\), we have fulfilled these conditions. Likewise, finding terms that satisfy the other order conditions, we get e.g.
$$\begin{aligned} \begin{aligned} \overline{S}(x,h) =&\, S + h S \big ( \frac{8}{9} Q(x,z_3) + \frac{1}{9} Q(x,x)\big ) S \\&+ h^2 S \big ( Q(x,z_2) S Q(x,z_2) - \frac{1}{12} D^2 H(z_1) S D^2 H(z_1)\big ) S \\&+ h^3 S \big ( Q(x,x) S Q(x,x) S Q(x,x) \\&- \frac{1}{12} D^2 H(x) S D^2 H(x) S Q(x,x) - \frac{1}{12} Q(x,x) S D^2 H(x) S D^2 H(x)\big )S, \end{aligned} \end{aligned}$$
(79)
where
$$\begin{aligned} z_1 = x + \frac{1}{2} h f(x), \qquad z_2 = x + \frac{2}{3} h f(x), \qquad z_3 = x + \frac{3}{4} h f(z_1). \end{aligned}$$
5.2 The general case
Allowing for S to be a function of the solution, we define now the set TV of bi-colored trees whose nodes are either circles of triangles, and whose leaves on the cut tree \(\tau ^{b}\), defined as the mono-colored tree left when all branches between black and white nodes are cut off, are always circles. Denoting as before black-rooted subtrees by \(\tau _i\) and white-rooted subtrees by \(\bar{\tau }_i\), the elementary differentials of trees \(\tau \in TV\) are given by and
where can be either or and can be either or . Let denote the set of trees in TV with black roots, either of the shape or .
Definition 5
A V-series is a formal series of the form
(80)
where is an arbitrary mapping, and the symmetry coefficient \(\sigma \) is given by (28).
Proofs of the theorems in this subsection can be obtained similarly to the proofs in Sects. 4 and 5.1, and are therefore omitted.
We redefine
and consider now approximations of S(x) that can be written as
with \(\phi _{sjk}(\emptyset ) = \psi _{sjk}(\emptyset ) = 1\) for every s, j, k, and with .
Theorem 7
The discrete gradient scheme (9) with the approximation of S(x) given by (81) and \(\overline{\nabla }H \in C^{\infty }(\mathbb {R}^d\times \mathbb {R}^d,\mathbb {R}^d)\) is a V-series method. It can be written \(\hat{x}= V(\Phi ,x)\), with
As in Sect. 4.2, we cut the branches between black and white nodes, regardless of the shape of the nodes, and denote this tree by \(\tau ^{b}\). Number the nodes and reattach the cut-off parts. For the node i and the corresponding stem \(s^i\), there exists a unique set of forests \(\hat{\tau }^i = \lbrace (\mu ^i_1,\eta ^i_1),\ldots ,(\mu ^i_{n+1},\eta ^i_{n+1})\rbrace \) such that
where \(\hat{e}(\emptyset ) = 1\) and \(\hat{e}(\tau ) = 0\) for all \(\tau \ne \emptyset \), and
(87)
with \(\theta \) given by (71) and \(\hat{s}^i\) given by \(\hat{s}^i_k = s^i_{n-k+1}\) for \(k=1,\ldots ,n\), and \(\hat{s}^i_{n+1} = s^i_{n+1}\).
The number of trees in TV grows very quickly. However, in our task of finding higher order schemes we may use the lessons of the previous sections, and require that the arguments of \(S, D^2 H\) and Q in (81) are B-series up to order \(p-1\). Then we only need to find order conditions for energy-preserving linear combinations of the form
(88)
where \(\mu _i\) and \(\eta _i\) are forests of trees in and respectively, for \(i=1,\ldots ,n+1\). Thus we can disregard any tree with in it. Furthermore, we may color all nodes of the trees in \(\mu _i\) and \(\eta _i\) except the roots gray, and let the elementary differentials corresponding to these trees be the same as the elementary differentials of B-trees.
to calculate \(\Lambda (\hat{\tau }^i)\) for \(i \in I_n\). The \(\hat{\theta }\) is given by (78), and \(\bar{s}^i\) is \(s^i\) with \(s^i_{n+1}\) replaced by .
Example 5
Consider , which is part of the energy-preserving linear combination . We have two black nodes, and calculate
Hence the order condition associated to this linear combination is
An approximation of S(x) satisfying all the order conditions in Tables 5 and 6 is given by
$$\begin{aligned}&z_1 = x + \frac{1}{3} h f(x), \qquad z_2 = x + \frac{1}{2} h f(x), \qquad z_3 = x + \frac{7-\sqrt{7}}{12} h f(z_1),\\&z_4 = x + \frac{7+\sqrt{7}}{12} h f(z_1), \qquad z_5 = x + \frac{2}{3} h f(z_2), \qquad z_6 = x + h f(z_2), \\&z_7 = x + \frac{5}{4} h f(z_2), \qquad z_{8} = x + \frac{4}{3} h f(z_2), \qquad z_{9} = x + h f(z_6), \quad z_{10} = x + h f(z_9),\\&z_{11} = \frac{1}{3}(x+z_2+z_6) + \frac{1}{12} (-z_9+z_{10}), \qquad z_{12} = \frac{\sqrt{3}}{36}(7 x-2 z_2-4z_6+z_9-2z_{10}), \end{aligned}$$
and hence a discrete gradient scheme with this \(\overline{S}(x,\cdot ,h)\) and any \(\overline{\nabla }\in C^3(\mathbb {R}^d\times \mathbb {R}^d,\mathbb {R}^d)\) will be of fourth order.
Table 6
The energy-preserving linear combinations of the form (88) not given in Table 5, up to fourth order
\(|\tau |\)
\(\omega \)
s
Order condition
2
3
4
One advantage of choosing the AVF discrete gradient is that the resulting scheme generally requires fewer computations at each time step. This is clearly evident in the above example: if \(\overline{\nabla }= \overline{\nabla }_{\text {AVF}}\), then (89) collapses to (67). However, if the AVF discrete gradient is difficult to calculate, there can also be much to gain in computational cost by choosing a symmetric discrete gradient, like the symmetrized Itoh–Abe discrete gradient (23) or the Furihata discrete gradient (25). Then one can ignore the order condition for any combination (88) for which and \(\mu _j = \emptyset \) for some \(j \in [1,n]\), since this corresponds to elementary differentials involving Q(x, x), which we recall is zero when the discrete gradient is symmetric. If we consider the conditions for fourth order presented in Tables 5 and 6, this eliminates 17 of the 22 conditions for trees with in the stem. By considering the remaining order conditions we get that, if \(\overline{\nabla }H \in C^3(\mathbb {R}^d\times \mathbb {R}^d,\mathbb {R}^d)\) and \(\overline{\nabla }H(x,y) = \overline{\nabla }H(y,x)\), the discrete gradient scheme (9) is of fourth order if
$$\begin{aligned}&z_1 = x + \frac{1}{2} h f(x), \qquad z_2 = x + h f(z_1), \qquad z_3 = x + h f(z_2),\\&z_4 = x + h f(z_3), \qquad z_5 = \frac{1}{3}(x+z_1+z_2) + \frac{1}{12} (-z_3+z_4),\\&z_6 = \frac{\sqrt{3}}{36}(7 x-2 z_1-4z_2+z_3-2z_4), \qquad z_7 = x + \frac{3}{4}h f(z_1). \end{aligned}$$
$$\begin{aligned} \overline{S}(x,\cdot ,h) = S + \frac{8}{9} h S Q(x,z_7) S - \frac{1}{12} h^2 \, S D^2 H(z_1)S D^2 H(z_1)S. \end{aligned}$$
(91)
6 Numerical experiments
For all the examples considered in the following, the resulting discrete gradient schemes are nonlinearly implicit systems, which we here solve using Newton’s method. Note that whenever \(\overline{S}(x,\hat{x},h)\) is independent of \(\hat{x}\), the Jacobian of
$$\begin{aligned} F(\hat{x}) = \hat{x}- x - h \overline{S}(x,\hat{x},h)\overline{\nabla }H(x,\hat{x}) \end{aligned}$$
is given by
$$\begin{aligned} J(\hat{x}) = I - h \overline{S}(x,\hat{x},h) D_2 \overline{\nabla }H(x,\hat{x}), \end{aligned}$$
(92)
where \(D_2 \overline{\nabla }H(x,\hat{x})\) may also be used for the calculation of \(Q(x,\hat{x})\). The extra computational cost of using a higher-order scheme with an explicit \(\overline{S}\) thus only lies in the computation of this \(\overline{S}\) once each time step. A scheme with an implicitly defined \(\overline{S}(x,\hat{x},h)\) can give a much more complicated Jacobian, but a quasi-Newton method using the approximate Jacobian given by (92) may still be very efficient.
6.1 Hénon–Heiles system
The Hénon–Heiles system can be written in the form (6) with
where I is the \(2 \times 2\) identity matrix. We use here the same initial conditions used in [37]: \(q_1=\frac{1}{10}\), \(q_2 = -\frac{1}{2}, p_1 = p_2 = 0\). The order of some of the energy-preserving methods proposed in this paper are confirmed by the left plot in Fig. 1. We compare the performance of the fourth order discrete gradient methods obtained by using the \(\overline{S}\) given by (79) coupled with three different discrete gradients: the Itoh–Abe discrete gradient (22), the Furihata discrete gradient (25), and the AVF discrete gradient (10) (right plot of Fig. 1). The symmetrized Itoh–Abe discrete gradient (23) is for this H identical to the Furihata discrete gradient. The AVF and Furihata discrete gradient methods perform in this case very similarly, and thus the error from the Furihata discrete gradient method is excluded from the right plot in Fig. 1. We observe that, although it initially performs on par with the AVF method, the Itoh–Abe discrete gradient method gives a lower global error than the other fourth order methods as time goes on. Note however that this method requires the most computations at every time step.
Fig. 1
Error plots for the Hénon–Heiles system (93) solved by various discrete gradient methods: AVFM2/4/5/6 are AVF discrete gradient methods of different orders; FDGM4 is a fourth order Furihata discrete gradient method; IADGM4 is a fourth order Itoh–Abe discrete gradient method. RK4 is the classic Runge–Kutta method and GL4 is the fourth order Gauss–Legendre method, included for comparison. The black dashed lines in the order plot are reference lines of order two, four, five and six. The step size in the right plot is \(h=0.1\)
×
6.2 Lotka–Volterra
The methods should also be tested on a skew-gradient system with non-constant S. We choose the Lotka–Volterra system also used for numerical experiments in [10]. It is given by
and initial conditions \(x_1 = 1, x_2=\frac{19}{10}, x_3 = \frac{1}{2}\). For this H, the Itoh–Abe, Furihata and AVF discrete gradients are all equivalent. Order plots are given in Fig. 2. We consider fourth order discrete gradient methods where \(\nabla {S}\) is given either dependent on or independent of \(\hat{x}\); that is, (66) or (67). The implicitly given (67) yields a significantly lower error in the solution of the corresponding discrete gradient method, as can be witnessed from the left plot in Fig. 3. In contrast to what we observed for the canonical Hamiltonian system studied above, none of the discrete gradient methods give a global error lower than that of the fourth order Gauss–Legendre method.
Fig. 2
Order or discrete gradient methods applied to the Lotka–Volterra system (94), with different \(\overline{S}\): \(\overline{S}(x,\hat{x}) = S(\frac{x+\hat{x}}{2})\) for DGM2, (65) for DGM3, (67) for DGM4-exp, (66) for DGM4-imp. The dashed lines are reference lines of order two, three and four
Fig. 3
Error in the solution and in the energy for discrete gradient methods with \(\overline{S}\) given by \(\overline{S}(x,\hat{x}) = S(\frac{x+\hat{x}}{2})\) for DGM2, (65) for DGM3, (67) for DGM4-exp and (66) for DGM4-imp, applied to the Lotka–Volterra system, with step size \(h=0.05\). For comparison, errors from using the standard fourth order Runge–Kutta (RK4) and Gauss–Legendre (GL4) methods are also included
×
×
6.3 Hamiltonian neural networks
We present here results on the pendulum problem also considered in [19, 27]. Training data is first generated by adding noise to solutions of the system (6) with
$$\begin{aligned} S = \begin{pmatrix} 0 &{} 1\\ -1 &{} 0 \end{pmatrix}, \qquad H(q,p) = 2 m g l (1- \cos {q}) + \frac{l^2}{2 m} p^2, \end{aligned}$$
with \(l=m=1\) and \(g=3\), for various times \(t \in \left[ 0,20\right] \) and 50 randomly sampled initial coordinates. Then a Hamiltonian neural network (HNN) is used to learn the Hamiltonian. If the automatic discrete differentiation algorithm is used for the training, the corresponding discrete gradient is learned simultaneously. To compute Q(x, y), we require that the network also learns the Jacobian of the discrete gradient with respect to the second argument. This necessitates a modification of the network developed by Matsubara et al [27], which we have done using the autograd class of PyTorch. The resulting Jacobian is in any case very useful for integrating the system by any discrete gradient method, since we then can employ a root-finding algorithm that use (92), e.g. Newton’s method.
We have tested second, third and fourth order discrete gradient methods both for training the network and for integrating the obtained dynamical system. For the fourth order scheme, we have used the \(\overline{S}\) given by (91) and for the third order scheme we have used
$$\begin{aligned} \overline{S}(x,\cdot ,h) = S + h S Q(x,z) S - \frac{1}{12} h^2 \, S D^2 H(x)S D^2 H(x)S, \end{aligned}$$
(95)
where \(z = x + \frac{2}{3} h S \nabla H(x)\). Note that \(\nabla H\) and \(D^2 H\) can be obtained from the network through the relations \(\nabla H(x) = \overline{\nabla }H(x,x)\) and \(D^2 H(x) = 2 D_2\overline{\nabla }H(x,x)\).
As is also noted in [27], energy preservation seems to be more important than high order for the method used to train the system. In Fig. 4 we see an example of this: the second order discrete gradient method outperforms the fourth order Runge–Kutta method. Whether or not higher-order discrete gradient methods give an improved performance that justifies the extra computational cost is not clear on this example. A thorough investigation of this for more complex problems is a matter for future studies.
Fig. 4
The trajectories that goes through \((q,p) = (2,0)\) for the dynamical systems learned by an HNN with the Euler method, the classic Runge–Kutta method and discrete gradient methods with \(\overline{S}\) given by S (DGM2), (95) (DGM3) and (91) (DGM4). The plots for DGM2 and DGM3 are almost entirely hidden behind the plot for DGM4. The step size used in the training is \(h=0.5\)
×
For energy-preserving integration of the learned system, much can be gained in accuracy by using a higher-order discrete gradient method, at the expense of not much additional computational cost. The order plots in Fig. 5 are obtained by comparing to a solution found by the fourth order discrete gradient method with a smaller step size. Python code for the neural networks used to produce the plots in Figs. 4 and 5, and additional results on a mass-spring system, is available at https://github.com/solveeid/dgnet4.
Fig. 5
Comparison of different integrators for the pendulum system found using an HNN with the second order discrete gradient method. Left: Order plots for discrete gradient methods with \(\overline{S}\) given by S (DGM2), (95) (DGM3) and (91) (DGM4). The dashed lines are reference lines of order two, three and four. Right: Energy errors for the same methods, and the fourth-order Runge–Kutta method. Step size \(h=0.1\)
×
7 Conclusions and future work
The main purpose of this paper has been to develop order theory for discrete gradient methods. This was achieved through the introduction of the function Q, Lemma 2 and a generalization of B- and P-series results. Propositions 3, 5, 6 and 7 present results which simplifies the derivation of the conditions from the general theory. The techniques introduced in this paper for building on B- and P-series methods can possibly be used on more methods than the discrete gradient methods. Future research may utilize this.
We have proposed some higher order schemes satisfying the derived order conditions. The development of specific schemes has however not been the main focus of this paper; analysis to find more optimal schemes is something we leave for the future. After such an analysis is performed, the methods could be tested on more advanced problems than those considered above, e.g. for the temporal discretization of Hamiltonian partial differential equations, and their performance as measured by accuracy relative to computational cost could be compared to existing methods.
The use of neural networks to train dynamical systems with preservation properties is an emerging field of study where new developments are coming with a high frequency. To our knowledge, the use of higher-order one-step energy-preserving integrators in this setting has not previously been studied, and may not even have been known to be possible until the novel results of this paper. The potential utility of the methods remain largely unexplored and will be considered in future work. This will include using methods of order higher than four and analysis of the methods compared to and in connection with other recent developments, both in the training of the network and for the integration of the resulting system. It would also be interesting to investigate how the methods perform on more advanced examples, including Hamiltonian PDEs, and for Lagrangian neural networks [1, 11].
The order theory presented in this paper can also be developed further in several different directions. The schemes given with \(\overline{S}\) independent of \(\hat{x}\) are linearly implicit when H is quadratic; if the order theory is extended to the polarized discrete gradient methods of [12, 13, 28], we could get higher order linearly implicit multi-step schemes for systems with polynomial first integrals of any degree. Another avenue could be to consider order conditions for the discrete Riemannian gradient methods presented in [4]. Then the results in Sect. 5 are especially interesting, since the integral in the AVF discrete Riemannian gradient can be challenging to compute analytically. Lastly, building on [2], order conditions for the exponential AVF method is given in [33]. This could be extended to exponential integrators using any discrete gradient by the theory presented in this paper.
Acknowledgements
The author is grateful to Brynjulf Owren for the invaluable suggestions he has provided during the writing of this paper. The author would like to thank the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme Geometry, compatibility and structure preservation in computational differential equations, where work on this paper was undertaken. This work was supported by EPSRC Grant No. EP/R014604/1.
Open AccessThis 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/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
and letting \(\tau = [\tau _1,\ldots ,\tau _m]\) be the tree obtained by grafting the roots of the trees \(\tau _1,\ldots ,\tau _m\) to a new root. Furthermore, \(F(\tau )\) is the elementary differential associated with the tree \(\tau \), defined by
andand \(\sigma (\tau )\) is the symmetry coefficient for \(\tau \), defined by
andwhere the integers \(\mu _1, \mu _2, \ldots \) count equal trees among \(\tau _1,\ldots ,\tau _m\). Then, if \(\phi : T \cup \lbrace \emptyset \rbrace \rightarrow \mathbb {R}\) is an arbitrary map, a B-series is a formal seriesThe exact solution of (1) can be written as the B-series \(B(\frac{1}{\gamma },x)\), where the coefficient \(\gamma \) satisfies
andwhere \(|\tau |\) is the order, i.e. the number of nodes, of \(\tau \).
and otherwise
and otherwise
Then we may rewrite (31) aswith
, and assume we have found \(\Phi \) for all trees up to and including order four already, as given in Table 1. We have
Then we calculate
where we have used in the second equality that
. Similarly we find
. Furthermore,
and
. Hence,
Now, if we assume the order condition (34) to be satisfied for all trees up to and including order four, we can replace \(\sum _j b_{2j} = -\frac{1}{24}\) and
in the above expression, use that
, and get that (34) is satisfied for
if and only if
Here we give their result as a lemma, which is proved later by the proof of the more general Theorem 5.
, which is part of the energy-preserving linear combination
Ignoring the two nodes on level 2, there are three nodes to calculate \(\Lambda \) for: \(i=1, i=4\) and \(i=5\). We find
The right hand side of (39) becomesand we have the order condition (35) for the linear combination
.
forms energy-preserving combinations with both
and
. Thus we have to calculate (39) for all three trees to find order conditions for the corresponding linear combinations. Starting with
, which has three nodes above level two, two leaves and one non-leaf, we get
For the right hand side of (39), we get
and hence the order condition for
is
Similarly we calculate (39) for
,
and for
,
Combining (40), (41) and (42), we get the equivalent system of equations
where the choice of \(\alpha \in \mathbb {R}\) is arbitrary. The order conditions (43)–(45) can be associated to the linear combinations \(, \) and
, respectively.
whereA symmetric sixth order scheme is given bywhere \(\bar{x}= \frac{x+\hat{x}}{2}\). If we wish to calculate the matrix in front of the integral explicitly, we have a non-symmetric sixth order scheme given bywith
where TP is the set of rooted bi-colored trees and
and
are the subsets of TP whose roots are black and white, respectively [21, Section III.2]. The bi-colored trees are built recursively; starting with
and
, we let
be the tree you get by grafting the roots of \(\tau _1,\ldots ,\tau _m\) to a black root and
the tree you get by grafting \(\tau _1,\ldots ,\tau _m\) to a white root. No subscript, i.e. \(\tau = [\tau _1,\ldots ,\tau _m]\), means grafting to a black root.
and (30). As noted in [10], setting \(f(x,y) :=S(y) \nabla H(x)\), the skew-gradient system (4) can be written as (51) with \(g=f\). When \(g=f\), all coefficients and the elementary differentials \(F(\tau )\) in (50) are given independently of the color of the root. Thus for the system (4), it suffices to consider
and we have that the exact solution of (4) can be written as \(x(t_0+h) = P(1/\gamma ,x_0)\). Breaking slightly with convention, we define a P-series to be the single row version (52) in the remainder of this paper. Denoting black-rooted subtrees by \(\tau _i\) and white-rooted subtrees by \(\bar{\tau }_i\), the elementary differentials \(F(\tau )\) for the skew-gradient system are given recursively by
, andfor both
and
. The bi-colored trees in
and their corresponding elementary differentials F are given up to order three in Table 3. The number of trees grows very quickly with the order; see https://oeis.org/A000151.
and otherwise
where we also use that
.
, we cut off all branches between black and white nodes and denote the mono-colored tree we are left with by \(\tau ^{b}\). We number the nodes in that tree as before, from 1 to \(|\tau ^{b}|\), and reattach the cut-off parts to the tree to get \(\tau \) again. Let \(\mu \) denote a forest of black-rooted trees and \(\eta \) a forest of white-rooted trees. Then, for a given node \(i \in [1,\ldots ,|\tau ^{b}|]\) on level \(n+1\), there exists a unique set of forests \(\hat{\tau }^i = \lbrace (\mu ^i_1,\eta ^i_1),\ldots ,(\mu ^i_{n+1},\eta ^i_{n+1})\rbrace \) such thatThat is,
Now we can generalize Proposition 3 as follows.
and
. For these matrices \(B_j\) and \(W_j\) corresponding to the forests \(\mu _j\) and \(\eta _j\), we getWe haveThus \(F(\omega )(x)\) is a skew-symmetric matrix times \(\nabla H(x)\), and the statement in the above theorem follows directly.
, which is part of the energy-preserving linear combination
. Assume that the order conditions up to and including order three are all satisfied. The cut tree
has three nodes of which two are leaves. Node number 2 is a leaf on level 2 with \(\eta ^2_1 = \eta ^2_2 = \emptyset \), and thus gives \(\Lambda (\hat{\tau }^2)=0\). We find for the other two,
For the right hand side of (64) we getand thus the order condition
for the energy-preserving linear combination
.
, i.e. trees with no black nodes on level 2, are all energy-preserving. They can be written \(\tau = [\eta _1^1]\), and their order condition is given by $$\begin{aligned} 2 \sum _j b_{0j} \psi _{0j1}(\eta _1^1) = \frac{1}{\gamma (\tau )}. \end{aligned}$$
we have the order condition
, where each of the gray nodes may be black or white. To satisfy these conditions, it is natural to require that \(\bar{z}_{0j1}\) in (56) is a B-series up to order \(p-1\).
, every tree \(\tau \in TG\) can be built recursively through
which denotes the grafting of the trees \(\tau _1,\ldots ,\tau _m\) to a root
or
, respectively. The elementary differentials \(F(\tau )\) corresponding to a tree \(\tau \in TG\) are likewise defined recursively by
and
We can then define a generalization of B-series which includes these elementary differentials.
Furthermore, we let \(|\tau |\) denote the total number of nodes in \(\tau \), and
the number of nodes of type
. Let SG be the set of tall trees in TG; that is, the set of trees with only one node on each level. For a tree \(\tau \in TG\), number every tree from 1 to \(|\tau |\), as before. For any node i on level \(n+1\), we define the stem \(s^i \in SG\) to be the tall tree consisting of the nodes connecting the root to node i, including the root and node i. Denote the \(j^\text {th}\) node of \(s^i\) by \(s^i_j\), so that \(s^i_1\) is the root and \(s^i_{n+1} = i\). Then we have a unique set of forests \(\hat{\tau }^i = \lbrace \mu ^i_1,\ldots ,\mu ^i_{n+1}\rbrace \) such thatThat is,
The following lemma is a generalization of Lemma 5 to G-series. Its proof is very similar to the proof of [34, Theorem 2.2], and hence omitted.
and otherwise
Moreover, \(h S Q(x,G(a,x))G(b,x) = G(a\otimes b,x)\), with
and otherwise
Then we have \(h S R(\phi _{sjk},x) G(b,x) = G(\phi _{sjk} \diamond b)\), with
andConsider now the class of skew-symmetric and consistent approximations to S that can be written in the form
whenever \(\hat{x}\) is the solution ofwith \(\phi _{sjk}(\emptyset ) = 1\) for every s, j, k, and with
.
Then we can write (9) with \(\overline{S}(x,\hat{x},h)\) given by (70) as
with
with \(\hat{s}^i\) given by \(\hat{s}^i_k = s^i_{n-k+1}\) for \(k=1,\ldots ,n\), and \(\hat{s}^i_{n+1} = s^i_{n+1}\).
The above does not give every energy-preserving linear combination of the elementary differentials of G-series; it gives the combinations one gets in the scheme (9) with \(\overline{S}(x,\hat{x},h)\) given by (70). Now, let again \(I_l\) and \(I_n\) denote the sets of leaf nodes and non-leaf nodes, respectively. If we assume the conditions for order \(< p\) to be satisfied, we have an equivalent order condition to (73) bywhere we may use the relationto calculate \(\Lambda (\hat{\tau }^i)\) for \(i \in I_n\). Here \(\bar{s}^i\) is \(s^i\) with \(s^i_{n+1}\) replaced by
, and \(\hat{\theta }(\emptyset ) = 0, \), and
Note that \(\Lambda (\hat{\tau }^1,s^1) = \hat{\theta }(\tau )\).
has the related order conditions \(\sum _j b_{sj} = \frac{1}{2}\) and
, which sets the requirements for the termChoosing \(b_{s1} = \frac{1}{2}\) and \(z_{11} = z_{21} = x+\frac{2}{3}h f(x)\), we have fulfilled these conditions. Likewise, finding terms that satisfy the other order conditions, we get e.g.where
and
where
can be either
or
and
can be either
or
. Let
denote the set of trees in TV with black roots, either of the shape
or
.
where
is an arbitrary mapping, and the symmetry coefficient \(\sigma \) is given by (28).
and consider now approximations of S(x) that can be written as
whenever \(\hat{x}\) is the solution ofwith \(\phi _{sjk}(\emptyset ) = \psi _{sjk}(\emptyset ) = 1\) for every s, j, k, and with
.
The scheme is of order p if and only ifwhere
with \(\theta \) given by (71) and \(\hat{s}^i\) given by \(\hat{s}^i_k = s^i_{n-k+1}\) for \(k=1,\ldots ,n\), and \(\hat{s}^i_{n+1} = s^i_{n+1}\).
where \(\mu _i\) and \(\eta _i\) are forests of trees in
and
respectively, for \(i=1,\ldots ,n+1\). Thus we can disregard any tree with
in it. Furthermore, we may color all nodes of the trees in \(\mu _i\) and \(\eta _i\) except the roots gray, and let the elementary differentials corresponding to these trees be the same as the elementary differentials of B-trees.
.
, which is part of the energy-preserving linear combination
. We have two black nodes, and calculate
Hence the order condition associated to this linear combination is
and \(\mu _j = \emptyset \) for some \(j \in [1,n]\), since this corresponds to elementary differentials involving Q(x, x), which we recall is zero when the discrete gradient is symmetric. If we consider the conditions for fourth order presented in Tables 5 and 6, this eliminates 17 of the 22 conditions for trees with
in the stem. By considering the remaining order conditions we get that, if \(\overline{\nabla }H \in C^3(\mathbb {R}^d\times \mathbb {R}^d,\mathbb {R}^d)\) and \(\overline{\nabla }H(x,y) = \overline{\nabla }H(y,x)\), the discrete gradient scheme (9) is of fourth order ifwithIf S is constant, (90) simplifies to