这是用户在 2024-3-28 11:00 为 https://app.immersivetranslate.com/pdf-pro/ed8ea26c-faf2-48de-bf67-d00d403798c4 保存的双语快照页面,由 沉浸式翻译 提供双语支持。了解如何保存?
2024_03_28_7eed7b69f809da89bcfeg

Implicit-explicit Runge-Kutta methods for time-dependent partial differential equations
时变偏微分方程的隐含-显式 Runge-Kutta 方法

Uri M. Ascher , Steven J. Ruuth , Raymond J. Spiteri a Institute of Applied Mathematics and Department of Computer Science, University of British Columbia, Vancouver, BC,
a 不列颠哥伦比亚大学应用数学研究所和计算机科学系,不列颠哥伦比亚省温哥华市、
Canada V6T  加拿大 V6T Department of Mathematics, University of California, Los Angeles, CA, USA
美国加州大学洛杉矶分校数学系
Institute of Applied Mathematics and Department of Mathematics, University of British Columbia, Vancouver, BC,
不列颠哥伦比亚大学应用数学研究所和数学系,不列颠哥伦比亚省温哥华市、
Canada V6T 1Z2 加拿大 V6T 1Z2

Abstract 摘要

Implicit-explicit (IMEX) linear multistep time-discretization schemes for partial differential equations have proved useful in many applications. However, they tend to have undesirable time-step restrictions when applied to convection-diffusion problems, unless diffusion strongly dominates and an appropriate BDF-based scheme is selected (Ascher et al., 1995).
在许多应用中,偏微分方程的隐式-显式(IMEX)线性多步时间离散化方案已被证明非常有用。然而,当它们应用于对流扩散问题时,往往会有不理想的时间步长限制,除非扩散占主导地位并选择了适当的基于 BDF 的方案(Ascher 等人,1995 年)。

In this paper, we develop Runge-Kutta-based IMEX schemes that have better stability regions than the best known IMEX multistep schemes over a wide parameter range. (c) 1997 Elsevier Science B.V.
在本文中,我们开发了基于 Runge-Kutta 的 IMEX 方案,与已知的最佳 IMEX 多步方案相比,该方案在较宽的参数范围内具有更好的稳定性区域。(c) 1997 Elsevier Science B.V. 版权所有。

1. Introduction 1.导言

