（应用数学专业论文）集合数据的拟合在实体造型中的应用.pdf

复旦大学硕士学位论文 摘要 在处理实体造型问题，特别是三维实体的重建问题时，一个主要的方法就是 利用三维物体的一组二维切片的图像来进行重构，也就是说，将每一个二维切片 的图像看作是一个采集来的初始的集合型数据( 通常假设为紧集) 而我们就是利 用这样得到的样本集，利用逼近算子得到一个函数值为集合的拟合函数这里基于 b e z i e r 和d eb o o r 的思想，我们利用一系列的细分算子来得到想要的拟合函数 由于对集合数据进行细分的关键就是集合的线性插值，本文对集合的m i n k o w s k l 平均和a r t s t e i n 【l 】给出的度量平均的定义作了改进，给出一种新的集合的加权 平均的定义，基于由此得到的新的集合插值，分别对一般紧集的样条细分和插值 细分作了研究，并给出了细分的收敛性性质并且，由文中的例子可以看出我们 的这种集合插值与前人的工作( 基于度量平均的插值及基于m i n k o w s k i 平均的插 值) 相比，更具合理性 关键词：集合值样条，集合插值，样条细分，插值细分 中图分类号： 0 1 8 复旦大学硕士学位论文 a b s t r a c t w h e nd e a l i n gw i t ht h es o l i dm o d e l l i n ga n dr e c o n s t r u c t i o n s ，e s p e c i a l l yt h e r e c o n s t r u c t i o no f3 do b j e c t ，af o u n d a t i o n a lm e t h o di st oc o n s t r u c tas e tv a l u e d f u n c t i o nf r o mas e r i e so f2 dd i m e n s i o n a lc r o s ss e c t i o n a ls e t s ( u s u a l l yc o m p a c t s e t s ) b a s e do nt h ei d e ao fb e z i e ra n dd eb o o r ，w ec a nu s et h es u b d i v i s i o ns c h e m e t oc o n s t r u c tap o l y n o m i a lo rs p l i n es e tv a l u e df u n c t i o nw i t hp i e c e w i s el i n e a ri n t e r p o l a t i o nf o rc o m p a c ts e ti m a g e s i nt h i sp a p e rw ei m p r o v et h ed e f i n i t i o no fs e t a v e r a g ed e f i n e di na r t s t e i n 1 1 b a s e do nt h en e wd e f i n i t i o nt h es p l i a es u h d i v v s i o ns c h e m e sa sw e l la st h ei n t e r p o l a t o r ys u b d i v i s i o ns c h e m e sf o rg e n e r a lc o m p a c t s e t sa r ei n t r o d u c e d f u r t h e r m o r et h ec o n v e r g e n c ep r o p e r t i e so ft h es u b d i v i s i o n s c h e m e sa r ed i s c u s s e d c o m p a r i s o nr e s u l t sb a s e do nt h en e wd e f i n i t i o nw i t ht h e o l do n ea r ei n c i u d e da n dd e m o n s t r a t e dt h a to u rd e f i n i t i o np o s s e s s e sm o r ep h y s i c a l m e a n i n g sf o rm o s tc a s e so ft h es o l i dm o d e l l i n g k e y w o r d s ：s e tv a l u e ds p l i n e ，s e ti n t e r p o l a t i o n ) s p l i n es u b d i v i s i o n ，i n t e r p o - l a t o r ys u b d i v i s i o n c h i n e s el i b r a r yc l a s s i f i c a t i o n ：0 1 8 l l 第一章引言 计算机辅助几何设计( c a g d ) 主要是研究在计算机图像系统的环境下，对 曲面信息的表示、逼近，分析和综合它肇源于飞机、船舶的外形放样工艺，由 c o o n s ( 1 9 1 2 1 9 7 9 ) 、b e z i e r ( 1 9 1 0 1 9 9 9 ) 等大师于2 0 世纪6 0 年代奠定理论 基础 随着计算机图形显示对于真实性、实时性和交互性的要求的日益增加，随着几 何涉及对象向着多样性、特殊性和拓扑结构复杂性靠拢的这种趋势的日益明显， 随着图形工业和制造工业迈向一体化、信息化和网络化步伐的日益加快，随着激 光测距扫描等三维数据采样技术和硬件设备的日益完善，计算机辅助几何设计近 几年来取得了长足的发展，这主要标线在研究领域的急剧扩展和表示方法的开拓 刨新 实体造型问题是c a g d 中的一类基本且广泛研究的问题，特别是三维重构 问题，长久以来都是大家研究关注的焦点它在实际生活中有着广泛的应用比 方说，医学上在设计外科整形手术、肿瘤切除手术( 这里肿瘤的大小、形状、位 置必须被准确计算出来，以便更准确的设计放射方案) 、牙科手术等等都会遇到重 构问题在此之前有很多专家作过这一方面的研究 一直以来，对三维重构问题的主要研究方法之一就是曲面重建曲面是具有 某种性质的点的集合，从理论上来讲，每张曲面都有它自己的数学模型但是曲 面的数学模型存在是一回事，人们对它的掌握又是另外一回事有很多复杂的曲 面，其数学模型并未为人们所掌握，例如人的头颅、动物的骨头、雕塑、工艺品 等外形和野外地形等为了利用计算机对这类物体和其外表曲面进行分析，首要 的任务就是为其建立数学模型对这种数学模型没有被人们掌握的曲面，建立数 学模型的过程称为曲面重建 曲面重建的基本要求是准确易行准确；要求建立的数学模型能比较准确的 反映原来曲面的形状，或者说较好的逼近原来的曲面；易行：要求对所建立的数学 模型易于进行各种操作，或者说较方便地适用于计算机进行曲面的存储、分析、 计算和绘制等 实现以上基本要求的主要方法是分而治之，化繁为简分而治之是指把复杂 的曲面分割成一块块小曲面片；化繁为简是把每块小曲面片的形状用简单的方法 来表示其中代表性的方法有以下五种： 分片线形法方法h o p p e ( 【1 1 j ) 于1 9 9 2 年提出，在曲面上采集大量的型 值点的位置信息以后，先构造拟合采样点的分片隐式曲面，再用三角片逼近隐式 曲面，最终以三角片曲面逼近需重构的曲面 1 复旦大学硕士学位论文 细分曲面法h o p p e ( f 1 2 1 ) 于1 9 9 4 年提出，通过反求控制点的方法，为 需要重建的曲面建立控制网格，然后运用一系列的细分算子，对控制网格进行细 分，生成细分曲面，来逼近需要重建的曲面 隐式曲面法m u r a k i ( 1 3 】) 在1 9 9 1 年进行的人头曲面重建中，借助于势 函数概念，用分片隐式曲面作为曲面重建的工具 参数曲面法e c k 等( ( 1 4 】) 于1 9 9 2 年提出用b 一样条曲面对任意给定的拓 扑网格进行重建的方法h a l s t a d ( 1 5 】) 等在同年提出了利用b 样条曲面构造 高精度的逼近需要重建的曲面法向的方法 变形模型法。m i l l e r ( 1 6 ) 等在1 9 9 1 年提出一种集合变形模型进行闭曲面 重建 另外一类三维重构的研究方法是整体重建整体重建不光可以研究实体的曲 面形状变化，而且可以更好的认识和研究实体内部机构和变化医学序列图像的 三维重建就是它的一个重要的应用领域一般的，人们主要是利用分解和合成的 方法分解的过程使用一簇等间距的平行平面将人体和生物体的有关部分切成一 片片很薄的切片，即将其分解成切片的序列合成的过程是将对每一个切片的观 察结果按顺序叠加起来，以形成有关部分结构的原来的空间形态，也就是说从切 片序列合成原物的模型实质上，分解过程是一个数据采集的过程，合成过程则 是一个实体重建的过程 最近几年，整体重建有了更进一步的发展在分解过程中，数据的采集量可以 适度的减少了，而且，合成的过程也不是简单的切片定位重叠，而是将每个切片 的图像看作是一个集合( 一般的不妨设为紧集) ，将这些集合看作是初始数据，利 用细分的思想得到原物体的逼近函数的过程而本文所研究的就是这一类方法 一般的，每一个n 维的物体都可以看作是一个一元的值为n 一1 维空间上的 紧集的集合值函数，我们在这里采用的切片图像就是这个一元函数的函数值我 们现在的问题就是从这样的采集数据出发，构造这样的集合值函数的插值或是逼 近( 统称为拟合) 这里我们所用的拟合方法是细分方法，特别是紧集的样条细分和插值细分， 是一般的细分方法对集合值函数的扩展但是由于集合运算与一般标量运算的差 异性，使得在将细分方法应用于初始数据为紧集的情况中时，紧集之间的运算是 至关重要的，它会影响整个逼近的精度及结论是否具有物理意义 n d y n 及e f a r n2 0 0 0 年，在凸紧集的运算中运用了m i n k o w s k i 平均：紧 集a ，b 的加权值为t 的m i n k o w s m 平均定义如下： ( 1 一t ) a + t b = “1 一) 。+ t b ：a a ，b 口) 由此给出了凸紧集的插值运算，n n f 4 条- n 分得到了比较满意的逼近结果( 参见 2 复旦大学硕士学位论文 d y n 等人的 3 j ) 但是，在处理更一般的紧集，特别是非凸紧集时，m i n k o w s k i 平均运算不能保持非凸性，会使运算结果变得很“胖”因此，2 0 0 1 年，n d y n 及e f a r k i 对这种情况进行了研究，利用a r t s t e i n 【1 】给出的度量平均来代替 m i n k o w s k i 平均：紧集a ，b 的加权值为t 的度量平均定义如下： ao cb = ( 1 一t ) 4 - ti i ( o ) ：nea u ( 1 一t ) li ( b ) + t 舻) ：b b ) 口a 其中n b ( n ) 为口中与a 距离最近的点的集合这样使得利用这样的线性插值得 到的样条细分也可以处理初始数据为非凸紧集的情况( 参见d y n 等人的 4 】) 但是，度量平均在处理有些问题时，也会出现运算结果变得很“胖”的问题， 例如图5 因此在本文中，我们给出一种新的集合插值的定义来解决这个问题 下面第二章对于细分方法的背景及常用的细分方法作了简单的介绍 第三章在简单介绍前人工作的同时，给出了新的集合插值的定义，具体讨论 了它的相关的性质我们证明了将这个新的集合插值应用在样条细分中时，细分 算法是收敛的，而且极限函数是一个l i p s c h i t z 连续的集合值函数并且，当初始 数据为凸集时，我们可以进一步证明这时细分算法具有集合意义上的保单调性 第四章在第三章讨论的基础上进一步讨论紧集的插值细分，特别是讨论了四 点法在紧集上的拓展，得到了满意的逼近结果说明了对于初始数据为紧集的情 况，当1ui 南时，四点法是收敛的 第五章给出了具体的例子，将新的集合插值与基于m i n k o w s k i 平均和基于度 量平均的集合插值作了比较 由实例可以看出，新的集合插值在处理一般紧集的问题时，是具有一定的优 越性的，它得到的结果要更具有物理意义，更符合实际情况最后给出了有待进 一步解决的问题 3 第二章标量数据的细分 2 1 细分的背景 细分算法是一个递归的过程，其基本思想如同雕塑，先从一个大概的样子， 一般是多边形或是多面体出发，去掉多余的部分，补上不足的部分一般的，是 从一些初始的散乱点开始的，这些点被称作控制点，可以构成控制多边形或是控 制网格 细分算法是由几个简单的线性规则决定的，运用这些规则，则可以从控制点 生成更稠密的点如果一个算法的这种规则选的比较恰当，就会在重复运用这些 规则的过程中，由旧的控制点不断生成新的更稠密的控制点，最终的极限会是一 个连续的曲线或是曲面整个过程是递归的、稳定的。这种算法不光可以有效地 生成曲线或是曲面，而且还可以决定曲面的交点，得到分层曲线或是曲面等等 尽管细分算法比较简单，但是极限函数的分析有可能会比较复杂例如，将 一个平面多边形的每条边顺次的按照i 1 ：j 1 ： 的比率分割，然后对生成的新的多 边形重复此过程，如此下去，会得到一列多边形，并且它们收敛到一个连续可微 的曲线这个方法最先由r h a m ( 【1 7 1 ) 提出，后来由c h a i k i n ( 【1 8 】) 作了细 致的分析和推广，并且指出这样的细分收敛到一个二次的样条函数因此，这种 细分算法被称为c h a i k i n 细分若将初始数据记为 艘) ，舞舻，z ， c h a i k i n 细分可以写成如下的形式： 苊= i 盘1 + i 芹叫 ，= ；群+ ；乒1 d er h a m 给出一个更一般的形式： 鸡= ( 1 一u ) 1 + u 芹一1 盛+ l = u 点1 + ( 1 一u ) 片一1 其中 u 1 我们可以将以上的公式看作是两条利用旧的控制点生成新的控制点的运算规 则，因此我们可以给出一种更一般的形式： 像= - - 十一2 疑+ o j i 一1 + o l 2 & + - 悠+ l = + n 一。1 + q ，骨一1 十q 。贮j 1 + 这在【6 中有详细的分析 4 复旦大学硕士学位论文 因此由以上的分析，我们可以将细分算法概括得写成以下的形式 贮= a a - 2 b f ；。1 口三 其中= f o t 。：a z ，为一个有限支撑的实数列不同的细分算法有不同的 2 2 样条细分 这一节中，我们来研究一类可以生成b 一样条曲线的细分算法，即样条细分 算法： 定义2 2 1 当给定 定 ，舞舻，。z ，m 阶样条细分为： 詹= n 掣。口站，q z ，k = l ，2 ，3 ( 2 2 1 ) 其中 n 非2 0 ：戮搿麓) 十。， 令，= 业in z c 虢由以上定义可以看出，可以看作是由以下一 系列的二元平均得到： 算法1 ： ( i ) 令 矗掌= 拦一1 ，以嚣。= ；( 盛一1 + 咒k + - 。i ) ，o z ( 2 ) 当l j m l 时 t ? 2i ( 业。1 十e k “, j - - 1 ) ，口， 其中 l5 霎搽萋 ( 3 ) 最后，令 跫= 露，“一当m 为奇数，z 站= 写1 当m 为偶数，。z 注意到：c h a i k i n 算法就是以上算法当m = 2 时的特殊情况： 鹰= ；盘1 + 1 ： 盘。= ；如1 + 1 独盘1 + 芹一1 ) 十骨。1 ， = ；f 虎1 + ；( 如1 + ”一1 ) 】 5 复旦大学硕士学位论文 对于任意的，相应的分段线性插值函数为： ：( - 一警) 髓+ ( 警) ， 其中0 2 一t ( q + 1 ) 2 一 定理2 2 2 ( ，。( t ) 为k 层细分时相应的线性插值函数，则( ，( c ) 在跪上一致 收敛于函数，。( ) ，其中 尸( ) = 月b m ( f z ) l z t 瓣，( ) 为m 次日样条函数 证明详见【7 】 2 3 插值细分 细分算法也可以生成插值型曲线 定义2 3 1 若一个细分算法具有以下形式 搿1 = 芹，傲j = q 以，i z ，k z 十 j 则这种细分叫做插值细分 以上的插值细分的定义是单参数的，不同的系数会得到不同的细分，例如d y n 的 9 】中给出的四点法就是其中的一种特例： 四点法也可以写成以下的加权平均的形式： 注2 3 1 _ 1 i 2 k n + 1 1 i 2 k 礼 ( 2 3 1 ) 爿，1 = 辟 一1 i 2 n + 1 腻= 【l 一( 一2 u ) 】( ；劈+ ；辟。) 十( 一2 u ) ( ；难，+ j i j l 十k 。) 一1s i 2 n 定理2 3 2 若给定辟= ，2 is 扎+ 2 ，令 在点2 “i ，一2 i 2 k n 十2 ，k 0 上的值如下式中给出： ，妒1 = 力 一1si 茎2 扎+ 1 以尊j = ( ；+ u ) ( 一+ 盛，) 一u ( 业。+ 盛。) 一l i 2 k n 则当iul j 时，存在，c o ，n 1 使得，( 2 “i ) = 站，0s 2 k ，k o 6 盘 十 雎“ 一 虑 十 骨 u + 芹哼 = = 搿璐 复旦大学硕士学位论文 定理2 3 3 若，c i o ，n 】为细分俾，3 ，得到的极限函数，且iui i 1 则当 uj 0 基于m i n k o w s k i 平均的样条细分在处理初始数据均为凸紧集时，可以得到比 较满意的结果。 例3 1 3 若我们选择两个不同的凸紧集，如图中所示的a 、b ，则当对插值函 数取不同的参数时，可以得到不同的插值结果： i 图j ：基于m i n k o w s k i 平均的插值，从左到右依次为：a ，0 7 a + 0 3 b o 3 a + 0 7 b b 3 2 基于度量平均的紧集的样条细分 虽然上一节中基于m i n k o w s k i 平均的样条细分在初始数据均为凸紧集时有 比较好的结果，但是，当初始数据为非凸紧集时，这样的样条细分得到的极限函 数与由初始数据的凸包同样细分得到的极限函数是相同的，也就是说，此时基于 m i n k o w s k i 平均的样条细分会使结果变得很“胖” 例3 2 1 若我们选取两个如下的非凸紧集a 、b ，可以看到，它们如下的 m i n k o w s k i 加权平均得到的均为凸集 9 复旦大学硕士学位论文 o o 图2 ：基于m i n k o w s k i 平均的插值，从左到右依次为：a ， 0 7 a + o 3 b ， 0 3 a + 0 7 b b 为了解决这个问题，d y n 等人用a r t s t e i n 【1 中给出的度量平均来代替m i n k o w s k i 平均( 见d y n 等人的( 4 】) 定义3 2 1 若4 ，b 尤( 渺) ，则它们的加权值为t 的度量平均为： a 。b = ( 卜) o ) + t ( o ) ：o a ) u ( 1 一t ) ( 6 ) + t 斜：b b ) 日a 其中n 且( ) = d b ：l n b = d i s t ( a ，b ) 定义3 2 2 k ( 舻) 中a 、b 之问的h a u s d o 啊距离为： h ( a ，b ) = m a x s u p d i s t ( x ，b ) ) ，8 u p d i s t ( y ，a ) ) ) x e a y e b 若记a f ( a ，t ，b ) ；u ( ( 1 一t ) n ) + t n b ( 凸) ) a c a 则 a o t b = m ( a ，t ，b ) u m ( b ，l t ，a ) 性质3 2 2 令4 ，日，a k ( 跪”) ，0st 茎l ，01s 1 ，则以下性质是成立 的： 口m ( m ( a ，t ，b ) ，s ，b ) = m ( a ，s ，b ) 俐m ( a n b ，t ，b ) = a n b m ( b ，s ，a ) i ao b = ( anb ) um ( a 一目，t ，b ) um ( b a ，1 一t ，a ) ( 4 ) a e o = a ，a g l = b ，ao tb =b o l ta 5 ) a o t a = a 俐a o tb ( 1 一t ) a + t b c o ( a ub ) r 动若b c ( 舻) ，且a b ，则当0st s 1 时，a 至a t b a o ，b b 俐 ( a o b ，a o 。b ) = i t s l h ( a ，b ) 特殊的，当在k ( 卵) 中考虑时，度量平均有一些特殊的性质 性质3 2 3 a ，b k ( 瓣) ，c ，d g ( 虢) ，t 0 ，1 】，月1 j f j co td = ( 1 一t ) c + t d ( 2 ) f f ( a o cb ) = ( 1 一t ) f ( a ) + p ( 日) 性质3 2 4 a 1 ，a 2 ，b 托f ( 虢) ，贝1 l a l0 b = a 2o tb = a 1 = a 2 l 【) 复旦大学硕士学位论文 以上性质的证明，详见n d y n 等的【5 1 ， 现在我们利用算法1 ，将算法( 2 21 ) 扩展到初始数据为 艘) 。z 的情况 其中艘圪( 渺) 算法2 ： ( 1 ) 令 础= 蜀k 。, 0 + 1 = ( 2 ) 当1sj 曼m 一1 时，定义 唆 = 磁卜1 。 磷o 其中 2k 薹；淼 ( 3 ) 第k 次细分时的元素定义为 磁= 磁，仇。i l l 为奇数时 磁= 磁罢。m 为偶数时 其中q z 因此，对应的分段线性插值函数为： f 。( t ) = 磺0 2 t t 一。磁+ 1 ，2 一。t ( o + 1 ) 2 一 定理3 2 3 f 。( - ) ) 一致收敛于关于h a u s d o 哂度量l i p s c h i t z 连续的集合值函数 f ”( ) ，并且l i p s c h i t z 常数为l = s u p h ( 瑶，f 。o + 1 ) a 这样的算法在处理初始数据为非凸紧集时，得到的结果比基于m i n k o w s k i 平 均得到的结果理想 例3 2 5 我们选取两个如下的不同的非凸紧集a 、b ，他们的度量加权平均如 下： oooo 图3 ：基于度量平均的插值，从左到右依次为： a ，a o o3b ，a 0 07b ，b z 噶 。 一 一 肿。甓 复旦大学硕士学位论文 3 3 新的集合插值的定义与性质 在上一节中，我们介绍了基于度量平均的一般紧集的样条细分，事实证明，这 样的细分算法是收敛的，并且从例子可以看出，在某些情况下，得到的结果也是 具有一定的物理意义的然而，度量平均在某些情况下也会使得结果很不理想， 比方说当我们想要复原一条分叉血管时，用度量平均做出来的结果会出现第三个 分叉( 见第四章中图5 和图7 ) 这个结果并不符合实际情况，为此我们引入一 种新的集合插值来解决这种问题 定义3 3 1 a ，b k ( 辩) ，0st 曼1 ，当加权值为t 时，a 、b 的新的集合 插值函数的相应函数值为： a u t b = ( c o a o c o b ) 一( ( c o a a ) o t ( c o b b ) )( 3 3 1 ) 注3 3 1 事实上，这个定义对于t 睨也是成立的 现在我们给出新的集合插值的一些相关性质： 性质3 3 2 a ，be 托( 瓣”) ，0st l ，则新的集合插值具有： 门，端点插值性： 4 刨ob = a ，a | | lb = b f 剀对称性：a 姚b = bu ( t 一) a 佃j 自反性：a 剞ta = a “，有界性： anb 以出b ( 1 一t ) a + t b c o ( aub ) r 彤单调性：若0 t c o a = c o b ，a = b 因此，当且仅当a = b 时，d ( a ，b ) = o ( 3 ) 由h a u s d o r f f 距离的性质可得 d ( a ，a ) = ；h ( c o a ，c 。g ) 十； ( 4 ，g ) ；h ( c o a ，c 。b ) 十i ( c 。b ，c 。e ) + ； ( a ，b ) + ； ( b ，g ) = d ( m ，b ) + d ( u ，c ) ( 4 ) 由定义， d ( a 出。b ，a | | 。b ) = ；h ( c o a 。c 。b ，c 。a 。c 。b ) + ； ( a 。b ，a 。b ) 由h a u s d o r f f 距离的性质可得 h ( c o ao c o b ，c o ao sc o b ) = i t s l h ( c o a ，c o b ) h ( a o b ，ao 。b ) = i t s l h ( a ，b ) 复旦大学硕士学位论文 因此 d ( a 姚b ，a 叫。b ) 1 = i t s 】；( ( c o a ，c o b ) + h ( a ，b ) ) = l t s l d ( a ，b ) 性质( 4 ) 得证口 注3 4 2 由以上性质可以看出，d ( ，) 为一个度量 定义3 4 1 a k ( 咿) ，平行体山记作： 4 十5 = 石啦“：d i s t ( x ，a ) sd ) 其中6 0 这儿，我们给出一个h a u s d o r f f 距离的等价定义 定义3 4 2 a ，b k ( 晚“) ，a 、b 的h a u s d o 哟。距离为 h ( a ，b ) = i n ， 620 ：acb 十6 ，bca + 6 ) 首先我们给出以下的扩展引理： 引理3 4 3 ( 舻，i i ) 为度量空间， a ；圪( 跪“) ) 箸为关于a ( - ，) 的c a u c h y 列， 唧) 驾为一无限正整数列：0 n l n 2 0 ，存在n z + ，使得当n n 时，aca 。+ ( d ) a 是完全有界的，因此由( b ) 可知a 为紧集 f e ) l i ma l = a 1 6 复旦大学硕士学位论文 ( a ) 的证明：要证明a 0 ，只须证舻中存在一个c a u c h y 列 a i a ) 就 可以了 由已知条件，存在一个正整数列n l 2 3 0 ，选取正整数l ，使得凳t 击 n m 时，有 ix 。一z 。l ix n m z w 。+ 。i + lz 。+ 。一z 。+ ：i + + fz 一。一。 墨肌寺 e 由扩展引理，存在一个收敛子列o t a t ，使得o m2z 挑，因此，t l i m o o a 。的极限 存在，并且 f i m a i a 因此，a o ( b ) 的证明：要证明a 为闭集，设a ，a ，f i m a ，= a ，只须证a a t o o 对z + ，存在一列 翰，。a 。) ，使得 l i m z l m = a z 1 7 复旦大学硕士学位论文 由f t m n 。= n ，存在单增正整数列 墨。，使得 l + 。 存在整数列 m 。 ，使得 1 f a n i x n i 。1 0 ，存在正整数，对任意m ，n n ， ( a ，) i 因此 a m c a 。+ 丢 对于n n ，令y a 。，则存在单增的正整数列 m ) ，n l 2 ； 当仇，k g j 时， a mca k + 赤 注意到a n a v + i ，既然y a 。，存在。1 a n l ， z 】一yi s ； 1 9 复旦大学硕士学位论文 继而，存在z w ：a 2 ， 一 x n i x n 2l s 云 用类似的方法，可以找到一列z 。2 ，茁满足 z w ，a m i 。一。+ 。i 曼刍i 重复利用三角不等式，可得 y 一。i e v j 并且 z 为c a u c h y 列假设 z ) 收敛到z ，z a 因为 y 一。屿l e 所以 y 一9 5j se 因此，当礼n 时， a 。ca + e 故而 l i ma 。= a 综上所述，一( 舻) 关于度量，l ( ，) 是完备的口 定理3 4 5 d ( ，) 与h a u s d o r f f 度量 ( - ，) 等价 证明：对任意的a ，b k ( 舻) ， d ( a ，b ) j h ( a ，b ) 设h ( a ，b ) = q ，由上述定义， a c b o ，b c a 。 因此 c o ac ( c o b ) 。，c o bc ( c o a ) 。 事实上，对任意o c o a 存在t 0 ，1 、a l ，a 2 a 使得 a = f 1 一t ) a l + t a 2 因为ac 玩，所以存在b 1 ，b 2 b 使得 d i s t ( a ；，b t ) 曼o l ，d i s t ( a 2 ，b 2 ) 茎o t 复旦大学硕士学位论文 因此 d i s t ( ( 1 一t ) n l + q 2 ，( 1 一t ) b l + t b 2 ) d i s t ( ( 1 一t ) a l + 。2 ，( 1 一t ) a t + t b 2 ) + d i s t ( ( i t ) a l + t b 2 ，( 1 一t ) b l + t b 2 1 = t d i s t ( a 2 ，b 2 ) + ( 1 一t ) d i s t ( a l ，b i ) s 因为( 1 一t ) b l + t b 2 c o b ，所以c o ac ( c o b ) 。类似的c o bc ( c o a ) 。所以 h ( c o a ，c o b ) 冬q = h ( a ，b ) 因此 h ( a ，b ) d ( a ，b ) 去 ( a ，b ) 命题得证口 定理3 4 6 k ( 跪“) 关于度量d ( ，) 是完备的 证明：由前面定理可知k ( 舻) 关于h a u s d o r f f 度量是完备的，既然h a u s d o r f f 度 量与d ( ，) 等价，则命题显然成立口 引理3 4 7 f = 磴) 定义如上，d = s u p d ( 咒k ，磁1 ) ，则 o 彳 d 。2 - k d o( 3 4 ，6 ) 证明：记驴，j = s u p d ( 咒k u ，磁。) ) ，由( 3 4 1 ) 及d ( ，) 的性质，我们有 n j d ( f , 2 ，k 。, o + 1 ) 茎；d 肛1 ，z d ( 碟，咝。) s ；d 1 ，qez 因此d 邶 d 1 因为 所以 d ( 磁乏，蹬。1 ) - - d ( ? k a , j - l , 碟 ) ；a ( f ： 2 7 1 ，皆一1 ) 十；d ( 审，磁f 1 ) d k , j 一1 2 1 一 一 ( n + 1 ) 2 “时，必存在正整数口，使得 ( a + 芦) 2 一。t + h5 ( o t + 卢+ 1 ) 2 一 由新的集合插值的单调性可得 f “( q + p ) cf 2 ( t + h ) 由于初始数据是单增的，所以 f ( 。+ 1 ) cf ( + 卢) 因为 f “( t ) cf “( o + 1 ) 因此f 。( ) cf 。( z + h ) 对任意、h 0 均成立，从而f 8 ( ) 为单增的因此 f o 。( ) 2l 鳃f ( t ) 也是单增的口 2 4 箱四章紧集的插值细分 4 1 基于新的集合插值的紧集的插值细分算法 如同第二章中讨论的，插值细分的算法有好多种，利用第三章中给出的新的 集合插值的定义，我们可以讨论初始值( 露 邕。为紧集的插值细分的情况在这 里，我们以四点法为例进行讨论 首先给出拓展到紧集上的四点法算法的定义； 定义4 1 1 若给定初始值 砰，c ( 蹰“) 誉2 ，则相应的四点法算法定义如下： 其中u 乳，= 0 ，1 1 i 2 k n + 1 1 i 2 k 扎 4 2 细分算法的收敛性分析 根据以上的定义，我们给出以下引理 引理4 2 1 f = ( 堙) 定义如上，d = s u p d ( 磁，珞1 ) ) ，则 o 彳 d 2s ( 6 + i ) 叼 ( 4 圳 证明：由以上细分法的定义 类似的 d ( 磁+ ”磁) = d ( ( 砖一1 圳；j 耘1 ) 叫( 一“) ( f 蔓1u ；，尊) ，砖一1 ) d ( ( 露一1 出 f 翁1 ) | | ( 一灿) ( f 高1 目 f i + 一2 1 ) ，礞一1d ；f 翁1 ) + d ( ( 辟。1 叫；赡1 ) ，劈。) 墨21u1d ( 霉一1 氆；列暑1 ，f 蓦1 勘 曩k 十- 2 1 ) 十 d ( 砖一1 ，e k + - 1 1 ) 2luj ；d ( f 蓦1 ，劈一1 ) + d ( 磅一1 ，e 冀1 ) 十j 1 叫，件k - 1 1 ，f i + 一2 1 ) + d ( 磷，残1 ) d ( 磁聪+ 。) s 2ui 嚏3 d f - 1 ，砖一1 ) + d ( 磷一1 ，f 甄1 ) + i 1 叭r l + k - 。1 ，牦1 ) + ；d ( 砰一，浅1 ) 碴 睦 u吨 u 彘件 f 盖 = i l 搿莨i 皇盔堂翌主堂垡鲨塞 2 6 因此 d 冬( 6 ui + ；) 铲一1 从而 d ( 6 【ui + ；) d o 命题得证口 引理4 2 2 f ( ) k 4 为层细分时相应的分段线形插值函数，则 h ( f ( ) ，矿( t ) ) 6 ud 。，k 4 ( 4 2 2 1 证明：记p ( ) 为后次细分的分段线性插值函数，在区间f 2 一。 ，2 一( i + 1 ) 】上 f 胖1 ( ) 与胪( - ) 的最大距离为： 矗( 垅k t 仙l 辟出；碟l ) = d ( ( 露u 礤- ) 出( 山) ( 罐。出 = d ( ( 露u 磷t ) 出( 山) ( 硭。出； ( 硭d 磷z ) | | 。( 碓。出；碴。) ) | 一2 w l d ( f 出 硌1 ，碴l 出 磷2 ) 凼为 d ( 露u 硌l ，砖，出；磷2 ) d ( 礞出 磷1 ，罐。) + d ( 硪l ，难。出；璐2 ) d ( 彤出 磷- ，硭) 4 - d ( 球，碓。) + d ( 碴，碴。) ；d ( 霹，麟t ) + 酬砖，罐。) + d ( 雅。，露) + ；d ( 露，磷i ) + j d ( 碴。，碴。) 2 d ( 碴，露j + d ( 辟，磷。) + ；d ( 硪。，碴。) 因此 h ( y + 1 ( ) ，f ( + ) ) 冬6fuj 功劳 d ( 霹，群，) ) s6ud 命题得证口 定理4 2 3 给定f 孽) 甚竺2 ，露如上定义，一2 i 2 k 扎+ 2 ，k 0 相应的 分段线性插值函数记为p ( ) 则对任意 u 去，存在连续的集合值函数f ，使得d ( 胪( t ) ，f ( ) ) 一0 ， k 一+ 。，且，( 2 一习：砰，0 i 2 n ， k 0 证明：由以上引理可知： h ( f 抖1 ( 一) ，f 。( ) ) s6ud 啮件 f 露 力0 磷碑 复旦大学硕士学位论文 d s ( 6 uf + ；) 2 d o 从而 1 愚( f “+ 1 ( ) ，f 。( ) ) s6u 】( 6 ui + 去) k d o 因此，若l 而1 ，函数列( p ) 为c a u c h f 列，且收敛于一个连续的集合