Variable stepsize variable formula methods based on predictor-corrector schemes

The use of fairly general predictor-corrector (PC) schemes of linear multistep (LM) formulae in the numerical solution of systems of ordinary differential equations (ODE's) is considered. It is assumed that both the stepsize and the PC scheme can be varied during the computational process. The numerical methods obtained under these two assumptions are called predictor-corrector linear multistep variable stepsize variable formula methods (PC LM VSVFM's). The consistency, zero-stability and convergence properties of the PC LM VSVFM's are studied. Several results concerning these fundamental properties of the numerical methods are established. It should be emphasized that all theorems are formulated and proved under very mild assumptions on the stepsize selection strategy. The extension of the results for the so-called one-leg methods is briefly discussed. The use of PC LM VSVFM's leads to a very efficient treatment of many mathematical models describing different phenomena in science and engineering. Such methods have successfully been used in the numerical solution of systems of ODE's arising after the space discretization of some air pollution models.     

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.     

Stability of some boundary value methods for the solution of initial value problems

The stability properties of three particular boundary value methods (BVMs) for the solution of initial value problems are considered. Our attention is focused on the BVMs based on the midpoint rule, on the Simpson method and on an Adams method of order 3. We investigate their BV-stability regions by considering the scalar test problem and constant stepsize. The study of the conditioning of the coefficient matrix of the discrete problem is extended to the case of variable stepsize and block ODE problems. We also analyse an appropriate choice for the stepsize for stiff problems. Numerical tests are reported to evidentiate the effectiveness of the BVMs and the differences among the BVMs considered.Work supported by the Ministero della Ricerca Scientifica, 40% project, and C.N.R. (contract of research # 92.00535.01).     

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.     

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.     

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.     

Time-transformations for reversible variable stepsize integration

The development of a Sundman-type time-transformation for reversible variable stepsize integration of few-body problems is discussed. While a time-transformation based on minimum particle separation is suitable if the collisions only occur pairwise and isolated in time, the control of stepsize is typically much more difficult for a three-body close approach. Nonetheless, we find that a suitable choice of time-transformation based on particle separation can work quite well for certain types of three-body simulations, particularly those involving very steep repulsive walls. We confirm these observations using numerical examples from Lennard-Jones scattering. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bregman operator splitting with variable stepsize for total variation image reconstruction

This paper develops a Bregman operator splitting algorithm with variable stepsize (BOSVS) for solving problems of the form $\min\{\phi(Bu) +1/2\|Au-f\|_{2}^{2}\}$ , where ? may be nonsmooth. The original Bregman Operator Splitting (BOS) algorithm employed a fixed stepsize, while BOSVS uses a line search to achieve better efficiency. These schemes are applicable to total variation (TV)-based image reconstruction. The stepsize rule starts with a Barzilai-Borwein (BB) step, and increases the nominal step until a termination condition is satisfied. The stepsize rule is related to the scheme used in SpaRSA (Sparse Reconstruction by Separable Approximation). Global convergence of the proposed BOSVS algorithm to a solution of the optimization problem is established. BOSVS is compared with other operator splitting schemes using partially parallel magnetic resonance image reconstruction problems. The experimental results indicate that the proposed BOSVS algorithm is more efficient than the BOS algorithm and another split Bregman Barzilai-Borwein algorithm known as SBB.     

Experiments with a New Fifth Order Method

Almost Runge–Kutta methods were introduced to obtain many of the advantages of Runge–Kutta methods without their disadvantages. We consider the construction of fourth order methods of this type with a special choice of the free parameters to ensure that, at least for constant stepsize, order 5 behaviour is achieved. It is shown how this can be extended to variable stepsize.     

Analysis of trigonometric implicit Runge–Kutta methods

Using generalized collocation techniques based on fitting functions that are trigonometric (rather than algebraic as in classical integrators), we develop a new class of multistage, one-step, variable stepsize, and variable coefficients implicit Runge–Kutta methods to solve oscillatory ODE problems. The coefficients of the methods are functions of the frequency and the stepsize. We refer to this class as trigonometric implicit Runge–Kutta (TIRK) methods. They integrate an equation exactly if its solution is a trigonometric polynomial with a known frequency. We characterize the order and A-stability of the methods and establish results similar to that of classical algebraic collocation RK methods.     

A new adaptive Barzilai and Borwein method for unconstrained optimization

In this paper we view the Barzilai and Borwein (BB) method from a new angle, and present a new adaptive Barzilai and Borwein (NABB) method with a nonmonotone line search for general unconstrained optimization. In the proposed method, the scalar approximation to the Hessian matrix is updated by the Broyden class formula to generate an adaptive stepsize. It is remarkable that the new stepsize is chosen adaptively in the interval which contains the two well-known BB stepsizes. Moreover, for the negative curvature direction, a strategy for the choice of the stepsize is designed to accelerate the convergence rate of the NABB method. Furthermore, we apply the NABB method without any line search to strictly convex quadratic minimization. The numerical experiments show the NABB method is very promising.     

Convergence of Conjugate Gradient Methods with a Closed-Form Stepsize Formula

Conjugate gradient methods are efficient methods for minimizing differentiable objective functions in large dimension spaces. However, converging line search strategies are usually not easy to choose, nor to implement. Sun and colleagues (Ann. Oper. Res. 103:161–173, 2001; J. Comput. Appl. Math. 146:37–45, 2002) introduced a simple stepsize formula. However, the associated convergence domain happens to be overrestrictive, since it precludes the optimal stepsize in the convex quadratic case. Here, we identify this stepsize formula with one iteration of the Weiszfeld algorithm in the scalar case. More generally, we propose to make use of a finite number of iterates of such an algorithm to compute the stepsize. In this framework, we establish a new convergence domain, that incorporates the optimal stepsize in the convex quadratic case. The authors thank the associate editor and the reviewer for helpful comments and suggestions. C. Labat is now in postdoctoral position, Johns Hopkins University, Baltimore, MD, United States.     

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.     

Modified Two-Point Stepsize Gradient Methods for Unconstrained Optimization

For unconstrained optimization, the two-point stepsize gradient method is preferable over the classical steepest descent method both in theory and in real computations. In this paper we interpret the choice for the stepsize in the two-point stepsize gradient method from the angle of interpolation and propose two modified two-point stepsize gradient methods. The modified methods are globally convergent under some mild assumptions on the objective function. Numerical results are reported, which suggest that improvements have been achieved.     

比例延迟微分方程组具有刚性精度Runge-Kutta方法的稳定性分析

该文研究比例延迟微分方程组具有刚性精度变步长Runge-Kutta方法的渐近稳定性，给出了一类普遍意义下的变步长格式。证明当且仅当其稳定函数在无穷远点处的模小于1时，变步长Runge-Kutta方法渐近稳定。     

A second-order compact difference scheme for the fourth-order fractional sub-diffusion equation

In this paper, the Euler–Maruyama (EM) method with random variable stepsize is studied to reproduce the almost sure stability of the true solutions of stochastic differential equations. Since the choice of the time step is based on the current state of the solution, the time variable is proved to be a stopping time. Then the semimartingale convergence theory is employed to obtain the almost sure stability of the random variable stepsize EM solution. To our best knowledge, this is the first paper to apply the random variable stepsize (with clear proof of the stopping time) to the analysis of the almost sure stability of the EM method.     

Local error and variable order Adams codes

Error estimates needed for the selection of order in Adams codes are studied in the presence of propagated errors. A new derivation of the Nordsieck form of the Adams methods reveals that codes based on this form have changed order incorrectly and shows how to do it properly.     

Explicit methods for mildly stiff oscillatory systems

We discuss error control for explicit methods when the stepsize is bounded by stability on the imaginary axis. Our main result is a formulation of a condition on the estimator of the local error which prevents the fast components to exceed the prescribed error tolerance. A PECE Adams method of 4th order accuracy is proposed for mildly stiff oscillatory systems. For comparison we also discuss embedded Runga-Kutta methods.Partially supported by the Office of Naval Research N00014-90-J-1382     

Second derivative general linear methods with inherent Runge–Kutta stability

In this paper, we find some relationships among the coefficients matrices of second derivative general linear methods (SGLMs) which are sufficient conditions, but not necessary, to ensure the methods have Runge–Kutta stability (RKS) property. Considering these conditions, we construct some A– and L–stable SGLMs with inherent RKS of orders up to five. Also, some numerical experiments for the constructed methods in variable stepsize environment are given.     

Scale and modify for the second and third order BDF methods

This paper investigates a ‘scale and modify’ technique used with variable stepsize BDF methods. When the stepsize is changed using the usual scaling procedure for Nordsieck methods, there can be adverse affects on the stability unless a severe restriction is placed on the allowable stepsize ratios. However, a modification to this scaling procedure may extend the range of permissible stepsize ratios. Results for the Nordsieck form of the second and third order methods indicate that this may be possible.