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.     

The equivalence ofB-stability andA-stability

It is a well-known result of Dahlquist that the linear (A-stability) and non-linear (G-stability) stability concepts are equivalent for multistep methods in their one-leg formulation. We show to what extent this result also holds for Runge-Kutta methods. Dedicated to Germund Dahlquist on the occasion of his 60th birthday.     

The stability function for multistep collocation methods

Summary C-polynomials for rational approximation to the exponential function was introduced by Nørsett [7] to study stability properties of one-step methods. For one-step collocation methods theC-polynomial has a very simple form. In this paper we studyC-polynomials for multistep collocation methods and obtain results that generalize those in the one-step case, and provide a way to analyze linear stability of such methods.     

Numerical experiments with a multistep Radau method

This paper describes an implementation of multistep collocation methods, which are applicable to stiff differential problems, singular perturbation problems, and D.A.E.s of index 1 and 2.These methods generalize one-step implicit Runge-Kutta methods as well as multistep one-stage BDF methods. We give numerical comparisons of our code with two representative codes for these methods, RADAU5 and LSODE.     

Some relationships between implicit Runge-Kutta,collocation and Lanczosτ methods,and their stability properties

In this paper relationships between various one-step methods for the initial value problem in ordinary differential equations are discussed and a unified treatment of the stability properties of the methods is given. The analysis provides some new results on stability as well as alternative derivations for some known results. The term stability is used in the sense ofA-Stability as introduced by Dahlquist. Conditions for any polynomial collocation method or its equivalent to beA-Stable are derived. These conditions may be easily checked in any particular case.     

解Stiff常微分方程组初值问题的线性隐式方法

对于Stiff常微分方程组初值问题的数值解,人们为了保证数值解过程误差传播的有界性,经常使用的方法之一是隐式的线性多步法.而在解由隐式线性多步法所产生的非线性方程组时,总是采用Newton-Raphson迭代方法.为此就要给出适当的预估式和计算     

Dahlquist's first barrier for multistage multistep formulas

Dahlquist's proof of his barrier for the order of stable linear multistep methods is combined with Reimer's proof of the corresponding barrier for multistep multiderivative methods. This leads to a shortening of Reimer's original proof and gives lower bounds for the error constant. These bounds are then studied for high error order and are used to model the optimal order and stepsize selection in an idealized integration code. Dedicated to Professor Germund Dahlquist on the occasion of his sixtieth birthday.     

Optimal residuals and the Dahlquist test problem

Numerical Algorithms - We show how to compute the optimal relative backward error for the numerical solution of the Dahlquist test problem by one-step methods. This is an example of a general...     

Convergence of multistep discretizations of DAEs

Standard ODE methods such as linear multistep methods encounter difficulties when applied to differential-algebraic equations (DAEs) of index greater than 1. In particular, previous results for index 2 DAEs have practically ruled out the use of all explicit methods and of implicit multistep methods other than backward difference formulas (BDFs) because of stability considerations. In this paper we embed known results for semi-explicit index 1 and 2 DAEs in a more comprehensive theory based on compound multistep and one-leg discretizations. This explains and characterizes the necessary requirements that a method must fulfill in order to be applicable to semi-explicit DAEs. Thus we conclude that the most useful discretizations are those that avoid discretization of the constraint. A freer use of e.g. explicit methods for the non-stiff differential part of the DAE is then possible.Dedicated to Germund Dahlquist on the occasion of his 70th birthdayThis author thanks the Centro de Estadística y Software Matemático de la Universidad Simón Bolivar (CESMa) for permitting her free use of its research facilities.Partial support by the Swedish Research Council for Engineering Sciences TFR under contract no. 222/91-405.     

Backward error analysis for multistep methods

Summary. In recent years, much insight into the numerical solution of ordinary differential equations by one-step methods has been obtained with a backward error analysis. It allows one to explain interesting phenomena such as the almost conservation of energy, the linear error growth in Hamiltonian systems, and the existence of periodic solutions and invariant tori. In the present article, the formal backward error analysis as well as rigorous, exponentially small error estimates are extended to multistep methods. A further extension to partitioned multistep methods is outlined, and numerical illustrations of the theoretical results are presented. Received January 20, 1998 / Revised version received November 20, 1998 / Published online September 24, 1999     

