Rooted Tree Analysis for Order Conditions of Stochastic Runge-Kutta Methods for the Weak Approximation of Stochastic Differential Equations

Abstract

A general class of stochastic Runge-Kutta methods for the weak approximation of Itô and Stratonovich stochastic differential equations with a multi-dimensional Wiener process is introduced. Colored rooted trees are used to derive an expansion of the solution process and of the approximation process calculated with the stochastic Runge-Kutta method. A theorem on general order conditions for the coefficients and the random variables of the stochastic Runge-Kutta method is proved by rooted tree analysis. This theorem can be applied for the derivation of stochastic Runge-Kutta methods converging with an arbitrarily high order.     

On the Starting Algorithms for Fully Implicit Runge-Kutta Methods

This paper is concerned with the behavior of starting algorithms to solve the algebraic equations of stages arising when fully implicit Runge-Kutta methods are applied to stiff initial value problems. The classical Lagrange extrapolation of the internal stages of the preceding step and some variants thereof that do not require any additional cost are analyzed. To study the order of the starting algorithms we consider three different approaches. First we analyze the classical order through the theory of Butcher's series, second we derive the order on the Prothero and Robinson model and finally we study the stiff order for a general class of dissipative problems. A detailed study of the orders of some starting algorithms for Gauss, Radau IA-IIA, Lobatto IIIA-C methods is also carried out. Finally, to compare the most relevant starting algorithms studied here, some numerical experiments on well known nonlinear stiff problems are presented.     

Variable stepsize continuous two-step Runge-Kutta methods for ordinary differential equations

A general class of variable stepsize continuous two-step Runge-Kutta methods is investigated. These methods depend on stage values at two consecutive steps. The general convergence and order criteria are derived and examples of methods of orderp and stage orderq=p orq=p–1 are given forp5. Numerical examples are presented which demonstrate that high order and high stage order are preserved on nonuniform meshes with large variations in ratios between consecutive stepsizes.The work of the first author was supported by the National Science Foundation under grant NSF DMS-9208048. The work of the second author was supported by the Italian Government.     

Order conditions for General Linear Nyström methods

The purpose of this paper is to analyze the algebraic theory of order for the family of general linear Nyström (GLN) methods introduced in D’Ambrosio et al. (Numer. Algorithm 61(2), 331–349, 2012) with the aim to provide a general framework for the representation and analysis of numerical methods solving initial value problems based on second order ordinary differential equations (ODEs). Our investigation is carried out by suitably extending the theory of B-series for second order ODEs to the case of GLN methods, which leads to a general set of order conditions. This allows to recover the order conditions of numerical methods already known in the literature, but also to assess a general approach to study the order conditions of new methods, simply regarding them as GLN methods: the obtained results are indeed applied to both known and new methods for second order ODEs.     

一般线性方法的正则性

１．引言数值方法的动力特征近年引起了人们的广泛关注。其中之一就是系统的平衡态和数值方法的平衡态相一致的问题,即用一个数值方法沿定步长求解系统时,是否会出现伪平衡。不可能出现伪平衡的方法称为是正则的。ＲＫ方法和线性多步法的正则性已被众多的文献研究［２,３,４］,其它方法的正则性显然是一亟待研究的问题。本文讨论较ＲＫ方法和线性多步法远为广泛的一般线性方法的正则性。设ｆ：Ｒ~（Ｎ）→Ｒ~（Ｎ）是一充分光滑的映射,考虑求解初值问题：的一般线性方法［１］：其中步长逼近于逼近于关于微分方程真解ｙ（ｔ）在第ｎ层…     

A class of scaled direct methods for linear systems

A generalization of the class of direct methods for linear systems recently introduced by Abaffy, Broyden and Spedicato is obtained by applying these algorithms to a scaled system. The resulting class contains an essentially free parameter at each step, giving a unified approach to finitely terminating methods for linear systems. Various properties of the generalized class are presented. Particular attention is paid to the subclasses that contain the classic Hestenes-Stiefel method and the Hegedus-Bodocs biorthogonalization methods.This work was partially supported by CNR under contract 85.02648.01.     

DIMSEMs - diagonally implicit single-eigenvalue methods for the numerical solution of stiff ODEs on parallel computers

