（计算数学专业论文）多元样条、分片代数曲线及线性丢番图方程组.pdf

摘要 多元样条函数在函数逼近、计算几何及小波等领域中均有较为重要的应用 另一方面，多元样条与基础数学的一些领域，如：抽象代数、代数几何、微分方 程及组合数学等，亦有着密切关联本文主要针对多元样条在应用中及与其相关 的基础数学领域中提出的一些问题进行研究考虑的问题主要为：样条函数空间 维数的奇异性、分片代数曲线b e z o u t 定理、整系数线性方程组非负整数解个数及 与其相关的组合数学问题主要工作如下： ( 1 ) 利用多元样条对散乱数据插值是多元样条一个重要的应用领域要使插 值的多元样条函数存在且唯一，一个必要条件是插值点数与多元样条函数空间的 维数一致。另一方面，人们对多元样条维数的研究亦有理论上的兴趣因此，多 元样条维数的研究是较重要的通常的，我们将剖分上k 次p 阶光滑的样条 函数空间记为罐( ) ，其维数记为d m 甜( ) 对于m o r g a n s c o t t 剖分人们 发现击m 是( 。) 严重依赖于剖分的几何特征【5 8 】，这个性质称为样条空间维数 的奇异性。因此，m o r g a n s c o t t 剖分上样条空间维数的研究一直令人感兴趣。施 锡泉在【6 6 中讨论了d m 霹( 。) 的变化特征，并对高维m o r g a n - s c o t t 剖分上的样 条空间维数奇异性进行了讨论d m n e r 在f 4 4 l 中对d m 躁( 。) ，r 0 进行了讨 论，发现d m 跞( 。，) ，r 0 也依赖于剖分的几何特征除此之外，d i e n e r 证明了 d m 岛( 。) ，d 2 r 不依赖于剖分的几何特征。文 4 6 】中对击m 躁( 。) ，r 0 进行 了进一步研究但迄今为止我们并不知道当d 2 r w a ss t a b l e b u tt h e r ei sn o ta n yr e s u l ta b o u tt h ed i m e n s i o no f 岛( m 5 ) ，d 2 r 一1 i nt h i st h e s i s ，t h ed i m e n s i o no f 彤( 。s ) ，d 2 r li sd i s c u s s e d t h e f o l l o w i n gr e s u l t sa r ep r e s e n t e d ：w h e nd 墨；r ，d i m s 5 ( m s ) = ( 4 j 2 ) w h e nd ；_ d i m s ：( 。) b e c o m e ss i n g u l a r i t y t h es i n g u l a r i t yo fd i m s 5 ( 。) i n c r e a s e s a l o n g w i t hd i n c r e a s i n gf i r s t l y , t h e ni td e c r e a s e sa l o n g w i t hd i n c r e a s i n g n e a r 警r ， t h es i n g u l a r i t yr e a c h e st h em a x i m u m w h e nd 2 r ，t h es i n g u l a r i t yv a n i s h e s ( 2 ) ap i e c e w i s ea l g e b r a i c c u r v ei sac u r v ed e t e r m i n e db yt h ez e r os e to fa b i v a r i a t es p l i n ef u n c t i o n i ti so b v i o u st h a tt h ep i e c e w i s ea l g e b r a i cc u r v ei sa g e n e r a l i z a t i o no ft h ec l a s s i c a la l g e b r a i cc u r v e t h ep i e c e w i s ea l g e b r a i cc u r v ei s n o to n l yv e r yi m p o r t a n tf o rt h ei n t e r p o l a t i o nb yt h eb i v a r i a t es p l i n e s ( c f 【8 2 ) ， b u ta l s oau s e f u lt o o lf o rs t u d y i n gt r a d i t i o n a la l g e b r a i cc u r v e s ( c f 5 1 1 ) i ti s w e l lk n o w nt h a tb e z o u t st h e o r e mi sa ni m p o r t a n ta n dc l a s s i c a lt h e o r e mi nt h e a l g e b r a i cg e o m e t r y 8 1 i t sw e a kf o r ms a y st h a tt w oa l g e b r a i cc u r v e sw i l lh a v e i n f i n i t e l ym a n y i n t e r s e c t i o np o i n t sp r o v i d e dt h a tt h en u m b e ro ft h e i ri n t e r s e c t i o n p o i n t sm o r et h a nt h ep r o d u c to f t h e i rd e g r e e s d e n o t eb yb n = b n ( m ，r ；n ，t ；a ) t h es o c a l l e db e z o u t sn u m b e r i tm e a n sa n yt w o p i e c e w i s ea l g e b r a i cc u r v e s f ( x ，y ) = 0 ，g ( z ，y ) = 0 ，s 二( ) ，g 畿( ) m u s th a v ei n f i n i t e l ym a n yi n t e r s e c t i o np o i n t sp r o v i d e dt h a tt h e yh a v em o r et h a n i v b i n t e r s e c t i o np o i n t s i n 6 9 ，a nu p p e rb o u n d a r yo fb = b n ( m ，o ；n ，o ；) i sp r e s e n t e d i nt h i st h e s i s ，ac o n j e c t u r ea b o u tt r i a n g u l a t i o nw h i c hi sp r e s e n t e d i nf 6 9 1i sc o n f i r m e d t h er e l a t i o nb e t w e e np i e c e w i s ea l g e b r a i cc u r v ea n df o u r c o l o rc o n j e c t u r ei sp r e s e n t e d b ym o r g a n s c o t tt r i a n g u l a t i o n ，w es h o wt h eb e z o u tn u m b e ro fp i e c e w i s ea l g e b r a i cc u r v ei si n s t a b i l i t y b yu s i n gt h ec o m b i n a t o r i a lm e t h o dw h i c hi sd i f f e r e n tw i t ht h em e t h o di n 【6 9 1a nu p p e rb o u n do ft h e b n ( m ，r ；冠，t ；) i sp r e s e n t e d ( 3 ) d i s c r e t et r u n c a t e dp o w e r sa r e d e f i n e da st h en u m b e ro fn o n n e g a t i v ei n t e g e rs o l u t i o no fl i n e a re q u a t i o n s i ti sc l o s e l yr e l a t e dw i t hm u l t i v a r i a t es p l i n e sa n d m u l t i v a r i a t et r u n c a t e dp o w e r s i ti sw e l lk n o w nt h a tt h en u m b e ro fn o n n e g a t i v e i n t e g e rs o l u t i o n so f l i n e a re q u a t i o n si sv e r yi m p o r t a n ti ns o m em a t h e m a t i c a ls u b j e c t s t h er e s e a r c ha b o u td i s c r e t et r u n c a t e dp o w e r sw i l li n f l u e n c et h es u b j e c t s i n 【3 7 】，t h ec o n c e p to fd i s c r e t et r u n c a t e dp o w e r sw a sp r e s e n t e db yd a h m e u a n d m i c c h e l l i i nf 3 8 1 ，d a h m e na n dm i c c h e l l is h o w e dt h ep i e c e w i s es t r u c t u r eo fd i s c r e t et r u n c a t e dp o w e r s t h el e a d i n gt e r mo fd i s c r e t et r u n c a t e dp o w e r sw e r ea l s o p r e s e n t e d 。i n 2 4 1 ，b yc o m b i n a t o r i c s ，a ne x p l i c i tf o r m u l a t i o no ft h en u m b e ro f n o n n e g a t i v ei n t e g e rs o l u t i o n so fl i n e a re q u a t i o nw a sp r e s e n t e d t h ef o r m u l a t i o n c a nb ec o n s i d e r e da st h ee x p l i c i tf o r m u l a t i o no fd i s c r e t et r u n c a t e dp o w e r so fo n e v a r i a b l e b u tt h em e t h o di nf 2 4 1 i sd i f f i c u l tt ob eg e n e r a l i z e dt os e v e r a lv a r i a b l e s i nt h i st h e s i s ，b ym u l t i v a r i a t et r u n c a t e dp o w e r sa n dm u l t i v a r i a t eb o xs p l i n e s ，a i l e x p l i c i tf o r m u l a t i o no fd i s c r e t et r u n c a t e dp o w e r so fs e v e r a lv a r i a b l e si sp r e s e n t e d i n 5 4 l ，ac o n j e c t u r e a b o u tm a g i cs q u a r ew a sc o n f i r m e d t h ek e yl e m m af o r c o n f i r m i n gt h ec o n j e c t u r ei s as p e c i a lc a s eo ft h ee x p l i c i tf o r m u l a t i o no fd i s c r e t e t r u n c a t e dp o w e r s ( 4 ) b y d i s c r e t et r u n c a t e dp o w e r s ，i ti s p r e s e n t e dt h a tt h ev o l u m eo f c o n v e x p o l y t o p e sa g r e e sw i t ht h ef u n c t i o nv a l u eo ft h em u l t i v a r i a t et r u n c a t e dp o w e r a ta p o i n t b yt h e c o n c l u s i o n am e t h o df o r c o m p u t i n g t h ev o l u m eo fc o n v e xp o l y t o p e s i s p r e s e n t e d a c c o r d i n gt ot h ec o n c l u s i o n ，ar e s u l ta b o u tt h ev o l u m eo fac o n v e x p o l y t o p e ，w h i c hi st h ec e n t r a lr e s u l to f 6 0 ，i sr e p r o v e d ( 5 ) b y d i s c r e t et r u n c a t e dp o w e r ls o m ec l a s s i c a lr e s u l t sa b o u tl a t t i c ep o i n t si n r a t i o n a lp o l y t o p ea r er e p r o v e d t h ee x p l i c i tf o r m u l a t i o no fe h r h a r tp o l y n o m i a l i si n t e r e s t i n g t h r e ec o e f f i c i e n t so fe h r h a r tp o l y n o m i a la r e p r e s e n t e db ye h r h a r t b u to t h e rc o e f f i c i e n t so fl p ( g ) r e m a i n e dam y s t e r y e v e nf o rag e n e r a ll a t t i c e3 一 s i m p l e x ，u n t i lr a t h e rr e c e n t l yw i t ht h ew o r ko fp o m m e r s h e r i m 【6 1 】i nr sk a n t o r v a n dk h o v a n s k i i 5 5 1i nr 4 ，c a p p e l la n ds h a n e s o n ( 3 2 】i nr “，a n dr d i a za n d s r o b i n sf 4 2 1i n 舻b u tt h e yo n l yc o n s i d e rt h ec a s eo fi n t e g e rs i m p l e x i nt h i s t h e s i s ，b ym u l t i v a r i a t et r u n c a t e dp o w e r sa n d b o x s p l i n e s ，t h ee x p l i c i tf o r m u l a t i o n o fe h r h a r tp o l y n o m i a lf o ra n yr a t i o n a lp o l y t o p e i sp r e s e n t e d ( 6 ) t os t u d yt h en u m b e ro fi n t e g e rs o l u t i o n so fl i n e a ri n e q u a t i o n s ，t h ec o n c e p to fg e n e r a l i z e dd i s c r e t et r u n c a t e dp o w e r s i sp r e s e n t e d ，s o m e p r o p e r t i e sa b o u t g e n e r a l i z e dd i s c r e t et r u n c a t e dp o w e m o r ea l s od i s c u s s e d i np a r t i c u l a r ，t h er e c i p r o c i t yl a w o fg e n e r a l i z e dd i s c r e t et r u n c a t e dp o w e r si sp r e s e n t e d b yg e n e r a l i z e d d i s c r e t et r u n c a t e dp o w e m ，t h ep e r i o do fm u l t i d i m e n s i o n a le h r h a r tp o l y n o m i a li s p r e s e n t e d f o u r i e r - d e d e k i n d s u m i sa g e n e r a l i z a t i o no f t h ec l a s s i c a ld e d i k i n ds u m a n di t sv a r i o u sg e n e r a l i z a t i o n s i nt h i st h e s i s ，f o u r i e r d e d e k i n ds u mi sg e n e r a l i z e dt os e v e r a lv a r i a b l e s t h er e c i p r o c i t yl a wo ff o u r i e r - d e d e k i n ds u mo fs e v e r a l v a r i a b l e si sp r e s e n t e d f 7 ) m u l t i v a r i a t es p l i n e sw h o s es m o o t hc o n d i t i o n sa r ep a r t i c u l a r ，s u c ha sm u l t l - a r i a t ew e a ks p l i n e s ，m u l t i v a r i a t es u p e rs p l i n e s ，a r ed i s c u s s e d t h ed i m e n s i o n o fm u l t i v a r i a t e w e a ks p l i n ei sp r e s e n t e d t h ebn e tm e t h o df o rs t u d y i n gm u l t i - v a r i a t ew e a k s p l i n e si sa l s od i s c u s s e d t h es m o o t h c o n d i t i o no fm u l t i v a r i a t e s u p e r s p l i n e si sp r e s e n t e d t h el o c a ls u p p o r t e df u n c t i o n so fb i v a r i a t es u p e rs p l i n eo n t y p e - 1t r i a n g u l a t i o ni sp r e s e n t e d m o r e o v e r ，t h ec r i t e r i at os e l e c tl o c a lb a s e si s a l s og i v e n a tl a s t av a r i a t i o n d i m i n i s h i n go p e r a t o ri sd i s c u s s e d v i 记号 文中，采用如下通用记号： n ，z ，r ，c 分别表示自然数集合、整数集合、实数域及复数域 z + ，r + 分别表示非负整数与非负实数集合 p 女表示次数为的多项式集合，其变量个数可依据上下文而定 带a 表示集合a 中元素的个数。 d i m 雕( ) 表示剖分上k 次卢阶光滑样条空间维数 吲表示实数x 的整数部分 g c a z l ，o 。) 表示整数o 一，工。的最大公约数 i 第一章绪论 1 1多元样条匝数简介 所谓样条函数( s p l i n ef u n c t i o n ) 就是具有一定光滑性的分段或分片定义的多 项式函数1 9 4 6 年，数学家i j s c h o e n b e r g 较为系统的建立了一元样条函数 的理论基础f 6 7 | 但是，s c h o e n b e r g 的工作刚开始对并未受到重视从6 0 年 代开始，随着电子计算机技术的飞速发展，样条函数也得到了迅速的发展和广泛 的应用签于客观事物的多样性和复杂性，多元样条函数的研究无疑也是十分重 要的在过去的三十几年里，多元样条函数在理论及应用方面亦得到了广泛的发 展现在，它在计算机辅助几何设计、小波及有限元等领域中中均有较为重要的 应用、另一方面，随着多元样条函数理论的发展，人们发现它与基础数学的一些 学科，如：抽象代数、代数几何、微分方程等，亦有着千丝万缕的联系更为有 趣的是，产生于逼近论的多元样条与研究离散对象的组合数学亦有密切关系一 般而言，多元样条研究的主要方法有；光滑余因子方法、b 网方法及多元b 样 条方法这些方法本文将均有涉及，我们在下边对其做简要的介绍 1 1 1 光滑余园子方法 1 9 7 5 年，王仁宏在文献( 1 l 中采用代数几何的方法建立了任意剖分下多元样 条函数的基本理论框架，并提出所谓的光滑余因子方法采用这种方法，多元样 条函数的任何问题都可以转化为与之等价的代数问题研究 设d 为r 2 中的一区域，以p t 记二元女次实系数多项式集合一个二元多 项式p 称为不可约多项式，如果除了常数和该多项式自身外没有其它复多项式可 整除代数曲线 r ：f ( o ，y ) = 0 ，f ( z ，y ) p k ， 称为不可约代数曲线，如果z ( 孔y ) 是不可约多项式用有限条不可约代数曲线对 区域d 进行剖分，将剖分记为，d 被分为有限个子区域d h 一，d ，它们被称 为d 的胞腔形成每个胞腔边界的线段称为网线，网线的交点称为顶点，同一网 线的两个顶点称为相邻网点以某一顶点y 为顶点的胞腔的并集称为顶点y 的 关联区域或星形区域，记为s t ( v ) d 上的关于剖分的二元女次弘阶光滑样 条函数空间定义为 s 掌( i x ) = s g “( d ) ：s d ，p 女，i = l ，一，) 大连理工大学博士学位论文 基于代数几何中b e z o u t 定理，王仁宏得到了多元样条函数光滑连接的条件表 现为如下定理： 定理1 1 1 刀设8 碟( ) ，d ：与b 是剖分的相邻胞腔不可约代数 曲线r ：f ( 。，y ) = 0 是d i 与岛的一条公共网线，毋= s i d 。，弓= s i b ，则有 只一只= “( z ，g ) ) d + i q ( z ，掣) ， 其中，q ( x ，y ) p 女一( p 十1 ) d 称为网线r 上的光滑余因子，此处d = d e g ( 1 ) 我们将位于区域d 内部的网点称为内网点，否则称为边界网点如果一条网线 的内部属于区域d 内，则称此网线为内网线，否则称为边界网线设 为任一 给定的内网点，v 的关联区域s t ( v ) 有个胞腔d l ，d n ，d i 与d f 的公共网 线记为f o ：t i ( z ，y ) = 0 ，i = 1 ， _ q i ( x ，) 以( z ，p ) “= 0 ， ( 1 1 ) i = l 其中，吼( 卫，y ) p k 一( 。+ l 妇也= d e g ( 1 d ，公式( 1 1 ) 称为样条函数s ( x ，g ) 在内网 点”处的协调条件。若样条函数在所有的胞腔上均为同一多项式，则称其为蜕化 的下面定理称为样条函数的存在性定理： 定理1 1 2 对于给定的剖分，样条函数存在的充要条件是在每个内网线上 存在非口的光滑因子，且在每个内网点处满足协调条件以州 由此，可以建立多元样条函数的一般表达形式设区域d 被剖分分割为如下 有限个胞腔d 1 ，d ，任意选定一个胞腔，例如_ d 。作为源胞腔，从d 。出发， 画一流向图口，使之满足： 1 0 流遍所有的胞腔d ，d 各一次 2 口穿过内网线的次数不多于一次 3 口不允许穿过网点 流向图g 所经过的内网线称为相应于c 本性内网线其他的内网线则为 相应于e 的可去内网线显然可去内网线与本性内网线只是一个相对概念设 f i i ：l i j ( x ，y ) = 0 为g 的任意一条本性内网线，将从原胞腔g 出发，沿从原胞腔 c 出发，沿c 前进时，只有越过r 。，后才能进入所有闭胞腔的并集记作u 聪，将从 原胞腔c 出发沿r ，时，在越过口之前所经过的各胞腔并集为巧，称u 呓u 巧 为网线n ，的前方，记作，r ( r ，) 2 第一章；绪论 定义1 1 1 设：幻( z ，9 ) = 0 为相应于流线亭的本性内网线，多元广义截 断多项式定义为 。c z ，? = t 孑”： ：；i 尝珐r 嵇， 由此，有如下的样条函数表现定理： 定理1 1 3 任意s s ( ) 均可唯一地表示为 s ( x ，y ) = p ( x ，) - b l i j ( x ，y ) p l q = i j ( x ，掣) ，( 。，y ) d ， 0 其中p ( x ，y ) p k 为s ( z ，y ) 在源胞腔上的表达式，百表示对所有本性内网线 求和 在文献f 3 】中，王仁宏给出了任意维的样条函数框架这些结果与上面结果类似 光滑余因子的方法可以研究任意剖分下的多元样条函数空间多元样条的一 些问题，例如维数问题，最终可归结为对协调条件的研究特别地，对于一种较 为实用的剖分，贯穿剖分( 用有限条直线对区域d 进行的剖分称为贯穿剖分) ，利 用上述方法，能较容易的得到该剖分下样条空间的维数与基底： d i m s f ( ) = n ( k ) - t - e 叩( 七一p + 1 ) + y q ( 一2 芦一2 ) 且空间碟( ) 中的任意元素可表示为 s ( z ，y ) = p ( z ，y ) + 吼扛，s ，) f i 扛，可) ：+ 1 + r i ( x ，y ) l j 。缸，可) ：+ 1o ，：( z ，可) ：+ 1 ， 此处，目为剖分中直线数目，y 为内网点数目，当m o , n ( m ) = ( m + 2 ) ( m + 1 ) ， 否则q ( m ) = 0 专著 8 3 】中，详细介绍了光滑余因子方法的应用，包括1 型2 型 三角剖分上的维数与基底，任意三角剖分下的维数等等 s 1 1 2b 网方法 所谓b 网方法，就是利用两个多项式在两个相邻单纯形上b e r n s t e i n 表达形 式的系数之间的关系，给出光滑拼接的条件最早将一元b e r n s t e i n 多项式推广 到二元情形的是五十年代d ec a s t e l j a u 的工作，但并未发表将b e r n s t e i n 多项 式用于多元样条理论的研究，当首推g f a r i n 在1 9 8 0 年完成的博士论文中的工 作g f a r i n 在博士论文中考虑了多元样条b 6 z i e r 坐标和光滑性的关系，从而 使b 网方法成为研究多元样条的重要方法之一中国学者苏步青、刘鼎元、常庚 哲、冯玉瑜等人也作了许多有意义的工作 b 网方法要求剖分为单纯形剖分，一般不能考虑任意剖分下的样条空间 3 大连理工大学博士学位论文 但由于剖分的针对性，b 网方法对处理单纯形剖分上的样条函数有其特殊的优 越性迄今为止，单纯形剖分上样条函数的一些问题的最佳结果，如任意三角剖 分上二元样条函数空间的维数问题，多是由b 网方法得到的下面介绍b 网方 法的基本思想和主要结果，有兴趣的读者可参考 1 7 4 9 1 设 - ， z ，v 3 是三角形d 按逆时针方向排列的三个顶点，则任意x r 2 可唯 一表示为 z = t i v l + t 2 v 2 + t 3 v 3 ， 其中，n + 7 2 + t 3 = 1 ，称 r l ，乃，t 3 为茁关于三角形d 的面积坐标不难得到 n = 毒竽三糕，亿= 善三鹅，n = 差 三糕 面积坐标有一个重要的性质就是具有仿射不变性令y = z 2 一卫1 ，嗣的面积坐标 为r ( ) = ( 矗“，矗“，矗) ，i = 1 ，2 o = ( 。l ，a 2 ，0 1 3 ) = 7 _ ( 2 ) 一7 ( 1 1 函数，( 。) 的自变 量z 用面积坐标替换后得到的函数仍用，( 下) 表示，替换前后函数的偏导数与方 向导数有如下关系： 叭) = 刚r m 掣怕掣怕掣 d u ( ，- ) = 磁( q ) d 1 ，( r ) 协b r 其中，b 2 ( 7 _ ) = 器丁1 = 可习n ! 可r a 谚2 毋3 ，a l + a 2 + a 3 = 扎，凡z + 称b ：b - ) 为 b e r n s t e i n 基函数其具有如下性质： 1 职( r ) 0 ，r 6 = h ， 2 ，v 3 1 2 k 。b a ( r ) 三1 3 且蛩( r ) ，= 札) 是多项式空间p 。的一组基底 4 j e 强( r ) 在点7 - = 处取唯一极大值 由性质3 可知，任一多项式p 可唯一表示成 p ( t ) = h 研( r ) ， i x l = n b ，= n ) 称为p ( 7 - ) 关于6 的b 6 z i e r 坐标，插值于 ( 害，b ) ：= n ) 的分片 线性函数称为p ( - r ) 关于6 的b 6 z i e r 网，简称b 网下述定理显示了b e r n s t e i n 形式的升阶公式 定理1 1 4 令e 1 = ( 1 ，0 ，o ) ，e 2 = ( 0 ，1 ，o ) ，e 3 = ( 0 ，o ，1 ) 6 炉南蚤脚岬洲2 札扎 第一章二绪论 则 6 - 瞅( r ) = 蚪b ；+ 1 ( 丁) ， = ni aj = n + l 定理1 1 5 ( d ec a s t e l j a u 算注假设礼次多项式p ( r ) = ：。h b 2 ( r ) 若 令6 7 ( r ) = 以，6 0 ( r ) = ；：l 勺6 黯( r ) ，= 扎一r 则 p ( r ) = 攻b ；一( 丁) ，0 曼rs n ， i ) q = n - r 特别地，取r = n ，则得p ( r ) = 毋( r ) 下述定理给出了礼次多项式p ( t ) 的方向导数 定理1 1 6 珑即) = 南i 是毋叫( - r ) 联( 口) 现在我们讨论样条函数的光滑条件设丁为以v l ，v 2 ，v 3 为顶点的三角形，t 为 以0 l ， 2 ，”3 为顶点的三角形t 与t 有公共边v 2 v 3 我们有， 定理1 1 7 设p ( r ) 与p ( r ) 分别是定义在相邻三角形t = 【v l ， 2 ，v 3 】和t = f 舌1 ， 。，v 3 上的n 次多项式， b ，i a l = 礼) 和( h ，i a f = n ) 分别是p