High orderP-stable formulae for the numerical integration of periodic initial value problems

Summary Recently there has been considerable interest in the approximate numerical integration of the special initial value problemy=f(x, y) for cases where it is known in advance that the required solution is periodic. The well known class of Störmer-Cowell methods with stepnumber greater than 2 exhibit orbital instability and so are often unsuitable for the integration of such problems. An appropriate stability requirement for the numerical integration of periodic problems is that ofP-stability. However Lambert and Watson have shown that aP-stable linear multistep method cannot have an order of accuracy greater than 2. In the present paper a class of 2-step methods of Runge-Kutta type is discussed for the numerical solution of periodic initial value problems.P-stable formulae with orders up to 6 are derived and these are shown to compare favourably with existing methods.     

Two-stage complex Rosenbrock schemes for stiff systems

New two-stage Rosenbrock schemes with complex coefficients are proposed for stiff systems of differential equations. The schemes are fourth-order accurate and satisfy enhanced stability requirements. A one-parameter family of L1-stable schemes with coefficients explicitly calculated by formulas involving only fractions and radicals is constructed. A single L2-stable scheme is found in this family. The coefficients of the fourth-order accurate L4-stable scheme previously obtained by P.D Shirkov are refined. Several fourth-order schemes are constructed that are high-order accurate for linear problems and possess the limiting order of L-decay. The schemes proposed are proved to converge. A symbolic computation algorithm is developed that constructs order conditions for multistage Rosenbrock schemes with complex coefficients. This algorithm is used to design the schemes proposed and to obtain fifth-order accurate conditions.     

On variable step Hermite–Birkhoff solvers combining multistep and 4-stage DIRK methods for stiff ODEs

Variable-step (VS) 4-stage k-step Hermite–Birkhoff (HB) methods of order p = (k + 2), p = 9, 10, denoted by HB (p), are constructed as a combination of linear k-step methods of order (p ? 2) and a diagonally implicit one-step 4-stage Runge–Kutta method of order 3 (DIRK3) for solving stiff ordinary differential equations. Forcing a Taylor expansion of the numerical solution to agree with an expansion of the true solution leads to multistep and Runge–Kutta type order conditions which are reorganized into linear confluent Vandermonde-type systems. This approach allows us to develop L(a)-stable methods of order up to 11 with a > 63°. Fast algorithms are developed for solving these systems in O (p²) operations to obtain HB interpolation polynomials in terms of generalized Lagrange basis functions. The stepsizes of these methods are controlled by a local error estimator. HB(p) of order p = 9 and 10 compare favorably with existing Cash modified extended backward differentiation formulae of order 7 and 8, MEBDF(7-8) and Ebadi et al. hybrid backward differentiation formulae of order 10 and 12, HBDF(10-12) in solving problems often used to test higher order stiff ODE solvers on the basis of CPU time and error at the endpoint of the integration interval.     

High order methods for the numerical solution of two-point boundary value problems

In a recent paper, Cash and Moore have given a fourth order formula for the approximate numerical integration of two-point boundary value problems in O.D.E.s. The formula presented was in effect a one-off formula in that it was obtained using a trial and error approach. The purpose of the present paper is to describe a unified approach to the derivation of high order formulae for the numerical integration of two-point boundary value problems. It is shown that the formula derived by Cash and Moore fits naturally into this framework and some new formulae of orders 4, 6 and 8 are derived using this approach. A numerical comparison with certain existing finite difference methods is made and this comparison indicates the efficiency of the high order methods for problems having a suitably smooth solution.     

A Fully Polynomial Approximation Scheme for Minimizing Makespan of Deteriorating Jobs

A fully polynomial approximation scheme for the problem of scheduling n deteriorating jobs on a single machine to minimize makespan is presented. Each algorithm of the scheme runs in O(n ⁵ L ⁴³) time, where L is the number of bits in the binary encoding of the largest numerical parameter in the input, and is required relative error. The idea behind the scheme is rather general and it can be used to develop fully polynomial approximation schemes for other combinatorial optimization problems. Main feature of the scheme is that it does not require any prior knowledge of lower and/or upper bounds on the value of optimal solutions.     

Numerical Evaluation of Integrals Involving the β‐PDF

