The life-span of backward error analysis for numerical integrators

Summary. Backward error analysis is a useful tool for the study of numerical approximations to ordinary differential equations. The numerical solution is formally interpreted as the exact solution of a perturbed differential equation, given as a formal and usually divergent series in powers of the step size. For a rigorous analysis, this series has to be truncated. In this article we study the influence of this truncation to the difference between the numerical solution and the exact solution of the perturbed differential equation. Results on the long-time behaviour of numerical solutions are obtained in this way. We present applications to the numerical phase portrait near hyperbolic equilibrium points, to asymptotically stable periodic orbits and Hopf bifurcation, and to energy conservation and approximation of invariant tori in Hamiltonian systems. Received October 18, 1995 / Revised version received February 28, 1996     

A robust trigonometrically fitted embedded pair for perturbed oscillators

A new kind of trigonometrically fitted embedded pair of explicit ARKN methods for the numerical integration of perturbed oscillators is presented in this paper. This new pair is based on the trigonometrically fitted ARKN method of order five derived by Yang and Wu in [H.L. Yang, X.Y. Wu, Trigonometrically-fitted ARKN methods for perturbed oscillators, Appl. Numer. Math. 9 (2008) 1375–1395]. We analyze the stability properties, phase-lag (dispersion) and dissipation of the higher-order method of the new pair. Numerical experiments carried out show that our new embedded pair is very competitive in comparison with the embedded pairs proposed in the scientific literature.     

Some remarks on an ODE-solver of Kirchgraber

Summary Kirchgraber derived in 1988 an integration procedure (called the LIPS-code) for long-term prediction of the solutions of equations which are perturbations of systems having only periodic solutions. His basic idea is to use the Poincaré map to define a new system which can be integrated with large step-size; the method is specially successful when the period is close to the unperturbed one. Obviously the size of the perturbation modifies the period and therefore affects the precision of the algorithm. In this paper we propose a double modification of Kirchgraber's code: to use a first-order approximation of the perturbed period instead of the unperturbed one, and a scheme specially designed for integration of orbits instead of the Runge-Kutta method. We show that this new code permits a spectacular improvement in accuracy and computation time.     

A new family of Runge–Kutta type methods for the numerical integration of perturbed oscillators

Summary. Our task in this paper is to present a new family of methods of the Runge–Kutta type for the numerical integration of perturbed oscillators. The key property is that those algorithms are able to integrate exactly, without truncation error, harmonic oscillators, and that, for perturbed problems the local error contains the perturbation parameter as a factor. Some numerical examples show the excellent behaviour when they compete with Runge–Kutta–Nystr?m type methods. Received June 12, 1997 / Revised version received July 9, 1998     

Nonlinear geometric optics for contact discontinuities and shock waves in one-dimensional Euler system for gas dynamics

The aim of this paper is to study the rigorous theory of nonlinear geometric optics for a contact discontinuity and a shock wave to the Euler system for one-dimensional gas dynamics. For the problem of a contact discontinuity and a shock wave perturbed by a small amplitude, high frequency oscillatory wave train, under suitable stability assumptions, we obtain that the perturbed problem has still a shock wave and a contact discontinuity, and we give their asymptotic expansions.     

Equilibrium attractivity of Krylov-W-methods for nonlinear stiff ODEs

Since implicit integration schemes for differential equations which use Krylov methods for the approximate solution of linear systems depend nonlinearly on the actual solution a classical stability analysis is difficult to perform. A different, weaker property of autonomous dissipative systemsy′=f(y) is that the norm ‖f(y(t))‖ decreases for any solutiony(t). This property can also be analysed for W-methods using a Krylov-Arnoldi approximation. We discuss different additional assumptions onf and conditions on the Arnoldi process that imply this kind of attractivity to equilibrium points for the numerical solution. One assumption is general enough to cover quasilinear parabolic problems. This work was supported by Deutsche Forschungsgemeinschaft.     

Analysis of the dynamics of local error control via a piecewise continuous residual

