Efficient higher order implicit one-step methods for integration of stiff differential equations

A new implicit integration method is presented which can efficiently be applied in the solution of (stiff) differential equations. The given formulas are of a modified implicit Runge-Kutta type and areA-stable. They may containA-stable embedded methods for error estimation and step-size control.     

The composite Milstein methods for the numerical solution of Stratonovich stochastic differential equations

In this paper, we present two composite Milstein methods for the strong solution of Stratonovich stochastic differential equations driven by d-dimensional Wiener processes. The composite Milstein methods are a combination of semi-implicit and implicit Milstein methods. The criterion for choosing either the implicit or the semi-implicit method at each step of the numerical solution is given. The stability and convergence properties of the proposed methods are analyzed for the linear test equation. It is shown that the proposed methods converge to the exact solution in Stratonovich sense. In addition, the stability properties of our methods are found to be superior to those of the Milstein and the composite Euler methods. The convergence properties for the nonlinear case are shown numerically to be the same as the linear case. Hence, the proposed methods are a good candidate for the solution of stiff SDEs.     

Approximating Runge-Kutta matrices by triangular matrices

The implementation of implicit Runge-Kutta methods requires the solution of large systems of non-linear equations. Normally these equations are solved by a modified Newton process, which can be very expensive for problems of high dimension. The recently proposed triangularly implicit iteration methods for ODE-IVP solvers [5] substitute the Runge-Kutta matrixA in the Newton process for a triangular matrixT that approximatesA, hereby making the method suitable for parallel implementation. The matrixT is constructed according to a simple procedure, such that the stiff error components in the numerical solution are strongly damped. In this paper we prove for a large class of Runge-Kutta methods that this procedure can be carried out and that the diagnoal entries ofT are positive. This means that the linear systems that are to be solved have a non-singular matrix. The research reported in this paper was supported by STW (Dutch Foundation for Technical Sciences).     

Finite-difference methods for solving the reaction-diffusion equations of a simple isothermal chemical system

Numerical methods are proposed for the numerical solution of a system of reaction-diffusion equations, which model chemical wave propagation. The reaction terms in this system of partial differential equations contain nonlinear expressions. Nevertheless, it is seen that the numerical solution is obtained by solving a linear algebraic system at each time step, as opposed to solving a nonlinear algebraic system, which is often required when integrating nonlinear partial differential equations. The development of each numerical method is made in the light of experience gained in solving the system of ordinary differential equations, which model the well-stirred analogue of the chemical system. The first-order numerical methods proposed for the solution of this initialvalue problem are characterized to be implicit. However, in each case it is seen that the numerical solution is obtained explicitly. In a series of numerical experiments, in which the ordinary differential equations are solved first of all, it is seen that the proposed methods have superior stability properties to those of the well-known, first-order, Euler method to which they are compared. Incorporating the proposed methods into the numerical solution of the partial differential equations is seen to lead to two economical and reliable methods, one sequential and one parallel, for solving the travelling-wave problem. © 1994 John Wiley & Sons, Inc.     

Total Variation Diminishing Implicit Runge-Kutta Methods for Dissipative Advection-Diffusion Problems in Astrophysics

We investigate the properties of dissipative full discretizations for the equations of motion associated with models of flow and radiative transport inside stars. We derive dissipative space discretizations and demonstrate that together with specially adapted total-variation-diminishing (TVD) or strongly stable Runge-Kutta time discretizations with adaptive step-size control this yields reliable and efficient integrators for the underlying high-dimensional nonlinear evolution equations. For the most general problem class, fully implicit SDIRK methods are demonstrated to be competitive when compared to popular explicit Runge-Kutta schemes as the additional effort for the solution of the associated nonlinear equations is compensated by the larger step-sizes admissible for strong stability and dissipativity. For the parameter regime associated with semiconvection we can use partitioned IMEX Runge-Kutta schemes, where the solution of the implicit part can be reduced to the solution of an elliptic problem. This yields a significant gain in performance as compared to either fully implicit or explicit time integrators. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Runge-Kutta Methods for the Numerical Solution of Stiff Semilinear Systems

This paper studies the stability and convergence properties of general Runge-Kutta methods when they are applied to stiff semilinear systems y(t) = J(t)y(t) + g(t, y(t)) with the stiffness contained in the variable coefficient linear part.We consider two assumptions on the relative variation of the matrix J(t) and show that for each of them there is a family of implicit Runge-Kutta methods that is suitable for the numerical integration of the corresponding stiff semilinear systems, i.e. the methods of the family are stable, convergent and the stage equations possess a unique solution. The conditions on the coefficients of a method to belong to these families turn out to be essentially weaker than the usual algebraic stability condition which appears in connection with the B-stability and convergence for stiff nonlinear systems. Thus there are important RK methods which are not algebraically stable but, according to our theory, they are suitable for the numerical integration of semilinear problems.This paper also extends previous results of Burrage, Hundsdorfer and Verwer on the optimal convergence of implicit Runge-Kutta methods for stiff semilinear systems with a constant coefficients linear part.     

