中文摘要 本文主要研究了一類曲線的多分辨率多進(jìn)制算法。從已有的線性多分辨率細(xì) 分算法出發(fā)，用對(duì)應(yīng)弦三分的方法來(lái)構(gòu)造一類三進(jìn)制的多分辨率細(xì)分法則。并且 在三進(jìn)制模板上給出誘導(dǎo)算法的定義，讓生成的近似曲線達(dá)到更高的光滑性。 文章先在第二章中2 1 中給出非線性三分多分辨率細(xì)分算法的定義以及 主要結(jié)果，然后在2 2 中給出證明所用的相關(guān)的一些引理，在2 3 中給出主 要定理2 1 的證明過(guò)程，定理2 1 證明了上述定義下的細(xì)分法則是一種細(xì)分算法。 同時(shí)研究了這個(gè)正則三分多分辨率細(xì)分算法的收斂性和穩(wěn)定性，證明了基本的正 則三分細(xì)分算法生成的極限近似函數(shù)滿足l f p 阻0 l o g i 垃i i “。2 4 中給出定理2 2 的證明過(guò)程，證明了小波參數(shù)精密地依靠基本的細(xì)分算法。正則多分辨率近似的 收斂性等于這個(gè)基本細(xì)分算法的收斂性。 在第三章中，通過(guò)對(duì)模板的研究，在3 1 中給出一類基于第二章基本三分 細(xì)分算法的誘導(dǎo)細(xì)分算法的定義以及基本性質(zhì)，此類e h = 進(jìn)制模板推導(dǎo)的誘導(dǎo)算 法，可以讓細(xì)分算法生成的近似曲線達(dá)到更高的光滑性。在3 2 中，給出了此 類誘導(dǎo)算法收斂性的證明。在3 3 中給出了一些具體的三進(jìn)制細(xì)分算法的例 子。 關(guān)鍵詞：多分辨率細(xì)分算法，正則三分法，多分辨率近似，小波參數(shù) 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 第一章細(xì)分格式概述 本章首先在1 1 中描述了細(xì)分方法產(chǎn)生的歷史背景及其發(fā)展過(guò)程，闡述了 細(xì)分方法的基本思想，在1 2 中介紹細(xì)分格式的一些基本定義，基本工具和一 些基本結(jié)果。最后介紹一些經(jīng)典的細(xì)分格式。這些是本文研究的基礎(chǔ)。 1 1 歷史背景 細(xì)分方法起源于曲面造型。由于在實(shí)際工程中對(duì)于大型復(fù)雜設(shè)備外形的研究 和改進(jìn)的需求，于是在計(jì)算機(jī)輔助幾何設(shè)計(jì)和計(jì)算機(jī)圖形學(xué)中，曲面造型的研究 就成為了個(gè)熱點(diǎn)。 從1 9 6 3 年開始，先是在飛機(jī)制造領(lǐng)域，繼而在汽車等其他工業(yè)領(lǐng)域，人們 漸漸對(duì)于參數(shù)控制的曲線曲面的研究發(fā)生了濃厚的興趣，得到了一些參數(shù)控制曲 面的研究成果。 但是這些參數(shù)曲面，不能表示任意拓?fù)浣Y(jié)構(gòu)的曲面，極大限制了曲面造型的 在現(xiàn)實(shí)工作中的應(yīng)用，遠(yuǎn)遠(yuǎn)不能適應(yīng)計(jì)算機(jī)輔助集合設(shè)計(jì)以及計(jì)算機(jī)圖形學(xué)中對(duì) 于顯示真實(shí)性、實(shí)時(shí)性的具體要求。同時(shí)隨著計(jì)算機(jī)輔助幾何設(shè)計(jì)對(duì)象的多樣性、 特殊性和拓?fù)浣Y(jié)構(gòu)復(fù)雜性的逐漸提高，普通參數(shù)曲面已經(jīng)不能滿足這一需求。細(xì) 分方法( s u b d i v i s i o n ) 正是應(yīng)這種要求而產(chǎn)生的。 1 1 1 相關(guān)：亡作 細(xì)分方法最早可追溯到1 9 5 6 年r h a m 提出的一種稱為“c o m e rc u t t i n g ”細(xì) 分算法。該算法的思想就是將平面上的一個(gè)多邊形的每一條邊按i ：2 ：l 的比 例分割，然后通過(guò)割角，得到一個(gè)新的多邊形。不斷的重復(fù)此過(guò)程，就得到一個(gè) 多邊形序列。它的極限是一條連續(xù)可微的曲線。 由于這一算法具有很快的收斂速度，1 9 7 4 年c h a i k i n 2 1 把該算法做了進(jìn)一步 推廣。 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 分別給出了在任意網(wǎng)格上設(shè)計(jì)雙三 次和雙二次曲面算法。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 樣條曲面的細(xì)分算法。隨后又提出了很多著名的細(xì) 分算法，如l o o p 算法、蝶型算法等。與此同時(shí)，細(xì)分方法理論方面的研究也得 到了很大的發(fā)展。單變量細(xì)分格式具有任意階光滑性的充要條件7 。8 】的提出以及 多變量細(xì)分格式在任意拓?fù)淝樾蜗率諗啃苑治龅睦碚摽蚣? 4 1 1 的建立，揭示了各 種細(xì)分格式的內(nèi)在聯(lián)系。細(xì)分方法如今已成為曲面造型理論研究和實(shí)際應(yīng)用中的 熱點(diǎn)。 1 1 2 細(xì)分格式的基本思想 對(duì)于曲線曲面的細(xì)分格式而言，由上一層點(diǎn)集計(jì)算下一層點(diǎn)集的計(jì)算規(guī)則一 般要求具有以下一些性質(zhì)： 可以高效的由上一層的點(diǎn)集計(jì)算得到新的下一層點(diǎn)集。 初始點(diǎn)列網(wǎng)格上任一點(diǎn)只能影響極限曲線曲面的有限局部。 新點(diǎn)的得到只依賴于原始曲線曲面拓?fù)渖舷噜彽挠邢迋€(gè)點(diǎn)。 若初始網(wǎng)格平移、放縮或旋轉(zhuǎn)，極限曲線曲面也被同樣變換，拓?fù)浣Y(jié)構(gòu)不變。 規(guī)則簡(jiǎn)單，易于計(jì)算。 極限曲線曲面應(yīng)具有一定的光滑性，光滑性由具體的細(xì)分方法而定。 細(xì)分方法作為一種原始曲線曲面的近似曲線曲面的生成工具，其實(shí)質(zhì)是一種 迭代算法?；舅枷刖褪侵鸫渭用?，從初始的點(diǎn)集出發(fā)，采用細(xì)分規(guī)則計(jì)算插入 新的點(diǎn)并不斷加密加細(xì)，并最終生成極限曲線曲面。 1 2 細(xì)分格式的一些基本定義和研究進(jìn)展 本小節(jié)簡(jiǎn)述細(xì)分格式的一些基本定義以及一些現(xiàn)有的研究進(jìn)展。 定義1 i ： 細(xì)分格式( s u b d i v i s i o ns c h e m e s ) 是定義在網(wǎng)格點(diǎn)集序列上的一系列細(xì) 分規(guī)則集合，每一個(gè)細(xì)分規(guī)則將定義在實(shí)數(shù)域上的網(wǎng)格點(diǎn)集映射到新的網(wǎng)格點(diǎn)集 上。細(xì)分格式就是利用這些細(xì)分規(guī)則對(duì)于給定的初始網(wǎng)格點(diǎn)集進(jìn)行逐次細(xì)化。 細(xì)分規(guī)則在第k 層具有形式： 丘“= 口 ( 1 1 ) 口 其中，為k 層的網(wǎng)格點(diǎn)集序列，“1 為k + l 層的網(wǎng)格點(diǎn)集序列，a 為k 層的細(xì) 分規(guī)則。 上式可以將其記作算子的形式： 系數(shù)集合a 稱為第k 層模板，它確定了第k 層的細(xì)分規(guī)則。如果模板與細(xì)分 層次k 無(wú)關(guān)，那么就稱細(xì)分格式是穩(wěn)定的，否則就稱為非穩(wěn)定的。對(duì)于非穩(wěn)定的 細(xì)分格式，它的第k 層的細(xì)分規(guī)則由a 2 確定。 細(xì)分格式可以記做s o l ，或?qū)懗伤阕蛹系男问解畹Vj 。 若下一層點(diǎn)列中包含上層點(diǎn)列，則它對(duì)應(yīng)的細(xì)分格式稱為插值型細(xì)分格 式，否則稱為擬合型細(xì)分格式。 i _ 己a ( a 。) = 忉i d ：o j 是模板d 的支集。如果仃( 口) 是有界的，則稱模板d 是 緊支的?，F(xiàn)階段對(duì)于緊支的情形理論比較完善。 1 2 1 細(xì)分格式的收斂性的定義 定義i ，2 ： 給定初始點(diǎn)集，。，連續(xù)函數(shù)，稱為，。關(guān)于細(xì)分格式沁- 的極限 函數(shù)，如果 腳s up | 露一i i = o ( 1 2 ) 這個(gè)極限函數(shù)也可記做s i t ，。其中，f 由( 1 1 ) 遞歸定義a 同時(shí)，與某一緊集上的每一細(xì)化層上通過(guò)這些插值點(diǎn)的線性折線樣條函數(shù) 序列慨) 的一致極限函數(shù)是等價(jià)的，也就是說(shuō) 疋) 滿足： r ( f ) = 露( f ) ( 1 _ 3 ) 其中t 是k 層上的插值點(diǎn)。 從這一等價(jià)性可以得到： 憋s u l _ f ( t ) 一 ( f ) f _ 0 ( 1 4 ) 定義1 3 ：細(xì)分格式稱為一致收斂的，如果對(duì)于任意的初始網(wǎng)格點(diǎn)集，存在一 個(gè)形如( 1 2 ) 的極限函數(shù)，或等價(jià)地，存在一個(gè)形如( 1 - 4 ) 的分段折線函數(shù)的 極限函數(shù)：并且至少存在一個(gè)初始網(wǎng)格點(diǎn)集，使得極限函數(shù)是非平凡的。 一致收斂的細(xì)分格式，如果對(duì)于任意初始點(diǎn)集，它的極限函數(shù)存在m 階連續(xù) 導(dǎo)數(shù)，則這個(gè)細(xì)分格式稱為c 1 或c “收斂的 n d y n 和d l e v i n 【1 2 1 的文章給出了基本極限函數(shù)的一些結(jié)果。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 的文章則研究了基本極限函數(shù)和細(xì)化方程的關(guān)系：如果不考慮 乘數(shù)因子的因素，細(xì)化方程的解是唯一解。在求解細(xì)化方程時(shí)，l d a u b e c h i e s 1 4 1 使用了一種并不求細(xì)分格式基本極限函數(shù)的方法。 1 2 2 生成多項(xiàng)式 作為分析細(xì)分格式收斂性和光滑性最重要工具的細(xì)分規(guī)則( 1 1 ) 也可以表示 成z 變換( l a u r e n t 級(jí)數(shù)) 的形式。定義模板a 的生成多項(xiàng)式為l a u r e n t 多項(xiàng)式： a k ( z ) = z 8 ( 1 5 ) 舵z 顯然，一個(gè)細(xì)分格式s 川可以由生成多項(xiàng)式集合f 4 2 ( 。) 唯一確定。研究中 并不嚴(yán)格區(qū)分模板和它的生成多項(xiàng)式。 對(duì)于細(xì)分格式收斂性的研究，0 r i o u l l l 5 1 研究了單變量細(xì)分格式，給出了更精 確的結(jié)果。對(duì)于變量細(xì)分格式的收斂性和細(xì)化方程的解之間的關(guān)系， 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 建立了穩(wěn)定細(xì)分格式收斂性和非 穩(wěn)定細(xì)分格式收斂性之間的聯(lián)系。同時(shí)得到了非穩(wěn)定細(xì)分格式生成的基本極限函 數(shù)的光滑性的結(jié)果。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 的文章也研究 了此類問題。 最簡(jiǎn)單的細(xì)分格式是單變量穩(wěn)定均勻細(xì)分格式。n d y n 和d l e v i n 【1 2 1 對(duì)于 均勻非穩(wěn)定基本細(xì)分格式做了比較細(xì)致的研究。 插值型的細(xì)分格式，是目前得到的研究成果較多的一種細(xì)分格式類型。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 都在此 領(lǐng)域做了比較深入的研究。k u q t 和v a nd a t u m e 2 1 1 給出了一種非線性、穩(wěn)定、具 有保形性的4 點(diǎn)插值細(xì)分格式。從一個(gè)具有嚴(yán)格凸性的初始點(diǎn)集出發(fā)， 2 1 中證 明了其極限函數(shù)是嚴(yán)格凸的，且屬于c 1 。k u i j t 和v a nd a m m e 還進(jìn)一步得到它具 9 有保單調(diào)性2 珥的結(jié)果。 進(jìn)步，還可以應(yīng)用該保形細(xì)分格式，在一定條件下，從一個(gè)嚴(yán)格凸的初始 點(diǎn)集得到一個(gè)凸的基本極限函數(shù)2 3 1 。 此外，還有矩陣細(xì)分格式、h e r m i t e 型細(xì)分格式、；細(xì)分格式等很多細(xì)分 格式。這些細(xì)分格式的研究工作可以參見文章t 3 6 - 3 8 1 。 更進(jìn)一步，對(duì)于3 d 空間上具有任意拓?fù)浣Y(jié)構(gòu)的網(wǎng)格細(xì)分格式。早期的工作 有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 樣條 構(gòu)造了任意三角形網(wǎng)格的二分細(xì)分算法。最近則有許多細(xì)分格式被提出【2 9 - 3 3 1 。 但是，現(xiàn)階段幾種細(xì)分格式的研究主要幾種在線性鄰域，對(duì)于多進(jìn)制非線性 的細(xì)分方法研究的很少，本文第二章、第三章的主要工作就是給出了一種非線性 三進(jìn)制細(xì)分法則的定義，并研究了這類三進(jìn)制非線性細(xì)分法則的一些性質(zhì)，同時(shí) 從這個(gè)細(xì)分法則里面得到了一類基于這個(gè)基礎(chǔ)三分算法的誘導(dǎo)細(xì)分算法。 1 0 第二章非線性三分多分辨率細(xì)分算法 第二章主要研究了一類曲線的多分辨率多進(jìn)制算法，從fd a u b e c h i e s 與 nr u n b o r g 提出的對(duì)分法線細(xì)分算法 2 4 中得到啟發(fā)。用對(duì)應(yīng)弦三分的方法來(lái)構(gòu) 造一類三進(jìn)制的多分辨率算法。 我們先在2 1 中給出非線性三分多分辨率細(xì)分算法的引用、定義以及主要 結(jié)果，然后在2 2 中給出證明所用的相關(guān)的一些引理，在2 3 中給出定理2 1 的證明過(guò)程，研究正則三分多分辨率細(xì)分算法的收斂性和穩(wěn)定性，證明了基本的 正則三分細(xì)分算法生成的極限近似函數(shù)滿足l 咖l r i | l o g i 出曠。2 4 中給出定理 2 2 的證明過(guò)程，證明了小波參數(shù)精密地依靠基本的細(xì)分算法。正則多分辨率近 似的收斂性等于這個(gè)基本細(xì)分算法的收斂性。 2 1 細(xì)分法則的定義及主要結(jié)果 一下面先給出下文中用到的一些符號(hào)的定義： ( 1 ) s ，：即為文中定義的曲線上非線性三分多分辨率細(xì)分法則。例如對(duì)于 點(diǎn)列 x 。 ，s ，工j = z j + 1 l 即在點(diǎn)列 工，l 上應(yīng)用下文定義的細(xì)分法則后得到的 下一層的點(diǎn)列f z 。 。 ( 2 ) il ：是下文中常用到的極大范數(shù)，f x l 。= s 印i 以i 。 ( 3 ) 為差分算子：( x ) = + 。一x 。， k 為整數(shù)。 ( 4 ) ( p c ”( ，) ：函數(shù)( p 弱p 階可微， c - ( ，) = ( p i l 幣o + f ) 一似f ) l - c l 出l i l o g l 血l l “ 二三進(jìn)制細(xì)分法則的定義： 對(duì)于原始光滑曲線上采樣得到的原始點(diǎn)列，先從相鄰點(diǎn)的具體坐標(biāo)值來(lái)計(jì)算 這對(duì)相鄰點(diǎn)之間的局部法向( 仿照上g u s k o v 與冗v i d i 口c e 在 2 8 中的方法) ，然 后基于這對(duì)相鄰點(diǎn)的弦三分和這個(gè)局部法向來(lái)計(jì)算得到原始曲線在這對(duì)相鄰點(diǎn) 之問的下一層點(diǎn)列，通過(guò)細(xì)分法則的迭代計(jì)算，就得到原始曲線的多分辨率逐層 點(diǎn)列，以及逐層的小波參數(shù)的長(zhǎng)度。 如下圖所示，設(shè)只，只是原始點(diǎn)列中相鄰的兩個(gè)點(diǎn)，把這兩個(gè)點(diǎn)由直線連 接起來(lái)，在這條直線上計(jì)算出弦三等分點(diǎn)吼一2 3p 。, + 只和q 一2 3p , + j 1p 。，再?gòu)?0 0 ，0 1 沿著r ，只連線的局部法向做直線，與原始曲線相交于焉，只，則這新 求得的巧，只+ 就是我們所需要計(jì)算得到的在相鄰兩點(diǎn)p 0 ，只 司的t - - n n a 。 這種插值方法即為三分細(xì)分法則。不斷重復(fù)這種細(xì)分法則，就可以由原始點(diǎn)列， 得到多分辨率不同細(xì)節(jié)水平的逐層點(diǎn)列。 另一方面，假設(shè)我們用上述細(xì)分方法v ，次迭代插值后，得到j(luò) 層的兩個(gè)相鄰 點(diǎn)：晶2 ( 工似，y 卅) ，置5 ( x 塒。y j , k + i ) ，則根據(jù)上面的等式，可計(jì)算出o o ，o l 兩點(diǎn)： 氏= ( 工二。m + 。，y 二1 , 3 k + 1 ) ，q = ( z 二。+ ：，y 二。+ ：) 。 同時(shí)，我們可以從上一層的相鄰點(diǎn)r 和只來(lái)計(jì)算得到法線方向，并且通過(guò) 計(jì)算o o ，0 1 沿法線方向與原始曲線相交的值來(lái)得到新的插入點(diǎn)。這樣就可以求 出戶1 層的插入點(diǎn)巧2 ( x + 。m 。y i + 1 , 3 k + 1 ) ，只+ 2 ( x _ 3 k 。y + j + ，。+ ：) ，其中o o 和巧 之間的距離可以看作層的小波參數(shù)w 。 w j 。= ( z 二，m + 。一j ：+ l 。+ 。) 2 + ( y 二。m + 。一y ：。，。) 2 這個(gè)小波參數(shù)長(zhǎng)度的收斂速度與三分法的公式的最高階數(shù)有關(guān)。注意到，新 插入的點(diǎn)曙，只+ 地位相等，所以驗(yàn)證的時(shí)候只需要驗(yàn)證其中之一，另外一個(gè)可 以相似證明。 同時(shí)，注意到對(duì)于任意一個(gè)曲線上的給定點(diǎn)，y 軸上投影的值可以表達(dá)為這 點(diǎn)在x 軸上投影值的連續(xù)函數(shù)y = y ( x ) ，所以，我們只需要證明點(diǎn)列在x 軸上投 影的值對(duì)于這種三分細(xì)分法則收斂且光滑，且對(duì)于x 的連續(xù)函數(shù)，這種收斂也成 立。則就可以證明這種三分細(xì)分規(guī)則是多分辨率細(xì)分算法。 這個(gè)定義f 的細(xì)分算法有如f 的主要結(jié)果： 定理2 1 ：設(shè)扛j ，“，以v ，s ，是我們上述定義給出的變量以及細(xì)分規(guī)則，對(duì)于 給定的丘有r 卅= k 3 一，是一個(gè)給定的區(qū)間。竹是j 層的分段線性折線 函數(shù)，竹( f ) 即為在t 肚上對(duì)應(yīng)的點(diǎn)為z ”。若k l o o ，則存在一個(gè)函數(shù) 妒c 。( ，) ，使得妒j - 妒成指數(shù)收斂，即妒滿足： 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 一“ 一細(xì)線b 0 ) - 原始曲線 一粗線毋- ( f ) 定理2 。2 ：設(shè)s 。是前面所描述的三分插值法，y = y ( x ) 是y 關(guān)于x 的連續(xù)函數(shù)，且 有： 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 主要證明了這個(gè)新定義的三分細(xì)分算法是一種多進(jìn)制的多分 辨率算法。 定理2 - 3 ：設(shè)s 是前面所描述的三分插值法，則相應(yīng)的小波參數(shù)w l ，。滿足 w ，i 。c 3 叫”y c “( r ) ，m n m - 10 0 由于等式右邊所有字母均為常數(shù)，所以等式右邊其實(shí)是一個(gè)常數(shù)。 其次，定義剩余變量r 為 0 + i = 0 “一s 3 工r o = x o 則根據(jù)上面的定義我們有： i 。l 。= j t + 。- s ，彳，i 。sd ( j + 1 ) “3 一5 s 0 ( 2 1 ) 其中v ，a ，a 均為大于0 的常數(shù) 另一方面，三分細(xì)分法則有如下模板公式： ( 足工) 。= 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 。的細(xì)分法則的定義，有s ，1 = 1 ( 1 是恒為1 的點(diǎn)列) 。同時(shí)根據(jù)模板 公式易得： 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 - 。川。 其中為差分算子：( 工) 。= 以“一五 得證 下面定義一個(gè)引理2 1 中會(huì)用到的幾何級(jí)數(shù)： 甲( 口 叻= 七8 口 明顯，當(dāng)a l 時(shí)，這個(gè)級(jí)數(shù)會(huì)小于一個(gè)于a ，口有關(guān)的常數(shù)c 引理2 1 ：設(shè)扛j ，0 c ，n ，v ，s ，是我們上述定義給出的點(diǎn)列、變量以及細(xì)分規(guī)則 則存在一個(gè)獨(dú)立于a ，x o 的常數(shù)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 ” 應(yīng)用( 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 均為常數(shù)) 得證。 2 3 定理2 1 及定理2 2 的證明過(guò)程 定理2 1 ：設(shè)b j j ，0 【，口，v 。s ，是我們上述定義給出的變量以及細(xì)分規(guī)則，對(duì)于 給定的血有”= k 3 一。，是一個(gè)給定的區(qū)間。哆是j 層的分段線性折線 函數(shù)，竹( f ) 即為在t 卅上對(duì)應(yīng)的點(diǎn)為_ 。若k l 0 ，并應(yīng)用前文所證的命題 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 另一方面，設(shè)3 一l a t l 1 。再應(yīng)用引理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 。均為常數(shù)。 得證。 1 7 + 窆啾 +x一 定理2 2 把y 軸的值看成是x 軸值的函數(shù)，證明了y 也收斂。 定理2 2 ：設(shè)s ，是前面所描述的三分法則，y = y ( x ) 是y 關(guān)于x 的連續(xù)函數(shù)，且有 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 ) ，所以對(duì)于任何一個(gè)給定的k ，可以把y ( x ) 在( s ，x ) 。泰 勒展開。同時(shí)注意到s 。1 = 1 ，我們有： (y(s3x)一s3y(x)。_(s，m(x-(s3xun竺粵業(yè))。+(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 的證明過(guò)程 最后，定理2 3 證明了小波參數(shù)的收斂性依賴于基本的正則三分細(xì)分算法的收斂 性。 引理2 2 l 設(shè)s ，是前面所描述的三分規(guī)則，y ( x ) 是y 關(guān)于x 的連續(xù)函數(shù)，且有 y c 4 ( r ) ，如果 上j 與 舅) 均為遞增的點(diǎn)列， 膏 為 z ) 在三分法則作用下的下 一層點(diǎn)列i = s 工，同時(shí)蘆l 且y 是一致連續(xù)，則對(duì)于足夠小的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 ) ) 。同時(shí)根據(jù) 三分法細(xì)分的規(guī)則，對(duì)于點(diǎn)序列x 和它的下一層點(diǎn)序列膏，我們有： ( 寫。一x ；。) ( z ) 。+ ( ，( 葛。) - y ；。+ ) ( 緲) t = 0 ( 2 - 2 ) 對(duì)于給定的k ，若y c i ( r ) ，則存在一個(gè)鼻 i i l i n ( 躉，x + ) ，m a x ( 躉，x ) 】，使得 y w ，) ：塑掣 ( 2 3 ) 對(duì)于遞增點(diǎn)列z 中的點(diǎn)x 。、x 。+ 1 存在f ： x 。，x ?！渴沟?y w ：，= 紫= 焉 c z 鍆 其中，( 2 4 ) 中后面一個(gè)等式由( 2 2 ) 式得到。 于是上面兩個(gè)等式( 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 也是遞增的點(diǎn)列，且x 。芟墨x 。，則應(yīng)用命題2 1 結(jié)果，有： 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 充分小，對(duì)于一致連續(xù)的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 。，則存在一個(gè)函數(shù)中c 。一( ，) ，使得仍_ 壚成指數(shù) 收斂，即母“1 滿足： 眇( h 出) 一( p ”訓(xùn)。- c l & l 。( 1 + 1 1 0 9 蚓) 1 v t ，t + a t ， 3 一。蚓 0 ( 3 1 ) 由于等式右邊所有字母均為常數(shù)，所以等式右邊其實(shí)是一個(gè)常數(shù)。 同時(shí)，由于s 的有界性，若取參數(shù)p ，其中p 滿足0 2 p p ，則存在一個(gè) 相應(yīng)的實(shí)數(shù)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 尹 則根據(jù)上面的定義我們有如下遞推式 ( 3 1 0 ) 螺“| 。= 3 “i m 刪l c 3 “渺i 。s o ( 3 3 ) 其中中是上文中用定義的算子 同時(shí)，根據(jù)( 3 3 ) 式，我們有： j t 9 1 i 。 3 l k + b ) 3 3 命題3 5 l 對(duì)于任意一個(gè)穩(wěn)定的細(xì)分算法s ( 其中s 的首一多項(xiàng)式系數(shù)p 0 ) 有： m a x l ( s x ，) t t z i _ c 3 一i x , i 。 證明：由于s 的是穩(wěn)定的細(xì)分算法，有s 1 = 1 ( 1 是恒為1 的點(diǎn)列) 。同時(shí)根據(jù)模 板公式易得： 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 ：設(shè)矗j j ，a ，n ，v ，s 。，p ，扯，( 其中p 滿足o 2 p p ) 是我們上述定 義給出的點(diǎn)列、變量以及細(xì)分規(guī)則，設(shè) 丸= m a x ( p v ，h ) 則存在一個(gè)獨(dú)立于a ，z 驢1 的常數(shù)g 使得下面的不等式成立 l 工，1 i 。c ，( i 工護(hù)1 i 。+ 口) ( 1 + j 3 對(duì)) 其中 ia t 1 。= c c + l 1 0 u p 一” 礬俐。= 眇制峭1 h s 2 粥刑制刮。= 伊卯制1 應(yīng)用( 3 4 ) 有 i s p ij 。俐。+ 伽主q = o 妒刊4 s 叫訓(xùn)” 再應(yīng)用( 3 。2 ) 有： sc 。3 時(shí)阿l 。+ c ：口j - t 3 ( 卜q ) n 3 廿舯訓(xùn) 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 + 產(chǎn)3 嬸) ( 其中c ，c ：，c 3 均為常數(shù)) 得證。 引理3 2 各個(gè)符號(hào)的假設(shè)和引理3 1 中一樣，假設(shè)0 j 。 p q + 1 九= p q + 1 九 p q + 1 定理3 1 ：設(shè)扛j j ，c ，口，v ，s ，p ，p ( 其中p 滿足o s2 p 尸) ，是我們上述定 義給出的變量以及細(xì)分規(guī)則，對(duì)于給定的幺有卅= k 3 一i ，是個(gè)給定 的區(qū)間。伊，是，層的分段線性折線函數(shù)，妒，( r ) 即為在m 上對(duì)應(yīng)的點(diǎn)為_ 設(shè) 九= m a x ( p v ，u ) q = t 一九= n + l c 其中 r = 引 p 為誘導(dǎo)算法，首一多項(xiàng)式的系數(shù)。 若q 0 且k i 。 o o ，則存在一個(gè)函數(shù)中c q - ( ，) ，使得p ，- 妒成指數(shù) 收斂，即( 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 ，并應(yīng)用前又 所證的命題3 1 和引理3 1 ，得到： 鯽一叩扎1 - 1 s 叫槲( r ) 一”叫 2 萎s 帥要巾圳巾) | 2 萎j - i 節(jié)陋 e l 廠c 爭(zhēng)一+ j 1 批、) | 唼z s u pm a x l e i 。 搬t(yī) 卅f 于是若有0 蔓2 q p 0 另一方面，設(shè)3 一1 血i 1 。再應(yīng)用引理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 均為常數(shù) 得證 3 3 幾個(gè)誘導(dǎo)細(xì)分算法的例子 1 如圖3 1 中所示，空心圓代表上一層點(diǎn)列中的點(diǎn)，實(shí)心圓代表計(jì)算得到的 下一層點(diǎn)列中的點(diǎn)。 由兩個(gè)相鄰點(diǎn)用三分法計(jì)算下一層點(diǎn)列： s 3 x i = x i + l j 0 于是根據(jù)定理3 1 及其引理，我們可以確定： “= 0 ，p = 1 ，n = 0 ，1 ( = 1 ，q = 0 再帶入定理3 1 的結(jié)果： 妒( 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 剖& 妒 化簡(jiǎn)之后為： l ( p o + r ) 一( p ( f 。sc l o t l 這個(gè)相鄰兩點(diǎn)的三分法則其實(shí)就是本文第二章的基本三分細(xì)分算法。 圖3 1 2 如圖3 2 中所示，空心圊代表上一層點(diǎn)列中的點(diǎn)，實(shí)心圓代表計(jì)算得到的 r 一層點(diǎn)列中的點(diǎn)。 圖3 2 中是用相鄰4 點(diǎn)來(lái)計(jì)算下一層點(diǎn)列，設(shè)相鄰四點(diǎn)分別為： z k ，工j ，t + l 工 十2 x d ，k 十3 則根據(jù)誘導(dǎo)算法的定義，我們從這四點(diǎn)里計(jì)算出： 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 再把這計(jì)算出的兩點(diǎn)z 似，z 肚+ 用基本的三分細(xì)分法則進(jìn)行計(jì)算。 根據(jù)命題3 3 的結(jié)果，基本的三分細(xì)分法則可以達(dá)到c 。的光滑性，同時(shí)相鄰 四點(diǎn)計(jì)算方法有 s ；0 1 = s 3 ，s 5 1 m = 由s ；川1 ，其中p = 1 為算子：( 峨) 。=