Unified analysis for variational time discretizations of higher order and higher regularity applied to non-stiff ODEs

We study variational time discretization methods applied to non-stiff initial value problems of the form where f is supposed to be sufficiently smooth and to satisfy a Lipschitz condition on the second variable. Here, an initial value u₀ is given at t = t₀. The system of ordinary differential equations (ODEs) is considered on a time interval I = (t₀,t₀ + T] with arbitrary but fixed length T > 0.

Probably the most popular variational discretization schemes for solving (1.1) numerically are discontinuous Galerkin (dG) methods, cf. [15], and continuous Galerkin–Petrov (cGP) methods, cf. [13]. Both types of methods have been studied in the literature for many decades. However, an important part for the design of a then fully computable discretization, namely the use of quadrature methods for approximate integration, is often only marginally considered or the assumptions on the quadrature formulas are quite restrictive and, thus, allow a small variability of quadrature formulas only. So, for example, the number of quadrature points is supposed to equal the dimension of the local ansatz space of the discrete solution, cf. [6, 7], or the number of independent variational conditions, cf. [13, 14]. Often also the investigations are restricted to special Gauss, Gauss–Radau, or Gauss–Lobatto formulas. A quite general setting is considered in [9] where different ways to approximate the integrals over products of f with test functions are studied. Since in [9] the dynamical behavior of the schemes is analyzed, it is assumed that at least for Dahlquist’s test problem \(u^{\prime } = \lambda u\) all integrals are integrated exactly which again is quite restrictive.

In this paper, we try to keep the requirements on the approximation operators involved in the definition of the discrete method as low as possible. Our scope is to figure out how the approximation properties of these operators affect the error behavior of the numerical solution. Thereby, our studies are not restricted to the dG or cGP method but cover the whole family of variational discretization methods recently introduced in [3, 4]. The used assumptions are quite general and abstract in order to enable the study of a wide variety of methods. Especially, we allow that the right-hand side is approximated by a composition of various interpolation operators (interpolation cascade) or that the quadrature formulas also use derivative values. Therefore, all variational methods considered in [3] and their convergence results can be verified by a rigorous and unified error analysis in the non-stiff case now.

The paper is structured as follows. In Section 2, the variational time discretization methods are formulated. The well-definedness of the method formulation is studied in Section 3 where the existence of unique discrete solutions is proven under appropriate conditions. Section 4 is devoted to the error analysis. Here, at first, the global error is bounded by a sum of rather abstract approximation error terms. Then, in order to give a better insight into the error behavior, the convergence orders of these approximation errors are estimated in terms of basic quantities describing the approximation properties of the involved operators. Thereafter, superconvergence results in the time mesh nodes are derived in Section 5. Finally, in Section 6, we use numerical experiments to illustrate the convergence behavior of the variational time discretization methods and show that the proven estimates are sharp.

In order not to obscure the view on the main arguments, we have reduced the proofs to the essential ideas. For the technical details and a more detailed tracing of the constants, we refer the reader to the preprint version [2]. Specific references are given at the beginning of each proof.

Notation: In this paper, C denotes a generic constant independent of the time mesh interval length. To describe the vector-valued case (d > 1) in an easy way, let (⋅,⋅) be the standard inner product and ∥⋅∥ the Euclidean norm on \({\mathbb {R}}^{d}\), \(d \in {\mathbb {N}}\).

For an arbitrary interval J and positive integers q, the spaces of continuous and k times continuously differentiable \({\mathbb {R}}^{q}\)-valued functions on J are written as \(C(J,{\mathbb {R}}^{q})\) and \(C^{k}(J,{\mathbb {R}}^{q})\), respectively. For non-negative integers s, we write \(P_{s}(J, {\mathbb {R}}^{q})\) for the space of \({\mathbb {R}}^{q}\)-valued polynomials of degree less than or equal to s. Moreover, \(P_{-1}(J,{\mathbb {R}}^{q}) := \{0\}\). For q = 1, we sometimes omit \({\mathbb {R}}^{q}\). Further notation will be introduced later at the beginning of the sections where it is needed.