When a time-dependent partial differential equation (PDE) involves terms of different types, it is a natural idea to employ different discretizations for them. Implicit-explicit (IMEX) time-discretization schemes are an example of such a strategy. Linear multistep IMEX schemes have been used by many researchers, especially in conjunction with spectral methods . Some schemes of this type were proposed and analyzed as far back as the late 1970s [5,15]. Instances of these methods have been successfully applied to the incompressible Navier-Stokes equations [9] and in environmental modeling studies [16]. A systematic, comparative study for PDEs of convection-diffusion type was carried out in [2], and a corresponding study for reaction-diffusion problems arising in morphology is reported in [11].
当一个与时间相关的偏微分方程(PDE)涉及不同类型的项时,对它们采用不同的离散方法是一个自然的想法。隐式-显式(IMEX)时间离散化方案就是这种策略的一个例子。线性多步 IMEX 方案已被许多研究人员采用,特别是与频谱方法结合使用 。早在 20 世纪 70 年代末,就有人提出并分析了这类方案[5,15]。这些方法已成功应用于不可压缩 Navier-Stokes 方程 [9] 和环境建模研究 [16]。文献[2]对对流-扩散类型的 PDE 进行了系统的比较研究,文献[11]对形态学中出现的反应-扩散问题进行了相应的研究。
In this work, we consider problems of convection-diffusion type (or hyperbolic-parabolic equations), e.g.,
在这项工作中,我们考虑的是对流-扩散型问题(或双曲-抛物方程),例如:
Discretization of the spatial derivatives (e.g., by finite-difference, finite-element, finite-volume, or spectral methods) yields a very large ODE system in time,
空间导数的离散化(如采用有限差分法、有限元法、有限体积法或频谱法)会在时间上产生一个非常大的 ODE 系统、
where corresponds to the convection (hyperbolic) term, , and corresponds to the diffusion (parabolic) term, . An IMEX scheme consists of applying an implicit discretization for and an explicit one for . This is natural because the system (1.2) with is generally stiff and linear, whereas with the system is not too stiff and it is often nonlinear. Moreover, if one insists on using an implicit discretization for the latter case, the construction of iterative solvers is made challenging by the properties of the matrix to be inverted.
其中 对应对流(双曲)项 对应扩散(抛物线)项 。IMEX 方案包括对 采用隐式离散化,对 采用显式离散化。这是很自然的,因为带有 的系统 (1.2) 通常是刚性和线性的,而带有 的系统则不太刚性,通常是非线性的。此外,如果坚持在后一种情况下使用隐式离散化,那么迭代求解器的构造就会因需要反演的矩阵的特性而面临挑战。
In [2] we have analyzed and experimented with linear multistep schemes for (1.2). For diffusiondominated problems, schemes utilizing Backward Differentiation Formulae (BDF) for have optimal damping properties. The corresponding IMEX scheme is a semi-explicit BDF (SBDF) [5,9,15]. However, when diffusion is not dominant, the choice of method is less obvious. Ideally, one would like a dissipative scheme for the hyperbolic term, so that the resulting IMEX scheme would have good stability and smoothing properties, independent of . Yet, it is well known that this necessitates looking for schemes of order (or more accurately, backward steps) at least 3 (cf. [2]). The main difficulty plaguing multistep IMEX schemes is the possibility that relatively small time steps become necessary due to stability restrictions (e.g., [14]). Such restrictions become worse when working with higher-order multistep schemes, as demonstrated in [2]. On the other hand, the stability region of explicit Runge-Kutta schemes actually increases slightly when three- and four-stage schemes are contemplated. Thus, we are led to investigate the development and performance of IMEX Runge-Kutta schemes.
在 [2] 中,我们分析并试验了 (1.2) 的线性多步方案。对于以扩散为主的问题,利用 的后向微分公式(BDF)的方案具有最佳阻尼特性。相应的 IMEX 方案是半显式 BDF(SBDF)[5,9,15]。然而,当扩散不占主导地位时,方法的选择就不那么明显了。理想情况下,我们希望双曲项采用耗散方案,这样得到的 IMEX 方案将具有良好的稳定性和平滑特性,与 无关。然而,众所周知,这就需要寻找阶数(或更准确地说,后退步数)至少为 3 的方案(参见 [2])。困扰多步 IMEX 方案的主要困难是,由于稳定性的限制,可能需要相对较小的时间步长(例如 [14])。正如文献[2]所示,在使用高阶多步方案时,这种限制会变得更加严重。另一方面,当考虑三阶和四阶方案时,显式 Runge-Kutta 方案的稳定区域实际上会略有增加。因此,我们开始研究 IMEX Runge-Kutta 方案的发展和性能。
When the system (1.2) arises from a PDE in more than one spatial variable, the simplicity and efficiency of solving the algebraic equations corresponding to the implicit part of the discretization at each time step is of paramount importance. In [2], we show that, under appropriate circumstances and for certain IMEX schemes, not much more than one multigrid W-cycle per time step is needed. Here, we aim at such a performance per Runge-Kutta stage. Hence, we concentrate on diagonally-implicit Runge-Kutta (DIRK) schemes for , paying particular attention to their attenuation properties. We construct a number of IMEX schemes of this sort, and investigate their properties. Since the effective order of DIRK schemes drops to 1 for very stiff ODEs [8], we do not expect the Runge-Kutta schemes to be competitive with SBDF in the limit where is heavily dominant and very stiff. However, our Runge-Kutta schemes are shown to have excellent properties for other parameter ranges.
当系统 (1.2) 由一个以上空间变量的 PDE 引起时,求解每个时间步离散化的隐含部分对应的代数方程的简便性和效率至关重要。在 [2] 中,我们证明了在适当的情况下,对于某些 IMEX 方案,每个时间步所需的多网格 W 循环不超过一个。在这里,我们的目标是实现每个 Runge-Kutta 阶段的性能。因此,我们专注于 的对角隐式 Runge-Kutta (DIRK) 方案,尤其关注其衰减特性。我们构建了许多此类 IMEX 方案,并研究了它们的特性。由于对于非常僵硬的 ODEs,DIRK 方案的有效阶数降到了 1 [8],因此我们预计在 占主导地位且非常僵硬的极限情况下,Runge-Kutta 方案与 SBDF 相比并不具有竞争力。不过,我们的 Runge-Kutta 方案在其他参数范围内具有出色的特性。
It is well known that, despite its recent rise in popularity, the use of Runge-Kutta schemes for the integration of time-dependent PDEs is not without drawbacks. One problem is a loss of accuracy order when time-dependent inflow boundary conditions are prescribed [4]. A remedy is proposed in [1]. Note also that, in the (usual) case where the accuracy of the solution at the end of the step is higher than at internal stages, the accuracy to which these internal stages must be calculated (say by an iterative method, as in Section 5) cannot be lowered.
众所周知,尽管 Runge-Kutta 方案近来大受欢迎,但使用 Runge-Kutta 方案对依赖时间的 PDEs 进行积分并非没有缺点。其中一个问题是,当规定了随时间变化的流入边界条件时,精确度会下降 [4]。[1]中提出了一种补救方法。还需注意的是,在(通常)步末解的精度高于内部阶段解的情况下,这些内部阶段的计算精度(如第 5 节中的迭代法)不能降低。
The system (1.2) can be cast as a partitioned system,
系统 (1.2) 可以看作一个分区系统、
with and . The IMEX Runge-Kutta schemes devised below are then partitioned Runge-Kutta schemes. Their orders are discussed in [7, Section II.15]. They can also be seen as a particular class of splitting methods. We note that for (1.2), and need not be known individually (indeed we may not have initial conditions for them). All we need to have is their smooth, local existence.
。下面设计的 IMEX Runge-Kutta 方案就是分区 Runge-Kutta 方案。它们的阶次在 [7, 第 II.15 节] 中讨论。它们也可以看作是一类特殊的分割方法。我们注意到,对于 (1.2), 不需要单独知道(事实上,我们可能没有它们的初始条件)。我们只需要知道它们平稳的局部存在。
In Section 2, we develop a number of IMEX Runge-Kutta schemes of up to four stages, which are up to third-order accurate. The schemes divide naturally into two classes-those whose last internal stage is identified with the solution at the next time instance (i.e., at the end of the time step), and those where an additional quadrature is used at the end of the step. The first class is particularly good for highly-stiff problems, but it is the second class which seems to yield some of the more promising variants for a wide range of parameters, particularly the scheme identified as ( 3 internal stages for the implicit formula, 4 stages for the explicit and a combined accuracy of order 3 ).
在第 2 节中,我们开发了多达四级的 IMEX Runge-Kutta 方案,其精度可达三阶。这些方案自然分为两类--一类是最后一个内部级数与下一个时间实例(即时间步结束时)的解相一致,另一类是在步结束时使用额外的正交。第一类方案尤其适用于高刚度问题,但第二类方案似乎能产生一些更有前途的变量,适用于各种参数,尤其是确定为 的方案(隐式为 3 个内部阶段,显式为 4 个阶段,综合精度为 3 阶)。
In Section 3, we investigate the performance of the various schemes for a simple test equation, which arises from a von Neumann analysis of an advection-diffusion equation. Stability regions are plotted in Figs. 1 and 2. Results of test runs for a linear advection-diffusion equation are reported in Section 4.1 and the Burgers equation is experimented with in Section 4.2. In Section 5, we investigate the performance of our various schemes in conjunction with employing a multigrid method for resolving the implicitness at each stage.
在第 3 节中,我们研究了各种方案在一个简单测试方程中的性能,该方程来自对一个平流扩散方程的 von Neumann 分析。稳定区域如图 1 和图 2 所示。第 4.1 节报告了线性平流-扩散方程的测试运行结果,第 4.2 节对布尔格斯方程进行了试验。在第 5 节中,我们将结合使用多网格方法解决每个阶段的隐含性问题,研究各种方案的性能。