The fast and accurate evaluation of expected values involving the probabilistic β‐distributions poses severe problems to standard numerical integration schemes. An efficient algorithm to evaluate such integrals is presented based on approximation and analytical evaluation rather than numerical integration. Starting from an extension of the 2‐parameter family of β‐distributions a criterion is derived to assess the correctness of any integration scheme in the numerically demanding limiting cases of this family.     

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.     

An analysis of stability and convergence of a finite-difference discretization of a model parabolic PDE in 1D using a moving mesh

^{The aim of this paper is to investigate the stability and convergenceof time integration schemes for the solution of a semi-discretizationof a model parabolic problem in 1D using a moving mesh. Thespatial discretization is achieved using a second-order centralfinite-difference scheme. Using energy techniques we show thatthe backward Euler scheme is unconditionally stable in a mesh-dependentL₂-norm, independently of the mesh movement, but the Crank–Nicolson(CN) scheme is only conditionally stable. By identifying thediffusive and anti-diffusive effects caused by the mesh movement,we devise an adaptive -method that is shown to be unconditionallystable and asymptotically second-order accurate. Numerical experimentsare presented to back up the findings of the analysis.}     

EfficientP-stable methods for periodic initial value problems

Efficient families ofP-stable formulae are developed for the numerical integration of periodic initial value problems where the required solution has an unknown period. Formulae of orders 4 and 6 requiring respectively 2 and 4 function evaluations per step are derived and some numerical results are given.     

L-stable Simpson’s 3/8 rule and Burgers’ equation

In this paper we develop an unconditionally stable third order time integration formula for the diffusion equation with Neumann boundary condition. We use a suitable arithmetic average approximation and explicit backward Euler formula and then develop a third order L-stable Simpson’s 3/8 type formula. We also observe that the arithmetic average approximation is not unique. Then L-stable Simpson’s 3/8 type formula and Hopf-Cole transformation is used to solve Burger’s equation with Dirichlet boundary condition. It is also observed that this numerical method deals efficiently in case of inconsistencies in initial and boundary conditions.     

Second order unconditionally convergent and energy stable linearized scheme for MHD equations

In this paper, we propose an efficient numerical scheme for magnetohydrodynamics (MHD) equations. This scheme is based on a second order backward difference formula for time derivative terms, extrapolated treatments in linearization for nonlinear terms. Meanwhile, the mixed finite element method is used for spatial discretization. We present that the scheme is unconditionally convergent and energy stable with second order accuracy with respect to time step. The optimal L ² and H ¹ fully discrete error estimates for velocity, magnetic variable and pressure are also demonstrated. A series of numerical tests are carried out to confirm our theoretical results. In addition, the numerical experiments also show the proposed scheme outperforms the other classic second order schemes, such as Crank-Nicolson/Adams-Bashforth scheme, linearized Crank-Nicolson’s scheme and extrapolated Gear’s scheme, in solving high physical parameters MHD problems.     

Blended extended linear multistep methods for the accurate numerical integration of stiff initial value problems

A class of blended extended linear multistep methods suitable for the approximate numerical integration of stiff systems of first order ordinary differential equations is described. These methods are formulated as a result of combining the second derivative extended backward differentiation formulae of Cash and the blended linear multistep methods of Skeel and Kong. The new methods combine a high order or accuracy with good stability properties and, as a direct consequence, they are often suitable for the numerical integration of stiff differential systems when high accuracy is requested. In the first part of the present paper we consider the derivation of these new blended methods and give the coefficients and stability regions for formulae of order up to and including 10. In the second half we consider their practical implementation. In particular we describe a variable order/variable step package based on these blended formulae and we evaluate the performance of this package on the well known DETEST test set. It is shown that the new code is reliable on this test set and is competitive with the well known second derivative method of Enright.     

A linear multistep numerical integration scheme for solving systems of ordinary differential equations with oscillatory solutions

In ^[1], a set of convergent and stable two-point formulae for obtaining the numerical solution of ordinary differential equations having oscillatory solutions was formulated. The derivation of these formulae was based on a non-polynomial interpolant which required the prior analytic evaluation of the higher order derivatives of the system before proceeding to the solution. In this paper, we present a linear multistep scheme of order four which circumvents this (often tedious) initial preparation. The necessary starting values for the integration scheme are generated by an adaptation of the variable order Gragg-Bulirsch-Stoer algorithm as formulated in ^[2].     