The interval I is decomposed by into N disjoint subintervals I_n := (t_n− 1,t_n], n = 1,…,N. Moreover, we set

For convenience and to simplify the notation in some proofs, we assume τ_n ≤ 1 which is not really a restriction since we are interested in the asymptotic error behavior for τ → 0. For any piecewise continuous function v, we define by the one-sided limits and the jump of v at t_n. Furthermore, standard notation for the floor function is used.

We now present a slight generalization of the variational time discretization methods \({\mathbf {VTD}_{k}^{r}}\) investigated in [3]. Let \(r, k \in {\mathbb {Z}}\), 0 ≤ k ≤ r. Then, the local version (I_n-problem) of the numerical method reads as follows:

Given \(U\left (t_{n-1}^{-}\right )\in \mathbb {R}^{d}\), find \(U\in P_{r}\left (I_{n},\mathbb {R}^{d}\right )\) such that and where \(U(t_{0}^{-}) = u_{0}\) and δ_i,j is the Kronecker symbol.

Here, \({{\mathscr{I}}_{n}}\) denotes an integrator that typically represents either the integral over I_n or the application of a quadrature formula for approximate integration. Details will be described later on. Moreover, \({\mathcal {I}}_{n}\) could be used to model some projection/interpolation of f or the usage of some special quadrature rules even if \({\mathscr{I}}_{n}\) is just the integral.

The problem class (2.1a) generalizes discontinuous Galerkin methods (corresponding to k = 0) and continuous Galerkin methods (corresponding to k = 1). The conditions (2.1b) and (2.1c) are higher order collocation conditions at the end points of the subintervals involving derivatives of the considered system of ordinary differential equations. For more details, we refer to [3, Remark 2.1].

First of all, we agree that both \({{\mathscr{I}}_{n}}\) and \(\mathcal {I}_{n}\) are local versions (obtained by transformation) of appropriate linear operators \({\widehat {{\mathscr{I}}}}\) and \(\widehat {\mathcal {I}}\) given on the closure of the reference interval (− 1,1]. However, \({\mathscr{I}}_{n}\) is an approximation of the integral operator while \({\mathcal {I}}_{n}\) approximates the identity operator. Thus, the transformations scale quite differently. More precisely, let denote the affine transformation that maps the reference interval (− 1,1] on an arbitrary mesh interval I_n = (t_n− 1,t_n]. Furthermore, let \({k_{{\mathscr{I}}}}\) and \({k_{\mathcal {I}}}\) be the smallest non-negative integers such that \(\widehat {{\mathscr{I}}}\) and \({\widehat {\mathcal {I}}}\) are well-defined for functions in \(C^{{k_{{\mathscr{I}}}}}([-1,1])\) and \(C^{k_{\mathcal {I}}}([-1,1])\), respectively. Then, we have for all \(\varphi \in C^{{k_{{\mathscr{I}}}}}(\overline {I}_{n},{\mathbb {R}}^{d})\) and for all \(\psi \in C^{k_{\mathcal {I}}}(\overline {I}_{n},{\mathbb {R}}^{d})\) that Of course, these operators act component-wise when applied to vector-valued functions. Moreover, we suppose for all non-negative integers l that \(\widehat {\mathcal {I}} \hat {v} \in C^{l}([-1,1])\) holds for all \(\hat {v} \in C^{\max \limits \{ k_{\mathcal {I}} , l \}}([-1,1])\), i.e., \(\widehat {\mathcal {I}} \hat {v}\) is at least as smooth as \(\hat {v}\).

The study of existence and uniqueness of solutions to (2.1) as well as the later error analysis is strongly connected with the following operator. Let \({\widehat {\mathcal {J}}^{{\mathscr{I}}, {\mathcal {I}}}} : C^{{k_{\mathcal {J}}}+1}([-1,1]) \to P_{r}([-1,1])\) where \(k_{\mathcal {J}} := \max \limits \left \{\left \lfloor \frac {k}{2} \right \rfloor -1,k_{{\mathscr{I}}}, k_{\mathcal {I}}\right \}\) be defined by

