（基础数学专业论文）曲线的一类非线性多分辨率细分算法的研究.pdf

中文摘要 本文主要研究了一类曲线的多分辨率多进制算法。从已有的线性多分辨率细 分算法出发，用对应弦三分的方法来构造一类三进制的多分辨率细分法则。并且 在三进制模板上给出诱导算法的定义，让生成的近似曲线达到更高的光滑性。 文章先在第二章中2 1 中给出非线性三分多分辨率细分算法的定义以及 主要结果，然后在2 2 中给出证明所用的相关的一些引理，在2 3 中给出主 要定理2 1 的证明过程，定理2 1 证明了上述定义下的细分法则是一种细分算法。 同时研究了这个正则三分多分辨率细分算法的收敛性和稳定性，证明了基本的正 则三分细分算法生成的极限近似函数满足l f p 阻0 l o g i 垃i i “。2 4 中给出定理2 2 的证明过程，证明了小波参数精密地依靠基本的细分算法。正则多分辨率近似的 收敛性等于这个基本细分算法的收敛性。 在第三章中，通过对模板的研究，在3 1 中给出一类基于第二章基本三分 细分算法的诱导细分算法的定义以及基本性质，此类e h = 进制模板推导的诱导算 法，可以让细分算法生成的近似曲线达到更高的光滑性。在3 2 中，给出了此 类诱导算法收敛性的证明。在3 3 中给出了一些具体的三进制细分算法的例 子。 关键词：多分辨率细分算法，正则三分法，多分辨率近似，小波参数 d a b s t r a c t i nt h i sp a p e rw eg i v ean e wn o n n a lt r i a d i cs u b d i v i s i o ns c h e m ei ft h e m u l t i r e s o l u t i o na n a l y s i so fac u r v ei sn o r m a l a n ds t u d yn o r m a lt r i a d i cs u b d i v i s i o n s c h e m ep r o p e r t i e s s u c ha sm g i l l a r i t y , c o n v e r g e n c e a n ds t a b i l i t y ，kp a r t i c u l a rw e s h o wt h a tt h e s ew a v e l e t sc o e f f i c i e n t c r i t i c a l l yd e p e n d 0 1 1t h en o r m a lt r i a d i c s u b d i v i s i o ns c h e m e i nt h ec h a p t e r1 i ，w eg i v ean e wd e f i n i t i o no f3 - b a n dn o r m a ls u b d i v i s i o ns c h e m e ， a n dg i v et h ep r o v eo ft h es u b d i v i s i o ns c h e m e i nt h e 2 2w eg i v es o m el e m m a s p r o v ew h i c hb eu s e di nt h em a i nr e s u l t sp r o v e i nt h e 2 3w eg i v et h em a i np r o v e ： l e t x ，j ，0 c ，口，v ，s 3 b eg i v e na s 胁a b o v es e c t i o n s , s u p p o s et h o s ej , k , s u c ht h a t ti ? k = k 3 一i l ，w h e r eii sa ( p o s s i b l yi n f i n i t e ) i n t e r v a l 。l e t 妒jb ea p i e c e w i s el m e a r f u n c t i o n ，伊j 矗) 妇t h e p o i n t ( x m ) a tt ”。i fi 。 o 。，t h e n t h e r ee x i s t s a f u n c t i o n 妒c 1 ( ，) ，s u c ht h a t 仍一伊u n i f o r m l ye x p o n e n t i a l l y a n d ( ps a t i s f i e s 腩p i n e q u a l i t y j f 平( f + f ) 一似f ) f 。- c l 血l l i n g w l l 。 v f ，f + e ， ， 3 一。i 4 ( 3 一十1 h lt h e 2 4w eg i v et h ew a v e l e t sc o e f f i c i e n tt h e o r e m a n d p r o v e t h e c o n v e r g e n c eo fw a v e l e t sc o e f f i c i e n te q u a lt ot h ec o n v e r g e n c eo fb a s i cs u b d i v i s i o n s c h e m e i nt h ec h a p t e rl i l ，w e 百v et h ed e f i n i t i o no ft h ed e r i v e ds u b d i v i s i o ns c h e m e s w i t hs t u d y i n gt h e3 - b a n dm a s k 3 - b a n dn o r m a ld e r i v e ds u b d i v i m o ns c h e m ec a nl e tt h e c u r v eg e th i g hl u b r i c i t y i nt h e 3 2w eg i v et h ep r o v eo fc o n v e r g e n c eo ft h e d e r i v e ds u b d i v i s i o ns c h e m e s ，a n di nt h e 3 3w eg i v es o m ee x a m p l e so ft h ed e r i v e d s u b d i v i s i o ns c h e m e s k e y w o r d s ：s u b d i v i s i o ns c h e m e ，n o r m a lt r i c h o t o m i z e d ，m u l t i r e s o l u t i o n a p p r o x i m a t i o n ，w a v e l e t sc o e f f i c i e n t 5 第一章细分格式概述 本章首先在1 1 中描述了细分方法产生的历史背景及其发展过程，阐述了 细分方法的基本思想，在1 2 中介绍细分格式的一些基本定义，基本工具和一 些基本结果。最后介绍一些经典的细分格式。这些是本文研究的基础。 1 1 历史背景 细分方法起源于曲面造型。由于在实际工程中对于大型复杂设备外形的研究 和改进的需求，于是在计算机辅助几何设计和计算机图形学中，曲面造型的研究 就成为了个热点。 从1 9 6 3 年开始，先是在飞机制造领域，继而在汽车等其他工业领域，人们 渐渐对于参数控制的曲线曲面的研究发生了浓厚的兴趣，得到了一些参数控制曲 面的研究成果。 但是这些参数曲面，不能表示任意拓扑结构的曲面，极大限制了曲面造型的 在现实工作中的应用，远远不能适应计算机辅助集合设计以及计算机图形学中对 于显示真实性、实时性的具体要求。同时随着计算机辅助几何设计对象的多样性、 特殊性和拓扑结构复杂性的逐渐提高，普通参数曲面已经不能满足这一需求。细 分方法( s u b d i v i s i o n ) 正是应这种要求而产生的。 1 1 1 相关：亡作 细分方法最早可追溯到1 9 5 6 年r h a m 提出的一种称为“c o m e rc u t t i n g ”细 分算法。该算法的思想就是将平面上的一个多边形的每一条边按i ：2 ：l 的比 例分割，然后通过割角，得到一个新的多边形。不断的重复此过程，就得到一个 多边形序列。它的极限是一条连续可微的曲线。 由于这一算法具有很快的收敛速度，1 9 7 4 年c h a i k i n 2 1 把该算法做了进一步 推广。 1 9 7 8 年，c a t m u l l c l a r k t 3 1 以及d o o s a b i n 4 1 分别给出了在任意网格上设计双三 次和双二次曲面算法。1 9 8 4 年，c o h e n 、l y c h e 和r i e s e n f e 膨5 1 以及d a h m e n 和 靠c 幽8 f f ，6 1 又分别给出了b o x 样条曲面的细分算法。随后又提出了很多著名的细 分算法，如l o o p 算法、蝶型算法等。与此同时，细分方法理论方面的研究也得 到了很大的发展。单变量细分格式具有任意阶光滑性的充要条件7 。8 】的提出以及 多变量细分格式在任意拓扑情形下收敛性分析的理论框架9 4 1 1 的建立，揭示了各 种细分格式的内在联系。细分方法如今已成为曲面造型理论研究和实际应用中的 热点。 1 1 2 细分格式的基本思想 对于曲线曲面的细分格式而言，由上一层点集计算下一层点集的计算规则一 般要求具有以下一些性质： 可以高效的由上一层的点集计算得到新的下一层点集。 初始点列网格上任一点只能影响极限曲线曲面的有限局部。 新点的得到只依赖于原始曲线曲面拓扑上相邻的有限个点。 若初始网格平移、放缩或旋转，极限曲线曲面也被同样变换，拓扑结构不变。 规则简单，易于计算。 极限曲线曲面应具有一定的光滑性，光滑性由具体的细分方法而定。 细分方法作为一种原始曲线曲面的近似曲线曲面的生成工具，其实质是一种 迭代算法。基本思想就是逐次加密，从初始的点集出发，采用细分规则计算插入 新的点并不断加密加细，并最终生成极限曲线曲面。 1 2 细分格式的一些基本定义和研究进展 本小节简述细分格式的一些基本定义以及一些现有的研究进展。 定义1 i ： 细分格式( s u b d i v i s i o ns c h e m e s ) 是定义在网格点集序列上的一系列细 分规则集合，每一个细分规则将定义在实数域上的网格点集映射到新的网格点集 上。细分格式就是利用这些细分规则对于给定的初始网格点集进行逐次细化。 细分规则在第k 层具有形式： 丘“= 口 ( 1 1 ) 口 其中，为k 层的网格点集序列，“1 为k + l 层的网格点集序列，a 为k 层的细 分规则。 上式可以将其记作算子的形式： 系数集合a 称为第k 层模板，它确定了第k 层的细分规则。如果模板与细分 层次k 无关，那么就称细分格式是稳定的，否则就称为非稳定的。对于非稳定的 细分格式，它的第k 层的细分规则由a 2 确定。 细分格式可以记做s o l ，或写成算子集合的形式忸矿j 。 若下一层点列中包含上层点列，则它对应的细分格式称为插值型细分格 式，否则称为拟合型细分格式。 i _ 己a ( a 。) = 忉i d ：o j 是模板d 的支集。如果仃( 口) 是有界的，则称模板d 是 紧支的。现阶段对于紧支的情形理论比较完善。 1 2 1 细分格式的收敛性的定义 定义i ，2 ： 给定初始点集，。，连续函数，称为，。关于细分格式沁- 的极限 函数，如果 脚s up | 露一i i = o ( 1 2 ) 这个极限函数也可记做s i t ，。其中，f 由( 1 1 ) 递归定义a 同时，与某一紧集上的每一细化层上通过这些插值点的线性折线样条函数 序列慨) 的一致极限函数是等价的，也就是说 疋) 满足： r ( f ) = 露( f ) ( 1 _ 3 ) 其中t 是k 层上的插值点。 从这一等价性可以得到： 憋s u l _ f ( t ) 一 ( f ) f _ 0 ( 1 4 ) 定义1 3 ：细分格式称为一致收敛的，如果对于任意的初始网格点集，存在一 个形如( 1 2 ) 的极限函数，或等价地，存在一个形如( 1 - 4 ) 的分段折线函数的 极限函数：并且至少存在一个初始网格点集，使得极限函数是非平凡的。 一致收敛的细分格式，如果对于任意初始点集，它的极限函数存在m 阶连续 导数，则这个细分格式称为c 1 或c “收敛的 n d y n 和d l e v i n 【1 2 1 的文章给出了基本极限函数的一些结果。l d a u b e c h i e s 和j c l a g a r i a s l l 3 1 的文章则研究了基本极限函数和细化方程的关系：如果不考虑 乘数因子的因素，细化方程的解是唯一解。在求解细化方程时，l d a u b e c h i e s 1 4 1 使用了一种并不求细分格式基本极限函数的方法。 1 2 2 生成多项式 作为分析细分格式收敛性和光滑性最重要工具的细分规则( 1 1 ) 也可以表示 成z 变换( l a u r e n t 级数) 的形式。定义模板a 的生成多项式为l a u r e n t 多项式： a k ( z ) = z 8 ( 1 5 ) 舵z 显然，一个细分格式s 川可以由生成多项式集合f 4 2 ( 。) 唯一确定。研究中 并不严格区分模板和它的生成多项式。 对于细分格式收敛性的研究，0 r i o u l l l 5 1 研究了单变量细分格式，给出了更精 确的结果。对于变量细分格式的收敛性和细化方程的解之间的关系， c a m i c c h g l l i 和h p r a u t z s c h 1 6 1 及mn e a m t u 1 7 1 建立了稳定细分格式收敛性和非 稳定细分格式收敛性之间的联系。同时得到了非稳定细分格式生成的基本极限函 数的光滑性的结果。e c o h e n ，z l y c h e l 5 1 和a s c a v a r e t t a ，w d a h m e n l 7 的文章也研究 了此类问题。 最简单的细分格式是单变量稳定均匀细分格式。n d y n 和d l e v i n 【1 2 1 对于 均匀非稳定基本细分格式做了比较细致的研究。 插值型的细分格式，是目前得到的研究成果较多的一种细分格式类型。u d y n ， j a g r e g o r y 和d l e v i n 1 9 1 s d u b u c 1 8 1 u o y n ，a g r e g o r y 和d l e v i n 都在此 领域做了比较深入的研究。k u q t 和v a nd a t u m e 2 1 1 给出了一种非线性、稳定、具 有保形性的4 点插值细分格式。从一个具有严格凸性的初始点集出发， 2 1 中证 明了其极限函数是严格凸的，且属于c 1 。k u i j t 和v a nd a m m e 还进一步得到它具 9 有保单调性2 珥的结果。 进步，还可以应用该保形细分格式，在一定条件下，从一个严格凸的初始 点集得到一个凸的基本极限函数2 3 1 。 此外，还有矩阵细分格式、h e r m i t e 型细分格式、；细分格式等很多细分 格式。这些细分格式的研究工作可以参见文章t 3 6 - 3 8 1 。 更进一步，对于3 d 空间上具有任意拓扑结构的网格细分格式。早期的工作 有c a t m u l l 和c l a r k 3 1 以及d o o s a b i n 4 1 的工作。1 9 8 7 年l o o p 2 踟用一种b o x 样条 构造了任意三角形网格的二分细分算法。最近则有许多细分格式被提出【2 9 - 3 3 1 。 但是，现阶段几种细分格式的研究主要几种在线性邻域，对于多进制非线性 的细分方法研究的很少，本文第二章、第三章的主要工作就是给出了一种非线性 三进制细分法则的定义，并研究了这类三进制非线性细分法则的一些性质，同时 从这个细分法则里面得到了一类基于这个基础三分算法的诱导细分算法。 1 0 第二章非线性三分多分辨率细分算法 第二章主要研究了一类曲线的多分辨率多进制算法，从fd a u b e c h i e s 与 nr u n b o r g 提出的对分法线细分算法 2 4 中得到启发。用对应弦三分的方法来构 造一类三进制的多分辨率算法。 我们先在2 1 中给出非线性三分多分辨率细分算法的引用、定义以及主要 结果，然后在2 2 中给出证明所用的相关的一些引理，在2 3 中给出定理2 1 的证明过程，研究正则三分多分辨率细分算法的收敛性和稳定性，证明了基本的 正则三分细分算法生成的极限近似函数满足l 咖l r i | l o g i 出旷。2 4 中给出定理 2 2 的证明过程，证明了小波参数精密地依靠基本的细分算法。正则多分辨率近 似的收敛性等于这个基本细分算法的收敛性。 2 1 细分法则的定义及主要结果 一下面先给出下文中用到的一些符号的定义： ( 1 ) s ，：即为文中定义的曲线上非线性三分多分辨率细分法则。例如对于 点列 x 。 ，s ，工j = z j + 1 l 即在点列 工，l 上应用下文定义的细分法则后得到的 下一层的点列f z 。 。 ( 2 ) il ：是下文中常用到的极大范数，f x l 。= s 印i 以i 。 ( 3 ) 为差分算子：( x ) = + 。一x 。， k 为整数。 ( 4 ) ( p c ”( ，) ：函数( p 弱p 阶可微， c - ( ，) = ( p i l 币o + f ) 一似f ) l - c l 出l i l o g l 血l l “ 二三进制细分法则的定义： 对于原始光滑曲线上采样得到的原始点列，先从相邻点的具体坐标值来计算 这对相邻点之间的局部法向( 仿照上g u s k o v 与冗v i d i 口c e 在 2 8 中的方法) ，然 后基于这对相邻点的弦三分和这个局部法向来计算得到原始曲线在这对相邻点 之问的下一层点列，通过细分法则的迭代计算，就得到原始曲线的多分辨率逐层 点列，以及逐层的小波参数的长度。 如下图所示，设只，只是原始点列中相邻的两个点，把这两个点由直线连 接起来，在这条直线上计算出弦三等分点吼一2 3p 。, + 只和q 一2 3p , + j 1p 。，再从 0 0 ，0 1 沿着r ，只连线的局部法向做直线，与原始曲线相交于焉，只，则这新 求得的巧，只+ 就是我们所需要计算得到的在相邻两点p 0 ，只 司的t - - n n a 。 这种插值方法即为三分细分法则。不断重复这种细分法则，就可以由原始点列， 得到多分辨率不同细节水平的逐层点列。 另一方面，假设我们用上述细分方法v ，次迭代插值后，得到j 层的两个相邻 点：晶2 ( 工似，y 卅) ，置5 ( x 埘。y j , k + i ) ，则根据上面的等式，可计算出o o ，o l 两点： 氏= ( 工二。m + 。，y 二1 , 3 k + 1 ) ，q = ( z 二。+ ：，y 二。+ ：) 。 同时，我们可以从上一层的相邻点r 和只来计算得到法线方向，并且通过 计算o o ，0 1 沿法线方向与原始曲线相交的值来得到新的插入点。这样就可以求 出户1 层的插入点巧2 ( x + 。m 。y i + 1 , 3 k + 1 ) ，只+ 2 ( x _ 3 k 。y + j + ，。+ ：) ，其中o o 和巧 之间的距离可以看作层的小波参数w 。 w j 。= ( z 二，m + 。一j ：+ l 。+ 。) 2 + ( y 二。m + 。一y ：。，。) 2 这个小波参数长度的收敛速度与三分法的公式的最高阶数有关。注意到，新 插入的点曙，只+ 地位相等，所以验证的时候只需要验证其中之一，另外一个可 以相似证明。 同时，注意到对于任意一个曲线上的给定点，y 轴上投影的值可以表达为这 点在x 轴上投影值的连续函数y = y ( x ) ，所以，我们只需要证明点列在x 轴上投 影的值对于这种三分细分法则收敛且光滑，且对于x 的连续函数，这种收敛也成 立。则就可以证明这种三分细分规则是多分辨率细分算法。 这个定义f 的细分算法有如f 的主要结果： 定理2 1 ：设扛j ，“，以v ，s ，是我们上述定义给出的变量以及细分规则，对于 给定的丘有r 卅= k 3 一，是一个给定的区间。竹是j 层的分段线性折线 函数，竹( f ) 即为在t 肚上对应的点为z ”。若k l o o ，则存在一个函数 妒c 。( ，) ，使得妒j - 妒成指数收敛，即妒满足： i ( p ( f + f ) 一t p o ) i 。c i f i l l o g i f 0 “ ， ，+ f ， ， 3 7 a t 3 一“ 一细线b 0 ) - 原始曲线 一粗线毋- ( f ) 定理2 。2 ：设s 。是前面所描述的三分插值法，y = y ( x ) 是y 关于x 的连续函数，且 有： y c m + ( r 1，m n m 10 r l 则：m s ，x 卜s s y ( 圳c 群i ( x ) t i m + r c h ， 定理z 1 和定理2 2 主要证明了这个新定义的三分细分算法是一种多进制的多分 辨率算法。 定理2 - 3 ：设s 是前面所描述的三分插值法，则相应的小波参数w l ，。满足 w ，i 。c 3 叫”y c “( r ) ，m n m - 10 0 由于等式右边所有字母均为常数，所以等式右边其实是一个常数。 其次，定义剩余变量r 为 0 + i = 0 “一s 3 工r o = x o 则根据上面的定义我们有： i 。l 。= j t + 。- s ，彳，i 。sd ( j + 1 ) “3 一5 s 0 ( 2 1 ) 其中v ，a ，a 均为大于0 的常数 另一方面，三分细分法则有如下模板公式： ( 足工) 。= n 。x t f 其中，若县= 3 m a x i t a ，o ) ，则有 1 4 f ，。= m 一8 ) 3 - l l ( k + 8 ) 3 j i 命置2 i ：。黔慨气) 。一划c 3 i x s l 。i拒l 一 证明：由s 。的细分法则的定义，有s ，1 = 1 ( 1 是恒为1 的点列) 。同时根据模板 公式易得： i ( s ，工) 一 cm 。a x x ， 其中z ，。= 【n 七一日) 3 1 l ( + 8 ) 3 3 于是有， m a 。x l ( s 。x s ) t 工；r i = = m a 。x l ( s ，( 工，z l - x , ) t c m ，：a ；x 。x s ，z ，- - x s b = c 黔陵( 缸 i c 璎警i ( 血a i = c | 血，l 。 c 3 - 。川。 其中为差分算子：( 工) 。= 以“一五 得证 下面定义一个引理2 1 中会用到的几何级数： 甲( 口 叻= 七8 口 明显，当a l 时，这个级数会小于一个于a ，口有关的常数c 引理2 1 ：设扛j ，0 c ，n ，v ，s ，是我们上述定义给出的点列、变量以及细分规则 则存在一个独立于a ，x o 的常数g 使得下面的不等式成立： i x j i 。c ( j 工。i 。+ 口) 证明：h 。= i s 3 x j _ 。+ r j 。= 防x j _ 2 + s 疗。+ 。l = 隆s ；_ ，l j q = oi ” 应用( 2 1 ) 式有 i s 北1 r 0 i + c a 芝l s ：l 。( 卜q ) a 3 刈砷 口= 0 j - i c t i x o 。+ c ：口( j g ) 一3 ” = c ：i x o l 。+ c ：口甲( 3 一”，j ，0 【) c 3 ( x o l 。+ 口) ( 其中c 。，c ：，c 3 均为常数) 得证。 2 3 定理2 1 及定理2 2 的证明过程 定理2 1 ：设b j j ，0 【，口，v 。s ，是我们上述定义给出的变量以及细分规则，对于 给定的血有”= k 3 一。，是一个给定的区间。哆是j 层的分段线性折线 函数，竹( f ) 即为在t 卅上对应的点为_ 。若k l 0 ，并应用前文所证的命题 2 1 和引理2 1 ，得到： 阮一l 。j , - 1 s 叫( f ) 一织( f ) l s = j 1 f = 篁s 甲( k 3 - r , * n ) 一纯( 盼m 1 ) ) l s = j i k = 篓s u p l x s + l , k - - ( 2 x , , l k 3 + , b y知吲l i j 。 j 。窆：s u 。p m 。a 。x i 并，+ 。，。一工，。 j 蓦, - i s ? 研胁a 0 另一方面，设3 一l a t l 1 。再应用引理2 1 和上式可以得到 i i p o + f ) 一( p u ) l l 叩( r + f ) 一q ，( f + f ) l + i p ，( r + f ) 一吼( f ) l + i 【p ，( t ) - q ) ( t ) l 。 c 1 j 4 3 一+ c 2 j 。3 一+ j 中，( t + a t ) - q o ( f ) l c l ，“3 1 + c 2 j 一37 + 3 。h 。 c 3 3 j “1 + c 4 3 一( i 工o l 。+ 4 ) c l 血l 1 0 9 l a t l l “ 其中c ，c 。，c ，g ，c 。均为常数。 得证。 1 7 + 窆啾 +x一 定理2 2 把y 轴的值看成是x 轴值的函数，证明了y 也收敛。 定理2 2 ：设s ，是前面所描述的三分法则，y = y ( x ) 是y 关于x 的连续函数，且有 y c m + 7 ( r )，m e n m 10 r 1 则：m s ，x ) 一s ，y ( x ) h c m a x ( a x ) t i ”c 蚓y 证明：由于y e c ( r ) ，所以对于任何一个给定的k ，可以把y ( x ) 在( s ，x ) 。泰 勒展开。同时注意到s 。1 = 1 ，我们有： (y(s3x)一s3y(x)。_(s，m(x-(s3xun竺粤业)。+(s3r(s x ) ) 。( y ( s 3 x ) 一，y ( x ) ) 。= ( s 3 ( ) 。) 。二字型) 。+ x ) ) 。 口2 l = m ( s 3 ( x - ( s 3 x u ) k 掣+ ( s 3 r ( x ) ) 。= ( s ，( x 一( ) k ) 8 ) 。二掣+ ( ( x ) ) 。 n 2 2 由于m 1 ，所以前半部分累加的和为0 ，我们只需要考虑等式的后半部分。由 于 | r ( x ) i c l x 一( s ，x ) 。r 用前述命颖2 1 和f 式可以得到： 得证 ( 5 j r ( z ) ) t _ c m 。a 。xg ( x k ) cm a 。xx , 1 。( s ，工) t i ”+ c m a 。x l ( & c ) t i ”7 c 眦” 1 4 定理2 3 的证明过程 最后，定理2 3 证明了小波参数的收敛性依赖于基本的正则三分细分算法的收敛 性。 引理2 2 l 设s ，是前面所描述的三分规则，y ( x ) 是y 关于x 的连续函数，且有 y c 4 ( r ) ，如果 上j 与 舅) 均为递增的点列， 膏 为 z ) 在三分法则作用下的下 一层点列i = s 工，同时芦l 且y 是一致连续，则对于足够小的l x l 有： i ( 芟一s 。x ) ，。+ 。j j ( s 。y ( x ) 一y ( s ，x ) ) ，。+ 。i v k 和 悻一s 。叫。 - i s ，y ( x 卜y ( s ，x m 。 证明：s ，如上所述，记x = ( s ，x ) 。+ 。 y = ( s ，y ) 。= ( s ，y ( x ) ) 。同时根据 三分法细分的规则，对于点序列x 和它的下一层点序列膏，我们有： ( 写。一x ；。) ( z ) 。+ ( ，( 葛。) - y ；。+ ) ( 缈) t = 0 ( 2 - 2 ) 对于给定的k ，若y c i ( r ) ，则存在一个鼻 i i l i n ( 趸，x + ) ，m a x ( 趸，x ) 】，使得 y w ，) ：塑掣 ( 2 3 ) 对于递增点列z 中的点x 。、x 。+ 1 存在f ： x 。，x 。】使得 y w ：，= 紫= 焉 c z 钔 其中，( 2 4 ) 中后面一个等式由( 2 2 ) 式得到。 于是上面两个等式( 2 3 ) 与( 2 4 ) 相减有： ( 趸一x ) 2 = ( y ( 冤) 一y ( x 。) ) ( y + 一y ( 芰) ) + ( 趸一x + ) ( y + 一y ( 趸) ) ( y ，( 厶) 一y ( 鼻) ) = ( y ( 爻) 一y ( x ) ) ( y + 一y ( 囊) ) + ( y + 一y ( 趸) ) 2 y 7 ( 炙) ( y ，( f ! ) 一y 7 ( t ) ) 若i 也是递增的点列，且x 。芟墨x 。，则应用命题2 1 结果，有： j f 。一f ：f m a x ( 障- - x k | f j fx k + 1 弦一x 。弦一x k + 。j ) - m a x ( 1 x 。m a x x t - ( s s x ) 一i ) - q 6 x l 于是，只要l x l 充分小，对于一致连续的y ，( x ) ，我们就可以有： 叭：) ( y ( ：) 一y 。) w - l r q 。l y ，( ：) - y 他，) i s 寺 因此： ( i x ) 2 ( y ( 置) 一y ( x ，) ) ( y 一y ( 薰) ) + ! 羔掣 0 且k l o 。，则存在一个函数中c 。一( ，) ，使得仍_ 垆成指数 收敛，即母“1 满足： 眇( h 出) 一( p ”训。- c l & l 。( 1 + 1 1 0 9 蚓) 1 v t ，t + a t ， 3 一。蚓 0 ( 3 1 ) 由于等式右边所有字母均为常数，所以等式右边其实是一个常数。 同时，由于s 的有界性，若取参数p ，其中p 满足0 2 p p ，则存在一个 相应的实数u o 使得下式成立： p 。l c 3 町v j _ o ( 3 2 ) 其次，定义剩余变量r 为 + l2 j + l s 3 x r o2 x o 于是显然有 删= 工蝌一s i 川x 尹 则根据上面的定义我们有如下递推式 ( 3 1 0 ) 螺“| 。= 3 “i m 删l c 3 “渺i 。s o ( 3 3 ) 其中中是上文中用定义的算子 同时，根据( 3 3 ) 式，我们有： j t 9 1 i 。 3 l k + b ) 3 3 命题3 5 l 对于任意一个稳定的细分算法s ( 其中s 的首一多项式系数p 0 ) 有： m a x l ( s x ，) t t z i _ c 3 一i x , i 。 证明：由于s 的是稳定的细分算法，有s 1 = 1 ( 1 是恒为1 的点列) 。同时根据模 板公式易得： i ( l i - c m 。a x x z i ，其中f ，t2 怖一8 ) 3 1 l ( k + b ) 3 ) 于是有， 警陋) t 飞j = m a 。x l ( s ( x , j 1 - x , ) t i 1 w ( a ，行，口) = k = a = 矿1 d = i “。 lc ( a 脚 n l 引理3 1 ：设矗j j ，a ，n ，v ，s 。，p ，扯，( 其中p 满足o 2 p p ) 是我们上述定 义给出的点列、变量以及细分规则，设 丸= m a x ( p v ，h ) 则存在一个独立于a ，z 驴1 的常数g 使得下面的不等式成立 l 工，1 i 。c ，( i 工护1 i 。+ 口) ( 1 + j 3 对) 其中 ia t 1 。= c c + l 1 0 u p 一” 矾俐。= 眇制峭1 h s 2 粥刑制刮。= 伊卯制1 应用( 3 4 ) 有 i s p ij 。俐。+ 伽主q = o 妒刊4 s 叫训” 再应用( 3 。2 ) 有： sc 。3 时阿l 。+ c ：口j - t 3 ( 卜q ) n 3 廿舯训 q = o = c 。3 町眇1 l + c ：a 3 ”甲( 3 ”，j + l ，0 c ) f ( 歹+ 1 ) “3 9 7 肛 p v - p v c ，( 桫i 。+ 以) ( 1 + 产3 婶) ( 其中c ，c ：，c 3 均为常数) 得证。 引理3 2 各个符号的假设和引理3 1 中一样，假设0 j 。 p q + 1 九= p q + 1 九 p q + 1 定理3 1 ：设扛j j ，c ，口，v ，s ，p ，p ( 其中p 满足o s2 p 尸) ，是我们上述定 义给出的变量以及细分规则，对于给定的幺有卅= k 3 一i ，是个给定 的区间。伊，是，层的分段线性折线函数，妒，( r ) 即为在m 上对应的点为_ 设 九= m a x ( p v ，u ) q = t 一九= n + l c 其中 r = 引 p 为诱导算法，首一多项式的系数。 若q 0 且k i 。 o o ，则存在一个函数中c q - ( ，) ，使得p ，- 妒成指数 收敛，即( p “满足： i ( p ”o + f ) 一叩“o ) l 。- c l l 。( 1 + l l o g i f ) ” v t ，t + a t ， 3 1 剐 0 ，并应用前又 所证的命题3 1 和引理3 1 ，得到： 鲫一叩扎1 - 1 s 叫槲( r ) 一”叫 2 萎s 帅要巾圳巾) | 2 萎j - i 节陋 e l 厂c 争一+ j 1 批、) | 唼z s u pm a x l e i 。 搬t 卅f 于是若有0 蔓2 q p 0 另一方面，设3 一1 血i 1 。再应用引理3 1 和上式可以得到： 妒1 ( f + f ) 一( f ) l ”( f + 出) 一9 y 1 ( f + 止) l + b 罗1 0 + 血) 一q y l o ) l + i p y ( t ) - _ c p i “1 酬。 c 。1 3 一。+ c 2 ，1 3 一+ | 平r 1 ( f + f ) 一叩y 1 ( f ) l c l ，”3 ”+ c 2 ，”3 ”+ 3 一眇+ 1 】l c l a , i | i o g l 旷 其中c ，c t ，c 2 均为常数 得证 3 3 几个诱导细分算法的例子 1 如图3 1 中所示，空心圆代表上一层点列中的点，实心圆代表计算得到的 下一层点列中的点。 由两个相邻点用三分法计算下一层点列： s 3 x i = x i + l j 0 于是根据定理3 1 及其引理，我们可以确定： “= 0 ，p = 1 ，n = 0 ，1 ( = 1 ，q = 0 再带入定理3 1 的结果： 妒( h 址) 一甲叫。sc h 1 + 1 1 0 9 吲) ” v t ，t + a t ， 3 一。m 3 ”1 即 l 审臼+ & ) 一p 呻( f ) | 。s c f j 1 ( 1 + 1 0 剖& 妒 化简之后为： l ( p o + r ) 一( p ( f 。sc l o t l 这个相邻两点的三分法则其实就是本文第二章的基本三分细分算法。 图3 1 2 如图3 2 中所示，空心圊代表上一层点列中的点，实心圆代表计算得到的 r 一层点列中的点。 图3 2 中是用相邻4 点来计算下一层点列，设相邻四点分别为： z k ，工j ，t + l 工 十2 x d ，k 十3 则根据诱导算法的定义，我们从这四点里计算出： z j ，r = 中( z ，t ) = ( 工1 + z ，t + l + 工“2 ) 3 工j ， + l = o ( x j ，i + 1 ) = ( x j + i + 石l k + 2 十工，。女+ 3 ) 3 再把这计算出的两点z 似，z 肚+ 用基本的三分细分法则进行计算。 根据命题3 3 的结果，基本的三分细分法则可以达到c 。的光滑性，同时相邻 四点计算方法有 s ；0 1 = s 3 ，s 5 1 m = 由s ；川1 ，其中p = 1 为算子：( 峨) 。=