Stability of linear multistep methods on the imaginary axis

The stability of linear multistep methods of order higher than one is investigated for hyperbolic equations. By means of the Routh array and the Hermite-Biehler theorem, the stability boundary on the imaginary axis is expressed in terms of the error constant of the third order term. As a corollary we state the result that the stability boundary for methods of order higher than two, is at most 3, and this value is attained by the Milne-Simpson method.This work was done during the author's stay at the Mathematical Centre Amsterdam, and the University of Technology, Eindhoven.     

Stability in linear multistep methods for pure delay equations

The stability regions of linear multistep methods for pure delay equations are compared with the stability region of the delay equation itself. A criterion is derived stating when the numerical stability region contains the analytical stability region. This criterion yields an upper bound for the integration step (conditional Q-stability). These bounds are computed for the Adams-Bashforth, Adams-Moulton and backward differentiation methods of orders ?8. Furthermore, symmetric Adams methods are considered which are shown to be unconditionally Q-stable. Finally, the extended backward differentiation methods of Cash are analysed.     

Symmetric linear multistep methods

Some important early contributions of Germund Dahlquist are reviewed and their impact to recent developments in the numerical solution of ordinary differential equations is shown. This work is an elaboration of a talk presented in the Dahlquist session at the SciCADE05 conference in Nagoya. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L06, 65P10     

Multirate linear multistep methods

The design of a code which uses different stepsizes for different components of a system of ordinary differential equations is discussed. Methods are suggested which achieve moderate efficiency for problems having some components with a much slower rate of variation than others. Techniques for estimating errors in the different components are analyzed and applied to automatic stepsize and order control. Difficulties, absent from non-multirate methods, arise in the automatic selection of stepsizes, leading to a suggested organization of the code that is counter-intuitive. An experimental code and some initial experiments are described.Dedicated to Professor Germund Dahlquist on the occasion of his 60th birthdaySupported in part by the Department of Energy under grant DOE DEAC0276ERO2383.Work done while attending the University of Illinois.     

Circle contractive linear multistep methods

Linear multistep methods satisfying a non-linear circle contractivity condition when the step-ratios are less than some 1+,>0, are shown to exist for any order. Methods with formulas of order 1 to 12 are given.     

Stability of implicit-explicit linear multistep methods for ordinary and delay differential equations

Stability properties of implicit-explicit (IMEX) linear multistep methods for ordinary and delay differential equations are analyzed on the basis of stability regions defined by using scalar test equations. The analysis is closely related to the stability analysis of the standard linear multistep methods for delay differential equations. A new second-order IMEX method which has approximately the same stability region as that of the IMEX Euler method, the simplest IMEX method of order 1, is proposed. Some numerical results are also presented which show superiority of the new method.      

Contractivity preserving explicit linear multistep methods

Summary We investigate contractivity properties of explicit linear multistep methods in the numerical solution of ordinary differential equations. The emphasis is on the general test-equation , whereA is a square matrix of arbitrary orders1. The contractivity is analysed with respect to arbitrary norms in thes-dimensional space (which are not necessarily generated by an inner product). For given order and stepnumber we construct optimal multistep methods allowing the use of a maximal stepsize.This research has been supported by the Netherlands organisation for scientific research (NWO)     

Multiplier techniques for linear multistep methods

A theory is developed for the fixed-h stability of integration schemes based on A(α)-stable formulas when applied to nonlinear parabolic-like stiff equations. The theory is based on a general multiplier technique whose properties we fully develop. Assuming that a few simply checkable criteria which are related to monotonicity properties of the nonlinearity around the computed solution are satisfied, we obtain various error bounds and boundedness results for that solution. Some practical implications of the theory are also given.     

A note on unconditionally stable linear multistep methods

It has been shown by Dahlquist [3] that the trapezoidal formula has the smallest truncation error among all linear multistep methods with a certain stability property. It is the purpose of this note to show that a slightly different stability requirement permits methods of higher accuracy.The preparation of this paper was sponsored by the Swedish Technical Research Council.     