In the following, we assume that the inverse inequalities

hold true where C_inv > 0 is independent of τ_n but may depend on l and r. The proof is standard and uses transformations to together with norm equivalences on finite dimensional spaces on the reference interval.

For the proof of the existence and uniqueness of solutions of (2.1a), we need some more assumptions.

Now, we investigate the solvability of the local problem (2.1a).

In order to prove an error estimate, we reuse the operator \(\widehat {\mathcal {J}}^{{\mathscr{I}}, {{{\mathcal {I}}}}}\) introduced in the previous section. By transformation, we get for n = 1,…,N local approximation operators \(\mathcal {J}_n^{{\mathscr{I}}, {{\mathcal {I}}}}:C^{k_{\mathcal {J}}+1}\left (\overline {I}_{n},\mathbb {R}^{d}\right ) \to P_{r}\left (I_{n},\mathbb {R}^{d}\right )\) satisfying

Of course, these operators are well-defined under Assumption 1.

For convenience, we define for \(v \in C^{k_{\mathcal {J}}+1}\big (\overline {I},\mathbb {R}^{d}\big )\) a global approximation operator \(\mathcal {J}^{{\mathscr{I}}, {{\mathcal {I}}}}\) by combining the local approximations on the mesh intervals, i.e., \(\big .\big (\mathcal {J}^{{\mathscr{I}}, {{\mathcal {I}}}}v\big ) \big |_{I_{n}} = \mathcal {J}_n^{{\mathscr{I}}, {{\mathcal {I}}}}(v|_{I_{n}}) \in P_{r}\big (I_{n},\mathbb {R}^{d}\big )\) for n = 1,…,N and setting \(\mathcal {J}^{{\mathscr{I}}, {{\mathcal {I}}}} v(t_{0}^{-}) = v(t_{0}^{-}) = v(t_{0})\). Note that even for k ≥ 1, in general \({\mathcal {J}^{{\mathscr{I}}, {{\mathcal {I}}}}} v\) is not globally continuous.

In order to prove the error estimate we need to strengthen the assumptions since derivatives can be handled given in certain points, but not their supremum. Therefore, compared to Theorem 5, we replace Assumption 3 by Assumptions 5a or 5b. Furthermore, we need an auxiliary interpolation operator \({\mathcal {I}^{\text {app}}}\), see Definition 7, which amongst others is based on these assumptions.

For brevity, the Assumptions 5a and 5b below are stated directly for the local operators \({\mathscr{I}}_{n}\) and \({\mathcal {I}}_{n}\). However, appropriate properties of \(\widehat {{\mathscr{I}}}\) and \({\widehat {\mathcal {I}}}\) guarantee these assumptions by transformation, cf. Assumptions 2 and 3.

Now, we are able to prove an abstract error estimate.

Of course, Theorem 8 provides an abstract bound for the error of the variational time discretization method. However, the order of convergence still is not clear. Since \({\mathcal {I}^{\text {app}}}\) is an Hermite-type interpolator of ansatz order larger than or equal to r its approximation order is at least r + 1. It remains to prove suitable bounds on the error of the approximation operator \({{\mathcal {J}}^{{\mathscr{I}}, {\mathcal {I}}}}\).

Using standard techniques the above quantities can be connected with certain approximation estimates. For example, let \(\check {r} \in {\mathbb {N}}_{0}\) then together with Assumption 2 we find that for arbitrary \(\varphi \in C^{\max \limits \{k_{{\mathscr{I}}},\min \limits \{\check {r},r_{\text {ex}}^{{\mathscr{I}}}+1\}\}}\left (\overline {I}_{n},\mathbb {R}^{d}\right )\).

In many cases, the approximation error of \(\mathcal {J}^{{\mathscr{I}}, {{\mathcal {I}}}}\) in the mesh points \(t_{n}^{-}\) behaves much better than the pointwise estimate of Lemma 12 suggests. However, to see this, we need some further knowledge on the approximation property connected with the quantity \({r_{{\mathcal {I}},{{i}}}^{{\mathscr{I}}}}\). Besides, the respective result presented in the following lemma will be also used later in the superconvergence analysis.

