In the following we explain and illustrate this approach by means of examples. For the purpose of generating order conditions it is sufficient to consider the case of a linear operator split into two parts A and B. We denote. This leading error term is a linear combination of higher-order commutators of the operators A and B. For this purpose we use the so-called Lyndon basis, also called Lyndon—Shirshov basis, of the free Lie algebra generated by A and B.
Assuming these first-order conditions are satisfied, the second derivative d 2 d h 2 L 0 , which now represents the leading error term, simplifies to the commutator expression. Generate the representation of d 3 d h 3 L 0 we do not display it here. This process is based on a special bijection between associative Lyndon words and bracketed, non-associative versions of these words which, in our context, are identified with higher-order commutators representing basis elements for the free Lie algebra generated by A and B.
The expanded version of such a commutator is a Lie polynomial in terms of the non-commutative variables A and B. The commutators are bracketed, non-associative versions of these words, 4. As mentioned above, the leading lowest monomials in the expanded commutators, in the sense of lexicographical order, correspond to the Lyndon words. The situation displayed in this example occurs also in the general case. The order conditions generated by the algorithm indicated in Sect. However, there exist special cases:.
Since symmetric schemes have an even order p cf. The general algorithm described in Sect. Interchanging the roles of A and B , i. If S is palindromic then. For an ansatz with palindromic coefficients, exchanging the roles of A and B in the algorithm from Sect. Due to this redundancy the number of order conditions is appropriately reduced.
A popular class of composition methods are symmetric Strang compositions. Some of the composition coefficients have to be chosen negative, and the local error measures of these composition schemes are rather large.
On the other hand, for higher orders, composition beats the generic lower limits on the number s of stages such that a given order p can be expected. Evidently, symmetric compositions are an attractive option for constructing higher-order schemes. Therefore we have included this class into our considerations concerning the search for optimal variants see Sect. Our considerations are not restricted to schemes with real coefficients a j , b j.
We also consider evolution equations where the right-hand side splits into three parts,. On the basis of these identities, the algorithm from Sect. Concerning symmetries, similar considerations as in Sect. For example, splitting into three operators can be used to handle evolution equations where the right-hand side splits up into two non-autonomous parts.
In this case, splitting means that the variable t is frozen over several subintervals comprising an integration step. For the purpose of efficient local error estimation as a basis for adaptive stepsize selection, using pairs of related schemes is a well-established idea. Order conditions for pairs of schemes of the types listed below can be generated with minor modifications of the approach described in Sect. Embedded pairs. Milne pairs.
In the context of multistep methods for ODEs, the so-called Milne device is a well-established technique for constructing pairs of schemes. Then, the additive scheme. Adjoint pairs.
Therefore, the averaged additive scheme. In this case the additional effort for computing the local error estimate is identical with the effort for the worker S but not higher as is the case for embedded pairs. Our approach for setting up order conditions described in Sect. The resulting set of order conditions is a multivariate polynomial system which, for higher orders, requires numerical solution techniques.
Once a scheme of order p has been found, its leading local error term is of the form see Sect. To compare schemes of equal order p one may consider.
Nonlinear Evolution and Difference Equations of Monotone Type in Hilbert Spaces
For finding and evaluating solutions and pairs of solutions we follow two different strategies. For the case where the number of equations equals the number of free coefficients we expect a set of isolated solutions. In this case we use the fsolve function in Maple combined with a Monte-Carlo strategy for generating different initial intervals. Higher precision is used to generate solutions with double precision accuracy.
Especially for the case where the number of equations is smaller than the number of free coefficients, the problem is to be considered as a constrained minimization problem: minimize the LEM representing the objective function, with the order conditions imposed as nonlinear equality constraints. Again a large number of initial guesses are generated randomly, since this optimization problem is nonconvex in general.
The results cannot be guaranteed globally optimal, but results from an exhaustive search usually suggest that this is indeed the case. A post-processing, i. We have also re-checked a number of known methods, refined their coefficients to full double precision, and computed their LEMs. This collection is not intended to be exhaustive.
Some methods are included mainly for the sake of completeness or their historical significance. In some simple cases such optimality properties can be established theoretically; for higher orders we have resorted to more or less exhaustive numerical search. Due to the rapidly increasing number of generic order conditions, finding general higher order schemes would be a very challenging task for this case.
Representations of Compact Linear Operators in Banach Spaces and Nonlinear Eigenvalue Problems II
As indicated in Sect. Moreover, as already mentioned in Sect. Palindromic schemes have a certain type of symmetry, but they are not time-symmetric. Investigating special properties of such schemes appears to be of interest in the context of geometric integration, for instance when they are applied to partitioned systems of the form. The latter condition is satisfied if the scheme is a composition of steps of symplectic Euler type, i. Summarizing, we may say that palindromic schemes by now have not been completely understood, and this may deserve further investigations.
For splitting we choose the time step h and separately integrate. All computations were performed in standard double precision arithmetic. Winfried Auzinger, Email: ta. David Ketcheson, Email: as. Othmar Koch, Email: gro. National Center for Biotechnology Information , U. Numerical Mathematics. BIT Numer Math.
Published online Jul Author information Article notes Copyright and License information Disclaimer. Corresponding author.
- A Guide to Imagework: Imagination-Based Research Methods (Asa Research Methods in Social Anthropology).
- Butlers Saint for the Day.
- mathematics and statistics online.
Received Jul 29; Accepted Jul Abstract We present a number of new contributions to the topic of constructing efficient higher-order splitting methods for the numerical integration of evolution equations. Overview We present some new contributions to the topic of splitting methods; here we will concentrate on the generic case, i.