A Reliable Error Estimation for Diagonally Implicit Multistage Integration Methods

A new approach to the estimation of the local discretization error for diagonally implicit multistage integration methods (DIMSIMs) is described. The error estimates that are obtained are very accurate and very reliable for both explicit and implicit methods for any stepsize pattern.This revised version was published online in October 2005 with corrections to the Cover Date.     

Error Estimation for Nordsieck Methods

The local discretization errors of general linear methods depend on the sequence of all stepsize ratios and the derivation of the exact formulas for the corresponding error estimates does not seem to be practical. In this paper we will describe an approach in which the estimates of local discretization errors are evaluated numerically as the computation proceeds from step to step.     

Nordsieck Methods with an Off-Step Point

Hybrid methods, incorporating one or more off-step points, are difficult to implement in a variable stepsize situation using the standard representation of input and output data in each step. However, instead of representing this data in terms of solution values and derivative values at a sequence of step points, it is possible to reformulate the method so that it operates on a Nordsieck vector. This has the consequence of reducing stepsize adjustments to nothing more than rescaling the components of the Nordsieck vector. This paper shows how to derive methods in both formulations and considers some implementation details. It is also possible to derive a new type of hybrid method using the Norsieck representation as the starting point and this is also discussed in the paper. The new method is found to have comparable accuracy for corresponding work expended as for standard methods.     

Experiments with a variable-order type 1 DIMSIM code

The issues related to the development of a new code for nonstiff ordinary differential equations are discussed. This code is based on the Nordsieck representation of type 1 DIMSIMs, implemented in a variable-step size variable-order mode. Numerical results demonstrate that the error estimation employed in the code is very reliable and that the step and order changing strategies are very robust. This code outperforms the Matlab ode45 code for moderate and stringent tolerances. This revised version was published online in August 2006 with corrections to the Cover Date.     

Nordsieck methods with computationally verified algebraic stability

We describe the search for algebraically stable Nordsieck methods of order p = s and stage order q = p, where s is the number of stages. This search is based on the theoretical criteria for algebraic stability proposed recently by Hill, and Hewitt and Hill, for general linear methods for ordinary differential equations. These criteria, which are expressed in terms of the non-negativity of the eigenvalues of a Hermitian matrix on the unit circle, are then verified computationally for the derived Nordsieck methods of order p ? 2.     

Explicit Nordsieck methods with extended stability regions

We describe the construction of explicit Nordsieck methods of order p and stage order q = p with large regions of absolute stability. We also discuss error propagation and estimation of local discretization errors. The error estimators are derived for examples of general linear methods constructed in this paper. Some numerical experiments are presented which illustrate the effectiveness of proposed methods.     

New Runge–Kutta Based Schemes for ODEs with Cheap Global Error Estimation

We present a particular 5th order one-step integrator for ODEs that provides an estimation of the global error. It's based on the class of one-step integrator for ODEs of Murua and Makazaga considered as a generalization of the globally embedded RK methods of Dormand, Gilmore and Prince. The scheme we present cheaply gives useful information on the behavior of the global error. Some numerical experiments show that the estimation of the global error reflects the propagation of the true global error. Moreover we present a new step-size adjustment strategy that takes advantage of the available information about the global error. The new strategy is specially suitable for problems with exponential error growth.     

Accuracy of multivalue methods during change of time‐step size: Adams‐Moulton

Multivalue methods are a class of time‐stepping procedures for numerical solution of differential equations that progress to a new time level using the approximate solution for the function of interest and its derivatives at a single time level. The methods differ from multistep procedures, which make use of solutions to the differential equation at multiple time levels to advance to the new time level. Multistep methods are difficult to employ when a change in time‐step is desired, because the standard formulas (e.g., Adams‐Moulton or Gear) must be modified to accommodate the change. Multivalue methods seem to possess the desirable feature that the time‐step may be changed arbitrarily as one proceeds, since the solution proceeds from a single time level. However, in practice, changes in the time‐step introduce lower order errors or alter the coefficient in the truncation error term. Here, the multivalue Adams‐Moulton method is presented based on a general interpolation procedure. Modifications required to retain the high‐order accuracy of these methods during a change in time‐step are developed. Additionally, a formula for the unknown initial derivatives is presented. Finally, two examples are provided to illustrate the potential merit of the modification to the standard multivalue methods. © 2000 John Wiley & Sons, Inc. Numer Methods Partials Differential Eq 16: 312–326, 2000     

Error propagation of general linear methods for ordinary differential equations

We discuss error propagation for general linear methods for ordinary differential equations up to terms of order p+2, where p is the order of the method. These results are then applied to the estimation of local discretization errors for methods of order p and for the adjacent order p+1. The results of numerical experiments confirm the reliability of these estimates. This research has applications in the design of robust stepsize and order changing strategies for algorithms based on general linear methods.     

Construction of General Linear Methods with Runge–Kutta Stability Properties

