Linearly implicit methods for nonlinear evolution equations

Summary.  We construct and analyze combinations of rational implicit and explicit multistep methods for nonlinear evolution equations and extend thus recent results concerning the discretization of nonlinear parabolic equations. The resulting schemes are linearly implicit and include as particular cases implicit–explicit multistep schemes as well as the combination of implicit Runge–Kutta schemes and extrapolation. We establish optimal order error estimates. The abstract results are applied to a third–order evolution equation arising in the modelling of flow in a fluidized bed. We discretize this equation in space by a Petrov–Galerkin method. The resulting fully discrete schemes require solving some linear systems to advance in time with coefficient matrices the same for all time levels. Received October 22, 2001 / Revised version received April 22, 2002 / Published online December 13, 2002 Mathematics Subject Classification (1991): Primary 65M60, 65M12; Secondary 65L06 Correspondence to: G. Akrivis     

一类反应扩散方程组的隐-显多步有限元方法及其分析

考虑一类非线性反应扩散方程组，提出了隐-显多步有限元格式逼近，证明了格式最优的L^2模误差估计．     

The arbitrary order implicit multistep schemes of exponential fitting and their applications

We develop the arbitrary order implicit multistep schemes of exponential fitting (EF) for systems of ordinary differential equations. We use an explicit EF scheme to predict an approximation, and then use an implicit EF scheme to correct this prediction. This combination is called a predictor–corrector EF method. We demonstrate the accuracy and efficiency of the new predictor–corrector methods via application to a variety of test cases and comparison with other analytical and numerical results. The numerical results show that the schemes are highly accurate and computationally efficient.     

半导体设备热传输中的隐式-显式多步有限元法

考虑热引导半导体设备中的传输行为，用一个有限元法离散电子位势所满足的Rpoisson方程；用隐式－显式多步有限元法处理电子密度和空洞密度满足的两个对流－扩散方程，热传导方程用隐式多步有限元法离散，推导了优化的L^2范误差估计。     

Implicit‐explicit multistep finite element methods for nonlinear convection‐diffusion problems

Implicit‐explicit multistep finite element methods for nonlinear convection‐diffusion equations are presented and analyzed. In space we discretize by finite element methods. The discretization in time is based on linear multistep schemes. The linear part of the equation is discretized implicitly and the nonlinear part of the equation explicitly. The schemes are stable and very efficient. We derive optimal order error estimates. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:93–104, 2001     

Linearly Implicit Finite Element Methods for the Time-Dependent Joule Heating Problem

Completely discrete numerical methods for a nonlinear elliptic-parabolic system, the time-dependent Joule heating problem, are introduced and analyzed. The equations are discretized in space by a standard finite element method, and in time by combinations of rational implicit and explicit multistep schemes. The schemes are linearly implicit in the sense that they require, at each time level, the solution of linear systems of equations. Optimal order error estimates are proved under the assumption of sufficiently regular solutions. AMS subject classification (2000) 65M30, 65M15, 35K60     

Optimal discrete and continuous mono‐implicit Runge–Kutta schemes for BVODEs

Recent investigations of discretization schemes for the efficient numerical solution of boundary value ordinary differential equations (BVODEs) have focused on a subclass of the well‐known implicit Runge–Kutta (RK) schemes, called mono‐implicit RK (MIRK) schemes, which have been employed in two software packages for the numerical solution of BVODEs, called TWPBVP and MIRKDC. The latter package also employs continuous MIRK (CMIRK) schemes to provide C ¹ continuous approximate solutions. The particular schemes implemented in these codes come, in general, from multi‐parameter families and, in some cases, do not represent optimal choices from these families. In this paper, several optimization criteria are identified and applied in the derivation of optimal MIRK and CMIRK schemes for orders 1–6. In some cases the schemes obtained result from the analysis of existent multi‐parameter families; in other cases new families are derived from which specific optimal schemes are then obtained. New MIRK and CMIRK schemes are presented which are superior to those currently available. Numerical examples are provided to demonstrate the practical improvements that can be obtained by employing the optimal schemes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic preserving time‐discretization of optimal control problems for the Goldstein–Taylor model