Efficient parallel multivalue hybrid methods for stiff differential equations

A class of efficient parallel multivalue hybrid methods for stiff differential equations are presented, which are all extremely stable at infinity,A-stable for orders 1–3 and A(α)-stable for orders 4–8. Each method of the class can be performed parallelly using two processors with each processor having almost the same computational amount per integration step as a backward differentiation formula (BDF) of the same order with the same stepsize performed in serial, whereas the former has not only much better stability properties but also a computational accuracy higher than the corresponding BDF. Theoretical analysis and numerical experiments show that the methods constructed in this paper are superior in many respects not only to BDFs but also to some other commonly used methods.     

On symmetrizers for Gauss methods

Summary In this paper the maximum attainable order of a special class of symmetrizers for Gauss methods is studied. In particular, it is shown that a symmetrizer of this type for thes-stage Gauss method can attain order 2s-1 only for 1 s 3, and that these symmetrizers areL-stable. A classification of the maximum attainable order of symmetrizers for some higher stages is presented. AnL-stable symmetrizer is also shown to exist for each of the methods studied.     

On the order conditions of Runge-Kutta methods with higher derivatives

Summary Runge-Kutta methods have been generalized to procedures with higher derivatives of the right side ofy=f(t,y) e.g. by Fehlberg 1964 and Kastlunger and Wanner 1972. In the present work some sufficient conditions for the order of consistence are derived for these methods using partially the degree of the corresponding numerical integration formulas. In particular, methods of Gauß, Radau, and Lobatto type are generalized to methods with higher derivatives and their maximum order property is proved. The applied technique was developed by Crouzeix 1975 for classical Runge-Kutta methods. Examples of simple explicit and semi-implicit methods are given up to order 7 and 6 respectively.     

A class of one-step one-stage methods for stiff systems of ordinary differential equations

A new class of one-step one-stage methods (ABC-schemes) designed for the numerical solution of stiff initial value problems for ordinary differential equations is proposed and studied. The Jacobian matrix of the underlying differential equation is used in ABC-schemes. They do not require iteration: a system of linear algebraic equations is once solved at each integration step. ABC-schemes are A- and L-stable methods of the second order, but there are ABC-schemes that have the fourth order for linear differential equations. Some aspects of the implementation of ABC-schemes are discussed. Numerical results are presented, and the schemes are compared with other numerical methods.     

The stability and convergence of two linearized finite difference schemes for the nonlinear epitaxial growth model

The numerical simulation of the dynamics of the molecular beam epitaxy (MBE) growth is considered in this article. The governing equation is a nonlinear evolutionary equation that is of linear fourth order derivative term and nonlinear second order derivative term in space. The main purpose of this work is to construct and analyze two linearized finite difference schemes for solving the MBE model. The linearized backward Euler difference scheme and the linearized Crank‐Nicolson difference scheme are derived. The unique solvability, unconditional stability and convergence are proved. The linearized Euler scheme is convergent with the convergence order of O(τ + h²) and linearized Crank‐Nicolson scheme is convergent with the convergence order of O(τ² + h²) in discrete L²‐norm, respectively. Numerical stability with respect to the initial conditions is also obtained for both schemes. Numerical experiments are carried out to demonstrate the theoretical analysis. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Positive definiteness in the numerical solution of Riccati differential equations

Summary. In this work we address the issue of integrating symmetric Riccati and Lyapunov matrix differential equations. In many cases -- typical in applications -- the solutions are positive definite matrices. Our goal is to study when and how this property is maintained for a numerically computed solution. There are two classes of solution methods: direct and indirect algorithms. The first class consists of the schemes resulting from direct discretization of the equations. The second class consists of algorithms which recover the solution by exploiting some special formulae that these solutions are known to satisfy. We show first that using a direct algorithm -- a one-step scheme or a strictly stable multistep scheme (explicit or implicit) -- limits the order of the numerical method to one if we want to guarantee that the computed solution stays positive definite. Then we show two ways to obtain positive definite higher order approximations by using indirect algorithms. The first is to apply a symplectic integrator to an associated Hamiltonian system. The other uses stepwise linearization. Received April 21, 1993