（计算数学专业论文）二元样条函数方法求数据插值拟合问题.pdf

摘要 样条函数被认为是在数值逼近，计算机辅助设计，图像分析和数值分析等方 面的一种高效率的工具。随着计算机的高速发展，样条函数以其便于计算机存储、 计算稳定、局部支集以及便于交互控制等优点，成为各类工程计算、计算机辅助制 造设计和几何建模等大型软件的重要数学工具之一。 早在6 0 年代一元样条的理论就开始了快速的发展，许多论文和书籍都纷纷发 表，这种发展一直持续n s o 年代并到达了顶峰。现在我们所熟悉的理论都是在那 个时候建立的( f 1 0 1 和f 3 1 1 ) 。一元样条现在已经成为各种应用领域重要的工具，并 且是现在数值分析中重要的一个方向。如果说6 0 到8 0 年代是一元样条的时代的话， 现在就是多元样条的时代。早在8 0 年代，就有一些关于二元、三元分片多项式作为 有限元的结果，但那时人们并没有重视多元的样条。现在关于多元样条的论文多 的举不胜举。 本论文主要讨论的是多元样条( 特别是二元样条) 函数方法在数据插值拟合 中的应用。这里我们所说的多元样条是指由定义在一些三角剖分上的分片多项式 的集合，而这些分片多项式之间满足一定的连续条件，从而整体上达到一定的光 滑性。多元样条和一元样条一样也具有许多优秀的性质，这些性质使它成为非常 重要的工具。比如多元样条在计算函数值和导数值的时候具有高效、稳定的算法 等。 本论文分为四章。第一章首先介绍样条函数的& 形式，接着推出在b 形式下 的一些基本算法。比如d ec a s t e l j a u 求值算法，求导、求积以及求内积算法等。这些 算法在构造矩阵方程时起到了重要的作用。然后介绍了分片多项式的拼接条件以 及如何建立整个样条空间，并简单的分析了一下常用的各种三角剖分。最后介绍 了一个用于矩阵计算的迭代算法。 第二章主要讨论了散乱数据h e r m i t e 插值问题。我们首先从如何构造满足条件 的样条函数说起，从文章【2 6 和 2 9 】中得到启发，提出了新的能量函数，来满足数 据h e r m i t c 插值的要求。并讨论了它的存在性和唯一性，以及它的逼近结果。从结 果上来看，如果散乱数据来自一个光滑的函数，那么我们做出的样条函数能够充 分的逼近于它。最后我们构造了一些数值例子来说明它的逼近结果，同时也采集 v 了中国大陆的各个地方的风速大小作为数据进行插值实验，并构造了中国大陆的 风速势力场。 最后两章主要讨论了散乱数据拟合的问题。当散乱数据充分多或者相对较少 的时候，显然用插值方法已经不合适了，我们只能用拟合的方法。其中第三章我们 采用的是扩展罚函数方法来解散乱数据相对较少的拟合问题，特别是我们对曲面 的扰度有特别要求的时候。相比于普通的罚函数方法【4 4 】，我们提出的扩展罚函数 法可以处理带导数信息的数据。因此可以看成是罚函数法的推广。而最后一章我 们采用的是扩展带权的二乘法来解散乱数据充分多的拟合问题，特别是我们知道 各种数据的误差程度或数据带有导数信息的时候。我们可以通过对权的选择，来 调整各种数据的重要性，并加入了对数据误差的概率分析，发现了多次拟合后求 平均可以明显改善误差这个结果。同样的这两章我们都是从样条函数的存在性和 唯一性讨论起，并给出了它的逼近结果以及一些数值例子。 关键词：二元样条函数方法，光滑性条件，b 形式，散乱数据h e r m i t e 插值，能量 函数，散乱数据拟合，罚函数，权函数 a b s t r a c t s p l i n ei sa ne x c e l l e n tt o o lf o rn u m e r i c a la p p r o x i m a t i o n ，w h i c hi sap e r f e c t r e s u l to ft h ec o m b i n a t i o no fa p p r o x i m a t i o nt h e o r ya n d c o m p u t e rt h e o r y i nm o d e m c o m p u t a t i o n a lw o r k ，s p l i n ei st h em a j o rt o o lf o re n g i n e e r sa n dc a d s o f t w a r es i n c e i ti se a s yt or e p r e s e n ta n de f f i c i e n tt oe v a l u a t e t h es p l i n ef i n i t ee l e m e n ti sa l s oa n e f f i c i e n tt o o li nf i n i t ee l e m e n ta n a l y s i s t h et h e o r yo fu n i v a r i a t es p l i n e sb e g a ni t sr a p i dd e v e l o p m e n ti nt h ee a r l ys i x - t i e s ，r e s u l t i n gi ns e v e r a lt h o u s a n dr e s e a r c hp a p e r sa n dan u m b e ro fb o o k s t h i s d e v e l o p m e n tw a sl a r g e l yo v e rb y1 9 8 0 ，a n dt h eb u l ko fw h a ti sk n o w nt o d a yw a s t r e a t e da l r e a d yi nt h ec l a s s i cm o n o g r a p h so fd e b o o r 1 0 a n ds c h u m a k e r 3 1 u n i - v a r i a t es p l i n e sh a v eb e c o m ea ne s s e n t i a lt o o li naw i d ev a r i e t yo fa p p l i c a t i o na r e a 8 a n da r eb yn o was t a n d a r dt o p i ci nn u m e r i c a la n a l y s i sb o o k s i f1 9 6 0 - 1 9 8 0w a st h e a g eo fu n i v a r i a t es p l i n e s ，t h e nn o wc a nb er e g a r d e da st h ea g eo fm u l t i v a r i a t es p l i n e s p r i o rt o1 9 8 0t h e r ew e r es o m er e s u l t sf o ru s i n gp i e c e w i s ep o l y n o m i a l si nt w oa n d t h r e ev a r i a b l e si nt h ef i n i t ee l e m e n tm e t h o d ，b u tm u l t i v a r i a t es p l i n e sh a da t t r a c t e d r e l a t i v e l yl i t t l ea t t e n t i o n n o ww eh a v et h o u s a n d so fp a p e mo nt h es u b j e c t t h em a i np u r p o s eo ft h i st h e s i si st od i s c u s sa b o u tm u l t i v a r i a t es p l i n em e t h o d ( e s p e c i a l l y i nb i v a r i a t es p l i n e ) a n di t sa p p l i c a t i o ni ns c a t t e r e dd a t af i t t i n g h e r eam u l t i v a r i a t e s p l i n ei saf u n c t i o nw h i c hi sm a d eu po fp i e c e so fp o l y n o m i a l sd e f i n e do ns o m ep a r t i - t i o n o fs e tq ，a n dj o i n e dt o g e t h e rt oe n s u r es o m ed e g r e eo fg l o b a ls m o o t h n e s s a s w es h a l ls e e ，m u l t i v a r i a t ep o l y n o m i a ls p l i n e sh a v em a n yo ft h es a m ef e a t u r e sw h i c h m a k et h eu n i v a r i a t es p l i n e ss u c hp o w e r f u lt o o l sf o ra p p l i c a t i o n ss u c ha ss p l i n e sa r e e a s yt ow o r kw i t hc o m p u t a t i o n a l l y , a n dt h e r ea r es t a b l ea n de f f i c i e n ta l g o r i t h m sf o r e v a l u a t i n gt h e i rd e r i v a t i v e sa n di n t e g r a l s ，e c t t h i st h e s i si so r g a n i z e da sf o l l o w s ： i nt h e 丘r s tc h a p t e rw ei n t r o d u c et h es p l i n ei nb - f o r ma n ds o m eo fi t su s e f u l a l g o r i t h mr e l a t et ot r i a n g l es u c ha st h ed ec a s t e l j a ua l g o r i t h m ，d e r i v a t i v ea l g o r i t h m ， i n t e g r a l sa l g o r i t h m ，e t c s o m eo ft h e ma r ev e r yi m p o r t a n ti nb u i l d i n gt h em a t r i x t h e nw es h o wh o wt ou s et h es m o o t hc o n d i t i o na n db u i l dt h ew h o l es p a c eo fs p l i n e n e x tw el i s ts o m ed i f f e r e n tk i n d so ft r i a n g u l a t i o n sw h i c ha r eu s u a l l yu s e di nm a n y p a p e r s f i n a l l y , w ei n t r o d u c eai t e r a t i o na l g o r i t h mu s e di nm a t r i xc o m p u t a t i o n i nt h es e c o n dc h a p t e rw ed i s c u s sa b o u ts c a t t e r e dd a t ah e r m i t ei n t e r p o l a t i o n p r o b l e m w es t a r tt h i sf r o mh o wt ob u i l das p l i n ew h i c hs a t i s f i e dt h ei n t e r p o l a t i o n p r o b l e m w ep r o v i d ean e we n e r g yf u n c t i o nm e t h o dw h i c hi sd i f f e r e n tf t o m 【2 6 1a n d 【2 9 】t h e nw es h o wt h ee x i s t e n c ea n du n i q u e n e s so ft h es p l i n ew h i c hi sg e n e r a t e d b yo u rm e t h o d n e x t ，w ep r e s e n tt h ee r r o rb o u n do ft h es p l i n e f i n a l l y , w eo f f e r s o m en u m e r i c a le x p e r i m e n t st od e m o n s t r a t eo u rm e t h o d t h el a s tt w oc h a p t e r sa r ea l la b o u ts c a t t e r e dd a t af i t t i n g i ft h en u m b e ro ft h e d a t aa r el a r g eo rv e r ys m a l l ，i tm a yn o tb ea p p r o p r i a t et oi n t e r p o l a t et h ed a t a i n t h et h i r dc h a p t e rw eu s ee x t e n d e dp e n a l t yf u n c t i o nm e t h o dt of i tt h ed a t aw h e nt h e n u m b e ro ft h ed a t aa r ev e r ys m a l l t h i sm e t h o dc a nd e a lw i t ht h ed a t aw i t hd e r i v a - t i r ec o m p a r et op e n a l t yf u n c t i o nm e t h o d i nt h ef i n a lc h a p t e r w el l s ew e i g h t e dl e a s t s q u a r e sm c t h o dt of i tt h ed a t ao fw h i c ht h en u m b e ri sl a r g e w ec a l la d j u s tt h e w e i g h t e df u n c t i o n sa c c o r d i n gt ot h ei m p o r t a n c eo fe a c hd a t a a sa l w a y s ，w es h o w t h ee x i s t e n c ea n du n i q u e n e s so ft h es p l i n e si nl a s tt w oc h a p t e r sa n da l s ow i t he r r o r b o u n da n dn u m e r i c a le x p e r i m e n t sa sw e l l k e y w o r d s b i v a r i a t es p l i n em e t h o d ，s m o o t h n e s sc o n d i t i o n ，b - f o r m ，s c a t t e r e d d a t ah e r m i t ei n t e r p o l a t i o n ，e n e r g yf u n c t i o n ，s c a t t e r e dd a t af i t t i n g ，p e n a l t yf u n c - t i o n ，w e i g h t e df u n c t i o n 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得浙江大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名虱云飞耷 签字日期：沙，锌臼9 日 学位论文版权使用授权书 本学位论文作者完全了解浙江大学有权保留并向国家有关部门或机构送交 本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江大学可以将学 位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：儒v 弋争 签字日期：伽寸g 年g 月孑日 导师签名： 群祆 签字日期沁青年6 月矿日 致谢 首先我想感谢的是我的父母，正是他们对我细心的培养，我才能在轻松的环 境中长大，并顺利的做完了博士阶段的研究。特别是现在自己有了孩子，才体会到 抚养孩子的艰辛，因此我最感谢的是我的父母。 我还要感谢我的导师韩丹夫教授五年来对我的关心和指导，不仅教会了我专 业知识，更主要的教会了我做人的道理，使我可以顺利的完成博士阶段的学习，并 完成了本篇博士论文。 同时也要感谢美国乔治亚大学的m i n g j u nl a l i 教授，正是由于m i n g j u nl a i 教授 邀请我才可以去美国乔治亚大学进行交流访问，学到了许多国外的先进的数学思 想，并一起合作发表了一篇科学论文，对我今后的发展指明了方向。 在浙江大学读博的这个阶段，王兴华教授，吴庆标教授以及程晓良教授等都 对我进行了指导，感谢他们帮助我建立了正确的专业知识，使我受益匪浅。在每周 的讨论班上，胡贤良博士，武鹏博士，尚绪凤博士以及练晓鹏博士等一批韩老师的 学生和我一起进行了深入的学术探讨，并产生了许多新的思路，帮助我完成了科 学论文，在此一并感谢! 最后特别要感谢我的妻子缪佳佳女士，由于做研究的关系，我对家里事务关 心很少，而她在我读博期间一直默默地支持我，处理各种家庭事务。特别是在我去 乔治亚大学交流访问期间，她生下了我们可爱的宝宝。而我在美国不能照顾怀孕 的她，十分的内疚。因此这篇博士论文献给我的妻子缪佳佳女士。 第一章背景知识 这一章我们主要来介绍一下二元样条函数空间的构造以及二元样条函数的一 种& 形式。我们所说的b 形式是定义在单元三角形上的，一般来说运用样条函数 的b 形式有以下优点：首先是运用这种形式对于计算多项式的函数值，导数值，积 分以及内积具有非常简单有效的算法。其次是运用这种形式在各个单元上建立连 续性条件具有非常直观的几何意义，十分容易理解。再次是运用这用形式对于计 算机的应用，特别是系数的存储上，各个单元可以建立起统一的形式。这样对于 工程上的应用具有良好的基础。最后是由于对于多元样条的研究，大量的文献都 是运用这种表示形式，这也为我们研究样条函数提供了良好的基础。文献中把这 种b 形式以及由此导出的一系列简单有效的算法统称为b e r n s t e i n b d z i e r 方法。 本章的结构是这样组织的：首先介绍了样条函数的b 形式，接着推出在& 形 式下的一些基本算法。然后介绍了分片多项式的拼接条件以及如何建立整个样条 空间，并简单的分析了一下常用的各种三角剖分。最后介绍了一个用于矩阵计算 的迭代算法。 一 1 1 样条函数的b 形式 假设丁是一个非退化的三角形，它的顶点是忱：= ( x i ，鼽) ，i = 1 ，2 ，3 ，我们 记t ：= 来表示这个三角形，并假定顶点是按照逆时针顺序排列的。那 么平面上的任何一点移：= ( z ，y ) 都有如下的关系式： z = b l x l + 5 2 x 2 + 6 3 x 3 y = b l y l + 5 2 y 2 + b 3 y 3 1 = b l + 5 2 + b 3 我们称( 6 l ，6 2 ，6 3 ) 是点秽关于三角形r 的重心坐标。显然由于丁是非退化的，这个解 是唯一的。同时重心坐标有非常有趣的几何解释，如图1 1 ：那么重心坐标可以表 示成如下的形式： b i = 半， i = 1 ，2 ，3 y l r 其中肿代表三角形t 的面积。因此重心坐标又被称为区域坐标。 1 2 1 1 样条函数的& 形式 图1 1 三角形上重心坐标的定义 有了重心坐标我们就可以定义t 上的d 次b e r n s t e i n 多项式： 硌( z ，秒) = 巧d ! b i m 。h 。k ，l + j + 七= d 这里i ，j ，七是自然数。为方便起见，磁七 ，可) 有时记为磁七( 口) 或磁。b e r n s t e i n 多9 式有许多优秀的性质，比如 磁七( t 7 ) 兰1 ， 协r 2 + j + 七= d 这是由于 1 = ( 6 - + 6 2 + 6 3 ) d = 淼醒磋醵，i + j 十七= d i + j + k = d 。 还有 0 醒七( t ，) 1 ， 协z 可以证明集合：= b v d k ) i + j + 七：d 是d 次多项式空间的一组基( 可以参考【4 6 】) ，其个 数为( d 言2 ) = 垡学，我们称之为b e n l s t e i n 基。 接下来我们将要引进一个域点的概念，域点就是指三角形上的这些点 现，t ：= 【岛奄：= ( t 口l + 歹也+ k v 3 ) d , + j + 七：d( 1 1 ) 如图1 2 。域点具有如下的性质： 磁七( t ，) i ，则c “。排在七前面。如 果矿= i 且p 歹，则白肚排在七前面。如果v = i ，i t = 歹且k k ，则钆。排在前 面。以次数是3 次的系数为例，它的排列顺序如下： 经过排列以后我们可以把系数写成向量形式c ，每个系数c q k 是向量c 的一个分量。 从图1 2 上可以看出，域点和系数具有一一对应的关系。即一个域点& 佧对应一个系 数知。许多时候，当= 岛知我们用础来代表b 吕k 。 最后我们再引入两个关于域点集合的概念。一个叫关于顶点v l 的半径为0 m d 的环磁( t ，1 ) ，它是指这些域点 白一m j ，m j ) 整。的集合。另一个叫一个叫关于 顶点口l 的半径为o m d 的盘瑗( 1 ) ，它是指这些域点u 箍。群( u 1 ) 的集合。同样 关于另外两个顶点的环和盘也可以类似的定义。 1 2样条函数的b e r n s t e i n - b 6 z i e r 方法 这一节我们主要介绍一下b 形式的一些重要的算法。这些算法在曲面计算以 4 1 2 样条函数的b e r n s t e i n b 1 3 z i e r 方法 及样条函数的计算上有着非常重要的应用。首先我们介绍一个样条函数& 形式的 求值算法：d ec a s t e l j a u 算法。 算法1 1 ( 求值算法) 假设6 ：= ( b 1 ，b 2 ，6 3 ) 是点移= ( z ，可) 关于t 的重心坐标，那么 样条函数b 形式可以用如下的递推算法来计算： 其中系数满足关系 p ( ) = 螺陈。( u ) ，v 0 z d ( 1 3 ) 订于+ - 七= d _ f 壤：= 奄，i + j + k = d ：= u b l 。a 件t - l j 1 ) ，七+ 。h 。、a t j - + 1 1 ) ，七+ 6 3 c ：品2 1 ，i + 歹+ 七= d z ，w = 1 ，d ( 1 4 ) 特别的 p ( t ，) = 貔 这个算法是样条函数方法里面最为重要的算法，它可以用于方向导数的计 算。我们先来看一下向量在重心坐标下的表示方法。记压是一个以以为起点，b 为 终点的向量，而a 和b 相对与三角形t 的重心坐标分别是q ：= ( q l ，眈，q 3 ) 和p ：= ( 岛，店，岛) ，那么向量压相对于丁的重心坐标表示法可以记成： b a r y ( 才杏) ：= a p = ( 口1 一屈，a 2 一恳，口3 一传) ( 1 5 ) 算法1 2 ( 求导算法) 设多项式p 在三角形t 上可以表示成如( 5 1 ) 吩b 形式，而 方向向量u 在丁中可以用( 1 5 ) 袁示成一个三元组a ：= ( n 1 ，0 2 ，口3 ) 。那么雄丁上沿方 向u 的导函数是一个d 一1 次多项式，且同样可用如下口形式表示： 砌( ) = d c o 七) a ) 陈1 ( u ) ， ( 1 6 ) i + k = d - i 这里d 印表示对p 沿方向u 求一次导数，鸢2 ( o ) 是算法( 1 4 ) 利用方向向量a 计算一步 得到的结果。更一般的设0 m d ， 叻= 南嘶三一m 掣磙咻 ( 1 7 ) 浙江大学博士学位论文 5 这里叼p 表示对p 沿方向钆求m 次导数，削( o ) 是算法( 1 4 ) 利用方向向量a 计算m 步 得到的结果。或 聊= 南；磊m 蘸帕， ( 1 8 ) 可以证明( 1 7 ) 和( 1 8 ) 是等价的。 b 形式的求导算法在数据拟合问题上具有重要的作用。特别是关于顶点的求 导算法在数据插值上也同样重要，虽然它可以从求导算法1 2 中推出，但是由于它 的重要性，我们也列在下面。 算法1 3 ( 顶点求导算法) 假设( 钉1 ，啦，) 是三角形的三个顶点，对任意的o m + n d ，有 蠼咖川p c 叫= 毒筹焉姜妄( ? ) ( ；) c 叫嘶钆叫m 相反的我们也有 劬年俐= 塞耋( 三) g ) 坠号掣嫒川川咖a 最后我们再介绍一个b 形式的内积算法，它主要运用在计算刚性矩阵上。 算法1 4 ( 内积算法) 关于b e 册t e 讥多项式的内积有以下等式成立： 舾小劫碓如，y)dxdyt= 掣鞘产 ， 、d ，、2 ， 这里a r 是三角形t 的面积因此对任意两个多项式 p ：= 勺七磁七，g ：= 砖。， + j + 七= dp + l ，+ k = d 他们的内积可以表示成 ( 1 9 ) f t p ( x , y m 训黼= 柏蔑晦似) ( 61 3 样条函数的光滑性条件及其空间 如果用c 和分别表示p 和g 的系数向量，则该内积公式可以记成 z 出m q ( x , y ) 如d y2 雨a 雨t 一蕊 这里g 是一个大小是( d + 2 ) 的方阵，且系数向量c 、和g 中的元素都是根据对应的下 标三元组安固定的顺序排列的。 这个结论用多重积分可以很容易计算得到。显然，g 是可以事先计算好的， 这为实际计算提供了快速算法。这是三角形单元上特有的，求刚度矩阵或质量 矩阵可以避免使用数值积分公式，这在单元次数比较高的时候是比较有效的。 其他情况则需要采用数值积分公式来计算。下面例子中的g 1 、g 2 和g 3 分别是 当d = 1 、d = 2 和d = 3 时的g ： 卵) g 2 = g 3 = 6 3 3 4 3 2 13 12 l1 3l 23 41 16 2 3 31 1l 2l 2 3 31 4 3 36 1 3样条函数的光滑性条件及其空间 前面我们所介绍的方法都是针对一个单元三角形上的，要表示一个样条函数， 除了考虑单元内部的算法和性质外还需要考虑单元连接处的光滑拼接条件，也就 1 l 4 l 4 加1 4 m l 2 3 3 6 6 4 9 抡加 1 3 2 6 6 3 m 圪9 4 1 4 l 加4 1加4 1 4 3 9 2 6 拢1 3 6 m 4 6 6 6 8 6 4 6 6 4 4 9 3 挖6 2 加6 3 1 m 6 挖3 6 9 1 2 3 4 加挖6 9 6 3 4 3 2 l 加加4 4 4 1 1 1 1 浙江大学博士学位论文7 是涉及到样条函数的全局分析，其核心内容是相邻单元是如何实现光滑拼接的。 下面的定理给出了- - 元b - 形式的光滑并接条件( 可以参考【2 0 】) ： 定理1 1 假设三角形t ：= 和t ：= 是相邻的两个三角形， 他们有公共边e ：= 。p 研别是定义在r 和于上的两个均为d 次的多项式， 他们的b 形式分别是 p ( o ：= 七磁七( 口) ( 1 1 0 ) i + j + k = d 和 烈t ，) ：= 岛t 鼹( 口) ， ( 1 1 1 ) i + j + k - - d 这里磁k 和彰七分别是关于t 和于的b e m 酊e i 堪函数，另假设u 不平行于公共边e 的 任意方向。则 d ：p ( 口) = d t p - ( ) ， 讹e ，佗= 0 ，( 1 1 2 ) 当且仅当 。 c a d ，七= ， + v , j + 。b 。( 饥) ， j + 七= d 一礼，礼= 0 ，r ( 1 1 3 ) j 上+ l ，+ 托= n 这个条件自从f a r i n 在 2 0 】中提出以后就被广泛地应用于曲面设计和多元样 条函数分析中，d e b o o r 在【1 5 】中给出了其多元的表示方法，也可以在最近的著 作 4 6 ，5 0 】中找到二元情形比较详细的证明。 有了上面的叙述，我们可以来定义样条函数空间了。在这之前我们先引入一 个s o b o l e v 空间的概念。这是因为我们的方法是用样条函数去逼近的是s o b o l e v 空间 上的函数。 给定1 口o 。和d 0 ，s o b o l e v 空_ 间定义为 时1 ( q ) ：= ，：1 1 1 1 d + 1 柙 o o ) ， 其中 胪 “l ( f ，i ：柙 k = o d + l 则 k = o 1 q ，1 口 0 0 口2o o 8 1 3 样条函数的光滑性条件及其空间 以及 f ( 慨i j 叫ui l g q ，o ) 1 加，1 冬g o 。 i p + l ，= 七 l 儿舟f l = ( 1 1 4 ) 【牌。磁彤州呻，q 2o o 岛( ) ：= s c r ( ) ：s i r p d ，v t )( 1 1 5 ) 就是定义在上的嗽r 阶光滑的样条函数空间，其中p d 是我们熟悉的( d + 2 ) 维的二 元d 次多项式空间。在【1 6 ，3 8 中已经知道，当d 3 r + 2 时样条函数空间懿( ) 是存 在的( 对于特殊的剖分，这个条件可以减弱) ，所以今后我们一直假定这个条件是 满足的。根据岛( ) 的定义( 1 1 5 ) ，若s s 5 ( ) ，则其在任意三角形t 上可以表示 成一个& 形式 8 1 t ( v ) = 磊磁七( 秒) ，讹t a i + j + k = d 因此，在整个剖分上样条函数s 可以写成 s = 巧七， t e ai + j + k = d 这里相应的b e r n s t e i n 基定义成 删= 掣口：盎 ( 1 1 6 ) 此外，s 的系数向量c = ( 岛七， i + 歹+ k = d ，t ) 还应满足伊光滑条件。因此， 对的每条内边都可以得到条件( 1 1 3 ) ，将他们合并到同一个矩阵中可以得到光滑 性条件( 1 1 3 ) 的全局表示： h c = 0 ( 1 1 7 ) 令现，：= u 吼n 假设r 巩，如果s s 以及龟= o 对所有的f r 都 t 成立，有8 三0 。我们就称r 是样条空间s 上的决定集。如果朋是样条空间s 上的一 个决定集，且朋是s 上的所有决定集中基数最小的一个，那么我们称m 是样条空 间s 上的最小决定集。显然巩是样条空间器( ) 上的最小决定集。 浙江大学博士学位论文 9 给定一个样条空间s 上的最小决定集m ，假设我们已经给定了这些系 数 q ) 锯m 的值。那么其余的系数7 7 吼朋可以通过连续性条件由已知的 系数计算过来。对于m ，如果改变的值能够引起岛值的改变，那么我们 称岛与呸相关。令 l ：= 任, a 4 ：岛与气相关) 如果可是一个三角剖分上的顶点，我们定义s t a r ( 口) 为三危剖分中所有拥有口顶点 的三角形的集合。令t ，定义 s t a r o ( t ) ：= t , 和s t a r ( t ) ：= u s t a r ( ) ：口s t a r 1 ( t ) ) ，1 ( 1 1 8 ) 假设 最) e m 是一组定义在三角剖分上样条空间s 上的基。如果存在一个整数z ， 满足 k m ，s u p p ( 反) gs t ( )( 1 1 9 ) 我们称基 & ) 朋是局部的。如果存在只与次数d 和三危剖分中的最小角有关的 常数0 g q o o ，满足 g m 州a x i c d | | 吒驯础q 搿v c j f 朋 ( 1 2 0 ) 。 f e a 4 我们称基 展) 朋是稳定的。 最后我们介绍一个重要的关于样条空问的逼近定理。从【1 1 ，1 7 中可以知道 对于一个任意给定的充分光滑的函数，q ，都存在一个拟插值算子q ，当d 3 r + 2 时把，映射到岛( ) 空间，从而达到了在岛( ) 空间上的最优逼近。也就是以 下的定理： 定理1 2 ( 可以参考口刀) 固定1 p o o 。对于某个0 m 西假设，属 于咿+ 1 ( q ) 空间。那么当o 口+ p m a c ，有 l i 聪瑶( ，一q f ) l l p k i a i ”+ 1 一。一p i f l m + - 一 其e l a l 是指三角剖分中三角形最长的边。如果q 是一个凸区域，那么常 数k 与d ，p ，m 以及中的最小角有关。如果q 是一个非凸区域，那么它还与边 界a q 上的l 咖s c i 沈常数l 踟有关。 对于一些特殊的剖分，达到最优逼近并不需要d 3 r + 2 ( 可以参考【3 7 ，3 9 ，4 0 ， 4 l ，4 2 】) ，我们将在下一节介绍这些剖分。 1 0 1 4 常用的三角剖分以及不等式 1 4 常用的三角剖分以及不等式 数值分析学者对于散乱数据拟合的问题一般都从两个角度去考虑：一个 是数值方法的本身，一个是三角剖分的方法。下面我们主要介绍几个常用于计 算的三角剖分方法。首先是c l o u g h - t o c h e r 剖分方法，简称为c - t 方法。它是由r c l o u g h 和j t o c h e r 两个人在1 9 6 5 年提出来的( 可以参考【1 4 】) ，许多时候人们也称 h s i e h - c l o u g h - t o c h e r 方法( 可以参考f 1 3 】) 。它最早被用于建立有限元的单位宏 元上( 可以参考f 6 ，8 ，1 2 ) 。同样它也可以运用至l j h e r m i t e 括值的问题上( 可以参 考【4 ，4 0 ) 。 令t = 是一个单元三角形，则卯：= ( 口1 + v 2 + v 3 ) 3 是三角形t 的 重心。如果我们用叼连接三个顶点，我们就把原来的三角形t 分为了三个三角形。 我们称这种分割法；寿c l o u g h - t o c h e r 分割法。如果把三角剖分中所有的三角形都 按照这种分割法进行分割，那么我们称a c t ) c l o u g h - t o c h e r 剖分方法。如图1 3 。 图1 3 单元三角形和c - t 分割三角形 对于一般的三角剖分，在其上建立样条空间要达到最优逼近的话，则要 求d 3 r + 2 。对于d t 剖分这个条件可以减弱，根据情况可以d 3 7 或d 3 r + 1 【4 0 1 。 另一种剖分口t t p o w e l l - s a b i n 法，简称p s 方法。它是d j p o w e l l ，m j d 和m a s a b i n 两个在1 9 7 7 年提出来的( 可以参考f 4 7 】) ，它被用予建立c 1 连续宏元的。这个 剖分可以运用在数值解微分方程和数值逼近上( 可以参考 4 2 1 ) 。 令为一个普通的三角剖分，用t l t 来代表三角剖分中的每一个三角形t 的 内心。连接鲫和其所在三角形的三个顶点。如果三角形丁与哺公共的边，连 浙江大学博士学位论文 1 1 接鲫和札亍，否则连接u r 和边界边上的中点。我们称三角剖分p s 为p o w e u - s a b i n 剖 分方法。如图1 4 。同样运用p - s 剖分方法可以使最优逼近的条件减弱( 可以参 图1 4 单元三角形和p s 分割三角形 考 4 2 】) 。 还有一种剖分方法叫三角化四边形方法。这种方法最早f r a e i j sd ev e u b e k e 【7 】和s a n d e r 【2 3 博 出用来建立宏元以解决板弯曲问题的( 可以参考 3 4 1 ) 。这种方法一开始并没有 受到样条工作者的重视，直到最近由来明俊教授等数值学家的研究( 可以参 考f 3 6 ，3 7 ，3 9 1 ) ，才逐渐被用到样条方法上来。 令q ：= 是一个严格凸的四边形，连接两条对角线 ， ，相交于如。这样一个四边形就被分为四个三角形了。如果整个区域都是 由四边形组成的，并对每一个四边形都分解为四个三角形，那么我们称这种剖分 法为三角化四边形法，如图1 5 。同样运用这种剖分方法可以使最优逼近的条件减 弱，只要d 3 r 就行了( 可以参考【3 9 ，4 1 】) 。 此外还有一些剖分，如w a n g s 剖分( 可以参考 5 1 1 ) ，p o w e n - s a b i n - 1 2 剖分( 可 以参考【4 7 】) 等等，这里我们就不介绍了。下面我们主要比较一下这些特殊剖分与普 通剖分在样条空间维度和计算复杂程度。令和分别是四边形区域上的内部 顶点和区域边界上的顶点，并假设是一个和四边形区域具有相同的和的 普通剖分。定义a c r 和a p s 分别是基于上的c l o u g h - t o c h e r 剖分和p o w e l l - s a b i n 剖 分，以及o 是四边形区域上的三角化剖分。假设普通剖分具有个三角形的 话，那么a c t 就具有3 n 个三角形，a p s 就具有6 n 个三角形，就具有2 n 个三角 形。我们知道 d i m ( s ( ) ) = 6 ( + v b ) + 3 + 2 v 8 3 1 21 4 常用的三角剖分以及不等式 v 1 v 1 图1 5 单元四边形和三角化四边形 d i m ( s 3 ( 凹) ) = 3 ( + ) + 3 v , + 2 v b 一3 d i m ( s ：( ) ) = 3 ( 1 1 1 + ) + 3 1 1 1 + 2 v b 2 2 d i m ( s ( a p s ) ) = 3 ( v i + ) 从上面的数据我们可以看出，母( ) 是相对的最佳选择。因为罐( ) 和霹( a c t ) 具 有相对大的维数，而避( a p s ) 虽然维数最小，但是它却具有最多的三角形。同样 的，我们可以相信鳍( ) 是相对于踞( ) ，s g ( 凹) 和霹( p s ) 的最佳选择，可以参 考f 3 6 和3 7 1 。 我们再介绍一个关于三角剖分的概念。令p ，如果一个三角剖分被叫 做p 型拟一致剖分是指i a lsp 咫，其中p 是指三角剖分中三角形里最小的内接 圆半径。 通过计算容易得到，如果一个三角剖分是p 型拟一致剖分的话，那么这个三角 剖分中最小的一个角一定大于2 p 。 最后我们介绍几个本文要用的不等式。首先是二元多项式的m a r k o v 不等 式( 可以参考 4 6 1 ) ： 定理1 3 ( m a r k o v 不等式) 令t 是一个三角形，固定l q 0 0 ，那么存在一个 常数k 只于次数d 有关，满足对于任意的非负整数o ，p 以及二元多项式p p d ，满足 i i 磋跆岫矿k a 西v o a + p sd( 1 2 1 ) 其中力代表的是t 中最大内接圆的直径。 浙江大学博士学位论文 1 3 定理1 4 假设s 是一个定义在型拟一致三角剖分上的样条空间，b ：= 展) m 是s 上的一组局部稳定基，那么存在- b & z 和p 有关的常数o 0 ，七= 0 ，1 ，如果对任意的m ， 有口，y n m ，那么 知m + 1 ， 妣( 7 + 1 ) ( 南) 这个定理可以参考 9 】。 定理1 6 假设是一个型拟一致三角割分，固定一个三角形t a ，有 粕s ( 2 q + 3 ) 2 伊7 r ， g 0 其中是_ s t a r q + 1 ( t ) s t a r q ( t ) 的三角形个数。 这个定理可以参考【4 5 】。 1 5一个矩阵迭代算法 用样条方法做散乱数