2. IMEX Runge-Kutta schemes
第二届 IMEX Runge-Kutta 计划

We now develop some IMEX Runge-Kutta schemes. For , we consider an implicit -stage DIRK scheme [8] with coefficients , in the usual Butcher notation. Let . For , we consider an -stage explicit scheme with the abscissae and coefficients . To cast the DIRK scheme as an -stage scheme as well, we can pad the -stage scheme with zeroes, obtaining the tableau
现在我们开发一些 IMEX Runge-Kutta 方案。对于 ,我们考虑系数为 的隐式 - 阶段 DIRK 方案 [8],采用通常的 Butcher 符号。设 。对于 ,我们考虑一个 级的显式方案,其主轴为 ,系数为 。为了把 "迪尔克 "方案也转换成一个 级方案,我们可以在 级方案中加入零,得到表格
Referring to the coefficients of this padded tableau as , we see that . This property simplifies significantly the form of the order conditions on the method's coefficients due to coupling between the individual schemes.
把这个填充表的系数称为 ,我们可以看到 。由于各个方案之间的耦合,这一特性大大简化了方法系数的阶次条件形式。
Set
One step from to of the IMEX scheme is given as follows:
IMEX 方案从 的一个步骤如下:
For do: 对于 这样做:
  • Solve for : 求出
