区域理论二阶Euler方法的可靠性、完备性和代数复杂性

可在www.sciencedirect.com在线获取理论计算机科学电子笔记352（2020）105-128www.elsevier.com/locate/entcs求解初值问题的区域理论二阶EulerAbbas Edalata，1 Amin Farjudianb，2 Mina Mohammadianc，3 Dirk Pattinsond，4帝国理工学院计算机英国伦敦b宁波诺丁汉大学计算机科学学院大不里士大学数学科学伊朗大不里士澳大利亚国立大学计算机科学学院澳大利亚堪培拉摘要给出了一种求解初值问题的区域理论方法，并证明了该方法的可靠性、完备性和代数复杂性。虽然常见的固定精度区间算术方法受到底层机器架构精度的限制，但域理论方法可能是完整的，即。例如，可以获得任何精确度的结果。此外，不像基于区间算术的方法需要访问向量场的语法表示，域理论方法只处理场的语义，在这个意义上，场被假设为通过有限可表示的近似给出，在任何要求的精度内。与区域理论的一阶欧拉方法不同，二阶方法使用了场的局部Lips- chitz性质。这是通过使用Lipschitz函数的域来实现的，其元素是提供场及其局部Lipschitz性质的近似的一致对。 特别如果场是可微分的，则局部Lipschitz性质恰好是局部可微分性质。场的关系。在求解IVP时，场的Lipschitz连续性是一个常见的假设，作为解的唯一性的充分条件。虽然用于求解IVP的验证方法通常对向量场施加进一步的限制，但二阶欧拉方法不需要进一步的条件。在这个意义上，该方法可以被视为同类方法中最通用的为了避免复杂的符号和冗长的论证，本文的结果是针对二阶欧拉方法的。尽管如此，框架和结果，可以扩展到任何高阶欧拉方法，在一个简单的方式。关键词：区域理论，Lipschitz函数域，初值问题，代数复杂性，区间算术。https://doi.org/10.1016/j.entcs.2020.09.0061571-0661/© 2020作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。106A. Edalat等人/理论计算机科学电子笔记352（2020）105⎪MM1介绍我们考虑常微分方程（ODE）初值问题（IVP）：⎧⎪⎨⎩yJ=f（y），y（0）=（0，...，（0）、（1）阿肯·阿肯克斯其中f：[−K，K]n→[−M，M]n是一个连续向量场，对某个自然数n≥1，且正有理数K，M∈Q+.从现在开始，我们称f为“场”。根据皮亚诺定理，场f的纯粹连续性保证了可微分解y的存在性：[ − K，K ] → [− K，K ] n（参见e.例如，在一个实施例中，[29]一个证明。它也是众所周知的，通过进一步假设f是Lipschitz连续的，可以保证解的唯一性。有很多已建立的方法和算法来解决类型（1）[19]的问题。这些通常使用实数的浮点近似来实现。这些实现具有固有的不准确性，主要是由于舍入和截断误差，当小错误不会产生重大成本时，这是可以容忍的。在有限的情况下，可以通过误差分析[17]一个更一般的替代方法是通过验证的数字，其中的结果是绝对保证正确性。区间算术为许多可用的有效数字提供了基础[25]。对于问题（1），已有许多有效的基于区间的数值方法，包括有效的高阶Taylor基方法，如：例如，在一个实施例中，[2、27、30]。事实上，众所周知，通过假设场f是解析的，可以通过使用泰勒模型在多项式时间内获得IVP（1）的解[26]，这与没有解析性假设的IVP求解的PSPACE完全性相反[20]。虽然上述方法是有效的，但它们并没有明确地基于由域和连续格提供的区间算术的指称语义[1，16]。通过结合序理论和拓扑学的强大工具，域理论为验证数字提供了丰富的语义模型在域理论框架中开发离散方程求解器的另一个优点是，它们可以随后被纳入其他重要应用的域理论模型中，例如混合系统的可达性分析[11，22，23]。与使用泰勒系数相反，在域理论方法中，实际上，已经为（一阶）欧拉方法[ 10 ]和皮卡德方法[ 12 ]引入了求解问题（1）的在经典数值分析中，（一阶向前）欧拉方法1电子邮件：A. ic.ac.uk2电子邮件：Amin. nottingham.edu.cn3电子邮件：Mina. anu.edu.au4电子邮件：Dirk. anu.edu.auA. Edalat等人/理论计算机科学电子笔记352（2020）105107·IVP的解通过迭代yn+1（x）=xf（yn0可以说是IVP数值解的最基本方案。欧拉方法是基于一个非常简单的几何直观，其中的解决方案是通过采取小的步骤（比如）h>0，并近似y（t+h）y（t）+hf（y（t））。另一方面，Picard方法是基于众所周知的Picard-Lindelüof定理[29，定理2.2]，其中通过成功近似{yn|n∈N}的注1.1解IVP的数值格式称为n阶格式，如果当IVP的解是至多n次的多项式时，则该解可以通过该格式精确地得到[19，第8页]。5在[15]中进一步研究了使用任意精度浮点数实现Picard尽管如此，Picard这是因为，在一阶Eu- ler方法[10]中，为了保证解的唯一性，需要场的Lipschitz连续性在本文中，我们提出了一个区域理论的二阶欧拉方法，它利用了该领域的局部Lipschitz性质。通过使用区域理论，我们能够保持完全的一般性，在这个意义上，虽然假设场f是Lipschitz连续的，但不需要进一步的限制注1.2 [自主与非自主IVP]在本文中，我们只考虑形式（1）的IVP，即：例如，自主的IVP。通过添加额外变量将非自主IVP转换为自主IVP是众所周知的技术。例如，给定非自治方程YI（t）= f（y（t），t），其中y（t）=（yi（t），.，y n（t）），定义为z（t）=（y（t），t）的函数满足自治方程zJ（t）=g（z（t）），其中g（θ1，.，θ n+1）=（f（θ1，.，θ n+1），1）. 众所周知，非自治IVP的解的唯一性是保证的，如果场f在它的前n个（n+1个中）变元上是Lipschitz连续的.为 了 确保自治IVP（1）的解的唯一性，我们假设场在其所有参数上都是Lipschitz连续的。因此，我们失去了一点普遍性。本文的结果可以直接推广到任何n阶Euler方法的类似分析。这一推广所需的主要结果是泰勒定理的一个变体，如Corol- lary 2.14所示。我们在这里只介绍二阶方法，因为符号（主要是索引）可以写得没有太多混乱。然而，给出一般n阶欧拉方法的结果需要处理多维矩阵的复杂符号，这只会模糊主要思想。[5]换句话说，如果对于每个步长h，所引起的局部误差为O（hn+1）阶，则称数值格式为n阶。108A. Edalat等人/理论计算机科学电子笔记352（2020）105i=1⊥..m（Q）一还应该指出，虽然我们已经将（1）中的初始值取为全零，但推广到形式y（t0）=（q1，...，q n），其中t0，q1，.，q n∈ Q，是简单的。一些初始值是无理点或非退化区间的情况需要进一步考虑，这不是当前工作的重点我们研究了二阶方法的代数复杂性和收敛性.这反过来又为更详细的位复杂性铺平了道路，类似于[15]。2符号和标记我们假设读者熟悉Domain理论[1，16]中的基本概念和常用符号，包括区间Domain[5，14]。设I[−K，K]n表示n维非空紧的ω-连续有界完备域hyper-rectanglesn[ai，bi]i n[−K，K]n，通过逆包含排序，i. 例如，A±BBA. 我们以类似的方式定义没有底元素的IRn通过增加Rn作为底元，我们得到整环IRn对任意x∈Rn，单点{x}是IRn的极大元= IRn<${Rn}。- 是的 哪里有为了简单起见，我们可以写x而不是{x}。 对于任意子集X，偏序集D，我们写X和X分别表示X的最小上界和最大下界，假设它们存在。在下面的例子中，我们假设a∈Q。虽然对于许多结果来说，该假设不是必需的，但它使材料的呈现更简单：定义2.1 [划分][0，a]的划分是有限序列（q0，.，q k）的实数，使得0=q0<···0：<$x∈[−K，K]n： [−MJ， MJ]n2±L<$（f）（x）.（三）定义3.3[V1]我们将域V1定义为下式的子域：V·=（I[−K，K]n<$I[−M，M]n）×。I[−K，K]n<$I[−MJ，MJ]n2<$，由相容对（u，uJ）∈ V<$组成。一个对（u，uJ）称为相容的i <$存在一个h：[−K，K]n→[−M，M]n满足u±Ih和uJ±IL<$（h）。注3.4给定一对（u，uJ）n，仅假设u和uJ是经典向量场g及其L-导数gJ的扩张，我们就可自由地获得相容性. 尽管如此，当处理不精确的输入数据时，没有控制，这种一致性可能会被违反。因此，我们需要一种有效的方法来检验给定对（u，UJ）∈ V∈的相容性.幸运的是，域V1确实可以配备有效的结构[8].我们还需要对区域理论的局部Lipschitz常数进行估计，一个给定领域的扩展。 对于任何区间矩阵A=[aij，aij]m×n，范数A∞定义为：A|ai，j|、|国际新闻报|，。1≤i≤mj=1假设2在接下来的文章中，我们假设u和uJ分别是场f及其L-导数L_（f）的区间扩张，并且满足以下附加条件：A. Edalat等人/理论计算机科学电子笔记352（2020）105117nQI条件：<$x ∈ I[−K，K] n：w（u（x））≤ <$uJ（x）<$∞w（x）.（四）引理3.5给定一个Lipschitz向量场f：[−K，K] n→[−M，M] n，令L·=supx∈[−K，K]n<$L<$（f）（x）<$∞。 证明了n，f在[-K，K]n，i中是L-Lipschitz连续的. e.第一步：<$x，y ∈ [−K，K]：<$f（x）− f（y）<$∞≤ L<$x − y <$∞.证据引理由L -导数的中值定理[8，定理5.4]得出，并且L-导数近似于L-导数的事实。Q推论3.6假设u：I[−K，K]n→I[−M，M]n和uJ：I[−K，K]n→I[−M J，M J] n2 是经典向量场f的正则扩展：[−K，K] n→[−M，M] n且满足条件（4）.L-导数L（f），具体而言。然后，u和uJ总之，条件（4）确保u的成对导数uJ的（矩阵）范数充当局部区间Lipschitz常数。如推论3.6所示，这个条件对于向量场的正则扩张和它的L-可导性是满足的。接下来，我们介绍本文的主要操作符定义3.7[二阶欧拉算子：E2]设a∈（0，K′]. 二阶Euler算子E2：P1×V1→[0，a]→M（1+nM）I[−K，K] n的定义如下：对于给定的划分Q（q0，.，[0，a]的q k）满足|Q| ≤ 1，且给定对（u，uJ）∈V1：y（x）·=.（0， . ，0），如果x=0，·y（qi）+xu（y（qi））+（t-qi）（uJ·u）（y（qi）<$Δqi M）dt，如果qi x≤qi+1，其中：• 第二次世界大战′（Q）;（五）（u，u）• Δqi· =qi+1−qi;• （UJ·u）（·）表示内向量矩阵UJ（·）与内向量向量的乘积u（·）。注3.8定义3.1中的一阶算子提供了解的分段二次包络，而定义3.7中的算子提供了解的分段二次包络。实际上，在特殊情况下，如果解是（最多）2次多项式，那么通过应用定义3.7的算子，可以得到精确解。例如，设y=（y1，y2），考虑相当简单的IVP：118A. Edalat等人/理论计算机科学电子笔记352（2020）105y1J（t）⎣y2J(t)⎦ ⎣1⎦ ⎣y2(0)⎦ ⎣0⎦A. Edalat等人/理论计算机科学电子笔记352（2020）1051192⎣00⎦|≤| ≤M +|Q|NMMdt= M（1 +|Q|nM）（xX其中α，β∈R.方程（6）的唯一解由y1（t）=αt2+βt给出，y2（t）=t.这是不难验证，通过采取扩展：u（ρ，θ）=α2αθ+β2α，uJ（ρ，θ）=α0 2αθ，（5）的算子产生（6）的精确二次解。这与注释1.1一起，证明了使用术语与定义3.1中的一阶算子不同，它只使用了场的一个延拓u，而二阶算子也使用了场的L-导数的一个延拓UJ。我们需要证明E2是定义明确的：引理3.9假设Q=（q0， . ，qk）∈P1，且ndletyj=[yj，yj]·=E2′（Q）j（u，u）对于E2′（Q）的第j个分量，对任意j∈{1， … ，n}。然后，bthyj和yj（u，u）是Lipschitz连续的，具有Lipschitz常数：Λ Q·= M（1 + |Q|nM J）。特别是<$x∈[0，a]： E（u，u′）（Q）（x）∈I[−K，K].（七）是的。 我们给出了y_j的引理。对于yj的概率几乎是相同的。因此，我们的目的是表明：nx，xJ∈[0，a]：|yj（xJ）−yj（x）| ≤ΛQ|xJ−x|.（八）实际上，对于qi≤x≤xJ≤qi+1的特殊情况，对于某个0≤i≤k− 1，证明了（8）。关于（5），请注意：• 向量u和矩阵uJ中的区间项由M和MJ界定，分别当uJ是n×n矩阵，u是n×1向量时，向量uJ·u的每个区间分量都有nMMJ的界.• t ∈ [q i，q i+1]：t − q i≤|Q|.因此，我们得到：j x′。JσJJ证明（8）。将证明扩展到所有对x，xJ∈[0，a]是直接的。最后，权利要求（7）也由a ≤K′的假设得出 和|Q| ≤ 1。M（1+nM）因此，证明是完整的。Q推论3.10 E2′（Q）∈ [0，a]<$I[−K，K] n，i.例如， E2（Q）是欧几里得的，（u，u）1n-X），120A. Edalat等人/理论计算机科学电子笔记352（2020）105斯科特连续。（u，u）A. Edalat等人/理论计算机科学电子笔记352（2020）1051212∈∫∫我qi）z（qi）+2（x我我我我1我−是的。 通过引理3.9，对于achj∈{1， . ，n}，yj是低半连续的，并且yj是上连续的，因为它们都是连续的。因此，E2′（Q）是（u，u）欧几里得-斯科特连续Q命题3.11（合理性）假设z：[0，a] → [−K，K] n是（1）的经典解。然后又道：<$x∈[0，a]： E（u，u′）（Q）（x）±z（x）.证据 假设Q=（q0，.，qk）∈P1，设y ∈ E2′（Q）. 通过感应（u，u）关于i，我们表明：i∈ {0，.， k}：yT [0，qi] ± zT [0，qi]。i = 0的基本情况是立即的。 对于归纳步骤，令x（qi，qi+1]。为z是（1）的解，满足zJ=f（z）。根据推论2.14，我们有：z（q） +（x-j-q）2IL<$（zJ）（[q，x]）±z（x）.（九）很抱歉， 根据[9]的链式法则，引理3.3]， wehav e（IL（f）·If）（Iz（[qi，x]））±IL<$（zJ）（[qi，x]）. 因此，从（9）我们推导出：z（q）+（x−-q）2（IL（f）·If）（Iz（[q，x]））±z（x）.（十）此外如|zJ|是有界的M，由中值定理，我们有：z（θ）∈Iz（qi）<$（x−qi）M<$y（qi）<$Δqi M，对于任何θ∈[qi，x]。由此可见：y（q i）<$Δ q i M± Iz（[q i，x]）.（十一）因此，我们可以这样写：Xy（x）=y（qi）+QIu（y（qi））+（t-qi）（uJ·u）（y（qi）<$Δqi M）dt（归纳假设和（11））±z（qi）+Xu（z（qi））+（tqi）（uJQI·u）（Iz（[qi，x]））dtqi）f（z（qi））+21122A. Edalat等人/理论计算机科学电子笔记352（2020）105--1.f和L<$（f）<$的u和UJ域扩张±z（qi）+Xf（z（qi））+（tqi）（IL<$（f）If）（Iz（[qi，x]））dtQI=z（q）+（x−-q）2（IL（f）·If）（Iz（[q，x]））我(by（10））±z（x）。qi）f（z（qi））+2（xiiQ∫A. Edalat等人/理论计算机科学电子笔记352（2020）105123·∫∫.wE′−4收敛性分析在本节中，将建立二阶方法的完备性换句话说，我们将证明，IVP（1）的解可以近似到任何所需的精度。自然地，为了获得更高的结果精度，二阶算子需要更精细地近似场f及其导数L（f），以及更精细地划分中间值[0，a]。首先，在4.1小节中，我们给出了对（f，L_j （f））的内值扩张（u，u_j）的收敛性结果。 从图灵可计算性角度（e.例如，在一个实施例中，在第二类电性理论（TTE）的框架内[31]）这个假设是不现实的，因为f（f，L（f））的所有内部扩展，如定义2.6中所定义的，不需要是有限可表示的。因此，在4.2小节中，我们将给出场及其导数的近似而非扩张的收敛结果注4.1注意，我们假设MJ>0，如（3）中所介绍的这将帮助我们避免在本节的一些分析中被零除只有当向量场f为常数时，才会出现MJ= 0的情况，在这种情况下，IVP（1）可以使用符号计算来简单地求解。4.1向量场回想一下，假设（u，uJ）∈V1 是f（f，L∈ （f））的域扩张，满足假设（4）：命题4.2假设Q=（q0，.，q k）是[0，a]的一个划分，令L =nM J. 然后又道：.2英里 。2Σ|2 LM|2LM<$x∈[qi，qi+1]：wE（u，u′）（Q）（x） ≤wE（u，u′）（Q）（qi）证据 设y∈2′（Q）. 我们有：（1个以上|Q|L）+2。（u，u）w（y（x））≤w（y（qi））+Xw（u（y（qi）+wQI. （t-qi）（uJ·u）（y（qi）<$Δqi M）σdt（假设（4））≤w（y（qi））+XuJ（y（qi））<$∞w（y（qi））dt+QI|2LM|2LMX（t qi）LMdtQI≤w（y（q i））（1 + |Q|L） +2。Q推论4.3（收敛速度）对于任何划分Q∈ P1，我们有：2（u，u）（Q）∫124A. Edalat等人/理论计算机科学电子笔记352（2020）105.σarLQ1≤2 |Q|M e−1。（十二）