（计算数学专业论文）基于细分节点二步算法的大规模数据拟合的自适应算法.pdf

! 苎塑塞 中山大学硕士学位论文 基于细分节点二步算法的大规模数据拟合 的自适应算法 专业 学位申请人 导师及职称 计算数学 李娇娇 关履泰教授 李小福副教授 摘要： 近几十年来，大规模散乱数据拟合成为数值逼近理论领域的热点问题。本 文从分析细分节点二步算法的散乱数据插值方法所存在的不足入手，通过引入 对数据点进行分层及阈值过滤的思想，提出了基于细分节点二步算法的大规模 数据拟合的自适应算法。该自适应算法包括二维和三维两种情形。对于二维平 面上的大规模任意散乱数据点，我们通过分析数据的分布特点，总结出一种分 层及闽值选取的方法，从而给出了细分节点上的大规模散乱数据拟合的自适应 算泫，该算法可以保证拟合函数在整个定义域上达到e 一。阶连续。将二维情 形的阈值选取方法推广到三维，就得到本文第五章所述的网格点上的大规模数 据拟合的自适应算法，根据细分插值点的分布特点，我们采用了矩形域上的散 乱数据最优插值方法进行细分插值，这样所求得的拟合曲面除在某些边界线之 外可以达到e ( 2 “_ 2 ，2 ”2 ) 连续性。这两种情形下的算法的基本思想是一致的，它 们在保证一定拟合精度的前提下减少了进行细分插值的数据量和存储量，从而 提高了计算速度，而且拟合函数可以达到较好的光滑性。实验证明，这种自适 应算法的时效性优_ 丁细分节点的二步算法。除此之外，本文还对三维空间中任 意散乱的大规模数据拟合问题进行探讨。 关键词： 大规模散乱数据，数据拟合，自然样条插值，细分节点，二步算法，细分 网格，分层，阈值，自适应算法 英文摘要 a s e l f - a d a p t i v ea l g o r i t h m o f l a r g e s c a l ed a t a f i t t i n gb a s e d o nt h e t w o s t e pa l g o r i t h m o f r e f i n e dn o d e s m a j o r n a m e s u p e r v i s o r c o m p u t a t i o n a l m a t h e m a t i c s l ij i a o j i a o p r o f e s s o rg u a r ll t i t a i a s s o c i a t ep r o f e s s o rl ix i a o f u a b s t r a e t ： p r o b l e m so fl a r g e s c a l es c a t t e r e dd a t af i t t i n ga r cd i s c u s s e df r e q u e n t l yi nr e c e n t y e a r s m yp a p e ri n t e n d st o s o l v et h ep r o b l e mo fl a r g e - s c a l ed a t af i t t i n gb yas e l f - a d a p t i v ea l g o r i t h m ，w h i c hi sb a s e d o nt h et w o s t e pa l g o r i t h m t h es e l f - a d a p t i v ea l g o r i t h mi n c l u d e st w op a r t s o n ei so nt w o d i m e n s i o n a lp l a n ea n dt h eo t h e ri so n 鲥d s o f t h r e e d i m e n s i o n a ls p a c e l a y e r i n gt h es c a t t e r e d d a t aa n d c h o o s i n g t h et h r e s h o l da r c u t i l i z e di nt h ep a p e ri na d d i t i o nt ot h eo r i g i n a lt w o s t e pa l g o r i t h m t h i sa l g o r i t h mc a l l r e d u c em e m o r ya m o u n t ，i m p r o v ec o m p u t i n gs p e e da n d d e c r e a s ec o m p u t i n gt i m e a n d a tt h es a m ct i m et h ef i t t i n gf u n c t i o nc a ng e ts a t i s f y i n gs m o o t hd e g r e ew i t h i ns o m e f i t t i n gp r e c i s i o n t h ec o r r e s p o n d i n ge x p e r i m e n t s i nt h ep a p e ri n d i c a t et h a tt h em e t h o d s a r ee 舵c t i v e k e y w o r d s ： l a r g e s c a l e s c a t t e r e dd a t a ；d a t af i t t i n g ；n a t u r a ls p l i n ei n t e r p o l a t i o n ；r e f i n e d n o d e s ；t w o s t e pa l g o r i t h m ；r e f i n e dg r i d s ；l a y e r ；t h r e s h o l d ；s e l f - a d a p t i v ea l g o r i t h m 1 i i 第章大规模散乱数据拟合 1 1 引言 第一章大规模散乱数据拟合 散乱数据 2 】是指在二维平面或三维空间中无规则的、随机分布的数据。 散乱数据拟合【3 就是找一个光滑的曲线或曲面来逼近或者通过这一系列无规则 随机分布的数据点。当这些数据点的数目非常多( 通常指1 0 0 0 0 个以上) 时，我 们称这个问题为大规模散乱数据的拟台。人们在进行生产实践的过程中，常常 希望能够通过测量得到的大规模散乱数据得原来的曲线或曲面得以重现，比如 在石油勘探、地震检测或者研究电子海图等活动中，通过仪器测量得到的是大 规模的散乱数据，我们需要根据这些已知的数据建立相应的曲线或瞳面信息， 这就需要进行散乱数据拟合。对于规模较小的散乱数据拟合问题，已经有了较 为成熟的方法，对大规模散乱数据的拟合闯题的研究，由于受到存储和计算速 度的制约，其研究进展相对较为缓慢，但却是近几十年来数据拟合领域的热点 和难点问题。 1 2 数据拟合问题的一般描述 数据拟合问题通常分为插值问题和逼近问题。插值问题的解要求严格经过 型值点( 已知的数据点) ，光顺逼近问题的解虽不要求严格经过型值点，但它 要求在某种约束条件下( 比如最小二乘意义下) 达到一种整体逼近效果。问题 的一一般捕述【4 】为： 问题1 1 已知区域d 中的数据点集p = 癍拉n 及对应的数集 f , i i n ( ，为指标集) ，如果在函数空间日中存在函数，满足如下插值条件： ，( 厩) = ，i i 则称此问题为插值问题，其解称为插值函数。 问题1 2 已知区域d 中的数据点集p = 蚓i j ) 及对应的数集 k ，1 ( ，为指标集) ，如果在函数空间日巾存在函数，满足如下最小二乘条件： a ，( ，( 霞) 一五) 2= m 剌i n 争( g _ ) 2 ) 畦0 往7 o 2 1 一 第+ 章大规模散乱数据拟舍 则称此问题为最小二乘光顺逼近问题，其解称为最小二乘光顺逼近函数，简称 逼近函数。 如果p 中的点的分布是随机散乱的，我们称上述两个问题为散乱数据的捅 值和拟合问题。当区域d 的维数n = 1 时问题即为益线插值或拟合，n ：2 时的 情形就是曲面插值或拟合问题，几2 时，上面的问题分别称为多元插值问题和 多元最小二乘光顺逼近问题。另外值得提的是，当p 中的数据有噪声时，光 顺逼近比插值逼近更为合理。本文主要讨论散乱数据的曲线和曲面拟合问题。 1 3 散乱数据拟合问题的解决方法 散乱数据拟合的问题自上世纪六七十年代提出以来，人们利用各种工具对 其进行研究，这个问题发展到今天，已经产生了许多中不同的方法，下面将近 几十年来较为主流的方法大致归纳如下1 4 j ： 1 3 1 样条函数方法 样条函数是分段( 片) 多项式函数，它是一类“半解析”逼近工具。它既 保持了多项式的某些优点( 如计算简单) ，又不象多项式函数那些在某些点附 近的性质足以决定它的整体性，具有相当的灵活性。自1 9 4 6 年1 j s c h o e n b e r g 提 出样条函数的概念以来，样条函数理论经过近六十年的蓬勃发展，至今已经产 生了许多门类，如分段样条、b 样条、自然样条、薄板样条、箱样条、顶点样 条、b 网、张量积样条等，它们在保持样条函数的共性的基础上有着各自不同 的特点。其中，b 一样条函数以其良好的光滑性和局部支撑性，特别适合作为数 据拟合的方法。我们重点介绍一下与本文课题关系较为密切的层次b 一样条函数 插值法和多项式自然样条函数插值法。 1 3 1 1 层次b 样条 1 9 8 8 年，f o r s e y 幕q l b a r t e l s 首先提出用层次b - 样条( h i e r a r c h i c a l b s p l i n e ) 的方法【5 】来解决编辑全局且维持细节的问题。它的逼近函数具有如 下形式： 33 l ( x ，) = 最( 5 ) 岛( t ) 焱似+ f ) 0 - 3 ) k = o1 = 0 翌：里盔塑坚墼塾墼塑型鱼 其中r i = 【z j 一1 ，j = l y j 一1 ，s = z i z j ，t = y 1 刎；风岛为标准的三次b 一样 条基函数： 9 0 ( t ) b l ( t ) b 2 ( t ) b 3 ( t ) = ( 1 一t ) 3 6 ， = ( 3 t 3 6 t 2 + 4 ) 6 ， = f 一3 t 3 + 3 t 2 + 3 t + 1 ) 6 = t 3 6 ， f j 4 ) ( 1 5 ) ( 1 6 ) ( 1 7 ) 其中，0 墨t 1 ；曲为控制点网格。 这一类方法的思想是将插值做一个从粗到精的逼近，首先做一个大致的逼 近，再反复修正逼近误差大的区域，这样步一步地从一个较粗糙的网格到一 个较精细的网格来提高逼近的精度，直至整张曲面控制在允许的误差范围之 内。这种方法能提供很好的连续性，并且具有修改方便的优点【5 】【6 】。有层次结 构的样条曲面主要有两点好处：表示同样的细节，它比细分样条曲面有更紧凑 的形式；易于修改其间的任何一层，且具有可传播性。这些曲面已相对成熟， 在动画领域，插值，图像变形等方面都有不少应用。而如何参数化给定的散乱 点对这个方法来说是至关重要的。 1 9 9 7 年，s e u n g y o n g b e e 等人从图像变形技术出发，提出了散乱数据的多 层次b 样条插值方法 7 】。该方法对给定的组散乱数据，通过求解一个不定方 程的伪逆矩阵来求解一组控制点，再通过最小二乘法来最终得到控制网格。 然后使用从粗到精的有层次的控制网格产生一系列的双三次b 样条求和并得 到最终的插值函数，通过使用b 样条的加细算法简化函数求和为一个b - 样条 函数等式，大大的提高了性能。该算法实现起来非常简单。但它的这些优点 部分来自于它处理的点集的规模小，它也是一个全局细化的算法。它的应用 也主要是集中在图像处理领域，特别适用于图像渐变( i m a g em a r p h i n g ) 中。s e u n g y o n gl e e 等人的算法虽然较以前的方法前进了一步，但在处理大规 模的散乱数据时，由于其不加选择的细化，在处理时间上远远不能满足需要。 1 9 9 9 年，张伟强和唐泽圣提出了一个基于三次b 样条曲面的自适应的拟 合方法【3 1 ，利用b 一样条曲面的特性，可以提供整个曲面的连续。该算法是 在s e u n g y o n gl e e 以及f o r s e y 等人的多层次b 样条插值算法的基础上，通过对 层次化的过程作出限制，用一种自适应的算法自动对某些需要细化的区域进行 第一苹大规模散乱数据拟合 细化。这样的处理在实际应用中，可以大大减少计算量，提高计算效率。 2 0 0 1 年，乇困夫，孙尧，张海勋，杨传安等人在讨论双三次b 一样条曲面 的构造算法和节点插入原理的基础上，提出了应用节点插入原理的、基 一多 层b 样条的大规模散乱数据的插值方法【”，它具有精度高、速度快的特点，适 合于要求严格的大规模散乱数据的可视化处理，并且已经在电子海图系统的三 维特性的研究中得到成功应用。 可以看出，基于层次b 样条的散乱数据插值方法近年来称为研究热点，1 向 且取得了定的结果。以卜- 的研究皆采用了标准的b 样条基函数及控制点网格 来做逼近函数，在下面的多项式自然样条中，采用了另外一种形式的b 样条局 部基函数做逼近函数。 1 3 1 2 多项式自然样条 样条函数理论建立之初，只有一元样条函数在唱独角戏，时至今日，一 元样条函数理论己经趋于完善。但是多元样条函数的研究进展由于在计算 上的复杂性及多维区域剖分的多样性，其发展较为缓慢，直到上世纪六十年 代如b o o r 等人引入了张量积样条，多元样条函数开始成为研究热点。 1 9 8 4 1 9 8 5 年，李岳生利用带广义约束条件的变分方法，解决了任意散乱 布点的多元插值问题，建立了散乱数据自然样条拟合的理论框架【8 l 【9 】。之后， 李岳生、关履泰、胡日章、黎罗罗等又在矩形域、圆域、三角形域、l 型域以 及更为广泛的情形采用不同的方法对散乱数据插值和光顺进行了深入系统地研 究0 0 1 1 ”】1 1 4 。1 9 8 9 年，关履泰、李岳生 1 5 1 1 6 j 研究了广义混合样条函数空间 矩形域带连续边界条件和离散边界条件的多元散乱数据最优插值问题，可以用 闭形式解决，并且提出二元希尔伯特空间多项式插值自然样条的概念。关子自 然样条问题的具体内容将在第二章和第三章给出详细的介绍，在此不作赘述。 1 9 9 3 年，关履泰基于希氏空间样条插值理论，给出了矩形域上散乱数据的 二元多项式自然样条插值、光顺或广义插值方法f m ，样条函数的基底由单边基 给出。同年，g k ，c h u i 与关履泰【17 】，把二元的结果全面地推向一般多元情形， 得出较一般区域的多元多项式插值自然样条的显函数表示格式。1 9 9 3 年韩国强 研究了这种类型的低次自然样条的误差估计及其收敛性【1 8 】。1 9 9 4 年关履泰研究 散乱点二元多项式自然样条的极小性质与定义区域，把自然样条推广到半任意 区域与无穷区域1 1 9 1 。1 9 9 7 年，关履泰在1 9 9 3 年的研究结果上f 2 0 】提出了类似b 样 条的局部支撑基函数，给出二元多项式自然样条的新基底，它可由二元多项式 一笙：童盔塑堡墼i ! 墼塑塑鱼 自然样条空间的单边基线性表出，并且具有最小局部支撑性。2 0 0 3 年又给出这 种局部支撑基的性质及插值自然样条的算法【2 “。之后，关履泰、逯峰对平而中 线上分布的大规模散乱数据亦提出适用的局部基自然样条插值【2 2 】：刘斌、关履 泰对细分节点和细分网格下散乱数据插值提出新的二步算法 2 3 1 1 2 4 1 。该算法在理 沧上具有可行性，本文就是基于这一算法提出了一种吏为有效的自适应算法并 得以实现。 1 3 1 3 其它样条函数方法 除了上述几种方法之外，还有许多其它的样条方法，比如薄 板样条( t h i np l a t es p l i n e ) 、顶点样条( v e r t e xs p l i n e ) 、箱样条 ( b o xs p l i n e ) 、b 网( b n e t ) 等等，根据各种函数自身的特点，人们从 不同的角度给出解决问题方法，也取得了一定的进展。比如薄板样条的方法， 就是在上面所述的数据插值问题中，令散乱数据插值函数的曲率的积分在整个 定义域上最小而导出薄板样条。该方法f 4 】具有较好的视觉效果且对海量数据非 常稳定，故有着广泛的应用。然而由于一般的薄板样条不是多项式样条，没有 多项式样条的良好性质，所以在大型网格上求解插值函数时其计算量仍然是巨 大的。 1 3 2 二步法 该方法是s e h u m a k e r 在总结张量积和利用h i l b e r t 空间构造再生核方法的基 础上提出的，它是针对的是格子点上的数据插值问题【4 】，其主要思想把散乱数 据拟合问题分成两步：第一步利用散乱数据点构造函数夕，由函数g 得到格子点 数据：第二步是针对上述格子点数据采用已有的格子点数据的处理方法。 1 9 9 1 年，l l s c h u m a k e r 和c t r a s s 提出了一种定义在球型光滑曲面上的函 数拟合方法 z “，运用张量积多项式样条和周期三兔样条，通过把曲面映射到 矩形域上构造了逼近曲而，并给出了最小二乘法全局逼近和拟内插局部逼近算 法，构造了一种二步法：第一步：用局部逼近方法构造拟内插所需的值。第二 步：用上述值去求拟内插系数。 韩国强在1 9 9 3 年提m 了一种计算稳定的二步拟合法，并且给出了二步拟合 法的误差估计。该方法可以避免薄板样条法和径向函数法当插值点较多时计算 上出现的病态，并可以减少存储与计算量。1 9 9 7 年，s c h u m a k e r 和l uh a n 构造 了具单调性散乱数据拟合的二步法 2 q ，其主要思想是：第一步：由具单调性的 塑里叁塑堡墼i ! 塑塑塑鱼 散乱数据构造具单调性格子点数据；第二步：用分片三次样条函数构造单调性 拟合曲而。 1 3 3 其它方法概述 基于三角划分的方法三角划分的具体方法有很多，其中应用最为广泛的当 属d e l a u n e y z 角划分。基于三角划分的散乱数据插值方法是一种较为直 接的方法，其基本思想【3 堤：直接对平面域上的点集进行d e l a u n e y - - 角划 分，然后用三角划分的结果来表示拟合后的曲面。该方法只能达到c o 连 续而且对大规模散乱数据进行d e l a u n e y ：三角划分的速度也很成问题。 s h e p a r d 方法有关散乱数据拟合较早的一个算法是s h e p a r d 于1 9 6 8 年提出的 个加权方法f 2 7 1 其基本思想是定义个对所有数据进行反距离加权平均的 插值函数。该方法可应用于任意分布的空间数据点，但是由于是对全局数 据的运算，而且它定义的插值函数只能e o 连续并且还不能保证抽样点周围 局部区域的正确形状，故用该方法得到的s h e p a r d 曲面代数精度低，在插 值点附近会形成平台形状，没有良好的极值性质，而且改变一个数据还会 影响整个曲面。8 0 年代，有不少关于s h a p a r d 方法的改进的文章出现，例 如1 9 8 0 年f r n 扎尼e 和m e f s d 礼引入了修正的二次s h e p a r d 方法解决上述缺点 并产生连续的插值【”1 ，r f a r w i g 在1 9 8 6 年给出了s h e p a r d 方法的全局误差 估计并证明s e p o r d 方法收敛性并给出最优逼近阶的条伊2 9 1 。经过这些改 进，s h e p a r d 方法可以处理观测数据的数目很大，尽管模型粗糙，但是对 于那些有峰值的曲面，却有良好的逼近效果。在实际应用中，s h e p a r d 插 值模型( 简称s p 模型) 是一种直观的、可操作的相似预测法，在降雨预 测中得到成功应用。 基于有限元的方法1 9 7 7 年，c l a w s o n 把有限元方法( f i n i t e e l e m e n t m e t h o d ) 引入到散乱数据点的曲面拟台领域，开创了基于有限元的插值 方法。该方法的基本思想是【3 l 】在给出具有双自变量的散乱数据点v i ( x 。，叭) 及其函数值盈以后，首先求出二维平面上散乱点的凸包，并对其进行= i 角剖分，形成一系列的三角形乃 i ，然后构造一系列的面片，使其插值j ： 所有散乱点的函数值五。之后，有很多研究学者将有限元方法与其它思想 相结合，产生了不少良好的结果，比如蔡中义、李明哲在2 0 0 3 年提出了。 种基于不规则分布的数据点重建三维曲面的光顺一有限元方法【”1 。该方法 6 第章大规模散乱数据拟合 根据数据光顺与最佳逼近相结合的概念建立目标泛函，采用有限元法求 解，并通过对目标泛函极小化得到重构的曲而。由于结合了光顺技术，这 种方法对原始数据的噪声误差具有明显的抑制效果，与有限元拟合方法相 比，所需的输入数据点少，重构的曲面逼近精度高、光顺性好。另外，该 方法对数据点分布形式没有任何特殊要求，对均匀及散乱分布数据点的曲 面重建问题同样适用。由于该方法采用了八节点等参数单元，对数据点所 分布的区域形状没有任何限制，可用于任意不规则边界的曲面重建问题。 径向基函数方法1 9 8 7 年1 9 9 1 年，p o w e l l 与j a c k s o n ，r i p p a 等人总结出径向 基函数方法( r a d i a lb a s i sf u n c t i o n s ) ，即用一系列径向基函数对数据进 行插值。所谓径向基函数法是指： 给定( 以 ) ，。彤，五r ，i = 1 ，求形如 的函数满足插值条件 n s ( 幻= a , g ( 1 l t 一钟) + ( t ) i = 1 s ( h ) = ，i = 1 ， 并且。n ，a i q ( t i ) = o ，v q ( t ) f k ，其中9 是定义在凰一上的一元函 数，口( 产) 又称为径向函数，m 是一个正整数，( t ) 尸怅，易是m 阶 多项式空间。有很多研究是围绕怎样选择合适的径向基函数展开的，其中 以h a t d y 在1 9 7 1 年引入的二次径向基函数( m u l t i q u a d r a t i c ) 的结果最为理 想，直到现在仍有很多研究成果是在这一方法的基础上进行的【3 3 】【3 4 】【”1 。 以卜i 的方法都是基于全局计算的，局部的个改变都将会导致整个区域上 的重新计算，而且在求解过程中往往需要锯一些大型的线性方程组，这样 的缺点往往是约束数据规模的重要因素。 光滑余因子方法王仁宏在1 9 7 5 年提出用光滑余因子方法解决数据插值的问 题。该方法从代数几何胞腔的观点来处理分片连接的样条函数，通过拼接 所要求的连续性条件和插值条件，得到线性方程组。这种方法能够保证良 好的光滑性，但是由于解方程组的系数矩阵是满的，因而这种方法也不适 于求解规模较大的插值问题。 7 第章大规模散 l 数据拟舍 另外，散乱数据拟合的方法还有许多方法，但是限于篇幅和本文的研究t 作的内容，在此不一列举。 1 4 本文的研究内容及组织结构 论文的第一章给出了大规模散乱数据拟合相关的概念及问题描述，并对近 年来问题的主流解决方法，特别是与本文研究工作相关的多项式自然样条捅值 方法等，做了较为全面的概述。 第二章主要回顾基于细分节点的平面散乱数据的一元多项式自然样条插值 及其二步算法，以及基于细分网格的三维散乱数据的二元多项式插值及其局部 基函数与二步算法。 第三章主要回顾矩形域上带连续边界条件的散乱数据插值方法。二、j 章 是本文研究工作的基础。 第四章介绍本文的研究工作之一：基于细分节点二步算法的大规模散乱数 据插值的自适应算法。 第五章介绍本文的研究工作之二：嘲格点上的大规模散乱数据插值的自适 应算法。 第六章对空间中大规模任意散乱点的拟合方法做出探讨，并本文的主要工 作进行总结，对将来的工作做出设想。 8 第二章细分1 5 点的多项式自然样条插值及其二j 步算法 第二章细分节点的多项式自然样条插值及其二步算法 2 1 细分节点的一元多项式自然样条插值及其二步算法 一元样条函数从2 0 世纪5 0 年代开始出现到现在，其理论已趋于成熟【3 6 1 1 3 7 】【3 8 】 刚 4 0 ，并且在逼近论、曲线拟合、微积分方程的数值求解以及计算机辅助j l 何设计( c a g d ) 等方面都有着广泛的应用。其中，b 样条函数以其良好的局部支 撑性和光滑性，成为用计算机构造和拟合曲线或曲面的有利工具。本章所介绍 的细分节点的样条插值及其二步算法，是研究在对给定的一批节点进行样条插 值之后，再在某两节点之间加插另一批节点时，怎样充分利用第一次插值的结 果进行曲线修改的方法。这种方法的价值在于在求节点加密后的插值曲线时， 无须对所有节点插值，只要利用加插节点的那段区间上的信息求出增补函数， 加到第一次的曲线上即得所求插值函数。这种方法充分而且有效的利用了节点 信息，速度快，光滑性也能够满足实际要求。因而具有较广阔的应用空间。本 文研究工作就是基于这一理论直接建立起来的。 2 1 1 一元自然样条插值 住区间【o ，6 】中，给定分划 7 r l ：a = x o 。1 x 2 - - z n x n + 1 = b 元样条插值问题【3 6 】的一般描述为 问题2 1 ：已知实数点集p = ( q ，y ， 。n ：l 其中 z 。) 譬1 如”，所述，求函数，( z ) ，满 足插值条件： f ( x j ) = y 3 ，j = 1 ，2 ，。，竹 ( 2 1 ) 则此问题称为一元样条插值问题，其解称为一元样条插值函数。 问题2 2 ：如果在问题2 1 的条件中要求，( z ) h ” n ，6 ，且除插值条件外还满足 变分条件：使泛函 厶( ，) ：，6 ( ，( m ) z 如 j o 9 第一章细分节点的多项式自然样条插值及其步算法 取最小，则称这个问题为一元自然样条插值问题【z ”，其解称为一元自然样条插 值函数。 根据文献f 3 7 艄】中自然样条插值的理论，容易得出下面的结论： 引理2 1 ：自然样条插值问题2 2 的解s ( z ) 可以表示成如下形式 s ( x ) ( 2 3 ) 引理2 2 ：自然样条插值函数空间s p ( d ”，7 r i ) 的维数是n + 2 m 。 引理2 3 ：b 样条函数系b 一2 。+ 1 ，b 一2 。+ 2 1 ，鼠构成b 样条函数空 i 、f i j s p ( d 2 ”，7 r 1 1 的基底。 引理2 4 ：自然样条插值问题2 2 的解s ( z ) 满足边界条件： s ( 。( n ) = s ( 。( 6 ) = 0 ，q = m ，m 4 - 1 ，一，2 m 一1( 2 4 ) 由上面四个定理可以得到 推论2 1 ：自然样条插值函数还可以用引理2 3 中的b 样条函数 系b 一+ ，b 一2 。+ 2 ，蜀的线性组合来表示，即 其中 马( z ) = b j ，。( z ) = ( + 。一q ) ，z ，+ t ，一，q + m ( + 一z ) 牢一1 2 1 2 细分节点自然样条插值 细分节点的自然样条插值问题叫描述如下： 在上述分划7 r 1 中，若某相邻两点z 。，z ( i 1 ，2 ，n 一1 ) 之间又有细分分划 7 7 2 ：茁。= x i o x i l 。 x i k 托，k + l = o i + 1 1 0 一m2 一 狮+q 一 协d p 。脚 +一 一触 筇q 扛岛吩 。一 f = z ，) 第二章细分节点的多项式自然样条插值及其j ：步算法 问题2 3 ：已知实数点集p = ( x j ，缈) ) 墨1u ( z 。蜘) ) 墨。( 2 1 ，2 q 各及z 。如7 r ，丌2 所述，求函数，( z ) h 7 “ o ，h i , 满足下述条件： ( 1 ) 插值条件： ( 2 ) 变分条件：使函数 f ( x j ) = y 3 ，j = 1 ，2 f ( x | l j ) = y i j ，= 1 ，2 厶( ，) ： 6 ( ，m ) 。如 j o ( 2 ，7 ) ( 2 8 ) 取最小，则称此问题为细分节点自然样条插值问蹶，其解称为细分节点自然样 条插值函数。 事实上，如果将丌1 ，i 2 两个分划中的节点依次重新排列即得到分划砘 7 r 3 ：n = z o z 1 - z l x i ，1 z t x i + l - 石n = b 则细分节点自然样条插值问题2 3 就变为上一节中的自然样条插值问题2 2 ，依照 推论2 ，1 ，其解函数可以表为如下形式： 其中 s ( z ) = 马( z ) + c r u b u ( z ) 马( 茁) = 易，。( z ) = ( x j + m 一码) ，x j + l b ”( 。) = 最a m ( z ) = ( z 。，j + m 一。t j ) 陋t ，j ，x i , j + l 同时此解函数也满足定理2 4 的边界条件( 2 4 ) 。 2 1 3 细分节点插值的二步算法 ，+ 。1 ( 一z ) 罕一1 z 。j + m 】( 一z ) 军一1 上面两节分别给出了关于分划”l 的白然样条插值问题及其解函数和在”1 的 第二章细分节点的多项式自然样条插值及其步算法 某个区间上进行的细分分划”2 的细分节点自然样条插值函数及其解函数。不 难看出，细分节点的自然样条插值实际卜就是在分划”。下的一般自然样条插 值。所谓细分节点的二步算法 2 3 】，是求解细分节点自然样条插值问题的一种 方法，它的基本思想是：在求得分划7 r 。的自然样条插值函数s ，( z ) 之后，只通过 细分分划7 r 2 上的插值信息和s ( o ) 求解一个增补函数岛( z ) ，并将这个增补函数加 到s ，( z ) 上，即得所求的细分节点自然样条插值解函数s ( x ) 。该二步算法特别适 用于已经对某分划进行了一次自然样条插值，但发现该分划内的某两个节点之 间的插值结果太粗糙，需要对其进行更细致的描绘的情形。该算法的优点在于 在求上述情形的问题时，可以充分利用第一次插值的结果及细分节点的插值信 息，无须重新对所有节点进行插值。 细分节点的二步算法在推导过程中用到了b 样条函数局部支撑性的性质。 即通过在细分分划丌2 的两端点区间上各增加m 一1 个节点，记为分划7 7 4 ： 7 ：z = x i ，一m & 一m + l x i ，0 x i ，1 。 而女 x i k + l 。 x i ，k + 2 m 一2 z 2 自+ m x i + 1 这样以来，由于m 阶b 样条的局部支撑性，它至多在m + 1 个节点上不为o ，故由 细分节点 z 玎) 譬。所产生的2 m 一1 阶b 样条基函数在分划丌的节点 瑶，处取值 为0 。由问题2 3 的插值条件( 2 7 ) ( 2 8 ) 及其所会满足的边界条件( 2 4 ) ，可以得到下 面的定理： 引理2 5 ：细分分划采用丌4 的细分节点自然样条插值问题的解s ( t ) 可以表示为 的形式，其中系数 n j p - 2 m + l 及 a d ) l 可以由下列线性方程组解出： n 马( 黝) 。，+ 民( 黝) 。旷蛳， k 1 川2 一，詹 一2 m + 1 j = l 岛( 札) = 执， k 1 川2 一，礼 j = - 2 m + l 1 2 ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) p岛 一= ， o 。触 卜 功岛q 。咖 产 | i p s j 堇童蔓塑坌! 皇塑墨翌塞鱼鉴壁墨堑焦墨基：生塞鲨 b ；1 ) ( d ) = 0 ，= m 一，2 m 一1 ( 2 1 4 ) j 22 m l 尉( 6 ) = 0 ，1 = 巩，2 m 一1 ( 2 1 5 ) j = - - 2 m + 1 细分节点的二步算法就是基于上面一个定理产生的，其步骤由下面个定 理给出 引理2 6 绍分节点采用分划皿的细分节点自然样条插值问题的解函数s ( 霉) 可以 用下述二步法解出： s t e p l 先解线性方程组( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) ，求出系数 o ，) 1 2 。l 及 s t e p 2 解线性方程组( 由( 2 1 2 ) 及上述& ( z ) 得出) 求出系数 n ：，) 嘉t 及 从而由( 2 11 ) 求出s ( x ) = 岛( z ) + 岛( z ) 说明：在引理2 5 与引理2 6 的推导中，我们用分划丌4 代替了分划7 r 2 ，二者 的不同在于前者是在后者的两端点区间上又各加插了m 1 个节点，因而事 实上用此算法求得的s ( 茁) 与问题2 3 的解相比在与筑+ 1 附近是有差异的。前 者是以，x i ，一m ( z t ) ，z t o ( 茁n ) ，z 1 1 l ，- - ，z t ，女( z 俯) - ，x i , k + m ( z 抖1 ) ，- 为节点 的2 m 一1 次分段多项式，而后者是以，翰，砧l ，z ；，z 件1 ，为节点的2 m 1 次多项式。根据文献f z ”，尽管两种分划所得的插值函数稍有不同，但是它们 有着相同的光滑性，而且满足同样的插值条件，并且这种二步算法是简单易行 的。本文的研究工作之一( 见第四章) 正是基于这一算法建立起来的。 扛吩 o + 。一 = 1 | 渖& 七2l = z a 一 玑 | | u 口z 玩 。触 忙，u q 。芦 = 协 2 2 细分网格的二元多项式自然样条插值及其二步算法 多元样条函数的研究f 4 习始于2 0 世纪6 0 年代，与一元样条函数相比，多元函 数在计算上更为复杂性，加之多维区域剖分的多样性，使得多元函数的研究进 展较为缓慢。在生产实践i _ l 应用最为广泛的当然是属于三维空间的二元样条函 数。目前，规则区域的二元样条函数的研究已趋于成熟，非规则区域的逼近以 及散乱点的二元插值成为研究的焦点。本章所要介绍的理论就是对三维空间中 的散乱数据进行二元样条插值的一种分层处理方法，首先通过张量积空间中的 局部基函数来构造大网格点上的二元自然样条插值函数，再利用与第二章的二 步算法同理的三维情况下的一二步算法( 文献【2 4 】中称之为多重二步法) 求解细网 格上的插值函数。文献 4 3 】【2 0 】【2 l 】给出了二元自然样条函数的局部支撑基的表达式 及其性质，利用这一局部基可以较快捷的求解插值函数。 2 2 1 细分网格的二元多项式自然样条插值 我们先来考虑张量积窄问中的二元多项式自然样条插值闯题。首先给出必 需的记号和假设条件： 在二维区域r = 【a ，卅x 【c ，词上，记 x = 日”，“( r ) = u ( z ，) i 瓦o 两m + n u l 2 ( r ) 器番是绝对连续函数，对o = 0 ，1 ，m 一1 ，卢= 0 ，1 ，竹一1 成立：( z ，) 哪 记 n 一1m 一1 y = l 2 ( r ) l 。 0 ，6 】l 2 【c ，d 】 u = o“0 是一个张量积空间。 记是个整数，z = 兄是维欧凡里得空间。 令t ：x y 是一个从x 到y 的线性算子，定义为 似2 州脚 p “q “脚 缸 f f 丁 笙三望塑坌苎皇塑墨堕壅皂鉴堂壅塑笪星基：垄蔓鎏 其中 a ”u ( xy 1 a z ”o y “ 烈“旧叱那) = 筹k 姐b , n - - 1 批一叫哪) = 筹k 洲= o ，卜一，m 1 令a ：x z 是一个插值算子，定义为 a u = ( u ( x l ，y 1 ) ，- 一，u ( x n ，y n ) )( 2 1 6 ) 给定个散乱数据点的值 ( 戤，y i ，盔) ，i = 1 ，一，) ，方便起见i d z = ( 动，z n ) 问题2 4 寻找一个函数盯( z ，y ) x ，满足 其中 i t o l l 2 。艘： l i t “t 1 2 ) f 2 1 7 ) 酬卜鲫2 蛐+ 薹z 6 叫”沁，嘲2 蚺薹，。”沁胁 ( 2 1 8 ) 这个问题称为二元多项式自然样条插值问题，其解称为二元多项式自然样条 ( n 一样条) 插值函数。 引理2 7 ：二元多项式自然样条口( z ，9 ) 具有如下的显式及紧凑格式的表达式： o ( x ，y ) ( 2 1 9 ) 其中皿( z ，y ) = g ( x i ，仇；。，) ，i = 1 ，是( 2 m 一1 ，2 n 一1 ) 次自然样条基函数， 并且有 g ( ，r ；z ，可) = ( 一1 ) “+ n t 石- - 五x 磊_ = 2 二m j - - j 1 可j t i _ 二_ i 2 豇n - - 一i 1 5 一 f 2 2 0 ) 矿 z 伽 一：l + 计 z 轨 第! ：章细分节点的多项式自然样条插值及其二二步算法 + ( p = 0 + ( “= 0 z ) 2 + m 一1 ( f c ) ”，( r c ) ” 西i 1 瓦r 一【万一 1 2 翌：坠二坐 ( 2 n 一1 ) ( _ 1 ) 糕 铲+ ，r 一群一 下面我们来考虑在第一4 节所述二维区域的r = 。，翻x c ，d 】上的分划 以及子分划 7 r l ：a = z o 。1 z k + 1 = b 7 r 2 ：c = y o y 1 虮+ 1 = d 7 r 3 ：x i = 孔，o 1 7 4 ：珊= 缈，o 协，1 x t ，r + 1 = 。 + l ，z 1 ， 协，。+ 1 = 协+ 1 ，j 1 ， 定义2 2 ：称上述分划所形成的网格点 以及子网格点 ( 鄂，跏) ) ，p = 1 ，七；q = 1 ，2 ( 戤，“，协) ) ，p = 1 ，。一，r ；p - = 1 ，一，s 膏) f ) 为r ；f a ，b l i t , d l 上的细分网格点。称丌1 丌2 为基本网格，7 i 3 丌4 为第一层细 分网格。 如果在第一层细分网格中再做子网格，就会形成第二层细分网格，由于道 理相同，在此不作赘述。下面的讨论只以第一层细分网格为例。 问题2 5 对于h 述网格分划， 给定网格点上的 值 知，。) 筹l ，1 及 荔。如) 嚣1 。，如果存在函数盯( 茁，! ，) x = h m , n ( 孔) ，满足 ( 1 ) 插值条件： a ( x p ，y q ) = 卸，q ，p = 1 ，q = 1 ，f ( 2 - 2 1 ) 1 6 第二二章细分节点的多项式自然样条插值及其一步算法 ( 2 ) 变分条件 其中 e ( x i ，p ，弘”) = 2 t 川 ”，p = 1 ，- - ，r = 1 ，一，8 ( 2 2 2 ) 乃lj 2 2 恕咿u 怫 f 2 2 3 ) | | 丁训| 2 2 “神扛) ) 2 d x d y + z 似“惭) ) 2 出+ 善z ( u ( 俐州胤 f 2 2 4 ) 则称此问题为细分网格的二元多项式自然样条插值问题，其解称为细分网格 的二元多项式自然样条插值函数。 由以上两个问题的捕述可见，问题2 5 可以看作是问题2 4 中的点取为定 义l 中的细分网格点时的一种特例，那么由二元多项式自然样条插值问题的理论 我们可以得到下面的结论： 引理2 8 ：细分网格点上的二元多项式自然样条插值函数口( z ，) 具有以下的显式 和紧凑格式表达式： kirsm ln 一1 一( 啪) = n 。甄，( 刎) + 风，蚀。，( 删) + 铀旷( 2 2 5 ) “= 1u = lp = 1u = lp = 0v = 0 其中 9 “。( z ，y ) = a ( x p ，珈；z ，可) ，肛 g l ，。，。( z ，y ) = g ( z 。，p ，约，；z ，可) ，p 1 ，一，七；= 1 ，l 1 一，r ：= 1 ，一，s 是( 2 m 一1 ，2 n 一1 ) 次自然样条基函数，并且有 g ( t ，r ；x ，g ) = ( 一1 ) ”+ n 垡二( 2 m 堕- 翌二1 ) l ! ( 二2 n 二- 望蟹1 ) ：! 二 ( 2 2 6 ) + 争，”黜铲c 学七矿簪罱， + ( 一1 尸 = 0 ( 7 - 一9 ) _ 1 ( z 一 1 i j 再 1 7 o ) “，o o ) p “!_ ( _ r 一鬻】 第二章细分节点的多项式自然样条插值及其二步算法 引理2 9 ：二元多项式自然样条插值函数可以表示为乘积型b 样条的形式 女fr5 一( 砌) = a ，e 。( z ) 雪。( ) + 鼠，。( 。) 岛，( ”) ( 2 2 7 ) “= 1p = 1“= 1p = l 其中 吼( z ) ) ：。， 或( ) ：， b i 。( x ，