This paper derives a new class of general linear methods (GLMs) intended for the solution of stiff ordinary differential equations (ODEs) on parallel computers. Although GLMs were introduced by Butcher in the 1960s, the task of deriving formulas from the class with properties suitable for specific applications is far from complete. This paper is a contribution to that work. Our new methods have several properties suited for the solution of stiff ODEs on parallel computers. They are strictly diagonally implicit, allowing parallelism in the Newton iteration used to solve the nonlinear equations arising from the implicitness of the formula. The stability matrix has no spurious eigenvalues (that is, only one eigenvalue of the stability matrix is non-zero), resulting in a solution free from contamination from spurious solutions corresponding to non-dominant, non-zero eigenvalues. From these two properties arises the name DIMSEM, for Diagonally IMplicit Single-Eigenvalue Method. The methods have high stage order, avoiding the phenomenon of order reduction that occurs, for example, with some Runge-Kutta methods. The methods are L-stable, with the result that the chosen stepsize is dictated by convergence requirements rather than stability considerations imposed by the stiffness of the problem. An introduction to GLMs is given and some order barriers for DIMSEMs are presented. DIMSEMs of orders 2-6 are derived, as well as an L-stable class of diagonal methods of all orders which do not, however, possess the single-eigenvalue property. A fixed-order, variable-stepsize implementation of the DIMSEMs is described, including the derivation of local error estimators, and the results of testing on both sequential and parallel computers is presented. The testing shows the DIMSEMs to be competitive with fixed-order versions of the popular solver LSODE on a practical test problem.     

Computation of order conditions for symplectic partitioned Runge-Kutta schemes with application to optimal control

We derive order conditions for the discretization of (unconstrained) optimal control problems, when the scheme for the state equation is of Runge-Kutta type. This problem appears to be essentially the one of checking order conditions for symplectic partitioned Runge-Kutta schemes. We show that the computations using bi-coloured trees are naturally expressed in this case in terms of oriented free tree. This gives a way to compute them by an appropriate computer program. This study is supported by CNES and ONERA, in the framework of the CNES fellowship of the second author.     

刚性Volterra泛函微分方程梯形方法的B-理论

最近,李寿佛建立了刚性Volterra泛函微分方程Runge_Kutta方法和一般线性方法的B-理论,其中代数稳定是数值方法B-稳定与B-收敛的首要条件,但梯形方法表示成Runge—Kutta方法的形式或一般线性方法的形式都不是代数稳定的,因此上述理论不适用于梯形方法.本文从另一途径出发,证明求解刚性Volterra泛函微分方程的梯形方法是B-稳定且2阶最佳B-收敛的,最后的数值试验验证了所获理论的正确性.     

Runge-Kutta methods for third order weak approximation of SDEs with multidimensional additive noise

A new class of third order Runge-Kutta methods for stochastic differential equations with additive noise is introduced. In contrast to Platen’s method, which to the knowledge of the author has been up to now the only known third order Runge-Kutta scheme for weak approximation, the new class of methods affords less random variable evaluations and is also applicable to SDEs with multidimensional noise. Order conditions up to order three are calculated and coefficients of a four stage third order method are given. This method has deterministic order four and minimized error constants, and needs in addition less function evaluations than the method of Platen. Applied to some examples, the new method is compared numerically with Platen’s method and some well known second order methods and yields very promising results.     

A New Integrator for Special Third Order Differential Equations With Application to Thin Film Flow Problem

In recent time, Runge-Kutta methods that integrate special third order ordinary differential equations (ODEs) directly are proposed to address efficiency issues associated with classical Runge-Kutta methods. Albeit, the methods require evaluation of three set of equations to proceed with the numerical integration. In this paper, we propose a class of multistep-like Runge-Kutta methods (hybrid methods), which integrates special third order ODEs directly. The method is completely derivative-free. Algebraic order conditions of the method are derived. Using the order conditions, a four-stage method is presented. Numerical experiment is conducted on some test problems. The method is also applied to a practical problem in Physics and engineering to ascertain its validity. Results from the experiment show that the new method is more accurate and efficient than the classical Runge-Kutta methods and a class of direct Runge-Kutta methods recently designed for special third order ODEs.     

Convergence and stability of implicit runge-kutta methods for systems with multiplicative noise

A class ofimplicit Runge-Kutta schemes for stochastic differential equations affected bymultiplicative Gaussian white noise is shown to be optimal with respect to global order of convergence in quadratic mean. A test equation is proposed in order to investigate the stability of discretization methods for systems of this kind. Herestability is intended in a truly probabilistic sense, as opposed to the recently introduced extension of A-stability to the stochastic context, given for systems with additive noise. Stability regions for the optimal class are also given.Partially supported by the Italian Consiglio Nazionale delle Ricerche.     

On the global and cubic convergence of a quasi-cyclic Jacobi method