We consider the development of implicit‐explicit time integration schemes for optimal control problems governed by the Goldstein–Taylor model. In the diffusive scaling, this model is a hyperbolic approximation to the heat equation. We investigate the relation of time integration schemes and the formal Chapman–Enskog‐type limiting procedure. For the class of stiffly accurate implicit–explicit Runge–Kutta methods, the discrete optimality system also provides a stable numerical method for optimal control problems governed by the heat equation. Numerical examples illustrate the expected behavior. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 1770–1784, 2014     

High order accurate semi-implicit WENO schemes for hyperbolic balance laws

In this paper we propose a family of well-balanced semi-implicit numerical schemes for hyperbolic conservation and balance laws. The basic idea of the proposed schemes lies in the combination of the finite volume WENO discretization with Roe’s solver and the strong stability preserving (SSP) time integration methods, which ensure the stability properties of the considered schemes [S. Gottlieb, C.-W. Shu, E. Tadmor, Strong stability-preserving high-order time discretization methods, SIAM Rev. 43 (2001) 89-112]. While standard WENO schemes typically use explicit time integration methods, in this paper we are combining WENO spatial discretization with optimal SSP singly diagonally implicit (SDIRK) methods developed in [L. Ferracina, M.N. Spijker, Strong stability of singly diagonally implicit Runge-Kutta methods, Appl. Numer. Math. 58 (2008) 1675-1686]. In this way the implicit WENO numerical schemes are obtained. In order to reduce the computational effort, the implicit part of the numerical scheme is linearized in time by taking into account the complete WENO reconstruction procedure. With the proposed linearization the new semi-implicit finite volume WENO schemes are designed.A detailed numerical investigation of the proposed numerical schemes is presented in the paper. More precisely, schemes are tested on one-dimensional linear scalar equation and on non-linear conservation law systems. Furthermore, well-balanced semi-implicit WENO schemes for balance laws with geometrical source terms are defined. Such schemes are then applied to the open channel flow equations. We prove that the defined numerical schemes maintain steady state solution of still water. The application of the new schemes to different open channel flow examples is shown.     

Stability of Partially Implicit Langevin Schemes and Their MCMC Variants

A broad class of implicit or partially implicit time discretizations for the Langevin diffusion are considered and used as proposals for the Metropolis–Hastings algorithm. Ergodic properties of our proposed schemes are studied. We show that introducing implicitness in the discretization leads to a process that often inherits the convergence rate of the continuous time process. These contrast with the behavior of the naive or Euler–Maruyama discretization, which can behave badly even in simple cases. We also show that our proposed chains, when used as proposals for the Metropolis–Hastings algorithm, preserve geometric ergodicity of their implicit Langevin schemes and thus behave better than the local linearization of the Langevin diffusion. We illustrate the behavior of our proposed schemes with examples. Our results are described in detail in one dimension only, although extensions to higher dimensions are also described and illustrated.     

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.     

Stability of Richtmyer Type Difference Schemes in any Finite Number of Space Variables and Their Comparison with Multistep Strang Schemes

The stability of generalized Richtmyer two step difference schemesin any finite number of space variables is examined and a sufficientstability condition obtained for each scheme. In certain casesthis condition is shown to be optimal C.F.L. The efficiencyof these schemes in solving time dependent problems in two andthree space variables is examined and the schemes are seen tocompare favourably with the corresponding multistep forms ofStrang's schemes.     

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.     

Finite Element Methods for Parabolic Stochastic PDE’s

We study the rate of convergence of some explicit and implicit numerical schemes for the solution of a parabolic stochastic partial differential equation driven by white noise. These include the forward and backward Euler and the Crank–Nicholson schemes. We use the finite element method. We find, as expected, that the rates of convergence are substantially similar to those found for finite difference schemes, at least when the size of the time step k is on the order of the square of the size of the space step h: all the schemes considered converge at a rate on the order of h^1/2+k^1/4, which is known to be optimal. We also consider cases where k is much greater than h², and find that only the backward Euler method always attains the optimal rate; other schemes, even though they are stable, can fail to convergence to the true solution if the time step is too long relative to the space step. The Crank–Nicholson scheme behaves particularly badly in this case, even though it is a higher-order method. Mathematics Subject Classifications (2000) 60H15, 60H35, 65N30, 35R60.     

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

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