Now, we can state and prove the improved estimate for the approximation error of \(\mathcal {J}^{{\mathscr{I}}, {{\mathcal {I}}}}\) in the mesh points \(t_{n}^{-}\).

Finally, summarizing the above results, we now want to list the proven convergence orders.

If \(\max \limits \left \{r_{\text {ex}}^{{\mathscr{I}}},r_{\mathcal {I}}^{{\mathscr{I}}}+1\right \} \geq r-1\) is satisfied, we obtain formally for the \(W^{1,\infty }\) seminorm. However, this also gives (4.18) only.

In order to prove superconvergence in time mesh points, we exploit a special representation of the discrete problem (2.1a). To this end, we need one further approximation operator \(\widehat {\mathcal {P}}^{{\mathscr{I}}, {{\mathcal {I}}}}\), see [2, (5.1)], which is connected to \(\widehat {\mathcal {J}}^{{\mathscr{I}}, {{\mathcal {I}}}}\) in such a way that \(\widehat {\mathcal {P}}^{{\mathscr{I}}, {{\mathcal {I}}}}(\hat {v}^{\prime }) = (\widehat {\mathcal {J}}^{{\mathscr{I}}, {{\mathcal {I}}}}\hat {v})'\) holds true. For brevity, we directly consider its local version \(\mathcal {P}_n^{{\mathscr{I}}, {{\mathcal {I}}}}\). Then, analogously to the respective statements for \(\mathcal {J}^{{\mathscr{I}}, {{\mathcal {I}}}}_{n}\), we get the following.

Inspecting the definition of U in (2.1a) and (5.1), we find that Therefore, since for k ≥ 1 furthermore \(U\left (t_{n-1}^{+}\right ) = U_{n-1}^{-}\) with \(U_{n-1}^{-}\) given, the discretization method fits into the unified framework of [1] for k ≥ 1.

Summarizing the above observations, our analysis guarantees the following estimates in the time mesh points.

We consider the initial value problem of a system of non-linear ordinary differential equations which has as solution.

The non-linear systems within each time step were solved by Newton’s method where we applied a Taylor expansion of the inherited data from the previous time interval to calculate an initial guess for all unknowns on the current interval. If higher order derivatives were needed at initial time t₀ = 0, we applied

based on the ode system (1.1) and its derivatives.

By considering different choices for \({{{\mathscr{I}}}}_{n}\) and \(\mathcal {I}_{n}\), we will show that our theory provides sharp bounds on the convergence order. Since \({\mathscr{I}}_{n}\) and \({\mathcal {I}}_{n}\) are obtained from \(\widehat {{\mathscr{I}}}\) and \({\widehat {\mathcal {I}}}\) via transformation, we only specify the reference operators.

Each integrator \({{\widehat {{\mathscr{I}}}}}\) that has been used in our calculations is based on Lagrangian interpolation with respect to a specific node set \(P_{\widehat {{\mathscr{I}}}}\). Hence, we have \({k_{{\mathscr{I}}}}=0\). The interpolation operator \({\widehat {\mathcal {I}}}\) is of Lagrange-type and uses the node set \(P_{{\widehat {\mathcal {I}}}}\). This means that \({k_{\mathcal {I}}}=0\). Both node sets are given for each of our test cases. Since often nodes of quadrature formulas are used, we also write for instance “left Gauss–Radau(k)” to indicate that the nodes of the left-sided Gauss–Radau formula with k points have been used. All upcoming settings fulfill Assumption 1.

For all test cases, the method \({\mathbf {VTD}_{3}^{6}}\), which is cGP-C¹(6), was applied as discretization. All calculations were carried out with the software Julia [5] using the floating point data type BigFloat with 512 bits. Errors were measured in the norms where ∥⋅∥ denotes the Euclidean norm in \(\mathbb {R}^{d}\).