Summary In this paper we consider the global and the cubic convergence of a quasi-cyclic Jacobi method for the symmetric eigenvalue, problem. The method belongs to a class of quasi-cyclic methods recently proposed by W. Mascarenhas. Mascarenhas showed that the methods from his class asymptotically converge cubically per quasi-sweep (one quasi-sweep is equivalent to 1.25 cyclic sweeps) provided the eigenvalues are simple. Here we prove the global convergence of our method and derive very sharp asymptotic convergence bounds in the general case of multiple eigenvalues. We discuss the ultimate cubic convergence of the method and present several numerical examples which all well comply with the theory.This work was supported in part by the University of Minnesota Army High Performance Computing Research Center and the U.S Army Contract DAAL03-89-C-0038. The paper was partly written while this author was a visiting faculty in the Department of Mathematics, University of Kansas, Lawrence, Kansas. The first version of this paper was made in July 1990 while this author was visiting AHPCRC.     

Flexible piecewise approximations based on partition of unity

In this paper, we study a flexible piecewise approximation technique based on the use of the idea of the partition of unity. The approximations are piecewisely defined, globally smooth up to any order, enjoy polynomial reproducing conditions, and satisfy nodal interpolation conditions for function values and derivatives of any order. We present various properties of the approximations, that are desirable properties for optimal order convergence in solving boundary value problems. AMS subject classification 65N30, 65D05Weimin Han: Corresponding author. The work of this author was partially supported by NSF under grant DMS-0106781.Wing Kam Liu: The work of this author was supported by NSF.     

Relationships among some classes of implicit Runge-Kutta methods and their stability functions

In this paper we apply the theory for implicit Runge-Kutta methods presented by Stetter to a number of subclasses of methods that have recently been discussed in the literature. We first show how each of these classes can be expressed within this theoretical framework and from this we are able to establish a number of relationships among these classes. In addition to improving the current state of understanding of these methods, their expression within this theoretical framework makes it possible for us to obtain results giving general forms for their stability functions.This work was supported by the Natural Sciences and Engineering Research Council of Canada.     

Natural Runge-Kutta and projection methods

Summary Recently the author defined the class of natural Runge-Kutta methods and observed that it includes all the collocation methods. The present paper is devoted to a complete characterization of this class and it is shown that it coincides with the class of the projection methods in some polynomial spaces.This work was supported by the Italian Ministero della Pubblica Istruzione, funds 40%     

Infinite-dimensional convex programming with applications to constrained approximation

In this paper, existence and characterization of solutions and duality aspects of infinite-dimensional convex programming problems are examined. Applications of the results to constrained approximation problems are considered. Various duality properties for constrained interpolation problems over convex sets are established under general regularity conditions. The regularity conditions are shown to hold for many constrained interpolation problems. Characterizations of local proximinal sets and the set of best approximations are also given in normed linear spaces.The author is grateful to the referee for helpful suggestions which have contributed to the final preparation of this paper. This research was partially supported by Grant A68930162 from the Australian Research Council.     

Conditions for the coefficients of Runge-Kutta methods for systems of n-th order differential equations

To derive order conditions for Runge-Kutta methods of Nyström or Fehlberg type, applicable to arbitrary order differential equations, a theory similar to that about Runge-Kutta methods for first order systems, due to Butcher [1], is developed. By a new definition of elementary differentials, which is independent of the order of the given system, each condition to be satisfied by the coefficients of the method directly follows from the representation of the corresponding elementary differential.     

Ideals of Multilinear Forms – a Limit Order Approach

A general theory of limit orders for ideals of multilinear forms is developed. We relate the limit order of an ideal to those of its maximal hull and its adjoint ideal. We study the limit orders of the ideals of dominated and multiple summing multilinear forms. Finally, estimates of the diagonal of a (non-necessarily diagonal) multilinear form are presented, in terms of the limit order of the ideals to which it belongs. The third author was supported by the MCYT and FEDER Project BFM2002-01423 and grant GV-GRUPOS04/45. The first and second authors were supported by CONICET-PIP 5272. The first author was also supported by UBACyT-X108 and ANPCyT-PICT 0315033.     

Runge-Kutta theory for Volterra integrodifferential equations

Summary The present paper develops the theory of general Runge-Kutta methods for Volterra integrodifferential equations. The local order is characterized in terms of the coefficients of the method. We investigate the global convergence of mixed and extended Runge-Kutta methods and give results on asymptotic error expansions. In a further section we construct examples of methods up to order 4.