On the convergence of advanced linear multistep methods

A convergence theorem is given showing that zero-stable advanced linear multistep methods with orderp consistency have orderp convergence.     

Nonlinear stability behaviour of linear multistep methods

For linear multistep methods sufficient conditions are derived such that the numerical solutions of stable nonlinear initial value problems in Banach spaces are also stable.     

Stability of linear multistep methods for nonlinear neutral delay differential equations in Banach space

This paper is devoted to investigating the nonlinear stability properties of linear multistep methods for the solution to neutral delay differential equations in Banach space. Two approaches to numerically treating the “neutral term” are considered, which allow us to prove several results on numerical stability of linear multistep methods. These results provide some criteria for choosing the step size such that the numerical method is stable. Some examples of application and a numerical experiment, which further confirms the main results, are given.     

A-Stable linear multistep methods for Volterra Integro-Differential Equations

Summary A class of linear algorithms for Volterra Integro-Differential Equations is studied. The concept of the associated canonical fraction is extended to this class and leads to an algebraic criterion forA-stability.     

A special stability problem for linear multistep methods

The trapezoidal formula has the smallest truncation error among all linear multistep methods with a certain stability property. For this method error bounds are derived which are valid under rather general conditions. In order to make sure that the error remains bounded ast , even though the product of the Lipschitz constant and the step-size is quite large, one needs not to assume much more than that the integral curve is uniformly asymptotically stable in the sense of Liapunov.The preparation of this paper was partly sponsored by the Office of Naval Research and the US Army Research Office (Durham). Reproduction in whole or in part is permitted for any purpose of the US Government.     

Parallel iterative linear solvers for multistep Runge-Kutta methods

This paper deals with solving stiff systems of differential equations by implicit Multistep Runge-Kutta (MRK) methods. For this type of methods, nonlinear systems of dimension sd arise, where s is the number of Runge-Kutta stages and d the dimension of the problem. Applying a Newton process leads to linear systems of the same dimension, which can be very expensive to solve in practice. With a parallel iterative linear system solver, especially designed for MRK methods, we approximate these linear systems by s systems of dimension d, which can be solved in parallel on a computer with s processors. In terms of Jacobian evaluations and LU-decompositions, the k-steps-stage MRK applied with this technique is on s processors equally expensive as the widely used k-step Backward Differentiation Formula on 1 processor, whereas the stability properties are better than that of BDF. A simple implementation of both methods shows that, for the same number of Newton iterations, the accuracy delivered by the new method is higher than that of BDF.     

On monotonicity and boundedness properties of linear multistep methods

In this paper an analysis is provided of nonlinear monotonicity and boundedness properties for linear multistep methods. Instead of strict monotonicity for arbitrary starting values we shall focus on generalized monotonicity or boundedness with Runge-Kutta starting procedures. This allows many multistep methods of practical interest to be included in the theory. In a related manner, we also consider contractivity and stability in arbitrary norms.

     

A note on the exponential fitting of blended,extended linear multistep methods

A class of exponentially fitted blended, extended linear multistep methods is investigated andA-stable formulae of order 3, 4 and 5 are derived.     

Constant coefficient linear multistep methods with step density control

In linear multistep methods with variable step size, the method's coefficients are functions of the step size ratios. The coefficients therefore need to be recomputed on every step to retain the method's proper order of convergence. An alternative approach is to use step density control to make the method adaptive. If the step size sequence is smooth, the method can use constant coefficients without losing its order of convergence. The paper introduces this new adaptive technique and demonstrates its feasibility with a few test problems.     

Experiments in stepsize control for Adams linear multistep methods

In this paper we consider stepsize selection in one class of Adams linear multistep methods for ordinary differential equations. In particular, the exact form of the local error for a variable step method is considered and a new class of direct approximations proposed. The implications of this approach are then discussed and illustrations provided with numerical results. This revised version was published online in June 2006 with corrections to the Cover Date.