A criterion forP-stability properties of Runge-Kutta methods

P-stability is an analogous stability property toA-stability with respect to delay differential equations. It is defined by using a scalar test equation similar to the usual test equation ofA-stability. EveryP-stable method isA-stable, but anA-stable method is not necessarilyP-stable. We considerP-stability of Runge-Kutta (RK) methods and its variation which was originally introduced for multistep methods by Bickart, and derive a sufficient condition for an RK method to have the stability properties on the basis of an algebraic characterization ofA-stable RK methods recently obtained by Schere and Müller. By making use of the condition we clarify stability properties of some SIRK and SDIRK methods, which are easier to implement than fully implicit methods, applied to delay differential equations.     

Extrapolation at stiff differential equations

Summary Asymptotic expansions of the global error of numerical methods are well-understood, if the differential equation is non-stiff. This paper is concerned with such expansions for the implicit Euler method, the linearly implicit Euler method and the linearly implicit mid-point rule, when they are applied tostiff differential equations. In this case perturbation terms are present, whose dominant one is given explicitly. This permits us to better understand the behaviour ofextrapolation methods at stiff differential equations. Numerical examples, supporting the theoretical results, are included.     

The Convergence Rate of Block Preconditioned Systems Arising from LMF-based ODE Codes

The solution of ordinary an partial differential equations using implicit linear multi-step formulas (LMF)is considered. More precisely, boundary value methods (BVMs), a class of methods based on implicit formulas will be taken into account in this paper. These methods require the solution of large and sparse linear systems x = b. Block-circulant preconditioners have been propose to solve these linear systems. By investigating the spectral condition number of , we show that the conjugate gradient method, when applied to solving the normalize preconditioned system, converges in at most O(log s) steps, where the integration step size is O(1/s). Numerical results are given to illustrate the effectiveness of the analysis.This revised version was published online in October 2005 with corrections to the Cover Date.     

广义中立型系统的渐近稳定性及数值分析

１．引 言 考察如下广义中立型系统：其中,Ｌ,Ｍ,Ｎ ∈ Ｃｄ×ｄ为已知矩阵,　　　为已知向量值函数,　　　　　　　　　　当ｔ＞０时为未知函数,　　　　　　　　　　　　　　　　　　　　　　　　　为常数延时量． 对于　　　　　　　　　　　　　　　　　,１９６７年,Ｂｒａｙｔｏｎ［１］基于Ｌ,Ｍ,Ｎ为实对称矩阵,以及Ｉ± Ｎ和－Ｌ± Ｍ为正定矩阵时,讨论了（１）渐近稳定的充分条件;１９８４年,Ｊａｃｋｉｅｗｉｃｚ［２］基于 Ｌ,Ｍ,Ｎ为复系数时,研究了理论解的渐近稳定性及单步方法的数值稳定性;１９８８年,Ｂ…     

Circulant preconditioners for second order hyperbolic equations

Linear systems arising from implicit time discretizations and finite difference space discretizations of second-order hyperbolic equations in two dimensions are considered. We propose and analyze the use of circulant preconditioners for the solution of linear systems via preconditioned iterative methods such as the conjugate gradient method. Our motivation is to exploit the fast inversion of circulant systems with the Fast Fourier Transform (FFT). For second-order hyperbolic equations with initial and Dirichlet boundary conditions, we prove that the condition number of the preconditioned system is ofO() orO(m), where is the quotient between the time and space steps andm is the number of interior gridpoints in each direction. The results are extended to parabolic equations. Numerical experiments also indicate that the preconditioned systems exhibit favorable clustering of eigenvalues that leads to a fast convergence rate.     

The NGP-stability of Runge-Kutta methods for systems of neutral delay differential equations

Summary. This paper deals with the stability analysis of implicit Runge-Kutta methods for the numerical solutions of the systems of neutral delay differential equations. We focus on the behavior of such methods with respect to the linear test equations where ,L, M and N are complex matrices. We show that an implicit Runge-Kutta method is NGP-stable if and only if it is A-stable. Received February 10, 1997 / Revised version received January 5, 1998     

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     

Computational methods for delay parabolic and time‐fractional partial differential equations

This article is concerned with ?‐methods for delay parabolic partial differential equations. The methodology is extended to time‐fractional‐order parabolic partial differential equations in the sense of Caputo. The fully implicit scheme preserves delay‐independent asymptotic stability and the solution continuously depends on the time‐fractional order. Several numerical examples of interest are included to demonstrate the effectiveness of the method. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

Time stepping procedures for the non-stationary Stokes equations

We consider first and second-order implicit time stepping procedures for the non-stationary Stokes equations in bounded domains of ?³. Using energy estimates we prove the optimal convergence properties in the Sobolev spaces H^m(G)(m = 0, 1, 2) uniformly in time, provided that the Stokes solution has a certain degree of regularity. Here in the case of the second-order scheme (method of Crank–Nicholson) the Stokes solution has to satisfy a non-local compatibility condition at the initial time t = O, which can be satisfied by a special initial construction.     

