Stability properties of variable stepsize variable formula methods

Summary When variable stepsize variable formula methods (VSVFM's) are used in the solution of systems of first order differential equations instability arises sometimes. Therefore it is important to find VSVFM's whose zerostability properties are not affected by the choice of both the stepsize and the formula. The Adams VSVFM's are such methods. In this work a more general class of methods which contains the Adams VSVFM's is discussed and it is proved that the zero-stability of the class is not affected by the choice of the stepsize and of the formula.     

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.     

Application of predictor-corrector schemes with several correctors in solving air pollution problems

Systems of ordinary differential equations obtained by using splitting-up techniques in some air pollution models and a pseudospectral (Fourier) discretization of the first-order space derivatives are considered. The application of a fairly general class of predictor-corrector (PC) schemes in the time-discretization process is discussed. Several corrections with different corrector formulae are carried out in thesePC schemes. The classicalDahlquist theory valid for the case when the stepsize is constant is preserved (under very mild restrictions on the stepsize) when suchPC schemes are used as variable stepsize variable formula methods (VSVFM's). This fact is exploited by allowing the stepsize to follow the variation of a certain norm of the wind velocity vector in aVSVFM based on specially constructedPC schemes with large intervals of absolute stability on the imaginary axis. A device that attempts to check both the accuracy and the stability in the course of the integration process has been developed. The code based on the application of thisVSVFM in the time-integration part of the treatment of both 2-dimensional and 3-dimensional models has been tested by using meteorological data prepared at stations located in practically all European countries. The numerical results indicate thatPC schemes with several correctors can successfully be used for the class of problems under consideration. The main reason for this success is the special nature of the computational cost per time-step (due to the splitting approach used). Some short remarks on the possibility of extending the results for large systems ofODE's arising in the treatment of other classes of problems are made.Dedicated to Germund Dahlquist, on the occasion of his 60th birthday.     

Multiderivative variable stepsize variable formula methods

In this paper we present a study of consistency, stability and convergence properties of linear multiderivative multistep variable stepsize variable formula methods.     

Two-parameter families of predictor-corrector methods for the solution of ordinary differential equations

Two-parameter families of predictor-corrector methods based upon a combination of Adams- and Nyström formulae have been developed. The combinations use correctors of order one higher than that of the predictors. The methods are chosen to give optimal stability properties with respect to a requirement on the form and size of the regions of absolute stability. The optimal methods are listed and their regions of absolute stability are presented. The efficiency of the methods is compared to that of the corresponding Adams methods through numerical results from a variable order, variable stepsize program package.     

Convergence of parallel multistep hybrid methods for singular perturbation problems

Parallel multistep hybrid methods (PHMs) can be implemented in parallel with two processors, accordingly have almost the same computational speed per integration step as BDF methods of the same order with the same stepsize. But PHMs have better stability properties than BDF methods of the same order for stiff differential equations. In the present paper, we give some results on error analysis of A(α)-stable PHMs for the initial value problems of ordinary differential equations in singular perturbation form. Our convergence results are similar to those of linear multistep methods (such as BDF methods), i.e. the convergence orders are equal to their classical convergence orders, and no order reduction occurs. Some numerical examples also confirm our results.     

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)     

求解变延迟微分方程的一类线性多步方法的收缩性

This paper presents a sufficient condition on the contractivity of theoretical solution for a class of nonlinear systems of delay differential equations with many variable delays(MDDEs), which is weak,compared with the sufficient condition of previous articles.In addition,it discusses the numerical stability properties of a class of special linear nmltistep methods for this class nonlinear problems.And it is pointed out that not only the backwm‘d Euler method but also this class of linear multistep methods are GRNm-stable if linear interpolation is used.     

Adaptive stepsize based on control theory for stochastic differential equations

The numerical solution of stochastic differential equations (SDEs) has been focussed recently on the development of numerical methods with good stability and order properties. These numerical implementations have been made with fixed stepsize, but there are many situations when a fixed stepsize is not appropriate. In the numerical solution of ordinary differential equations, much work has been carried out on developing robust implementation techniques using variable stepsize. It has been necessary, in the deterministic case, to consider the “best” choice for an initial stepsize, as well as developing effective strategies for stepsize control—the same, of course, must be carried out in the stochastic case.

In this paper, proportional integral (PI) control is applied to a variable stepsize implementation of an embedded pair of stochastic Runge–Kutta methods used to obtain numerical solutions of nonstiff SDEs. For stiff SDEs, the embedded pair of the balanced Milstein and balanced implicit method is implemented in variable stepsize mode using a predictive controller for the stepsize change. The extension of these stepsize controllers from a digital filter theory point of view via PI with derivative (PID) control will also be implemented. The implementations show the improvement in efficiency that can be attained when using these control theory approaches compared with the regular stepsize change strategy.     

On the derivation of explicit two-step peer methods

The so-called two-step peer methods for the numerical solution of Initial Value Problems (IVP) in differential systems were introduced by R. Weiner, B.A. Schmitt and coworkers as a tool to solve different types of IVPs either in sequential or parallel computers. These methods combine the advantages of Runge-Kutta (RK) and multistep methods to obtain high stage order and therefore provide in a natural way a dense output. In particular, several explicit peer methods have been proved to be competitive with standard RK methods in a wide selection of non-stiff test problems.The aim of this paper is to propose an alternative procedure to construct families of explicit two step peer methods in which the available parameters appear in a transparent way. This allows us to obtain families of fixed stepsize s stage methods with stage order 2s−1, which provide dense output without extra cost, depending on some free parameters that can be selected taking into account the stability properties and leading error terms. A study of the extension of these methods to variable stepsize is also carried out. Optimal s stage methods with s=2,3 are derived.     

Backward Euler discretization of fully nonlinear parabolic problems

This paper is concerned with the time discretization of nonlinear evolution equations. We work in an abstract Banach space setting of analytic semigroups that covers fully nonlinear parabolic initial-boundary value problems with smooth coefficients. We prove convergence of variable stepsize backward Euler discretizations under various smoothness assumptions on the exact solution. We further show that the geometric properties near a hyperbolic equilibrium are well captured by the discretization. A numerical example is given.

     

On interval predictor-corrector methods

One can approximate numerically the solution of the initial value problem using single or multistep methods. Linear multistep methods are used very often, especially combinations of explicit and implicit methods. In floating-point arithmetic from an explicit method (a predictor), we can get the first approximation to the solution obtained from an implicit method (a corrector). We can do the same with interval multistep methods. Realizing such interval methods in floating-point interval arithmetic, we compute solutions in the form of intervals which contain all possible errors. In this paper, we propose interval predictor-corrector methods based on conventional Adams-Bashforth-Moulton and Nyström-Milne-Simpson methods. In numerical examples, these methods are compared with interval methods of Runge-Kutta type and methods based on high-order Taylor series. It appears that the presented methods yield comparable approximations to the solutions.     

The Incremental Gauss-Newton Algorithm with Adaptive Stepsize Rule

In this paper, we consider the Extended Kalman Filter (EKF) for solving nonlinear least squares problems. EKF is an incremental iterative method based on Gauss-Newton method that has nice convergence properties. Although EKF has the global convergence property under some conditions, the convergence rate is only sublinear under the same conditions. One of the reasons why EKF shows slow convergence is the lack of explicit stepsize. In the paper, we propose a stepsize rule for EKF and establish global convergence of the algorithm under the boundedness of the generated sequence and appropriate assumptions on the objective function. A notable feature of the stepsize rule is that the stepsize is kept greater than or equal to 1 at each iteration, and increases at a linear rate of k under an additional condition. Therefore, we can expect that the proposed method converges faster than the original EKF. We report some numerical results, which demonstrate that the proposed method is promising.     

API stepsize control for the numerical solution of ordinary differential equations

A control-theoretic approach is used to design a new automatic stepsize control algorithm for the numerical integration of ODE's. The new control algorithm is more robust at little extra expense. Its improved performance is particularly evident when the stepsize is limited by numerical stability. Comparative numerical tests are presented.     

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.     

Equilibrium states for predictor-corrector methods

A theory is developed that explains the stepsize patterns observed when standard predictor-corrector methods with variable stepsize strategy are used to solve stiff or mildly stiff problems. In some cases an algorithmic steady state occurs with smooth almost constant stepsizes; at other times an oscillating stepsize pattern of stepsizes is observed with the possibility of frequent rejected steps.     

Nonlinear Stability of General Linear Methods for Delay Differential Equations

This paper is devoted to a study of nonlinear stability of general linear methods for the numerical solution of delay differential equations in Hilbert spaces. New stability concepts are further introduced. The stability properties of (k,p,q)-algebraically stable general linear methods with piecewise constant or linear interpolation procedure are investigated. We also discuss stability of linear multistep methods viewed as a special subset of the class of general linear methods.     

Variable multistep methods for delay differential equations

In this paper, variable stepsize multistep methods for delay differential equations of the type y(t) = f(t, y(t), y(t − τ)) are proposed. Error bounds for the global discretization error of variable stepsize multistep methods for delay differential equations are explicitly computed. It is proved that a variable multistep method which is a perturbation of strongly stable fixed step size method is convergent.     

Asymptotical Stability of Numerical Methods with Constant Stepsize for Pantograph Equations

In this paper, the asymptotical stability of the analytic solution and the numerical methods with constant stepsize for pantograph equations is investigated using the Razumikhin technique. In particular, the linear pantograph equations with constant coefficients and variable coefficients are considered. The stability conditions of the analytic solutions of those equations and the numerical solutions of the θ-methods with constant stepsize are obtained. As a result Z. Jackiewicz’s conjecture is partially proved. Finally, some experiments are given. AMS subject classification (2000) 65L02, 65L05, 65L20     

A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm

Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm²)\mathcal{O}(nm^{2}) operations per iteration. When n≫m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good update and could be ignored to achieve computational savings. This idea was considered in the 1990s by Dantzig and Ye, Tone, Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple “constraint-reduction” scheme and proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of Mehrotra’s predictor-corrector algorithm, under less restrictive nondegeneracy assumptions. These stronger results extend to primal-dual affine scaling as a limiting case. Promising numerical results are reported.