（计算数学专业论文）具最优收敛阶二维自适应多尺度积分公式.pdf

中山大学硕士学位论文 具最优收敛阶二维自适应多尺度积分公式 专业：计算数学 学位申请人：曾艳 导师及职称：邹青松副教授 摘要： 本论文构造和分析具最优收敛阶二维自适应多尺度数值积分公式。利用二 维三角形区域和矩形区域上具有多尺度性质的小波插值点和小波基，构造多尺 度的数值积分公式：然后把自适应思想与多尺度积分公式结合起来，构造了具 最优收敛阶二维自适应多尺度积分算法，得出奇性函数的一种快速积分算法， 该算法有最优的收敛阶估计；最后还以数值算例验证了理论结果的有效性。 关键词： 不变集，可加细集，小波，自适应积分 a d a p t i v em u l t i s c a l eq u a d r a t u r ew i t ho p t m a lc o n v e r g e n c e r a t ef o rt w od i m e n s i o n a li n t e g r a l a b s t r a c t ： m a j o r ：c o m p u t a t i o n a lm a t h e m a t i c s n a m e ：z e n g y a h s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rz o uq i n g s o n g i nt h i s p a p e r , w ec o n s t r u c ta n da n a l y z ea d a p t i v em u l t i s c a l e q u a d r a t u r ew i t ho p t m a lc o n v e r g e n c er a t ef o rt w od i m e n s i o ni n t e g r a l f i r s t , w ea p p l yt h eb a s i so fw a v e l e ta n di n t e r p o l a n tp o i n t s a tr e c m n # ea n d t r i a n g l e t oc o n s t r u c tm u l t i s c a l eq u a d r a t u r e f o r m u l a n e x t , w ec o m b i n e a d a p t i v em e t h o dw i t hm u l t i s c a l e q u a d r a t u r e f o r m u l at oo b t a i na m u l t i s c a l e a d a p t i v eq u a d r a t u r ea l g o r i t h m ，a n dc o n c l u d ei tar a p i d a l g o r i t h mf o rs i n g u l a ri n t e g r a lw h i c hc a no b t a i no p t m a ic o n v e r g e n c er a t e f i n a l l y , an u m e r i c a le x a m p l ei sg i v e nt ot e s t i f yt h e o r e t i c a lr e s u l t k e y w o r d ： i n v a r i a n ts e t s ，r e f i n a b l es e t s ，w a v e l e t ，a d a p t i v eq u a d r a t u r e 第一章绪论 1 1 引言 第一章绪论 函数积分的数值逼近一直以来都受到很多学者的关注，因为其不仅在理，工 科中有重要的应用，而且在医、农、文、商等很多学科和工程实际中都有很重要 的应用。数值积分是求解定积分近似值的数值方法，即用被积函数的有限个抽样 值的离散或加权平均近似值代替定积分的值。求某函数的定积分时，在多数情况 下，被积函数的原函数很难用初等函数表达出来，因此能够借助微积分学的牛 顿- 莱布尼兹公式计算定积分的机会是不多的。另外，许多实际问题中的被积函 数往往是列表函数或其他形式的非连续函数，对这类函数的定积分，也不能用不 定积分方法求解。由于以上原因，数值积分的理论与方法一直是计算数学研究的 基本课题。对微积分学作出杰出贡献的数学大师，如i 牛顿、l 欧拉、c f 高斯 等人也在数值积分这个领域作出了各自的贡献，并奠定了它的理论基础。 其中，奇异积分的求解是数值积分中最重要的研究方向之一，早先的插值逼 近算法，如牛顿柯特斯算法，龙贝格算法及高斯积分法，对奇异积分计算的精 度和计算速度都不尽如人意，对此，越来越多的学者提出了很多新的计算方法， 包括离散前的正则化方法、离散后的正则化方法、自适应积分方法等等。离散前 的正则化是在边界积分方程中采用分部积分变换方法消除或降低积分核的奇异 阶次；离散后的正则化方法是对离散后的奇异积分单元在局部坐标空间进行解析 或半解析积分，消除奇异积分中的发散部分：自适应积分方法通常是将整个区域 分成可变长度的小区域，使得每个小区域上的局部误差都要控制在给定的范围 内。但是，求解奇异积分仍然欠缺一般性方法，这是数值积分的困难问题之一， 有关这方面内容的介绍可参考文掣1 】【2 0 】【2 “。 对于奇异积分的求解，本文将构造另外一种方法：多尺度自适应的积分算法， 该方法基于不变集和可加细集的理论，构造了一个具有多尺度性质的求积公式， 第一章绪论 然后把自适应剖分的思想和多尺度求积公式结合起来，从而成功地推导出一个奇 异积分的快速计算方法。与前人所做的自适应积分算法相比，该算法基于被积函 数的性质，对奇异性强的区域不断细分，从理论上论证，该算法可得到最优收敛 阶估计。 对于不变集的介绍可参考文章【18 1 ，文章0 1 1 4 1 1 8 1 介绍了怎样利用不变集来构 造规范正交的多重小波，而文章【2 】【1 9 i n n 我们证实了这种规范j 下交的多重小波在 积分数值解中有着非常重要的应用。有关小波和多尺度思想的介绍可以参考文章 【8 l 【1 4 1 1 1 5 1 6 1 ，而有关小波和插值小波的构造可参考文章【l 】【5 1 1 6 1 1 9 1 1 2 】【1 3 1 。 在我们这篇论文中，我们将利用文掣1 8 】的方法递归得到的具有多尺度性质的 插值点和插值小波，针对定义在单位等腰直角三角形区域和单位正方形区域上的 可加细集的具体特点，构造出其多尺度的积分计算公式，最后将自适应剖分的思 想和多尺度积分公式结合起来，在此计算公式的基础上建立一种快速的算法，有 关自适应积分的思想可参考文章叫1 7 】嘲】。对单位正方形区域上的函数，我们采 用张量积的方法从一维的线性小波基生成二维的双线性小波基，而对单位等腰直 角三角形上的函数，我们仍然采用二维线性的小波基。实际上，该算法也是采用 一种逐步细分的思想，我们对误差最大的区间进行细分，从而获得更多的插值点， 使得积分值越来越接近精确的值，实现逐步逼近的目的。该算法与其他的插值算 法的主要区别在于，每当对积分区间进一步细分时，无需从新计算，而只需对新 增加的插值点进行处理，从而实现了快速计算的目的。我们从简单入手，分析一 个一维的例子来说明这个思想。 假设要计算的是函数f ( t ) = 1 2t 【o ，1 】的积分，我们先在区间 0 ，1 】上选取两 个插值点l 3 和2 3 ，利用线性插值使得在这两个点上的值是准确的，可得到，( f ) 的一个逼近函数邱，如图1 1 所示；接着，我们将【0 ，1 1 区间进行平分，成为两 个n i n o ，1 2 1 n 1 2 ，1 1 ，之前选取的两个插值点分别落在一个区间里，与第一次 选取插值点时相同，对每一个新的区间，选其l 3 点和2 3 点，可得到两个新的 插值点1 6 和5 6 ，在各自区间上利用线性插值使其在两个插值点上都是准确的， 可得到f ( t ) 另一个逼近函数毋，如图1 2 所示；如此反复操作，直到达到满意 的结果。同理，在我们这篇论文里，可以看到，对于单位正方形区域和单位等腰 第一章绪论 直角三角形区域进一步细分时，也无需从新计算，只需对新增加的插值点进行处 理，从而实现了快速计算的目的。 论文的第二章我们介绍了本论文要用到的预备知识，即理论基础，包括不变 集和可加细集的定义和相关定理、怎样由不变集和可加细集递归构造集合小波和 插值小波的相关定理、自适应积分思想等等；在第三章中，我们对积分区域是三 角形的函数积分进行了讨论，由于任何三角形最终可通过分割、坐标旋转和变量 替换变成如图1 3 右所示的单位等腰直角三角形，我们基于其可加细集，生成了 二维的线形的小波基，得出了三角形区域上的多尺度积分公式，同时引进自适应 剖分的思想，以加快其数值积分的收敛速度，构造出了多尺度自适应积分算法， 最后从理论上证明了该算法的收敛阶估计：在第四章中，我们对积分区域是矩形 图1 1 图1 - 2 第一章绪论 的函数积分进行了探讨，由于任何矩形都可以通过坐标旋转和变量替换变成如图 1 3 左所示的单位正方形，因此我们可以利用前面所介绍的理论基础，用张量积 的方法生成单位正方形区域上的双线性小波基，并推导和证明了其插值点和插值 小波的快速计算公式，同时引进自适应的思想，构造出了多尺度自适应积分算法； 在第五章中，我们以数值算例来说明白适应算法的有效性，并与不采用自适应思 想的数值积分进行了比较。 图1 - 3 y 1 从最后的实验结果可以看出，该算法的收敛阶为1 阶，其计算的时问复杂度 接近似h ) ，用于计算具有奇性的积分时，确实是一种计算复杂度较低而收敛较 快的算法。 1 2 符号说明 a b 】表示求整运算； m o d ( a b ) 表示整数求余； j ，= ( 一。，y i 。，) ，。，表示一个二维空间上的一个点，j ，是其x 轴方向的分量， * j ，是其y 轴方向的分量： 4 第二章预备知识 2 1 不变集和可加细集 第二章预备知识 在这一章节里，我们主要来介绍一些本论文要用到的理论知识。因为不变集 和可加细集是整个算法的基础，由不变集和可加细集，我们才可以递归地构造出 具有多尺度性质的集合小波和插值小波，因而在这一节里，我们先简单地介绍不 变集和可加细集的概念和相关定理，并给出几个例子对其进行说明。 我们用伍矽来表示一个完备的度量空间，在此空间上定义一簇压缩映射集 o ：2 屯：s e u ) ，毛：= o ，l ，一1 ) ，其中是正整数。对m 我们 做以下定义： ( a ) = u 屯( a ) 6 e e “ 由此，我们引出不变集和可加细集的定义。 定义2 1x 上的紧子集合k 称为在一簇压缩映射集巾之下的不变集，如 果k 是x 上唯一满足以下条件的有界闭集： c i ) ( k ) = k 定义2 2x 上的子集v 称为映射集中之下的可加细集，如果v 满足： v ( v ) 由以上两个定义可知，一个对应某一簇压缩映射集的不变集同时也是对应这 簇压缩映射集的一个可加细集。 为了介绍下面的定理，我们先引进一些记号。 对任意的七n ：= l 2 ，记( ，s 。) e 为，其中e ：为e u 的k 第二章预备知识 次笛卡儿积，即e ：= e e ，k 次，并且有以= 允。九o 。其中。表示x 上的复合函数，于是令中。- 晚：唧或) 定义2 3 一个点称为是映射九下的不动点，如果： 也就是说，当一个点通过某个映射变换之后还是原来的那个点，那就说明这 个点是这个映射下的一个不动点。为了更好的说明问题，并且给出检验一个集合 是否为某个压缩映射集下的可加细集的方法，我们介绍一个定理，在介绍定理之 前我们先做一些记号以方便说明问题。对任意的r 岛e r j ：= ( ，钆p ，q ) ， 龙，= 如。砖+ 。如，_ ，为以，的不动点。显然，当，= ，时，映射啦，为一恒等算 子。 定理2 1 如果中= 屯：占瓦) 是完备度量空间x 上的一簇压缩映射， x 是基数为k n 的非空集。那么v o 是。下的可加细集，当且仅当对任意的 v ，存在整数，m e 乓。， 脚和t ，i e 瓦使得v = 屯，( ，) 和点v r - 屯，( 毛，) e v o ，r e 历，v + ，：= 忆，( 。) ，r 玩f 下面我们给出三个例子，一个是一维空间上的，另两个是二维空间上的，由 于高维空间上的比较复杂，这里就不给出例子了，通过这三个例子，我们可以清 楚的理解不变集和可加细集的定义。 例1令集合k = 0 ，1 】cr ，并定义一个压缩映射集中包含以下两个压缩映 射： 丸( f ) = - 3 h 2 萌( f ) = 3 t 一1 则可以看到唬( k ) u 萌( k ) = k ，因此集合k 是压缩映射集m 之下的一个不变集也 是一个可加细集。由于算法的要求，我们需要的可加细集是有限的点集。在本例 6 第二章预备知识 的压缩映射集西下，通过简单的证明可知以下集合是可加细集：哼1 ，j 2 ) 。 例2 令足c r 2 是一个单位正方形，则四个顶点分别为y o = ( 0 ，o ) ，y l = ( o ，1 ) ， y 2 = ( 1 ，o ) ，y 3 = ( 1 ，1 ) ，并定义一个压缩映射集。包含四个压缩映射定义如下： 九( ，) = ：1 0 + 虬) ，f r2 ，譬e 4 则可以看到巾( k ) = uc a k ) = 置( 如图2 - 1 ) ，因此集合足是压缩映射集中下的一 。5 髓 个不变集也是一个可加细集a 通过简单的证明可知以下集合是可加细集： ( ；，了1 ) ， c 挎c 孙c 持， ( 0 ，1 ) ( 0 ，0 ) 缟( z o呜( 幻 磊( 固萌僻) 图2 一l ( 1 ，1 ) ( 1 ，0 ) 例3 令cr2 是一个单位等腰直角三角形( 直角边长度为1 ) 。则三个顶点 分别为y 。= ( o ，0 ) ，y = ( 0 ，1 ) ，y ：= ( 1 ，0 ) ，设乃= ( 1 ，1 ) ，并定义一个压缩映射集m 包含 四个压缩映射定义如下： 1 九( f ) ：= = i ( j 0 + ( 一1 ) 7 5 f ) ，e 臣，f r 2 二 其中r ( s ) = o ，当s 易；r ( 3 ) = 1 。则可以看到o ( ) = u 纯( ) = ( 如图2 - 2 ) ，因此 躔也 集合是压缩映射集巾下的一个不变集也是一个可加细集。通过简单的证明可知 以下集合是可加细集： 第二章预备知识 ( 0 ，1 ) ( 0 ，0 ) ( 号，了4 ) ，了l ，了2 ) ，了4 ，号) ) 图2 2 ( 1 ，0 ) 在后面的章节里，我们根据图2 1 和图2 2 所示单位正方形和单位等腰直角 三角形上的对应于一簇压缩映射集的不变集和可加细集，由此递归地构造出二维 空问单位正方形区域和单位等腰直角三角形区域具有多尺度性质的小波插值点 和小波基，然后利用这些点和基构造多尺度求积公式，将自适应的思想应用到该 求积公式中，试图得出任意平面区域上函数的一种快速积分算法。如没有特别说 明，在后面章节里，所提到的单位正方形和单位等腰直角三角形均如图2 1 和图 2 2 所示。 2 2 集合小波 上一节我们已经介绍了不变集和可加细集的相关定义和定理，这些将在这一 节得到应用。在这一节里，我们介绍如何利用不变集和可加细集为基础，递归地 构造集合小波，集合小波对于在胄。的紧子集上构造插值小波是非常重要的，在 这一节里我们还将对如何构造在集合小波上的插值小波进行简单的介绍，详细内 容可参考文章【1 8 l 。接下来，我们以一个与集合序列相关的定义来开始这一节。 定义2 4 我们称一个集合序n a ，：f n o ) 是嵌套的( 严格嵌套的) ，如果： 第二章预备知识 4 1 4 ，f n ( 4 一l c 4 ，f ) 在后面我们可以看到，这一定义对于集合小波的构造过程有重要的应用。我 们试着选择一个压缩映射集和在这个压缩映射集下的一个可加细集，通过压缩映 射集对可加细集的作用，可递归地产生一个集合序列，并且这个集合序列是嵌套 的，这一集合序列是我们需要的集合小波的基础。接下来我们介绍一个定理，说 明如何构造这一嵌套的集合序列。 定理2 2 i 埔lk 是工上对应于有限压缩映射集巾的一个不变集。假设k 不 是有限的，且k 是z 上的非空有限子集。那么集合序列 k ：f 0 ，k ：= d ( k 一。) ，f n 是严格嵌套的，当且仅当集合是对应于m 的可加 细集。 利用定理2 2 介绍的严格嵌套的集合序列，接下来我们将介绍如何产生我们 所需要的集合小波。当集合序n e ：f n o ) 是严格嵌套的时，我们记彬一，= + f n 。同样地，为了表示方便，我们再引入记号1 ，当两个集合a 和b 符合4 n b = a 时，用爿u 1 b 代替a u b 。则我们有k = k l u l 彬+ j n 。定理2 3 将说明 所构造的集合序列与原先的不变集的关系。 定理2 3 1 1 a lk 是x 上对应于有限压缩映射集中的一个不变集。假设对中 中任意的压缩映射屯：占e 在上都有连续的逆，并且满足以下方程： 丸( i n t 置) n 纯( i n t k ) = a ，s ，s7 e ，占占 若是对应于中的可加细集，并且w oc i n t k 。那么有： 彬= 中1 ( 彬一) ，i n 并且紧子集有以下分解： k = t o 一( u1 ) n 0 定理2 3 实际上得出了不变集k 的一个多分辨率分解。集合彬，i n 称为集 9 第二章预备知识 合小波，其中为初始集合小波，i l i i w , ，i n 所构成的k 的这种分解称为k 的 集合小波分解。这样，我们就成功的构造了一个具有多尺度性质的集合小波。在 接下来的小节里，我们将在集合小波的基础上构造我们所需要的插值小波。 2 3l a g r a n g e 插值小波 这一节中，我们介绍用集合小波构造我们所需要的插值小波。通常，我们采 用l a g r a n g e 插值小波。为此，我们先做以下假设： 1 0x ：r o 2 0 m 等 纯：s 瓦) 是满足定理2 3 中假设的压缩映射集 3 0 k r 4 是对应于m 的不变集，并且满足m e a s ( k i n t k ) = 0 ，其中m e a s ( a ) 表示集合a r 。的l e b e s g u e 度。 4 0 v o 等 v 0 ，v ”，u 1 ) c i n t k ，k e n 为对应于的可加细集 5 0 f # ( 五，z ，五一。) 7 ：k j 只是满足以下方程的可加细曲线：f 。谚= 4 厂，i 既，其中4 ，f 既是某些指定的七七矩阵 6 0 f o ：= s p a n f o ，z ，五一 ，且d i mf 0 = k ，此外，对任意6 ：= ( b o ，6 l ，良一) 7 r ，只存在唯一的元素厂磊使得，( 叶) = 岛，f 乓也就是说，f 0 中存在七 个元素五，z ，以一使得z ( 0 ) = 4 i ，乓 如果以上假设成立，我们就说 z ：f b ) 在集合k 上插值，z 在点v ，j 耳 上插值，在这种情形之下，任意的元素f f 0 都可以表示成以下这种形式： ，= ，( v l m 由此，我们再引入以下定义。 定义2 5 一个集合圪r 4 称为对应( 中，吩) 是( l a g r a n g e ) 容许的，如果 满足以下两个条件： 1 0 第二章预备知识 ( 口) k 是对应于的可加细集； ( 6 ) 函数z ：f 乓存在着一个组基，使得f 0 在集合上插值。 为了表示的更简单，我们再引入算子l ：r ( k ) 一r ( k ) ，s e ，其定义 为： 吼删；o 一g a g ( 足) ) ( 2 1 ) 并且令 噩l + ，= o t 。e 为了说明插值小波的定义，我们有以下定理。 定理2 5 1 8 1 如果v o 对应9 ( m , f o ) ：是l a g r a n g e 容许的，那么对每个一n o ， 集合圪同样也对应于( 巾，e ) ；是l a g r a n g e 容许的。 定理2 5 保证了对每个f e 都有一种表示，= 见，+ 岛，其中p f 是厂e 在圪上的l a g r a n g e 插值，而岛= 厂一p f 则是插值误差。令： g 。= 岛：岛= 厂一以厂，f e + 。 在参考文章口1 中证明了对砸：| + 。有以下分解： b “= f 0 0 g 0 0 o g 。 对此，我们把g 。称为插值小波空间，而g 。称为初始插值小波空间，明显地有 d i m g 。= k u ”( f - 1 ) 。 接下来我们以两个重要的定理来结束这一节的内容。 定理2 6 如果对应于( m ，r ) l a g r a n g e 容许的，令哌，竹0 是由 产生的集合小波，那么有： g o = s p a n t 。：s b ，j 乓，t 。在九( ) 上面插值) ， g 。= o t 。g ，一n ， e l 第二章预备知识 并且有g 。= s p a n g , ，其中 q ：= ，：巳+ - 髟“，j e ，t 。乃在允。( _ ) 上面插值) ， 0 定理2 7 t 1 8 l i f ( k ) = d ( o f 。) = c l f oo g 。】 h e n o n e 前面我们介绍了多尺度的小波构造，现在开始我们将介绍怎样利用前面所介 绍的内容来构造一个多尺度求积公式。 假设足，分别是完备度量空间x 上对应某一压缩映射集的不变集和可加细 集，呒，h n 是由产生的集合小波，取初始集合小波为= u ：j e 乓( 川) ) ， 记 t o ，。：0 ，j 乓；，：= ：，毛( t - i ) ； ，u ：= 如。屯o 。晚。，j = ( 卜2 + + t g ，3 + t 一2 ) 七( 一1 ) + ， s _ ee j ，m 巨一i ，e i p i ) ，i = 2 ，3 ，7 于是k = ：，e ，( f ) ，f e + i ，其中 f 七 i ：0 ，( d 。- 1 七( 一1 ) “卜1 f l 集合序列k 就是具有多尺度性质的集合小波，我们用其作为插值点，由定理 2 3 可知集合序列k 构成了不变集足的一个多分辨率分解。有了插值点之后，我 们将进一步介绍怎样构造出在这些插值点上的插值小波。类似插值点的表示方 法，我们取初始插值小波空间为g 0 = g ，：，e ( 川) ) ，则 g j ( t o 。) = o ，i 乓，j 巨( 川) ； 毋( ) = ，j e ( 川) 并令： g o ：= ，j 乓；g a ，：= g j ，j 乓( p j ) ； g u ：= t 句。t 毛一：g t ，j = ( 卜2 岛+ + 鹏一3 + 一2 ) 七( 一1 ) + ， b ，m 巨_ l ，e ( 川) ，i = 2 ，3 ，n 可以看出吕，( ) = 点j 谚，目( f ) ，j 日( ) ，i ，i e 扎i - i ，且有 第二章预备知识 e = s p a n g i 。：，日( ) ，f e + 1 ) 类似于其他的插值积分运算，利用这些插值小波的加权组合，我们就可以表示任 何x c ( k ) 的插值投影： n x = x ，j g i 。 ( 2 2 ) ，e “j e l ：, 上式中的系数x i 可通过以下的公式递归获得 x o j = x ( t o j 、，j e k t ，= x 纯，) 一。g i j ( f l ，) ，目( f ) ，f e “ ( 2 3 ) r e e ，r e e h n 与其他的插值积分运算不同的是，在这里，当标号玎增加l 变成盯+ 1 时，我们不 需要重新计算之前的那些系数五，o f 片，因为当我们增加插值点的时候，原 有的插值点和插值函数都没有改变，这一点也是多尺度积分公式的特点，这一特 点也加快这种算法的运算速度。 令以+ 一= 见x + q x ，则q x q ， q x ；矗山岛+ l ， ( 2 4 ) ，e 日t 肿l ， 那么系数矗+ 1 ，可由以下公式得到： 矗删= x ( o + l j ) 一w g i j 纯扎，) ( 2 5 ) ，e + | 。e 日f ， 至此，我们已经完整地介绍了通用的具有多尺度性质的插值逼近公式，当选 择线性的小波基时，这便是一个l a g r a n g e 小波插值逼近公式。在后面的章节中， 对单位等腰直角三角形，我们使用的也是线性的小波基，对于单位正方形，我们 根据其实际情况，由张量积的方法生成二维的小波基。由于高维情况较为复杂， 在本论文中就不详细的进行介绍，接下来，我们将以上的结论用到积分区域是单 位正方形上和单位等腰直角三角形的函数积分上，其他高维的情况可类似二维的 情况同理推导即可。 2 4 自适应积分 第二章预备知识 这篇论文主要是利用前面章节所构造的小波插值点和小波基，进行多尺度的 自适应插值积分，因此在这一节里，我们有必要说明自适应积分的基本思想。 假设有一被积函数，( 曲，x 【口，6 ，s 是容许误差，我们需要计算积分值： f ( x ) a x 自适应积分的思想通常会把整个区间【口，b 】分成可变长度的小区间，使得在每个 小区间上的数值积分的误差都控制在一定的误差范围内。 下面我们以s i m p s o n 公式为例来说明白适应积分的思想，其形式为： i ， ) a x = 跗，6 ) - 寺( b - a ) ，2 ( a 善咄，6 】 s ( a ，6 ) ：鱼j m ) + 4 ( 等鱼) + 胛) 】 oz 自适应积分的主要思想如下： 第一步：首先在区间 d ，b 】上应用s i m p s o n 公式。如果其数值积分的误差满足 要求，停止运算；如果其数值积分的误差不够精确，我们将【口，b 】区间平分成两 个相等的小区间 第二步：在每个小区间上应用s i m p s o n 公式。如果在这个小区问上的误差满 足要求，则这个区间不需要再细分；如果这个小区间上的误差不满足要求，则要 求平分这个小区间 第三步：这个过程将被继续，直到每个子区间上的数值积分的误差都满足要 求。 最后，我们得到了 个可变长度的小区间，每个小区间都将分别应用s i m p s o n 公式，对此我们有： p o ) a x = m ) 出= ( s + 巴) = s + q 口 仁l i 忙lj 3 l忙i 其中s 是e f b j 阮+ 一】上的近似积分值，e t 是区间【t + t 】上的局部误差。如果在 每个小区间上的局部误差满足： 4 第二章预备知识 i q i s ( 一一。) ( 6 一口) 那么在整个区间【口，卅上，总体误差估i , 4 - j 勾- n” ” 酬iqll=1i = l 击i = l 瓴刊钳ll 可见，由自适应积分算法得出的数值积分值可以满足整个的误差要求，即： 砂c 舳一窆墨f 占 d = 1 1 完整的所，即s d ”自适应积分算法步骤可见参考文章【7 】o 第三章基于三角形区域的最优自适应积分 第三章基于三角形区域的最优自适应积分 3 1 三角形上的多尺度求积公式 实际问题当中常常需要计算积分。当在一个任意的平面区域上进行积分运算 的时候，由于积分区域的不规则性，我们无法用常规的方法来计算这个积分。为 了解决这个问题，我们可用一个多边形去逼近这个不规则区域，然后把多边形分 成许多矩形和三角形之和，最后只分别在矩形和三角形上计算我们需要的积分 值。 对于三角形区域，我们可用分割、旋转和变量替换的方法，将三角形区域变 为方便讨论的单位等腰直角三角形区域，即只需计算积分，= ff g ( x ，y ) d x d y 。 依据人们所熟知的微积分基本定理，对于二维积分ii g ( x ，y ) d x d y 只要找到被 万 积函数g ( x ，j ，) 的原函数便可求得积分值，这就是牛顿- 莱布尼兹公式法。但实际 使用这种求积方法往往有困难，因为大量的被积函数找不到用初等函数表示的原 函数，另外，当g ( x ，_ y ) 是由测量或数值计算给出的一张数据表时，牛顿一莱布尼 兹公式也不能直接运用，因此有必要研究积分的数值计算问题。 通常，我们可以在区域d 上适当选取某些节点( 坼，雎) ，然后用g ( 坼，y k ) 加权 平均得到近似值，这样构造出的求积公式具有下列形式： j f g ( x , y ) d x d y2 荟4 9 ( x k 式中( _ ，n ) 称为求积节点；4 称为求积系数。权4 仅仅与节点( 以，y o 的选 取有关，而不依赖于被积函数g ( x ，y ) 的具体形式。这类数值积分方法通常称作机 械求积，在将自适应思想引入机械求积方法前，我们先构造积分区域是如图1 - 3 右所示的单位等腰直角三角形的多尺度积分公式。 1 6 第三章基于三角形区域的最优自适应积分 令cr2 是一个单位等腰直角三角形，则单位等腰直角三角形的三个顶点 分别为j ，。= ( o ，o ) ，y = ( o 1 ) ，y ：= ( 1 ，o ) ，设j ，= ( 1 ，1 ) ，并定义一个压缩映射集面包含 四个压缩映射定义如下： 以( ，) ：= 1 ( 咒+ ( 一1 ) r ( s r ) ，s 巴，f r 2 其中r ( 占) = 0 ，当s e 3 ；r ( 3 ) = l 。 容易证明是对应于巾的一个不变集( 如图3 1 ) ( 0 ，1 ) ( o ，0 ) ( 1 ，0 ) 令v o = v o ，v l ，v ：) - ( 号，砂4 了1 ，弘2 了4 ，号) ) ，则有： 丸( ) = ( 专，拶2 百i ，砂1 了2 ，击) ) 磊( ) = ( 云，了2 ) ，了4 ，了1 ) ，百1 1 ，击) ) 丸( ) 2 ( 专，百1 1 ) 咕1 ，百9 从了2 ，了4 ) 丸( ) = 百5 ，百3 ) ，哼3 ，百5 ) ，再3 ，了3 ) ) v o c # o ( v o ) u 氟( k ) u 欢( ) u 九( ) 故是对应于m 的可加细集，且由v o 产生的初始集合小波为：w o = w o ，w l ，w 9 ) 。 ( 击，了1 ) ，了2 ，百1 ) ，百9 ，了2 ) ，百1 1 ，百1 ) ，了1 ，百1 1 ) ，百1 ，酉9 ) ，百5 ，百3 ) ，了3 ，百5 ) ，百3 ，了3 ) 。 第三章基于三角形区域的最优自适应积分 我们不妨记：= w 0 1 l ，w o 刀w i , o ，w 雌w 2 ，0 ，w 2 p w 3 t o ，w 3 ”w 3 ，2 ) ，其中w j ，是由力作 用在n 上产生的结点。 按照前面的定义和记号，假设，分别是完备度量空间x 上对应于压缩映 射集国的不变集和可加细集( ，中如上定义) ，w n ，胛0 是由产生的集合 小波，取初始集合小波为= m ，：当，毛时，r ee 3 ，；当j = 3 时，r e 毛) ， 则： t o , j = v ，j e 3 ；t l d r = w ，当_ ，易时，r 毛，r - ，；当_ ，= 3 时，r e f u ，= 九。九。尢一：w f ， j = 4 x ( 4 2 知+ + 4 e h + 占j - 2 ) + 7 ，e e 4 ；j 日， 当m o d ( ( j + 1 ) 4 ) 0 时，r e a r m o d ( y 4 ) ( 即r m o d ( 1 4 ) ) ： 当m o d ( ( j + 1 ) 4 ) = 0 时，岛；s 。e 4 ，n e ，1 ，i = 2 ，3 ，” ( 3 1 ) 可见，对于单位等腰直角三角形上的插值点f 。，要通过计算( f 1 ) 次映射而 求得，即迭代的方法，我们可由上一层的结点产生下一层的结点，根据以上结论， 有： r j + l 扣5 吒。吒。吒w t ，j = 4 。( 4 ”。岛+ + 4 鬈一2 + 一t ) + 7 ，7 e 4 ；j e m ， 当m o d ( ( j + 1 ) 4 ) 0 时，r e 毛a r m o d ( j 1 4 ) ( 即r r o o d ( 4 ) ) ： 当m o d ( ( j + 1 ) 4 ) = 0 时，r e ；s 。e 4 ，行e ，i = 2 ，3 ，” 当岛= f ， e l - l 时，有： 4 ( 4 i - i s o + + 4 占一2 + 占h ) + ， = 4 o + 4 x ( 44 2 占i + + 4 s 一2 + s l - i ) + ， = 4 。s o + 4 x ( 4 一2 s o + + 4 t 一3 + s 卜2 ) + ， = 4 占o + ， 于是： ， l ，h r ? ，= 牵。j t u i ，j 1 2 4 n + j ，o e 4 ， _ ，= 4 x ( 4 卜2 s o + + 4 e 。一3 + s 卜2 ) + ，e 4 ；j e 一， 第三章基于三角形区域的最优自适应积分 m o d ( ( j + 1 ) 4 ) 0 时，e r r m o d ( j 4 ) ( 即，m o d ( 1 4 ) ) ： 当m o d ( ( j + 1 ) 4 ) = o 时，r 岛； 占。臣，n e i l ，i = 2 ，3 ，聆( 3 2 ) 当i = 1 时，利用式( 3 2 ) ，有； t 2 , f , r = 簪矗t l , j , r ：。；w ，j ? 2 4 s o + j ，s q e 4 ， 当_ ，e 3 时r 巨且，m o d ( j 4 ) ( 即r m o d ( j 4 ) ) ： 当_ ，= 3 时，b( 3 3 ) 若利用式( 3 1 ) ，有： t 2 d , r = 吒，r - ，2 4 占o + 1 ，g - o e 4 ， 当，e 3 时r e 且r m o d ( j 4 ) ( 即r m o d ( 1 4 ) ) ： 当，= 3 时，乓( 3 4 ) 对式( 3 3 ) 和式( 3 4 ) 进行比较，我们可以发现，这两个式子是等价的。由式( 3 2 ) 我们可以得到以下公式： r s o = 0 时 t f + i ，：= 丸( t i , j , r ) 2 ( x ，1 2 ，y u ，2 ) 2 。 氏= l 时 ，f + i ，- _ 办( t i , j , r ) 2 ( ( x u ，+ 1 ) 2 ，j ，u ，2 ) 3 。e o = 2 时 t ，：= 庐2 ( f w ) 2 ( x w 2 ，( 儿 ，+ 1 ) 2 ) 4 。c o = 3 时 - ，r = 以( t i , j , r ) 2 ( ( 1 一x i d , r ) 2 ，( 1 一y i j , , ) 2 ) 注释：，。，是二维空间上的个点，x 。，表示其第一个分量，y i , j , r 表示其第二个 分量。 由上面的推导可知，在单位等腰直角三角形上，我们用迭代的方法可从上一 层的插值点得到下一层的插值点。类似集合小波的构造，我们对不变集做一个 9 第三章基于三角形区域的晟优自适应积分 区间的剖分。为了表达的方便，我们先做以下记号： 厶。2 ，i i + l , j = 办( ，) ，= 4 s + r e 4 ， s n o ，e 4 ，i n o 现在开始选择我们所需要的小波基。在单位等腰直角三角形上，由前面的论 述可知，= v o , v l , v 2 = “；，尹4 ，( 号，了2 ) ，( 二4 ，了i ) ) ，即中包含三个点，建立二维 性l a g r a n g e 小波基，即珊+ 砂+ c 的形式，正好需要三个点。设： 矗，：2 s p a n 五，一， ) ，= a o ，+ 6 0 ，j y + c o ，j 毛 根据：z ( 叶) = 4 ，即a o ，一+ b o ，y j + c o ，2 4 。，我们求得： 厶= x + 3 y 一1 石3 x2 y + 2 五= 2 x y 显然，在上插值。类似地，我们令初始插值小波空间为g 。2 h i ，：当，e 3 ， ，e 且r ，：当，= 3 ，岛 ，而由此产生的插值小波空间记为g 。，则有： l ，( t o , i ) 2 0 ，i e 3 ；当，e e 时，r e 毛，_ ，；当_ ，= 3 时，e 3 1 ，( f 。，) 2 口4 ，当，e 3 时，毛，r ，；当j = 3 时，r 毛 我们记： g o ，j = ，j e 3 9 1 。，= h 。，当，岛时，r 易，r ，；当，= 3 时，r 如 g u ，2 o l l io 毛一：啊，= 4 ( 4 卜2 s o + + 4 一3 + g 一2 ) + z ，l e 4 ；j 6 乓， 当m o d ( ( j + 1 ) 4 ) 0 时，r e 且r m o d ( j 4 ) ( 即r m o d ( 1 4 ) ) ： 当m o d ( ( j + 1 ) 4 ) = 0 时，马 矗e 4 ，n e h ，i = 2 , 3 ，n ( 3 5 ) 类似插值点，当计算每一个插值小波g 。，时都需要做( j 1 ) 次变换，由此方 法，我们可在算法中由迭代的方法依次产生后面的插值小波。由式( 3 5 ) 有： 第三章基丁= 三角形区域的最优自适应积分 n ，2 毛，。l 啊，r i ，= 4 ( 4 1 岛+ + 4 一2 + 占f - i ) + ，e 4 m ， 当m o d ( ( j + 1 ) 4 ) 0 时，r e r r m o d ( j 1 4 ) ( 即，m o d ( 1 4 ) ) ： 当m o d ( ( j + 1 ) 4 ) = 0 时，易 毛e 4 ，聆e i ，e 4 ， i = 2 , 3 ，胛 当p 。= e n + l 时，”e h 时，有： 4 ( 4 h 占o + + 4 s s 一2 + g - 1 ) + ， = 4 。g o + 4 x ( 4 卜2 g l + + 4 s 和2 + 占- i ) + z = 4 s o + 4 x ( 4 卜2 岛+ + 4 s 卜3 + t 一2 ) + z 2 4 氏+ j 于是： ， g i + l , r ，2 t ：g i i ，j = 4 q + j q e 4 ，= 4 x ( 4 卜2 g o + + 4 8 卜3 + 占卜2 ) + ，e ， 当m o d ( ( j + 1 ) 4 ) 0 时，e g _ r m o d ( j 4 ) ( 即r m o d ( 1 4 ) ) 当m o d ( ( j + 1 ) 4 ) = 0 时，r 墨 矗i f ：e 4 ，n e i i ，e 4 ， i = 2 ，3 ，n 当i = 1 时，利用式( 3 5 ) 得： 9 2j ，= z 2 啊， ，= 4g o + z s o e 4z e 4 当m o d ( ( j + 1 ) 4 ) 0 时，r e 3 且r m o d ( j 4 ) 当m o d ( ( j + 1 ) 4 ) = 0 时，r 毛 若利用式( 3 6 ) ，有： ( 3 6 ) j 巨6 ， ( 即r m o d ( 1 4 1 ) ( 3 7 ) 9 2 j - 。r = t 9 1 。j ，2 t i h j ，j 1 = 4 s o + js q e 4l e 4j e 4 m o d ( ( j + 1 ) 4 ) 0 时，r 易且r m o d ( j 4 ) 当m o d ( ( j + 1 ) 4 ) = 0 时，如 ( 3 8 ) 对式( 3 7 ) 和式( 3 8 ) 进行比较，可以发现，这两个式子是等价的。我们可由迭代 第三章基于三角形区域的最优自适应积分 的方法由上一层的小波产生下一层的小波。对于单位等腰直角三角形上的任意层 小波，其在三角形区域上的积分面积我们有如下定理。 定理3 1 对任意固定的i ，有： p 。脚) 舭2 。( a i j , r x + 小“r ) 触2 警+ 竽+ 孚 证明： g 。，( x ，y ) d y d x 2 f j g 。，( x ，y ) d y d x l lj 2 ( q 。”6 。肘q 。，y ) d y