Implicitly enriched Galerkin methods for numerical solutions of fourth‐order partial differential equations containing singularities

Highlights are the following:

• For any integer , we construct ‐continuous partition of unity (PU) functions with flat‐top from B‐spline functions to have numerical solutions of fourth‐order equations with singularities. B‐spline functions are modified to satisfy clamped boundary conditions.
• To handle singularity arising in fourth‐order elliptic differential equations, these modified B‐spline functions are enriched either by introducing enrichment basis functions implicitly through particular geometric mappings or by adding singular basis functions explicitly.
• To show the effectiveness of the proposed implicit enrichment methods (mapping method), the accuracy, the number of degrees of freedom (DOF), and matrix condition numbers are computed and compared in the h‐refinement, the p‐refinement, and the k‐refinement of the approximation space of B‐spline basis functions.

Using Partition of unity (PU) functions with flat‐top, B‐spline functions are modified to satisfy boundary conditions of the fourth‐order equations. Since the standard isogeometric analysis (IGA) as well as the conventional FEM have limitations in handling fourth‐order differential equations containing singularities, we consider two enrichment methods (explicit and implicit) in the framework of the p‐, the k, and the h‐refinements of IGA. We demonstrate that both enrichment methods yield good approximate solutions, but explicit enrichment methods give large (almost singular) matrix condition numbers and face integrating singular functions. Because of these limitations of external enrichment methods, we extensively investigate implicit enrichment methods (mapping methods) that virtually convert fourth‐order elliptic problems with singularities to problems with no influence of the singularities. Effectiveness of the proposed mapping method extensively tested to one‐dimensional fourth‐order equation with singularities. The implicit enrichment (mapping) method is extended to the two‐dimensional cases and test it to fourth‐order partial differential equations on cracked domains.     

Growth Behavior of Two Classes of Merit Functions for Symmetric Cone Complementarity Problems

In the solution methods of the symmetric cone complementarity problem (SCCP), the squared norm of a complementarity function serves naturally as a merit function for the problem itself or the equivalent system of equations reformulation. In this paper, we study the growth behavior of two classes of such merit functions, which are induced by the smooth EP complementarity functions and the smooth implicit Lagrangian complementarity function, respectively. We show that, for the linear symmetric cone complementarity problem (SCLCP), both the EP merit functions and the implicit Lagrangian merit function are coercive if the underlying linear transformation has the P-property; for the general SCCP, the EP merit functions are coercive only if the underlying mapping has the uniform Jordan P-property, whereas the coerciveness of the implicit Lagrangian merit function requires an additional condition for the mapping, for example, the Lipschitz continuity or the assumption as in (45). The authors would like to thank the two anonymous referees for their helpful comments which improved the presentation of this paper greatly. The research of J.-S. Chen was partially supported by National Science Council of Taiwan.     

Convergence of euler-stokes splitting of the navier-stokes equations

We consider approximation by partial time steps of a smooth solution of the Navier-Stokes equations in a smooth domain in two or three space dimensions with no-slip boundary condition. For small k > 0, we alternate the solution for time k of the inviscid Euler equations, with tangential boundary condition, and the solution of the linear Stokes equations for time k, with the no-slip condition imposed. We show that this approximation remains bounded in H^2,p and is accurate to order k in L^p for p > ∞. The principal difficulty is that the initial state for each Stokes step has tangential velocity at the boundary generated during the Euler step, and thus does not satisfy the boundary condition for the Stokes step. The validity of such a fractional step method or splitting is an underlying principle for some computational methods. © 1994 John Wiley & Sons, Inc.     

Reducible quadrature methods for Volterra integral equations of the first kind

Quadrature rules, generated by linear multistep methods for ordinary differential equations, are employed to construct a wide class of direct quadrature methods for the numerical solution of first kind Volterra integral equations. Our class covers several methods previously considered in the literature. The methods are convergent provided that both the first and second characteristic polynomial of the linear multistep method satisfy the root condition. Furthermore, the stability behaviour for fixed positive values of the stepsizeh is analyzed, and it turns out that convergence implies (fixedh) stability. The subclass formed by the backward differentiation methods up to order six is discussed and illustrated with numerical examples.     

An optimization approach for the numerical approximation of differential equations

An alternative approach for the numerical approximation of ODEs is presented in this article. It is based on a variational framework recently introduced in S. Amat and P. Pedregal [A variational approach to implicit ODEs and differential inclusions, ESAIM: COCV 15 (2009), 149–172] where the solution is sought as the minimizer of an error functional tailored after the ODE in a rather straightforward way. A suitable discretization of this error functional is pursued, and it is performed using Hermite's interpolation and quadrature formulae. Notice that only Hermite's interpolation is necessary when polynomial systems of ODEs are considered (many models in practice use these types of equations). A comparison with implicit Runge–Kutta methods is analysed. With this variational strategy not only some classical collocation methods, but also new schemes that seem to have better numerical behaviour can be recovered. Although the driving idea is very simple, the strategy turns out to be very general and flexible. At the same time, it can be implemented efficiently.