两类线性隐式方法

众所周知,在Stiff常微分方程组初值问题的数值解法中,向后微分公式(即Gear方法)是目前最通用的方法之一(见[1]).但是,Gear方法是一类隐式方法,在数值解的过程中,一般说来,每向前积分一步,需要解一个非线性方程组,它的求解是采用Newton-Raphson迭代方法,因此需要给出适当精度的预估值和计算右函数f(t,y)的Jacobi阵以     

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.     

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.     

Non-linear stability of a general class of differential equation methods

For a class of methods sufficiently general as to include linear multistep and Runge-Kutta methods as special cases, a concept known as algebraic stability is defined. This property is based on a non-linear test problem and extends existing results on Runge-Kutta methods and on linear multistep and one-leg methods. The algebraic stability properties of a number of particular methods in these families are studied and a generalization is made which enables estimates of error growth to be provided for certain classes of methods.     

Variational time discretizations of higher order and higher regularity

We consider a family of variational time discretizations that are generalizations of discontinuous Galerkin (dG) and continuous Galerkin–Petrov (cGP) methods. The family is characterized by two parameters. One describes the polynomial ansatz order while the other one is associated with the global smoothness that is ensured by higher order collocation conditions at both ends of the subintervals. Applied to Dahlquist’s stability problem, the presented methods provide the same stability properties as dG or cGP methods. Provided that suitable quadrature rules of Hermite type are used to evaluate the integrals in the variational conditions, the variational time discretization methods are connected to special collocation methods. For this case, we present error estimates, numerical experiments, and a computationally cheap postprocessing that allows to increase both the accuracy and the global smoothness by one order.

     

QUADRATIC INVARIANTS AND SYMPLECTIC STRUCTURE OF GENERAL LINEAR METHODS

1. IntroductionInvestigating whether a numerical method inherits some dynamical properties possessed bythe differential equation systems being integrated is an important field of numerical analysisand has received much attention in recent years See the review articlesof Sanz-Serna[9] and Section 11.16 of Hairer et. al.[2] for more detail concerning the symplectic methods. Most of the work on canonical iotegrators has dealt with one-step formulaesuch as Runge-Kutta methods and Runge'methods …     

Multistep Hermite collocation methods for solving Volterra Integral Equations

In this paper, we propose a new class of multistep collocation methods for solving nonlinear Volterra Integral Equations, based on Hermite interpolation. These methods furnish an approximation of the solution in each subinterval by using approximated values of the solution, as well as its first derivative, in the r previous steps and m collocation points. Convergence order of the new methods is determined and their linear stability is analyzed. Some numerical examples show efficiency of the methods.     

Parallel ODE solvers based on block BVMs

In this paper we deal with Boundary Value Methods (BVMs), which are methods recently introduced for the numerical approximation of initial value problems for ODEs. Such methods, based on linear multistep formulae (LMF), overcome the stability limitations due to the well-known Dahlquist barriers, and have been the subject of much research in the last years. This has led to the definition of a new stability framework, which generalizes the one stated by Dahlquist for LMF. Moreover, several aspects have been investigated, including the efficient stepsize control [17,25,26] and the application of the methods for approximating different kinds of problems such as BVPs, PDEs and DAEs [7,23,41]. Furthermore, a block version of such methods, recently proposed for approximating Hamiltonian problems [24], is able to provide an efficient parallel solver for ODE systems [3].     

Asymptotic expansions of the global error of fixed-stepsize methods

Summary In his fundamental paper on general fixed-stepsize methods, Skeel [6] studied convergence properties, but left the existence of asymptotic expansions as an open problem. In this paper we give a complete answer to this question. For the special cases of one-step and linear multistep methods our proof is shorter than the published ones.Asymptotic expansions are the theoretical base for extrapolation methods.     

Generating numerical algorithms using a computer algebra system

An useful application of computer algebra systems is the generation of algorithms for numerical computations. We have shown in Gander and Gruntz (SIAM Rev., 1999) how computer algebra can be used in teaching to derive numerical methods. In this paper we extend this work, using essentially the capability of computer algebra system to construct and manipulate the interpolating polynomial and to compute a series expansion of a function. We will automatically generate formulas for integration and differentiation with error terms and also generate multistep methods for integrating differential equations. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65D25, 65D30, 65D32, 65L06