where 其中
  • Evaluate 评估
Finally, evaluate 最后,评估
We consider two special cases, which lead to two sub-families of methods: those which satisfy (2.2) and those which satisfy (2.3)-(2.4):
我们考虑了两种特殊情况,由此产生了两个方法子系列:满足 (2.2) 的方法和满足 (2.3)-(2.4) 的方法:
(1) In the case that (and in particular ), we have in place of (2.1e)
(1) 在 (尤其是 )的情况下,我们可以用(2.1e)来代替
(2) In the case that need not be evaluated. Furthermore, if
(2) 在 无需求值的情况下。此外,如果
(implying that the implicit scheme is stiffly accurate and ), then substituting (2.1e) into the expression for , we see that
(意味着隐式方案是刚性精确的,且 ),然后将 (2.1e) 代入 的表达式,我们可以看到
This is useful for very stiff problems. We note also that the explicit scheme can now be generated from a general explicit -stage scheme based on the abscissae ,
这对于非常僵硬的问题非常有用。我们还注意到,显式方案现在可以从基于缺省值 的一般显式 级方案生成、
In (2.1b), there are nonlinear systems to solve involving alone, and the operators to be inverted are
在 (2.1b) 中,有 个仅涉及 的非线性系统需要求解,需要反演的算子是
Assuming that the Jacobian is evaluated only once (at ), this operator is the same for each if is independent of , i.e., for SDIRK schemes. However, if an iterative method like 1-cycle multigrid is used for the implicit scheme, then perhaps it is less critical for the overall efficiency to insist on SDIRK, and a more general DIRK scheme can be contemplated. See [8, Section IV.6], for stifflyaccurate SDIRK schemes. In our search for particularly accurate and stable schemes, we have allowed the diagonal elements of to differ from one another. Despite this, the schemes we recommend are all SDIRK, since there were sufficient excess degrees of freedom in the solution process to allow for this computationally-efficient choice.
假设 Jacobian 只求值一次(在 处),那么如果 无关,即对于 SDIRK 方案,该算子对每个 都是相同的。然而,如果隐式方案使用了像 1 周期多网格这样的迭代法,那么坚持使用 SDIRK 也许对整体效率并不那么重要,可以考虑使用更通用的 DIRK 方案。关于刚性精确的 SDIRK 方案,请参见 [8,第 IV.6 节]。在寻找特别精确和稳定的方案时,我们允许 的对角元素彼此不同。尽管如此,我们推荐的方案都是 SDIRK,因为在求解过程中有足够多的自由度,允许这种计算效率高的选择。
Example 1. Consider the case of (1.2) where
例 1.考虑 (1.2) 的情况,其中
Thus, we apply the implicit scheme to advance and the explicit one to advance . Observe that if is influenced by a control function, for instance, then at each stage , this influence is propagated to from . This does not happen when using a "normal" explicit scheme (cf. [13]). Moreover, if is independent of then
因此,我们采用隐式方案推进 ,采用显式方案推进 。请注意,如果 受到控制函数的影响,那么在每个阶段 ,这种影响会从 传播到 。在使用 "正常 "显式方案时,这种情况不会发生(参见 [13])。此外,如果 无关,那么
and the scheme becomes explicit!
,该方案就变得清晰明了!
In particular, for Hamiltonian systems we can set . If is independent of , then we obtain an explicit scheme which still retains some advantages of the implicit one.
特别是,对于哈密顿系统,我们可以设置 。 如果 无关,那么我们得到的显式方案仍然保留了隐式方案的一些优点。
We now proceed to construct some instances of our IMEX RK family of schemes. We will use the triplet to identify a scheme (2.1), where is the number of stages of the implicit scheme, is the number of explicit scheme stages (so for case (1), i.e., (2.2), and for case (2), i.e., (2.3)-(2.4) above), and is the combined order of the scheme.
现在,我们开始构建 IMEX RK 系列方案的一些实例。我们将使用三元组 来标识方案 (2.1),其中 是隐式方案的级数, 是显式方案的级数(因此 表示情况 (1),即 (2.2), 表示情况 (2),即上文 (2.3)-(2.4)), 是方案的组合阶数。