Positive results are obtained about the effect of local error control in numerical simulations of ordinary differential equations. The results are cast in terms of the local error tolerance. Under theassumption that a local error control strategy is successful, it is shown that a continuous interpolant through the numerical solution exists that satisfies the differential equation to within a small, piecewise continuous, residual. The assumption is known to hold for thematlab ode23 algorithm [10] when applied to a variety of problems. Using the smallness of the residual, it follows that at any finite time the continuous interpolant converges to the true solution as the error tolerance tends to zero. By studying the perturbed differential equation it is also possible to prove discrete analogs of the long-time dynamical properties of the equation—dissipative, contractive and gradient systems are analysed in this way. Supported by the Engineering and Physical Sciences Research Council under grants GR/H94634 and GR/K80228. Supported by the Office of Naval Research under grant N00014-92-J-1876 and by the National Science Foundation under grant DMS-9201727.     

Dynamics of prey threshold harvesting and refuge

The dynamics of a predator-prey model with continuous threshold prey harvesting and prey refuge is studied. One central question is how harvesting and refuge could directly affect the dynamics of the ecosystem, such as the stability properties of some coexistence equilibria and periodic solutions. Theoretical and numerical methods are used to investigate boundedness of solutions, existence of bionomic equilibria, as well as the existence and stability properties of equilibrium points and periodic solutions. Several bifurcations are also studied.     

On the influence of numerical preservation of invariants when simulating Hamiltonian relative periodic orbits

We study the structure of the error when simulating relative periodic solutions of Hamiltonian systems with symmetries. We identify the mechanisms for which the preservation, in the numerical integration, of the Hamiltonian and the invariants associated to the symmetry group, implies a better time behavior of the error. A second consequence is a more correct simulation of the parameters that characterize the relative periodic orbit.     

On optimal triangular meshes for minimizing the gradient error

Summary Construction of optimal triangular meshes for controlling the errors in gradient estimation for piecewise linear interpolation of data functions in the plane is discussed. Using an appropriate linear coordinate transformation, rigorously optimal meshes for controlling the error in quadratic data functions are constructed. It is shown that the transformation can be generated as a curvilinear coordinate transformation for anyC data function with nonsingular Hessian matrix. Using this transformation, a construction of nearly optimal meshes for general data functions is described and the error equilibration properties of these meshes discussed. In particular, it is shown that equilibration of errors is not a sufficient condition for optimality. A comparison of meshes generated under several different criteria is made, and their equilibrating properties illustrated.This work was supported by the Natural Sciences and Engineering Research Council of Canada, by the Information Technology Research Centre, which is funded by the Province of Ontario, by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc., and through an appointment to the U.S. Department of Energy Postgraduate Research Program administered by Oak Ridge Associated Universities     

Local error estimation for multistep collocation methods

Multistep collocation methods for initial value problems in ordinary differential equations are known to be a subclass of multistep Runge-Kutta methods and a generalisation of the well-known class of one-step collocation methods as well as of the one-leg methods of Dahlquist. In this paper we derive an error estimation method of embedded type for multistep collocation methods based on perturbed multistep collocation methods. This parallels and generalizes the results for one-step collocation methods by Nørsett and Wanner. Simple numerical experiments show that this error estimator agrees well with a theoretical error estimate which is a generalisation of an error estimate first derived by Dahlquist for one-leg methods.     

A note on error expressions for reflected and averaged implicit Runge-Kutta methods

In addition to their usefulness in the numerical solution of initial value ODE's, the implicit Runge-Kutta (IRK) methods are also important for the solution of two-point boundary value problems. Recently, several classes of modified IRK methods which improve significantly on the efficiency of the standard IRK methods in this application have been presented. One such class is the Averaged IRK methods; a member of the class is obtained by applying an averaging operation to a non-symmetric IRK method and its reflection. In this paper we investigate the forms of the error expressions for reflected and averaged IRK methods. Our first result relates the expression for the local error of the reflected method to that of the original method. The main result of this paper relates the error expression of an averaged method to that of the method upon which it is based. We apply these results to show that for each member of the class of the averaged methods, there exists an embedded lower order method which can be used for error estimation, in a formula-pair fashion.This work was supported by the Natural Science and Engineering Research Council of Canada.     

A stability property ofA-stable natural Runge-Kutta methods for systems of delay differential equations

A natural Runge-Kutta method is a special type of Runge-Kutta method for delay differential equations (DDEs); it is known that any one-step collocation method is equivalent to one of such methods. In this paper, we consider a linear constant-coefficient system of DDEs with a constant delay, and discuss the application of natural Runge-Kutta methods to the system. We show that anA-stable method preserves the asymptotic stability property of the analytical solutions of the system.     

