（应用数学专业论文）三进制细分算法的连续性分析及应用.pdf

复旦大学硕士学位沦文 三进制细分算法的连续性分析及应用 摘要 细分算法是计算机辅助几何设计与计算机图形学中比较受关注的领 域1 9 8 7 年d y n 提出了四点插值细分算法，生成的插值曲线达到c 1 连续；2 0 0 2 年，h a s s a n 在此基础上提出了三进制四点法，与d y n 的四点法相比，该细分法 收敛速度更快，同时，生成的插值曲线达到c2 连续，具有二次多项式再生能 力 本文将主要研究三进制细分算法，探讨三进制翊分算法的收敛性，给出了 细分算法c 。连续的充分条件，以及插值细分算法c 。连续的充要条件；同时构 造新的三进制四点法和三进制五点法，并对其连续性进行分析 关键词曲线生成：细分；三进制；连续性：插值；逼近 中图分类号0 2 9 c o n t i n u i t ya n a l y s i sa n da p p l i c a t i o no ft e r n a r v s t a t i o n a r ys u b d i v i s i o ns c h e m e a b s t r a c t s u b d i v i s i o ns c h e m ei so n eo ft h en e i d st 1 1 a th a v eb e e n i n19 8 7 ，d y nd e v e i o p e da4 。p o i n ts u b d i v i s i o n t h i ss c h e m ec a nb ec 1 c o n t i n u i t y i n2 0 0 2 ， p o i n ts u b d i v i s i o ns c h e m eb a s e h a s s a j l ss c h e m e w i d e l ys t u d i e di nc a g d s c h e m e ；t h el i m i tc u n ，eg e n e r a t e db v h a s s a nd e v e i o p e das o c a l l e dt e m a 巧4 o n d y n ss c h e m e c o m p a r e dt o d y n ss c h e m e c a ng e n e r a t et h el i m i tc u n ，ef a s t e r ，a n di t sl i m i tc u r v e c a nr e a c h c o n t l n u l t y ，b ep o s s e s s e do fr e p r o d u c i n g p r o p e n ) ，o f p o l y n o m i a l so fd e g r e e2 mt n l sp a p e r ，w ew o r l ( o nt e m a r ys u b d i v i s i o ns c h e m e ，d i s c u s s t h ec o n v e r g e n c e o it h et e m a r ys u b d i v i s i o ns c h e m e ，a n dg i v et h es u 师c i e m c o n d i t i o n so fc c o n t i n u i t v n e c e 5 s a 巧a n ds u f f i c i e n tc o n d i t i o n sf o ri n t e r p o i a t i n gs u b d i v i s i o ns c h e m e f i n a l l v w e c o n s t r u c tan e w t e r n a r y4 1 p o i n ts u b d i v i s i o ns c h e m ea n dt e m 哪5 p o i n ts u b d i o n s c h e m e ，a n a l y z et h e i rc o n t i n u i t yp r o p e r t i e s k e y w 。r d s ：c u r v e g e n e r a t e ；s u b d i v i s i 。n ；t e m a 叫；c 。n t i n u i t y ；i n t e 印。l a t i 。n ； a p p r o x i m a t i o n c h i n e s e l i b r a r yc l a s s i n c a t i o n ：0 2 9 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均己在论文中作了明确的声明 并表示了谢意。 作者签名 论文使用授权声明 日期：。 本人完全了解复旦大学有关保留、使用学位论文的规是，即学校有权保留 送交论文的复印件，允许论文被查阅和借阅：学校可以公布讫又的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵奇此 规定。 ， 作者签名：- 一：二： 导师签名蛊趋 日期 复旦大学硕士学位论文 第一章引言 细分算法是近年来在计算机辅助几何设计及图形学领域的一项重要研究内 容传统的曲线曲面设计方法，是先从控制点得到曲线曲面的数学表达式，然 后再进行赋值，这样需要大量的计算，而且在复杂的物体造型时则很难处理； 相比于传统的造型方法，细分算法拥有更快的曲线曲面生成速度、数值稳定、 可适用于任意的拓扑网格等等特点，使细分算法成为一种强大的曲线曲面造型 工具 细分算法的研究在近几年取得了一系列有意义的成果n 1 削，d y n 等n 。2 3 的结 果与研究方法，为细分算法奠定了基础；只是中的“四点法”的极限曲线仅 有c 1 连续性；。”指j 了d v n 的“四点法”要达到c 2 连续的充分必要条 件n 1 ( h a s s a n 等) 提出了一种三进制四点细分算法，其插值极限曲线是c 2 连续 的，具有二次多项式再生能力，极限函数的逼近阶是d ( 矗3 ) ( 见出。) 在细分算法连续性的参数域研究中，以砼3 中关于二进制细分算法的收敛性 研究最为经典，为找出参数的收敛域提供了有力的手段只要己知细分系数集 ( 【l a s k ) ，便可求出有关参数的收敛域，从而得到极限函数各阶连续的充分条件， 而且此方法具有一般性，可适用于逼近模式和插值模式的细分算法，可以方便 地推广到p 进制细分算法，例如h 1 中的三进制四点细分算法的相关定理就直接 来自睇相对来说，关于连续性必要条件的研究理论则结果不多，h 邮中研究了 插值模式的三进制细分算法各阶连续的必要条件但h 1 在研究必要条件时语焉 不详，所用的方法也不具有普遍意义为此，哺3 中引入了一种由函数差商推广 而来的向量差商，可以用来逼近细分算法中与向量有关的各阶导数因此，只 要求得细分矩阵的特征值及其对应的左、右特征向量，运用这一方法，就可以 得到插值模式的三进制四点法各阶连续的必要条件，并且得到其极限函数在顶 点与中点处各阶导数的解析表达式为此，本文在构造插值模式的三进制五点 法时，将利用3 的方法研究其极限函数各阶连续的必要条件 本文将分析三进制细分算法的一些收敛性条件，并构造两种细分算法：逼 近模式的三进制四点法和插值模式的三进制五点法，利用已有的理论方法对这 两种算法进行分析，研究其连续性与收敛性 复旦大学硕士学位论文 第二章三进制细分算法的连续性分析 2 1 基本定义 1 三进制细分算法 定义1 给定初始控制点p o = p ? i p ? r d ，f 山 ( ，。为初始的有限下标集) ，设 p 2 = p ? lf 以 为第尼次细分后得到的控制点，。为其相对应的有限下标集， 且j i m 里萼五极限存在，则三迸制细分算法可表示为： ”田 j 憎“= 一p ；，f 以+ 。 f： ( 2 1 ) y 晓；：3 卜“7 j _ - 一 j l ，z 其中口= 口，f z 为给定的实系数序列，且只有有限个量不为零，称为该细分 算法的m a s k 我们将此细分算法表示为s ，因此有p “1 = s p 。，则s 为线性算 子，表示从p 。到p “1 的线性变换 2 一致收敛性 为了便于研究细分算法的收敛性及连续性，对每步细分所得到的点赋予合 适的参数，把极限曲线的连续性问题归结为其任一分量的连续性问题，将问题 归结为极限函数的连续性分析，因此我们有如下定义： 定义2 对于任何给定的初始值尸o = p ? | p ：) 瑕，f 山 ，设三进制细分算法s 第 七次细分后得到的值为尸。= ff 以 ，并假设的对应参数为筹( h 为初始 值的步长，以下如无特殊说明，均取h 为1 ) ，这时若存在瓜或碾子集上的不 恒为零的连续函数厂( x ) ，满足! 鲤s u p l 厂( 等) 一| = o ，则称细分算法s 一致收 敛，即由细分算法s 生成的极限函数是连续的记为厂( x ) = s ”尸? c o ，简记 s c o 若 s r ”j p o c ，则称细分算法j s 是c 连续的，简记为 5 r c 3 细分算法s 的均差细分法 定义3 设s 是以尸o = f 矿l p ? 瓞，f 山 为初始值的三进制细分算法， = if 以 为第尼次细分后所得到的值，令耐= 3 ( p 磊一p ? ) ，则可定义 卯= 咖f 以，f m a x 以 ，如果存在以卯。为初始值的细分算法s ，满足 卯“1 = s 卯。，则称s 为细分算法s 的一阶均差细分法类似地，如果s 的一 阶均差细分法存在，则称之为细分算法5 r 的二阶均差细分法，记做s t ，同理， 可定义细分算法s r 的，? 阶均差细分法，记作s 。，此时 d ”p ? ：3 ( d ”一1 p 二。c ，”一1 p ? ) = ：( 3 。) ” ( 1 ) 6c ? p 鼻。一。1 2 复旦大学硕士学位论文 2 2 连续性分析及相关定理 本节将给出几个三进制细分算法的相关定理，其中，定理1 、定理2 、定理 3 、引理2 和引理3 在文献n l n 。1 有了类似的结论及证明，这里给出另一种证 定理1 如果由式( 2 1 ) 定义的三进制细分算法s 满足 口，= 口，川= m = 1 j z，zj z 则存在细分算法s 的一阶均差细分法s ，满足 证明 卯“1 = s 卯。，且辟= 3 ， 色) 为s 的m a s k j z 由鸭，= ，z = 坤 j zz = 1 可得 ( 岔：厂口，川) = ( 口。川 ，ze z 一口3 川) = ( 口3 坤一3 朋) = o ，e z 由于口= 口，l z 仅有有限个量不为零，于是对于任意的f， 呓川一 ( 2 2 ) 一川| ，刁 也只有有限个量不为零所以对任意固定的f ，存在墨= 毛( f ) ，也= 尼：( f ) ，满足 毛 尼2 ，且当 砭时，牛1 一a 3 j 一，= 0 定义层。= 3 用阿贝尔变换得 ( 一i 一口3 川) = 0 联合式( 2 2 ) ，得 ( a ，卅- 川一口。州) ，易知当 盔或歹也时，屈一= 0 。因此，利 七2 硝1 一露“= ( 徽，一。一一) = ( 口，一一，一口。一) 露 ，zj = 岛 七， = ( 苏，r 口，) 菇+ “一1七， 姚一州) ( 颤，一p j ) ，= 膏 m = j + 1 ( 口，。一一口，。一，) ( p 二。一矿) ：篁丢屈川( p 鼻。一力) 歹= 七i j = 屈川( p j r ) ，zj 由定义3 ，科= 3 。( 苁，一) ，得印? “= 层印； 这是以卯。= 纠li 山，? m 觚厶) 为初始值的三进制细分算法，记为s ，有 卯“1 = s 舻容易计算 勿 1 + 咖嚣+ 劫揣= 3 “1 ( 瑞一p 爹1 ) = 3 “1 ( 口，一一p ；一 j e z 3 “以一肋各，；) = 3 一，彰 ，z 3 j z 口3 一，p ；) 如触 。叩 。咿 础础 = 皿 复旦大学硕士学位沦文 另一万向 咖爹1 + 咖姑+ 硝置= ( 屈一，+ 屈一h + 岛一心) 勿； 上面两式对于任意的初始值均成立，因此可得 岛= ( 属一，+ 屈一h + 屈一h ) = 3 口，一。= 3 证毕 ，出 ，e zz 引理1 若三进制细分算法s 的一阶均差细分法s ，存在，则有 口，= 口。川= 朋= 1 证明设阶均差细分法s ；的m a s k 为 ，l z ，由定义可得 印y = 3 “1 ( p 竺1 一p ? + 1 ) = 3 “1 ( 口，川一。一甜，一) p ；，且咖y = 属川勿； 取初始值p o = p ? = 1f 山 ，并取尼= o ，可知咖? = 咖? = ( 苁。一p ? ) = o ，因此 有 咖3 ( 以一一。一阢，一，) 矿= 3 ( a ，川一。一口，) ，且咖屈川印；= o 从而可知( 口，川一，一瞰h ) = o 由i 的任意性及式( 2 1 ) 可得 识，= 口，川= 口。坤= 1 证毕 定理2 - 三进制细分算法s 一致收敛的充要条件为，= 州= 吃m = 1 ， j zj e zz 且对于任意的初始值，妻s 均一致收敛于。函数 证明任意给定初始值尸o = p j ) l p ? 酞，f 厶 ，设细分算法s 第j 次绌分后得 到的值为p 。= if 以 ( 。为尼次细分后的有限下标集) ，并假设对应的参 数为专 必要条件：因为s t 一致收敛，所以存在连续函数厂( x ) ，满足 受s u pj 厂( 争) 一j _ o 于是有 p 量，一p ? l _ lp 三。一厂( 等) + 厂( 等) 一厂( 寺) + 厂( 舌) 一i ip 墨，一厂( 学) + 厂( 等) 一( 寺) l + 厂( 寺) 一p ? l 又厂( x ) 是连续的且! i m s u p 厂( 寺) 一p ? f = o ，从而有 庀 一 威，一厂( 等) l - o 厂( 等) 一厂( 多) l _ o 厂( 争) 一卜o 4 p p p u ， u ， u ， s s g m m m g一-骞一g1i1lt，lk r，；，(，l 复旦大学硕士学位论文 因此可得j i ms u pp 乏j p ? j = o 与定理1 的证明类似，因为口= 口，i z 只有有限分量不为零，则对于任意的 f ，存在包和尼2 ，满足向 恕，j 向+ ，一 一，j 0 ，j 吗”h 一吃址， o 且任何 包，均有l 凹3 h 一1 一a 3 川| _ o 因此有 p 竺1 一p ? “2 ( 川一，一口，) = 乏以川( 或；一) + 咄川一。一，一，) p ： 。“ j 一“l j = 蚂 “七 其中，识川2 ( 口s 一- 一口，) 从而! 臻( 臼。川一。一日。川) p ：= o 又对于固定的t ，有! i m 成= ! i m p ：；由初始值尸。的任意性，则存在一组初始 值，使其极限函数厂( x ) ，满足厂( o ) o ，这时有l i m p ：o ，因此有 女， ( 以h 一。一比h ) = o ，又根据尼，和尼：的性质，可知( 识h 一，一口，川) = o ，由f ，2 七i j z 的任意性可得 以，= 口班，= 凹。坤= 1 令卯= 勿；= 3 。( 矗，一) f 以且m a x 以 ，由定理1 可知，存在细分算法 s ，满足 卯“1 = s 卯。且岛= 3 j z 由于 受8 u pl 威。一p ? i = o 且尸。是任意性的，由定义3 ，可得对任何初始值，专s 均一致收敛于0 函数 充分性：由于，= 口，川= 阮坤= 1 ，且对任何初始值，去s 均一致收敛 于。函数，则有l i m s u pp 二；一i _ o 设厂( x ) 为细分尼次后的分段线性插值函 数，厂“1 ( x ) 为细分尼+ 1 次后的分段线性插值函数，显然i 厂“1 ( x ) 一厂2 ( x ) l 的最 大值只能出现在x = 六，f 以+ 。上，因此，考虑3 种情况： 1 ( x ) 的端点处，即石= 嘉，z 以，此时有 l 厂川( 斋) 一厂( 斋) _ p p ： i = i ，p ；一p 因为口，= 1 且 臼，l z 仅有有限分量不为零，所以有 i 瓯一，j _ l 西崩( p 知，一) l 其中 口i - 3 。) 只有有限分量不为零，又j i ms u p | p 三。一l _ o ，从而有 5 复旦大学硕士学位沦文 ! 鳃l 厂“1 ( 翥) 一厂( ；) 1 21 骢i 篆西一，( 露+ ，一p ；) i = o 2 厂川( x ) 的端点处，x ：要等，f 了。，此时有 i 九等h 2c 等怍i 九筹，一弘；，一弘等川 ：ip 茹一昙p ? 一昙p 竺，l 同理可得1 p 裂- 一一扛h 一碱t 一蒯_ 知) 贿有限分量不为 零从而 拶+ l ( 等h 2 ( 劳怍 受i 酗叫( 或。一辩。 3 九帕端点处，x = 等，f 蚴寸有 j 九等h c 等游l 九等，一扣势一弘等怍删一孙 同样可得剐九等h 。( 等j = o 综合以上情况可知! 塑f l 厂1 ( x ) 一厂2 ( x ) k = ! 翌s u p i 厂“1 ( 。寿) 一厂( 奇) 卢o ，因 r q i i r o 。一 此函数序列 厂。( x ) 一致收敛，设其收敛于连续函数厂( x ) ，则 ! 骢s u p | 厂( 考) 一f = ! 鳃s u p i 厂( ；) 一广( 孝) l = o 即细分算法j 5 r 一致收敛于厂( 戈) 证毕 定理3 设三进制细分算法s 一致收敛，若其一阶均差细分法s 也一致收敛， 则s 一阶连续，即i s r c 1 证明根据定义，对于任何初始值p 。= p j 0i p ? 酞，f 山) ，均存在连续函数 厂f x ) ，2 f x l ，满足 受s u p l 厂( ；) 一l = 。 ! 现s u p l g ( ；) 一耐 = 。 记= m a x 以，m = 多，由三进制细分算法的表示，知舰m 存在，记为聆考 察 o ，m 】上关于控制点 p ? if 以 ( 以为尼次细分后的有限下标集) 的 b e r n s t e i n 多项式序列 瓯( x ) ： 驰，：剽蝴t 一矿p ? 则其导函数序列 睨( x ) ： 6 一 墨呈奎兰堕主兰垡笙茎 _ - - - - _ _ - _ _ _ _ _ _ _ _ _ _ - l - _ _ _ _ - _ _ _ _ - - - _ _ - _ _ - _ _ - _ _ - _ l _ - _ _ _ _ _ l 一一 磷c x ，= 瓮篓( y _ 1 ) ( 袁) ( t 一袁) c p 乏，一p 幻 = 戮。1 旧 - l 一科 由b e m s t e i n 多项式的一致收敛性，s 。p 。一致收敛于( x ) ，可得 瓯( x ) ) 在 0 ，船】 上一致收敛于( x ) ；s 严卯。一致收敛于g ( x ) ，可得 ( x ) ) 在【o ，以 上一致收敛 于g ( x ) 从而厂( x ) 可导且 八x ) = 丢厂( x ) = 丢 骢( x ) 2 憋丢玩( x ) 2 鬯联( x ) 2 g ( x ) 因此0 ) 一阶连续，s c 1 证毕 定理4 假设三进制细分算法s 一致收敛，对于任何初始值 尸。= f p ? p ? r ，f 厶 ，记厂( x ) = s 。j p 。，且满足以下条件： 存在与f 无关的序列k ) ，满足! 受x t 2 o ，且有厂( 毒+ 稚) 2 p ? ，v 涎以 细分算法s 的一阶均差细分法s 存在，并假设s 的m a s k 为g ”= 口j 1 。 础= 口；冀。= 口；并：= 1 则细分算法s c 1 的充要条件是s 一致收敛 证明充分性可由定理3 直接得出 必要性：由于细分法算法s c 1 ，因此厂( x ) 一阶连续，由定义2 、定义3 可得 科：3 。( p ：，一p ：) = 3 。( 厂岸m ) 一厂( 专+ k ) ) ：厂，( 夤) 蚓去+ ，学+ 稚l 碱，纠( p ：一p 鲁1 ) - 3 ( ( 等+ 磁) 一厂( 等+ 圳 ( 受) 受l 等等+ k 于是有 觋s u p l 勿墨一一科i 2 1 觋s u p f 厂( 美) 一厂( 磊) l ；i ms u pl 厂( 受) 一厂7 ( 鼻) l = o 七 o 。 喝一班亏 由定理1 及定义3 ，可知s 的二阶均差细分法s ：存在，且妄s ：均一致收敛于。 函数，从而s 一致收敛，命题成立 证毕 引理2 设三进制细分算法s 一致收敛，若其尼阶均差细分法存在且一致收 敛，尼：1 ，2 ，2 均成立，则l s r 为c ”连续，即s c ” 7 复旦大学硕士学位论文 证明任何初始值尸o = p ? i p ? 凰，f 山 ，记s 。尸o = 厂。由定理3 可知，厂一 阶连续且s 尸卯。一致收敛于厂；同理，由s ：一致收敛可得厂7 一阶连续且 霹d 2 尸。一致收敛于厂”由递推法可知厂为以阶连续，即有1 5 t c ” 证毕 引理3 设l s r 川为三进制细分算法s 的，? + 1 阶均差细分法，且对于任意初始值 尸o ，妄瓯+ ，均一致收敛于。函数，则5 - 为c ”连续，即j s r c “ j 证明联合定理1 、定理2 、引理1 、引理2 可得 引理4 任何给定的初始值尸o = p ? f p ? r ，f 山 ，s 为满足式( 2 1 ) 的三进制 细分算法，p = p ? if 以 为其第尼次细分后所得到的值，若该细分算法s r 一 致收敛，记厂( x ) = j s f 。p o ，且满足以下条件： 存在与f 无关的序列 魂) ，满足 i m h = o ，且有厂( + 魂) = p ? ，v f 以； 一w 一 细分算法s 的胛+ 1 阶均差细分法s 洲存在 1 则细分算法 s r c ”的充要条件是s 。一致收敛，即对于任意初始值，最+ 。均一 j 致收敛于o 函数 证明充分性可直接由引理3 得出，现证必要条件 由均差细分法的定义知，细分算法s 的即阶均差细分法瓯也存在设 d ” 为 s 。第七步细分后所得到的值， 厂k 叫= 作函数厂( x ) 的均差： 厂( 气) 一厂( ) m ，吒 ：坐掣掣 从而有d ”p ? = 门! 厂k _ ， ，= 写+ = o ，1 ，门 又函数厂( x ) 为c ”连续，由均差的基本性质可得 肌， 】= 掣茜b 印字蜗l职：ij j 因此有d ”p ? = 厂”( 卣) ，同理可得 聪；( 鼽如l 等帆，等蝇 又i 孝：一舌l 芝，从而可以推出 ! 鳃s u p p 苁- 一d ”p 纠! 囊岛强l 厂( 色) 一厂( 刊5 。 由p 。的任意性以及定义3 知，对于任意的初始值，昙瓯+ ，均一致收敛于。函 数，根据引理1 、定理1 ，可得s r 。一致收敛 证毕 8 复旦大学硕士学位论文 第三章三进制四点法 为了更好讨论该算法的连续性，由引理3 ，我们自然希望该算法拥有若干 阶均差细分法，通过定理1 、引理1 ，我们可验证得知，当细分算法s 满足以下 条件时，该算法存在四阶均差细分法s 口o + a l + 日2 + = 1 一“。+ 口：+ 2 口，：三 1 一一巳+ “2 歹 旷2 q = 刍 由此可解砜= 音一十努= 等= 击 算法1 给定初始控制点 瓞d 三，设第七步细分得到的控制点为 ) ：2 ，定义细分算法s 如下： p 1 = 印三。+ ( 1 2 “) p ? + 印三， p ；二= 口o p 三1 + 口1 p ? + 口2 p 墨1 + 吩p 墨2 碟| 1 2 = 吩t 。+ 盘：p ? + q 砝。+ 砝： o f 3 。，2 1 f 3 ，2( 3 1 ) 一1 f 3 。刀 其中日。= 詈“一言，臼。= 一甜+ 努，口：= 等，口。= 喜“一云 显然算法1 满足式( 2 1 ) ，一般情况下逼近生成点，当甜= 0 时，则插值所有生 成点，且该细分算法有四阶均差细分法 2 几何意义 该细分算法具有一定的几何意义，由于对称性，这里仅考虑p 1 和p 嚣两 种情况，由式( 3 1 ) 可得： p 笋1 = p ? + 2 “( 毕一p ? ) 9 复旦大学硕士学位论文 p 嚣= ( ；p ；+ p 二。) + 吾 ( 詈+ 吉p 乏，) 一( 吾p 三。+ 吾p 各：) + “ c 詈p 兰。+ 三以：，一 由此，我们可得其几何意义( 图1 ) 陡 图1 算法1 表示的三迸制四点法的几何意义 一土暾2 3 2 连续性分析 关于该细分算法的收敛性，我们只需考察控制点的任一分量f p ? r r 2 ， 由此我们可以得到以下几个定理 定理3 1 当一署 甜 云时，细分算法s 一致收敛，即s c 。 证明根据式( 3 1 ) ，可以得到： 蒯一砖1 = 专掰一寺( p 盘：一藏。) + ( 一詈“+ 普) ( 菇。一) + 号“+ 言) ( p j 一蘸。) 燃一蒯= ( ；材一击) ( 菇：一或。) + ( 一；“+ 署) ( 威。一露) + 专“一击) ( 硝一蘸。) p 籀一燃= ( ；致+ 音) ( p 乏：一p 墨。) + ( 一詈掰+ 普) ( 蘸，一p ? ) + 咕铭一寺( 露一p ：。) 当一芸蚤时，有 宣一 甜 h 习，伺 5 45 4 设m = 引司叫司 + 一 “ 甜 l 一3 1 3 + + 6一叫91 力一8 2 8 + 掰 甜 2 3 2 3 一 一 十 + 引司司 一 一 甜 ” b n b 哿砖弗脯 m m ， r；l 1 j2 mmxam 复旦大学硕士学位论文 p 茹一砖1 l m 一。墨舞+ ：1 p ? 一p 墨， p 姑一蒯j m z 一。爨舞+ ：i p ? 一p 兰， p 姑一揣i m ，一。曼瑟+ ：l p ? 一p 兰。 因此有一，爨筑+ ：i “一p 竺1j m 一。窦薮+ ：i 一p 兰t i ，又m 1 ，所以有 s u p 防一p ：i |：o ，由定理2 可知，s 一致收敛 定理3 2 当一去 “ 舅时，细分算法s 一阶连续，即s c 1 证明令钟= 3 ( 苁。一p ? ) ，则可得算法1 的一阶均差细分法s ： 设m = 4 “一l + 2 7 l 嚣1 = ( “一刍) 戤。+ ( 一2 “+ 蒡) 钟+ + 寺) 敲， 或：1 = ( “一刍) 教，+ ( 一2 “+ 考) 钟+ 一刍) 。 或皂= ( “+ 寺) 敲。+ ( 一2 蹦+ 莠) 钟+ ( 甜一刍) ， 也+ 孙 甜一 证毕 m = m a x 售，m 。) ，由上式可得： d 嚣一d 笋1 b 一。窦刊d ? 一雄。 一础b 一。曼刊d ? 一d 墨。i d 鼎i 坛一。鬟+ ，弦一d 二 同样可得一。曼戮+ 。l d ? “一d 竺1 l m 一。鬟+ 。j d ? 一d 墨。f ，又一去 “ 茜时， m 。 1 ，因此m 1 ，则有s 1 一致收敛，由定理3 可知s c 1 定理3 3 当刍 “ 等时，细分算法s 二阶连续，即s - c 2 证明令p ? = 3 。( d 墨；一d ? ) ，则可得算法1 的二阶均差细分法s ： p 箩t ：昙p ? + 昙e ： jj g 嚣：昙p ? + 要p 三 )， p 鼎邛引一缸小6 扰+ 咎邯扰一抛 同理可得一群竺1 印嚣。卜“m = m a x 肿“一卦 证毕 珊 又刍 “ 齿时，m l ，从而s ：一致收敛，由引理2 可知s c 2 证毕 1 1 4 一所 2 3 “虮 “弧 d d 复旦大学硕士学位论文 定理3 4 当寺 “ 刍时，细分算法s r 三阶连续，即s c 3 证明令厂。= 3 。( p 二，一e ? ) ，则可得算法1 的三阶均差细分法s ，： 露“= z ! 。 制_ ( 9 甜一弦+ ( - 9 “+ 弘 曼_ ( - 9 “+ 弦+ ( 9 铭一拟 同理可证得当刍 材 寺时，s 一致收敛，这时s c 3 证毕 定理3 5 一般情况下，当尝 “ 三时，细分算法s 无法达到四阶连续 2 72 7 。 一一 证明令g ? = 3 。( z ：，一) ，则可得算法1 的四阶均差细分法_ l s r 。： g 1 = ( 2 7 甜一4 ) g 兰。 g 鬈：= ( 一5 4 + 11 ) g 兰 g 要曼= ( 2 7 “一4 ) g 墨。 1 菠砹细分算纭s 日j 以达剑四阶连续，返时设s 收敛于函数p ( x ) ，p ( x ) c 4 ，由 引理2 可知，当寺 甜 寺时，l s r ，一致收敛于尸”( x ) 记厂= 尸”( x ) ，厂为 。摸三的分段线性插值函数因此有 受l l 一州。= o 由于厂。( 妄) ：z t 且露“：z ! 。，通过递推可得： 厂”( 寺+ 妄( 1 + + + ( 上广一) ) = 因此有 ! 骢厂“”( + ( 1 + + + ( ) ”1 ) ) = ! 受“”( ；+ 兰专) 叫事+ 三卅 又由s 可以达到四阶连续，可知厂一阶连续，由引理4 可知s 。一致收敛 由定理2 可得只有“= 寺时才能成立，这时s 。为： g 爹1 = g 兰。 g 鼎= g 墨， g 姑= g 三。 显然该细分算法只有当g ? = g ；时才成立，这时s c 。 证毕 定理3 6 设 p ? l _ 2 抠3 2 船+ 2 ) 和 p ? + 1l _ 2 f 3 “1 露+ 2 分别为算法l 第七步 和第觅+ 1 步细分所生成的点， 如果 落在一个三次多项式 1 2 g 。( ，) = 讲3 + 6 r 2 + c f + 矗上，且有 = g ( 爹) ( h 为初始控制点的步长) ，则 落在另一个三次多项式烈呲，且有= g ( 蠡) 证明根据题意，由式( 3 1 ) 可有 p 1 = 印兰+ ( 1 2 “) + m 蘸， 2 昭。( 等五) + ( 1 2 “) g 。( 爹) + 增。( 等办) = 口 = 岔 p 嚣= p 三。 ( 爹) 3 + 6 ( 爹) 2 + c + 6 口甜( 多) 2 ( 笋) + + 2 6 甜( 多_ ) 2 + f ，丝 j l 、3 “1 j 瑚( 等聃( 啪( 等卅学庇) 2 6 饼1 。烈等卅。( 警) m 以掣卅g t 洋力) 跏( 筹办卜( 等办) 2 + c + 6 臼甜( 别( 等厅) + 卜6 “1 设三次多项式g 。“p ，= a 广十6 ，2 + c + 6 口甜( 多) 27 ，+ fd + 2 6 甜( ) 27 ，经验证可 知，“= g “( 篑) ，对于任何一2 f 3 船十2 均成立 因此占“1 ( f ) 符合要求，命题成立 证毕 声，3 - 7 设算法1 的初始值落在一个三次多项式g ：口，+ 6 ，z + 订+ d 上，且 p ? 2g ( 砌) 卜2 f 门+ 2 ( h 为步长) ，则由算法l 生成的极限函数为三次多 项式厂。( ，) = 讲3 + 厨2 十( c + 孕口砌2 ) ，+ ( d + 号6 砌2 ) 在区间f o ，门危】上的限制 证明由定理3 6 可知，算法1 每步细分所生成的点均落在一个三次多项式 上，此时，记第七步细分所生成的点落在。( f ) 上且：t ( 要) ，显然 。( f ) = g ( ) ，由递推法及定理3 。6 可得 。) +d i_。，fi + ， 历箩 ，、 “臼f o 一 圯 如丝o 门悟蘸 6 “。 丝叩 力一梦 塑向箩 + n丫厂以叮嘲降加 、lf p 0 护 h 伤 碧j o 口 吩 一一 i i 土产 10 q u 2 - 办 弘 材榭 严 复 d 铲p 舻施 ，94扫p 叶1， + ，一产 专 _ 1 l h 0 产 扔 以 m 口 7 一 国 卯一4 _ f i p 七 产 ： 6 玎 舶 晰 广 ， 口 讲 i l = 复旦大学硕士学位论文 因此可得到 l i ms u pi 厂( f ) 一厂“( f ) l 8 。f o ，肭1 = 鳃，端】圭睁新鼢2 = o ! 受s u pi 厂6 ( 爹) 一i = ! 受s u pi 广( 爹) 一、。( 箬) i l i ms u pi 。( f ) 一6 ( ) i - o 女 c o f o ，翻1 “ 即细分算法s 一致收敛于厂6 ，命题成立 证毕 3 3 数值算例 对于给定的初始控制点，不同的参数“，算法1 所生成极限曲线的形状也 会发生变化，由定理3 7 知，当扰= 0 时，算法1 为插值细分法，且具有三次多 项式再生性这里将给出一组落在曲线y = s i nx 上的控制点，取 分别为 一刍，0 ，羟；，扣算法1 多次细分后所生成的慨 1 4 复旦大学硕士学位论文 复旦大学硕士学位论文 图7 甜：罢时，算法l 生成的极限曲线( c 2 ) j 图8 “：三时，算法1 五次细分后所生成的曲线 2 第四章三进制五点法 4 1 算法描述及几何意义 设三进制五掌嚣主 嚣臻甜哪。： fp ：= 口o p ：2 + 日l p 二l + 口2 p j + a 3 p f + 1 十“4 ”2 ：a。 。州曩巍羔的黧黧， 繁雾磊鬻鬻鬟鬈嘉 答徽慧要数篡蠢幕焉嚣”扣燧出帛大m 牟m 一 1 足以下条件时，该算法存在四阶均差细分法s a 解= 扣击， 2 口o + a l d 3 一日0 1 2 d 4 = ： j 1 一日3 3 口42 万 l 一2 + 鸭+ 6 口42 而 2 1 0 q j 时而 矿“十哿心：一争云门5 其 a z2 “十西及，一亏扩歪1 4 6 “7 。 耋参蒸勰黼删酬”、，设酞佬3 为第走步细骺删的 算法2 给定初始控制点 p ? 碾“ ，议i p ? 憾j 一，川昂丸刚川。 点，要翌鬣譬? o 蝎也怕 毋州 f p 苎5 以? 兰z + 口t p 兰、+ a ：p ：+ a 3 夕： + a 4 p j 2 二i 三亍三；：二， ( 4 ，) 俘! 力。把以懈加碱怕 水剐2 玎 ip ；置= 以。p 兰：+ d ，p ：，十a z p ：+ a p ：，+ 口。p ：z1 _ 1 s2s j ：5 1 甘二仃一三：卜! 棚：一三“+ 罢，旷髓十筹，旷一专扩云川a 。 兰纛三誊二嘉三纂磊三纛：且砉四巍差细募法 该算法满足式( 2 1 ) ，生成的极限曲线插值所有生成息且伺纠川卅4 一“ 2 燃右几何音鹫。由于对称性，仅讨论p 描由式( 4 1 ) 可得： 窃锃泱且有门。何意义，由于对称性，仅诃化p 3 i - l 出n 、：“。 p ；：。：( 吉p 兰。+ 吾p ? ) 十吉 ( 吉p 三+ ；p ：) 一( 吾p ：z + 吾p 1 ) j 、 + 二f f p ? 一( 丢p 兰。+ 丢p ：。+ 专 ( 圭旌：+ 丢p 竺：) 一( 圭蘸t + 丢p ：t ) 复旦大学硕士学位论文 1 ，- - 7 一一一一一一一= _ = = 害黼l ，7 v 一：遗卜： i 。= i 一一要簟慧纛7 o i ，一f 、i 一一 ll4f j 二7 + 3 h 十1 ) 9 i 、 一一 一 | = l 、鬈一一五麓弦一j 讯2( 唑7 + 嗡。) 2 4 2 连续性一充分条件 与三进制四点法类似，考察控制点的分量情况 群碾 ? 一，我们可以得到 几个算法2 各阶连续的充分条件 定理4 1当一兰 材 竺时，细分算法s 一致收敛，即s c o 2 。71 0 8 证明令群= 3 ( 藏。一p ? ) ，由式( 4 1 ) ，可以得到s 的一阶均差细分法s ： 剞= 一言“戤。+ ( 吾甜+ 寺) + ( 一三甜+ 等) 碓。+ ( 三“一寺) ： 球1 = ( 吉甜一寺) 。+ ( 一吾掰+ 等) 群+ 睦秘+ 寺碓。一丢“硅： ( 4 2 ) 【制= 缸：+ ( - 2 甜一寺苁t 当一茜盖时，有 宣一 材 h 一，伺 2 71 0 8 + ( 3 甜+ 等) 影+ ( _ 2 “一寺) 砝。+ 兰“： f l - 言“三“+ 寺一吾甜+ 豸丢”一寺f 3 旧甜一2 “一刍3 “+ 茜_ 2 “一刍三“i 3 由此可得，对于任意的初始值，吾s 均一致收敛于。函数，由定理2 可知s 一 致收敛，即s c o 证毕 定理4 2 当一去 甜 寺时，细分算法s 一阶连续，即s c 1 证明令p j ：3 。( d 兰一) ，由式( 4 2 ) ，可以得到s 的二阶均差细分法& ： 复旦大学硕士学位沦文 p 描_ ( 3 “一小6 “+ 咎。邯甜一转 8 ；“= 弘l + ( 也+ 扣+ ( 萼甜+ 弘小3 咖兰： ( 4 3 ) p 篇= 3 “p 墨，+ ( 萼“+ ；) p ? + ( 一6 甜+ 三) e 兰。+ 吾“p 兰： 当一上 甜 ! 时，有 5 42 7 3 “一针也+ 扣陬一扣 吾甜i + ! 一6 扰+ 吉i + l 萼“+ ；l + i 一3 “ 3 由此可得，对于任意的初始值，三均一致收敛于。函数，可知s c t 。 证毕。 定理4 3 当去 “ 刍时，细分算法s 二阶连续，即s c 2 证明令：。= 3 。( p 二，一p j ) ，由式( 4 3 ) ，可以得到 s r 的三阶均差细分法s 。： 础：昙够t + ( 一等蹦+ 孤。+ ( m 一瓤： 露“：一娶谚t + ( 2 7 川) 芘+ ( 一孕“) z ! ： ( 4 4 ) 制：( 1 8 甜一鲫+ ( 一等甜+ 孤。+ 昙碟： 当土 甜 上时，有 5 42 7 + i 萼“一卦一扣 【i2 7 甜l + i2 7 “+ 1l 3 由此可得，对于任意的初始值，昙s 均一致收敛于。函数，可知s c 2 证毕 4 3 连续性一必要条件 与中的处理方法相同，我们将分析极限函数在标志点的连续性即分别 讨论极限函数在顶点和中点各阶连续的必要条件然后将参数范围求交得到极 限函数各阶连续的必要条件顶点和中点的细分过程与参数的对应关系见图1 0 和图11 设 巾“是算法2 第m 步细分后所得到的值，矽的对应参数为 ，= 一j ； 寺( o f 3 ”门) ，如果其极限函数存在，则记为厂( x ) ，即厂( 3 ”f ) = 1 9 复旦大学硕士学位论文 1 标志点是顶点的情形 定义7 维向量p = ( 磋，磋，e ，碚，芹，毯，霹) 7 ，劈对应于参数3 f + 3 - ( 卅峒 ( = 一3 ，一2 ，一l ，o ，l ，2 ，3 ) 上的细分值( 图1 0 ) ，o f 3 ”门易知 ，o = ( 罐，诧：，硭。，p ：。，以：，藏，) 。，且罐= 霹= 对任意的尼o 均成立 曾1 簟1 畸+ 1 啼+ l 寸+ 1 咕+ 1 时+ 1 星竺笠笠空笠竺 j ：；j 2 jj 2 jj 二jt 二j 、：jj 2 ；j 二jl 2 j j 二：? 二j 0 。 ! 。 i ， 。、 ，i，j ，+ ) 左、，- ， l 。 ，j +，1f - jf ij )f 1f 1r 1 ；主；i主 rrr 1 r= 广rrrrr 一 一7。 二二二 。 。一 m ： 。 一 7 。r l ju 广u广。 图1 0 项点的细分过程标志点瑶对应的参数是3 ”f 令p = ( 1 ，1 ，1 ，1 ，1 ，l ，1