2.1. Forward-backward Euler
2.1.前后欧拉

The pair of backward and forward Euler schemes
一对后向和前向欧拉方案
can be padded to read
可以填充为
This yields the linear one-step IMEX (cf. [2]):
这就产生了线性一步 IMEX(参见 [2]):
Note that this scheme satisfies (2.3).
请注意,该方案符合 (2.3)。

2.2. Forward-backward Euler
2.2.前后欧拉

The above form of Euler's method does not satisfy . The variant that does is
上述形式的欧拉方法不满足 。满足要求的变体是
i.e., , where . This scheme involves an additional evaluation of per step, compared to the previous one.
,其中 。与前一种方案相比,这种方案每一步需要额外评估

2.3. Implicit-explicit midpoint
2.3.隐式-显式中点

The Euler pairs are first-order accurate and the scheme has well-known disadvantages when (cf. Section 3 and [2]). The following pair of implicit-explicit schemes:
欧拉对是一阶精确的,而 方案在 时有众所周知的缺点(参见第 3 节和 [2])。下面是一对隐式-显式方案:
correspond to applying explicit midpoint for and implicit midpoint for . It is second-order accurate because the two schemes from which it is composed are each second-order accurate and [7]. This scheme performs usually comparably to the unreasonably popular CNAB considered in [2], and has better symmetry properties.
它是二阶精确的,因为由它组成的两个方案分别是二阶精确的和 [7]。这种方案的性能通常可与 [2] 中考虑的不合理流行的 CNAB 方案相媲美,并且具有更好的对称性。
Example 2. Applying the scheme to the separable Hamiltonian system
例 2.将 方案应用于可分离的哈密顿系统
and defining 并界定
we obtain 我们得到
We note that this scheme is explicit, and it can also be shown to be symplectic. It is identical to the leap-frog/Verlet scheme [12]
我们注意到这个方案是显式的,也可以证明它是交映的。它与跃迁/韦莱方案[12]相同

2.4. A third-order combination
2.4.三阶组合

The two-stage, third-order DIRK scheme with the best damping properties turns out to be the DIRK scheme [7, p. 207]
具有最佳阻尼特性的两级三阶 DIRK 方案是 DIRK 方案 [7, 第 207 页]。
with . For the test equation , if we let , then as . This is a marked improvement over the midpoint scheme which has no attenuation at the stiffness limit .
。对于测试方程 ,如果我们让 ,则为 。这比中点方案 有了明显的改进,因为中点方案在刚度极限 没有衰减。
The corresponding third-order explicit Runge-Kutta scheme (ERK) is
相应的三阶显式 Runge-Kutta 方案(ERK)为
The resulting IMEX combination is third-order accurate, has some dissipation near the imaginary axis (like all three-stage third-order ERK methods) and has some attenuation of the stability function at .
由此产生的 IMEX 组合具有三阶精度,在虚轴附近有一些耗散(与所有三级三阶 ERK 方法一样),在 处的稳定函数有一些衰减。

2.5. L-stable, two-stage, second-order DIRK
2.5.L 稳定、两阶段、二阶 DIRK

One may be concerned that the attenuation that the above scheme has may not be sufficient for some problems. A two-stage, second-order DIRK scheme which is stiffly accurate is [8, p. 106]
有人可能会担心,上述方案的衰减可能不足以解决某些问题。一个两级二阶 DIRK 方案是刚性精确的 [8,第 106 页]。
where . The corresponding three-stage second-order ERK is
其中