Stability and accuracy of time discretizations for initial value problems

Summary This paper continues earlier work by the same authors concerning the shape and size of the stability regions of general linear discretization methods for initial value problems. Here the treatment is extended to cover also implicit schemes, and by placing the accuracy of the schemes into a more central position in the discussion general method-free statements are again obtained. More specialized results are additionally given for linear multistep methods and for the Taylor series method.This research has been supported by Swiss National Foundation, Grant No. 82-524.077This research has been supported by the Heinrich-Hertz-Stiftung, B 32 No. 203/79     

A unified discontinuous Galerkin framework for time integration

We introduce a new discontinuous Galerkin approach for time integration. On the basis of the method of weighted residual, numerical quadratures are employed in the finite element time discretization to account for general nonlinear ordinary differential equations. Many different conditions, including explicit, implicit, and symplectic conditions, are enforced for the test functions in the variational analysis to obtain desirable features of the resulting time‐stepping scheme. The proposed discontinuous Galerkin approach provides a unified framework to derive various time‐stepping schemes, such as low‐order one‐step methods, Runge–Kutta methods, and multistep methods. On the basis of the proposed framework, several explicit Runge–Kutta methods of different orders are constructed. The derivation of symplectic Runge–Kutta methods has also been realized. The proposed framework allows the optimization of new schemes in terms of several characteristics, such as accuracy, sparseness, and stability. The accuracy optimization is performed on the basis of an analytical form of the error estimation function for a linear test initial value problem. Schemes with higher formal order of accuracy are found to provide more accurate solutions. We have also explored the optimization potential of sparseness, which is related to the general compressive sensing in signal/imaging processing. Two critical dimensions of the stability region, that is, maximal intervals along the imaginary and negative real axes, are employed as the criteria for stability optimization. This gives the largest Courant–Friedrichs–Lewy time steps in solving hyperbolic and parabolic partial differential equations, respectively. Numerical experiments are conducted to validate the optimized time‐stepping schemes. Copyright © 2013 John Wiley & Sons, Ltd.     

Understanding Saul'yev‐type unconditionally stable schemes from exponential splitting

Saul'yev‐type asymmetric schemes have been widely used in solving diffusion and advection equations. In this work, we show that Saul'yev‐type schemes can be derived from the exponential splitting of the semidiscretized equation which fundamentally explains their unconditional stability. Furthermore, we show that optimal schemes are obtained by forcing each scheme's amplification factor to match that of the exact amplification factor. A new second‐order explicit scheme is found for solving the advection equation with the identical amplification factor as the implicit Crank–Nicolson algorithm. Other new schemes for solving the advection–diffusion equation are also derived.© 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 1961–1983, 2014     

求解非线性刚性初值问题的隐显线性多步方法的误差分析

隐显线性多步方法由隐式线性多步方法和显式线性多步法组合而成.本文主要讨论求解满足单边Lipschitz条件的非线性刚性初值问题和一类奇异摄动初值问题的隐显线性多步方法的误差分析.最后,由数值例子验证了所获的理论结果的正确性及方法处理这两类问题的有效性.     

General Full Implicit Strong Taylor Approximations for Stiff Stochastic Differential Equations

In this paper, we present the backward stochastic Taylor expansions for a Ito process, including backward Ito-Taylor expansions and backward Stratonovich-Taylor expansions. We construct the general full implicit strong Taylor approximations (including Ito-Taylor and Stratonovich-Taylor schemes) with implicitness in both the deterministic and the stochastic terms for the stiff stochastic differential equations (SSDE) by employing truncations of backward stochastic Taylor expansions. We demonstrate that these schemes will converge strongly with corresponding order $1,2,3,\ldots$ Mean-square stability has been investigated for full implicit strong Stratonovich-Taylor scheme with order $2$, and it has larger mean-square stability region than the explicit and the semi-implicit strong Stratonovich-Taylor schemes with order $2$. We can improve the stability of simulations considerably without too much additional computational effort by using our full implicit schemes. The full implicit strong Taylor schemes allow a larger range of time step sizes than other schemes and are suitable for SSDE with stiffness on both the drift and the diffusion terms. Our numerical experiment shows these points.