Convergence analysis of waveform relaxation methods for neutral differential-functional systems

In this paper, the problems of convergence and superlinear convergence of continuous-time waveform relaxation method applied to Volterra type systems of neutral functional-differential equations are discussed. Under a Lipschitz condition with time- and delay-dependent right-hand side imposed on the so-called splitting function, more suitable conditions about convergence and superlinear convergence of continuous-time WR method are obtained. We also investigate the initial interval acceleration strategy for the practical implementation of the continuous-time waveform relaxation method, i.e., discrete-time waveform relaxation method. It is shown by numerical results that this strategy is efficacious and has the essential acceleration effect for the whole computation process.     

On the equivalence of BS-stability and B-consistency

Among several stability and consistency concepts for Runge-Kutta methods applied to stiff initial value problems, BS-stability and B-consistency turn out to be equivalent for initial value problems with a one-sided Lipschitz constantm 0. In addition to this result, it is shown that the same holds for their internal counterparts.This paper was written while this author was visiting the Centre for Mathematics and Computer Science with an Erwin-Schrödinger stipend from the Fonds zur Förderung der wissenschaftlichen Forschung.     

A second-order hybrid finite difference scheme for a system of singularly perturbed initial value problems

A system of coupled singularly perturbed initial value problems with two small parameters is considered. The leading term of each equation is multiplied by a small positive parameter, but these parameters may have different magnitudes. The solution of the system has boundary layers that overlap and interact. The structure of these layers is analyzed, and this leads to the construction of a piecewise-uniform mesh that is a variant of the usual Shishkin mesh. On this mesh a hybrid finite difference scheme is proved to be almost second-order accurate, uniformly in both small parameters. Numerical results supporting the theory are presented.     

Convergence of linear multistep and one-leg methods for stiff nonlinear initial value problems

To prove convergence of numerical methods for stiff initial value problems, stability is needed but also estimates for the local errors which are not affected by stiffness. In this paper global error bounds are derived for one-leg and linear multistep methods applied to classes of arbitrarily stiff, nonlinear initial value problems. It will be shown that under suitable stability assumptions the multistep methods are convergent for stiff problems with the same order of convergence as for nonstiff problems, provided that the stepsize variation is sufficiently regular.     

A family of multistep methods to integrate orbits on spheres

Summary A trajectory problem is an initial value problem where the interest lies in obtaining the curve traced by the solution, rather than in finding the actual correspondence between the values of the parameter and the points on that curve. This paper introduces a family of multi-stage, multi-step numerical methods to integrate trajectory problems whose solution is on a spherical surface. It has been shown that this kind of algorithms has good numerical properties: consistency, stability, convergence and others that are not standard. The latest ones make them a better choice for certain problems.     

A second-order difference scheme for a parameterized singular perturbation problem

In this paper we consider a singularly perturbed quasilinear boundary value problem depending on a parameter. The problem is discretized using a hybrid difference scheme on Shishkin-type meshes. We show that the scheme is second-order convergent, in the discrete maximum norm, independent of singular perturbation parameter. Numerical experiments support these theoretical results.     

Parallel defect control

How can small-scale parallelism best be exploited in the solution of nonstiff initial value problems? It is generally accepted that only modest gains inefficiency are possible, and it is often the case that “fast” parallel algorithms have quite crude error control and stepsize selection components. In this paper we consider the possibility of using parallelism to improvereliability andfunctionality rather than efficiency. We present an algorithm that can be used with any explicit Runge-Kutta formula. The basic idea is to take several smaller substeps in parallel with the main step. The substeps provide an interpolation facility that is essentially free, and the error control strategy can then be based on a defect (residual) sample. If the number of processors exceeds (p ? 1)/2, wherep is the order of the Runge-Kutta formula, then the interpolant and the error control scheme satisfy very strong reliability conditions. Further, for a given orderp, the asymptotically optimal values for the substep lengths are independent of the problem and formula and hence can be computed a priori. Theoretical comparisons between the parallel algorithm and optimal sequential algorithms at various orders are given. We also report on numerical tests of the reliability and efficiency of the new algorithm, and give some parallel timing statistics from a 4-processor machine.