无界向量场的区域理论解方法及其在初值问题中的应用

理论计算机科学电子笔记155（2006）565-581www.elsevier.com/locate/entcs无界向量场初值问题的区域理论解Abbas Edalat，Dirk Pattinson1英国伦敦帝国理工学院计算机系摘要本文将文献[11]中所描述的求解初值问题的区域理论方法推广到无界向量场。 基于向量场的一系列近似，我们构造了两个分段线性函数序列，它们从上到下以指数方式快速收敛到初值问题的经典解。然后，我们将展示如何构造向量场的近似。首先，我们表明，快速收敛的组合下的近似，如果近似函数满足一个额外的属性，我们称之为“豪斯多尔Lipschitz从下面”。 特别是，这使我们不必再处理经典函数的极大扩展。在第二步中，我们将展示如何从给定的可计算向量场构造满足此条件的近似。关键词：常微分方程，区域理论，精确计算1引言我们考虑以下形式的初值问题（IVP）：ystec =v（y），y（0）= 0（1）其中v：Rn→Rn是一个Lipschitz向量场，我们寻找定义在区间[0，a]上的解y：[0，a]→Rn，其中a≥ 0是任意的，满足（1）。与标准数值方法不同，标准数值方法不保证计算解的正确性（参见例如，[14]我感兴趣1 电子邮件：{ae，dpattin} @ doc.ic.ac.uk1571-0661 © 2006由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2005.11.073566A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）565MK在满足以下两个性质的精确解中：（i）保证解在某个给定的误差容限内是正确的，以及（ii）该误差容限可以任意小。区间分析[19，18，15，17]提供了一种计算解的保证包围的方法，通过区间表示实数，如果算术运算的结果不能用机器表示，则应用向外舍入。由于在该技术的实现中使用了浮点运算，因此无法控制向外舍入，因此无法保证收敛速度。从更理论的角度来看，初值问题已经在可计算分析的各种背景下进行了研究[16，20，1，3]。虽然这些研究的计算模式基本上与我们的[21]相同，但我们的方法的主要优点是可以在数字计算机上无缝实现所获得的算法这是通过使用域理论[2，13]，它给出了适当的数据类型，基于有理数或二进数，以计算解决方案达到任意精度。特别是，使用有理数（或二进数）确保在计算过程中不会产生舍入误差以前关于初值问题的区域理论解的工作[5，11，10，7]针对的是类型（1）的方程，其中v：[−K，K]n→[−M，M]n是定义在原点的紧凑矩形邻域中的向量场在实践中，人们经常遇到这样的情况，其中v：Rn→Rn定义在整个n维欧几里得空间上，这使得定义在某个超矩形[−K，K]n 上的v的限制变得极其严格：为了使方程定义良好，必须施加限制aM≤K，这对任何解的生存期a这是因为，对于IVP的解z：[0，a]→Rn，（1），我们有zstec =v（z）≤M，即M是z的导数上的一个界.当z（0）= 0时，我们只能保证z（t）≤M t，这会产生限制a≤K对于所有t∈[0，a]，表达式v（z（t））都是定义良好的。下一个例子说明了这种情况。例1.1考虑初始条件y（0）= 0的IVPy stec =y这个问题有解y（t）=et− 1，它定义在整条实数直线上。然而，对于[11，10]中解的构造至关重要的要求aM ≤ K迫使我们考虑向量场为v型：[−K，K] →[−（K+1），K+1]（即M=K+1），随后a≤K+1，这将构造解的定义域限制在长度≤ 1的区间内。A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）565567IVP解的整体存在性特别重要的一种情况是线性边值问题，即以下形式的微分方程：ystec =Ay+g ，边界条件涉及y（a）和y（b）其中A是一个（可能依赖于时间）n×n-矩阵。显然，我们需要在这种情况下至少在区间[a，b]中构造解本文的第一个贡献是描述了如何构造定义在整个欧氏空间上的向量场v：Rn→Rn的IVP的域理论解，并得到定义在任意长区间[0，a]。虽然这是一个重要的步骤，使精确的域理论技术适用于实际问题，另一方面需要解决。只有当我们有向量场v的扩张u的域理论近似uk：IRn→IRn时，域理论机器才能工作。本文的第二个主要贡献是构建这些近似值来自给定的可计算Lipschitz函数。为了获得一个快速收敛的近似库，我们需要保证近似组合的收敛速度。我们通过一个例子表明，快速收敛一般不保存的组合，然后引入一个新的概念，我们建议称之为“豪斯多尔Lipschitz从下面”，确保保存快速收敛。特别是，满足这一要求的函数在复合下是封闭的，这使我们不必处理经典函数的最大扩展这补充了Krznaric即将发表的博士论文的方法总的来说，这两个贡献代表了在实践中使用域理论解决IVP的本文件是一系列文件，开发一个域理论框架的数学分析。以前的工作研究了一个域的可微分和局部Lipschitz函数的一个变量[7，8]。这种方法已被扩展到多变量的情况[9]，逆和隐函数定理作为第一个应用[12]。在微分方程的上下文中，单变量可微分函数的域已被用作求解由时间相关标量场定义的IVP的基础[6]。 这种技术随后被简化并扩展到多变量函数[11，10]。本文改进了这一推广，去掉了向量场定义在原点的紧邻域上的条件，并给出了一个明确的区域理论的构造。568A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）5652向量场的近似。2符号和标记我们使用域理论的基本概念，参见例如[2]或[13]。我们的工作是基于区间域IR ={[a，a] |a≤ a，a，a∈ R}<${R}，按逆包含排序，即α±β i <$β<$α。对于包含在[a，b]中的紧区间的子域，我们写I[和IRn（resp.I[a，b]n）对于IR（resp.（a，b）本身。符号表示IRn的最小元素。为了方便起见，我们用区间[x，x]来标识实数x∈R，对于实向量，即Rn的元素，也是类似的。特别地，这允许我们将类型X→Rn的向量值函数视为在IRn中取值。紧区间[a，b]的宽度为w（[a，b]）= b − a，其中间点为m（[a，b]）=a+b。 Weputtw（ω） =∞. F〇rα=（α1， . . ，αn）∈IRn我们令w（α）= max{w（α i）|1 ≤i≤n}和m（α）=（m（α1），.，m（αn））。 如果X是一个集合，f：X→IRn是一个函数，则f的宽度为w（f）=supx∈Xw（f（x））。 我们说一个函数f：IRn→ IRn是区间Lipschitz，如果它只线性地增加它的辐角的宽度，即。 如果对所有x ∈IRn且某些L ≥ 0，w（f（x））≤ L·w（x）.给定两个区间α =[a，a]和β =[b，b] ∈ IR，它们的Hausdor距离为d（α，β）= max{|a−b|、|a−b|}.类似地，对于α=（α1，.，α n）和β =（β1，.，β n）∈IRn，设d（α，β）= max{d（α i，β i）|1 ≤i≤n}，并定义两个函数f，g：X→IRn的距离为d（f，g）= sup{d（f（x），g（x））|x∈X}。在整个论文中，·表示最大范数（x1，.，x n）n = max {|X i||1 ≤i≤n}的实向量（x1，...，xn）∈Rn.我们注意到以下有关宽度和距离的基本引理。引理2.1设α，β∈IRn是紧矩形.(i)<$m（α）−m（β）<$≤d（α，β）(ii) w（α）−w（β）≤ 2 d（α，β）如果α± β.如果A∈IRn且f：A→Rm是一个函数，则函数g：IA→IRm扩张f，如果{f（x）}=g（{x}），或者，使用上面的约定，如果f（x）=g（x）对所有x∈A。对于连续函数f：A→Rm的极大扩张，我们记为If：IA→IRm。给定一个函数f：X→IR，我们写f=[f，f]，如果f（x）=[f（x），f（x）]，所有x∈X。 如果f=[f，f]：[a，b]→IR是Scott连续的，且a≤s≤t≤b，我们不，不，不让sf（x）dx =[s f（x）dx，s f（x）dx]. 注意f =[f，f]的Scott连续性A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）5655692L我这意味着f（resp. （f）较低（分别为 上）半连续，因此阿勒特勒贝格积分sf（x）dx在IR中总是存在的。 集成理解对于函数f：[a，b] →IRn的分量态。最后，区间[a，b]的划分是序列Q =（q0，.，q k）s.t.a = q0<···0。使用有界性假设在u上，可以证明最小定点的宽度为0，并且是IVP。下一个例子表明，在没有关于v的有界性假设的情况下，这是失败的，并且通常将未定义的函数作为最小定点。例4.3假设v：R→R是恒等函数v（x）=x，其中正则扩张u（α）=α，α∈IR。则函数y = λx。是Pu的最小固定点：阿勒特Pu（y）（t）=0u（y（x））dx=特鲁姆特u（x）dx=0 0dx=注意，相应的IVPy stec =v（y），y（0）= 0具有唯一解y（t）= 0。这表明需要更复杂的技术。我们现在证明，在前一节中介绍的先验界允许我们在函数空间[0，a]的子域中构造IVP（1）的解。定义4.4假设Q=（q0，.，q k）是[0，a]的一个分区，|Q|<1，取先验界Ki和全局界KQ，如定义3.1所示。我们SQ={f：[0，a] → I[−K Q，K Q] n|f T [0，q i）± λt. [−Ki，Ki]for all1≤i≤k}写yQ对于S Q的最小元素。我们称SQ为解空间如果分区是空的，则删除子/上标Q从上下文来看。图形上，集合SQ是其区间值由双阶梯限定的函数集合，如图1所示。使用引理3.4，我们现在可以证明Picard算子将SQ映射到SQ。引理4.5设Q∈ P[0，a]，|Q| 1<.一、 则Pu（y）∈ SQ，如果y∈ SQ.为了证明PuTSQ的最小定点实际上产生IVP（1）的解，我们必须确保Pu是收缩的。最简单的572A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）5652LαK3K2K1Q1Q2Q3图1. Q =（q0，q1，q2，q3）的集合S Q看到这一点的方法是考虑加权宽度，它将阻尼因子应用于函数定义域远端的宽度。这消除了[11，第4节]中存在的解的生存期的第二个限制aL≤1。正式定义如下：定义4.6设0 ≤α∈R且f：[0，a] →IRn. 然后wα（f）=supt∈[0，a]e−αtw（f（t））是f的加权宽度，加权因子为α。我们收集两个简单的属性。引理4.7设f：[0，a] →IRn.则w（f）≤e aα w α（f）且w α（f）≤w（f）。下面的引理表明，PuTSQ是[0，a]的适当划分Q引理4.8假设Q∈ P[0，a]，|Q| ≤1且y∈SQ。 则w α（P u（y））≤Lw α（y）.Coroll ary4.9Su.p ∈yk+1=Pu（yk），其中llk≥0.则w（yk）∈O（2−k）.特别地，y=ky k是实值，并求解IVP（1）。 .如果u是一个可计算向量场，我们有u=kukfor a recursive序列（uk）k≥0的有限可表示函数uk。因为我们只能用无穷近似uk，推论4.9的算法不能直接实现;相反，我们必须考虑近似。收敛到解的速度显然取决于uk接近u的速率，其测量如下。定义4.10如果t，u：IRn→IRm且K≥0，则限制距离dK（t，u）由下式给出：d K（t，u）= sup{d（t（α），u（α））|α∈I[−K，K] n}。A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）565573k≥0KK2L2L如果u =.u，我们说d（u，u）∈ O（2 −k），如果对所有K≥ 0，我们有，d K（u，uk）∈ O（2−k）.也就是说，我们说序列（uk）以指数速度收敛到u，如果它在所有紧集上以指数速度收敛我们现在建立的工作与近似（uk）的u不会破坏收敛到一个解决方案，并给出一个估计的收敛速度。首先，注意对于 UJ±u，对于 所有 的y ∈ SQ ，不 长时 间地 保证 Puj（y）∈SQ。这个问题在下一个引理中解决。引理4.11假设Q∈ P[0，a]，|Q|1，uJ±u，d2K1 个月（0）天。 对于任意的h1y ∈ SQ，n1Puj（y）∈SQ.（u，uJ）≤2 2 2下一个引理是在区间向量场u的近似uk存在的情况下给出收敛速度估计的关键垫脚石。引理4.12假设Q∈ P[0，a]，|Q| ≤1且uJ±u，d2K（u，uJ）≤1<$v（0）<$，y∈2SQ. 其中nwα（PuJ（y））≤Lwα（y） +2d2K（u，u，J）。2α αeQ从加权宽度到普通宽度，我们得到了本节的主要结果：无界向量场的Picard迭代的快速收敛。.TheoreM4.13Sup p pose. u=kuk 其中d（u，uk）∈ O（2 −k）。 对于k≥0，yk+1=Puk（yk），y=kk k。 则P u（y）= y且w（y k）∈ O（2−k）。.我们认为这是一个很好的选择。对于递归单调函数，ifu=kukk序列（uk）k∈N，其中每个uk=j∈Ikαj\βj是有理阶跃函数而Ikαj，βj∈IRn有有理端点，.α\β（x）=βif xα否则的话。由于我们所有的建筑都是明显有效的，我们特别有Coroll ary4.14Sup poseu是有效的。. 当我们可以有效地控制-构造一个有效序列（yk）k∈N，使得kyk是IVP（1）。可用于实现此方法的数据结构与[ 11 ]中处理的有界情况相同，我们称之为loc。前引书用于计算复杂性的估计，其逐字地也适用于该扩QQ574A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）565展设置。同样，欧拉方法的区域理论版本A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）565575ln2[10]可以使用局部技术扩展到无界向量场 先验界限;这将在本文的完整版本中详细说明5逼近连续函数我们的理论已经在实践中得到了证实。在独立的向量上的NDEPEN场u，以阶跃函数的上确界u=k∈Nukk 为了为了应用我们的理论，必须满足以下假设(i) u是经典向量场 v的扩张(ii) 满足区间Lipschitz条件(iii) 区间距离d（u，uk）以指数速度收敛。本节展示如何获得满足上述假设的序列（uk）k∈N。我们讨论了两种技术，用于构建近似-向量场的计算：首先，我们讨论近似的合成，然后我们展示如何从一个函数构造区间值近似，该函数计算向量场的值到任意精度。5.1近似值的构成在本节中，我们假设有两个函数g：IRn→IRm，f：IRm→IRk，用序列（gn）和（fn）近似，并说明我们如何使用这些近似来计算fg的近似，这取决于本节开始时规定的条件我们从一个例子开始，表明组合的近似不一定保持收敛速度。..例5.1这个例子表明，如果f=kfk和g=kgk，且两者都（fk）和（gk）指数快速收敛，则这对于复合g<$f不一定是真的，即使f和g都是区间Lipschitz。考虑由下式给出的连续函数h：[0，∞）→ [0， 2]：.h（x）=1−12log2（1−x）X11x≥ 1其中log2是二进对数（对数w.r.t.基数2）。显然h在[0，1）中是可微的，初等分析表明，对x ∈ [0，1），0 ≤hJ（x）≤1≤2，因此对所有x ∈ R，h（x）≤ 2 x.因此，Scott连续函数f（α）= [0，h（w（α））]满足区间Lipschitz条件w（f（α））≤ 2 w（α）.设f k= f，我们清楚地知道d（f，fk）≤ 2 −k。注意f是常零函数的非极大区间扩张。576A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）565K对于g（α）=[0，w（α）]和gk（α）=[0，w（α）+2−k−1]，我们也有g是Lipschitz区间，d（g，gk）= 2−k−1≤ 2−k。 我们证明了组合f kg k不以指数速度收敛到fg。考虑区间α k=[0，1−2−k−1]。 则d（f k<$gk，f <$g）≥ d（f k（g k（α k）），f（g（α k））= h（w（g k（αk）−h（w（g（α k）=h（1）− h（1 − 2 −k−1）=1，表明函数复合不保持指数收敛速度。正如这个例子所示，我们需要额外的条件来确保近似的组合保持收敛速度。我们建议考虑的功能是豪斯多尔利普希茨从下面：定义5.2设f：IRn→ IRm。 那么f是Hausdor Lipschitz从下面，id（f（α），f（β））≤L·d（α，β）对某些L≥ 0和所有α±β，α，β∈ IRn.注意，我们只要求估计在α±β时成立，因此下面的Hausdor Lipschitz是比Lipschitz w.r.t.更弱的条件。分别是IRn和IRm上的Hausdor度量我们简单地把这个条件与我们以前介绍过的区间Lipschitz条件联系起来。回想一下，f是区间Lipschitz，如果对于某个L≥0且所有α∈dom（f），w（f（α））≤L·w（α），即f至多线性地增加其辐角的宽度。注5.3“区间Lipschitz”和“Hausdor从下到上的Lipschitz”这两个概念(i) 例5.1中的函数f是区间Lipschitz，但不是下面的HausdorLipschitz。(ii) 函数λx。[0，1]：IR→IR是Hausdor Lipschitz，但不是区间Lipschitz。从 下 面 很 容 易 看 出 经 典 Lipschitz 函 数 的 最 大 扩 张 也 是 HausdorLipschitz，但反之则不然。命题5.4假设f：Rn→Rm满足Lipschitz条件，其中Lipschitz常数为L。 则对所有紧的α ± β ∈ IRn，d（If（α），If（β））≤Ld（α，β）.下一个例子表明，从下面的豪斯多·利普希茨函数不一定是最大的。例5.5假设−：IR×IR→R是减法函数的最大扩张，即[α，α]−[β，β] =[α−β ， α−β] 。则 函数f ：IR→IR ， x<$→x−x 既 是区 间Lipschitz 又 是Hausdor <$LipschitzA. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）565577从下面，但不是最大的，作为函数g=λx。0满足f±g和f/=g。对于我们的目的来说，是什么使得从下面是Hausdor Lipschitz的函数有吸引力的是，这样的函数的集合在复合下是封闭的，与最大扩张相反。引理5.6假设f：IRn→ I Rm和g：IRm→ I Rk是下式的豪斯多-利普希茨。所以是Gf。命题5.4和例5.5引导我们把下面的Hausdor Lipschitz函数看作是接近于极大扩张的函数，而不是实际上是极大的。特别是，这些函数在组合下是封闭的，这使得它们对构建库很有吸引力我们现在能够证明承诺的结果组合的近似，特别是我们建立了一个保证组合近似的收敛速度。定理m5.7辅助势gk：IRn→IRm和fk：I.Rm→IRla re。我一个人Scott连续函数序列，f=kfk和g=kgk，满足以下要求：(i) f和g都是Lipschitz区间， f是Hausdor Lipschitz区间，(ii) d（ f，fk），d（ g，gk）∈O（2−k）则fg是区间Lipschitz，并且是满足d（f kg k，fg）∈ O（2 −k）的经典函数的扩张。此外，如果g也是Hausdor Lipschitz，则fg也是。这个定理表明，从下面的区间Lipschitz和Hausdor-Lipschitz函数类可以用来建立一个快速收敛Lipschitz函数的组合库。在下一节中，我们将讨论如何实际构造属于这一类的函数，因此可以用作近似Lipschitz向量场的构建块。5.2构建近似既然我们已经看到了如何得到区间向量场的合成近似，本节概述了一种构造这些近似的技术，给定一个计算Lipschitz函数f：Rn→Rm的函数，直到任意精度。更准确地说，我们假设g：Qn×N→Qm被给出，使得<$f（x）-g（x，k）≠2−k。 在实践层面上，这允许我们计算近似值，578A. 埃达拉特湾Pattinson/Electronic Notes in Theoretical Computer Science 155（2006）565QQQQRQ对于一大类函数。此外，具有上述性质的可计算函数g的存在性等价于f的可计算性，本节的结果表明，我们对每个可计算的Lipschitz向量场都得到了阶跃函数的近似。构造的思想如下：给定一个矩形α<$Rn，我们计算α的中点m（α）的g（m（α），k）的值，精度为2−k。为了适应这种不准确性，我们通过在每个坐标轴的方向上以2−k然后使用f的Lipschitz常数，导致一个矩形，其中包含x∈α的所有值f（x）。形式定义如下，在本节的其余部分，我们假设f：Rn→Rm满足Lipschitz条件，Lipschitz常数为L，g：Qn×N→Qm使得<$g（x，k）−f（x）<$≤2−k。定义5.8对于实向量x =（x1，. ，xn）∈ Rn且λ ∈ [0，∞），对于中心为x、宽度为2 λ的n维立方体[x1− λ，x1+ λ] ×···× [xn− λ，xn+ λ]，我们记为x <$λ. 给定分区Q =（q0，. ，q k），我们将端点在Q中的n维矩形的集合表示为：R（Q）={[qi1，qj1]×· · ·×[qin，qjn]|0≤ir

下载后可阅读完整内容，剩余1页未读，立即下载