We describe the construction of explicit general linear methods of order p and stage order q=p with s=p+1 stages which achieve good balance between accuracy and stability properties. The conditions are imposed on the coefficients of these methods which ensure that the resulting stability matrix has only one nonzero eigenvalue. This eigenvalue depends on one real parameter which is related to the error constant of the method. Examples of methods are derived which illustrate the application of the approach presented in this paper.     

Local error estimates for moderately smooth problems: Part I – ODEs and DAEs

The paper consists of two parts. In the first part, we propose a procedure to estimate local errors of low order methods applied to solve initial value problems in ordinary differential equations (ODEs) and index 1 differential-algebraic equations (DAEs). Based on the idea of defect correction we develop local error estimates for the case when the problem data is only moderately smooth. Numerical experiments illustrate the performance of the mesh adaptation based on the error estimation developed in this paper. In the second part of the paper, we will consider the estimation of local errors in context of stochastic differential equations with small noise. AMS subject classification (2000)  65L06, 65L80, 65L50, 65L05     

Time Discretisation of Parabolic Problems with the Variable 3-Step BDF

In this paper the stability of the 3-step backward differentiation formula (BDF) on variable grids for the numerical integration of time-dependent parabolic problems is analysed. A stability inequality with a stability constant depending in a controllable way on the mesh is obtained. In particular if the ratios r _j of adjacent mesh-sizes of the underlying grid satisfy the bound r _j r¯ < 1.199 then any mixture of the j-step BDF for j {1, 2, 3} is stable provided the number of changes between increasing and decreasing mesh-sizes is uniformly bounded. From the stability inequality error estimates can be obtained.     

The construction of order 4 DIMSIMs for ordinary differential equations

Diagonally Implicit Multistage Integration Methods (DIMSIMs) of type 1 and 2 have considerable potential as numerical algorithms for ordinary differential equations. The aim of this paper is to construct such methods of order 4 of type 1 and 2, which completes the set for orders 1–8.     

Two-Step Runge-Kutta: Theory and Practice

Local and global error for Two-Step Runge-Kutta (TSRK) methods are analyzed using the theory of B-series. Global error bounds are derived in both constant and variable stepsize environments. An embedded TSRK pair is constructed and compared with the RK5(4)6M pair of Dormand and Prince on the DETEST set of problems. Numerical results show that the TSRK performs competitively with the RK method.     

One-leg variable-coefficient formulas for ordinary differential equations and local–global step size control

In this paper we discuss a class of numerical algorithms termed one-leg methods. This concept was introduced by Dahlquist in 1975 with the purpose of studying nonlinear stability properties of multistep methods for ordinary differential equations. Later, it was found out that these methods are themselves suitable for numerical integration because of good stability. Here, we investigate one-leg formulas on nonuniform grids. We prove that there exist zero-stable one-leg variable-coefficient methods at least up to order 11 and give examples of two-step methods of orders 2 and 3. In this paper we also develop local and global error estimation techniques for one-leg methods and implement them with the local–global step size selection suggested by Kulikov and Shindin in 1999. The goal of this error control is to obtain automatically numerical solutions for any reasonable accuracy set by the user. We show that the error control is more complicated in one-leg methods, especially when applied to stiff problems. Thus, we adapt our local–global step size selection strategy to one-leg methods.     

Strong representation of weak convergence

Skorokhod's representation theorem states that if on a Polish space,there is a weakly convergent sequence of probability measures μnw→μ0,as n →∞,then there exist a probability space(Ω,F,P) and a sequence of random elements Xnsuch that Xn→ X almost surely and Xnhas the distribution function μn,n = 0,1,2,... We shall extend the Skorokhod representation theorem to the case where if there are a sequence of separable metric spaces Sn,a sequence of probability measures μnand a sequence of measurable mappings n such that μnn-1w→μ0,then there exist a probability space(Ω,F,P) and Sn-valued random elements Xndefined on Ω,with distribution μnand such that n(Xn) → X0 almost surely. In addition,we present several applications of our result including some results in random matrix theory,while the original Skorokhod representation theorem is not applicable.     

Evaluating departures from fair representation

Computer–intensive estimates are introduced to evaluate departures from proportionality between the numbers of electors in a partition of a voting population and the numbers of representatives in the corresponding partition of the elected representation. At the first stage a pair of indices is proposed, one to evaluate the total strength of the departures and the other to indicate to what extent they are due to over–representation increasing (or decreasing) with the number of electors in a group. The properties of the indices are examined in suitably defined stochastic models which describe this type of over–representation. Since the values of the indices are strongly influenced by the distribution of electors in the given partition, a second stage of estimation is performed in order to get some [partition–free] information on the existence of a monotone size representation, and, if it exists, on its strength. The relevant transformation is based on intensive computer simulation in the introduced models. The methods proposed are applied to the results of the 1991 election of the Polish Scientific Research Council, which distributes funds among universities, scientific institutions and individual groups of researchers.     

Isomorphisms of global representation rings

In this paper, we study properties of isomorphisms of global rings that preserve the standard bases.