分形插值与拉格朗日插值的比较研究

第25卷 第3期2008年6月 黑龙江大学自然科学学报JOURNALOFNATURALSCIENCEOFHEILONGJIANGUNIVERSITY Vol125No13June,2008

分形插值与拉格朗日插值的比较研究李信富1,2,3, 李小凡3(1.中国地质大学(北京)地下信息探测技术与仪器教育部重点实验室,北京100083;2.中国地质大学地球物理与信息技术学院,北京100083;3.中国科学院地质与地球物理研究所岩石圈演化国家重点实验室,北京100029)

摘 要:数据插值方法的精度和效率是人们在插值方法的研究中关注的主要问题。在理论分析的基础上给出了自仿射分形插值函数的表达形式和垂直比例因子的显式表达形式。分别利用分形插值方法和拉格朗日插值方法对给定数据进行了插值拟合处理,结果表明分形插值方法对数据的拟合精度整体上高于拉格朗日插值方法,而且不会出现数据拟合中常见的/龙格现象0。通过对拟合曲线的分析,发现由于垂直比例因子采用了局部显式表达形式,从而将局部信息与全局信息有机地结合了起来,既突出了局部信息,避免了/龙格现象0,又保持了数据总体的变化趋势。拉格朗日插值在插值区间的中部精度很高,而靠近区间两端则会出现严重的/龙格现象0。关键词:分形插值;拉格朗日插值;垂直比例因子;精度;龙格现象中图分类号:O241.3文献标志码:A文章编号:1001-7011(2008)03-0323-04

收稿日期:2007-12-19基金项目:国家自然科学基金重点项目(40437018);地下信息探测技术与仪器教育部重点实验室开放课题(GDL0709)作者简介:李信富(1976-),男,博士,主要研究方向:复杂介质中地震波传播的数值模拟及地震数据处理、天然地震层析通讯作者:李小凡(1959-),男,研究员,博士生导师,主要研究方向:地震波动及散射理论、地球物理非线性反演理论及方法、地震全波及散射层析成像、地球内部物理及结构

1 引 言欧氏空间中的曲线和曲面的插值,已经有了一套成熟的理论和方法。几百年来,数学家对插值问题的解决是朝着越来越光滑的方向发展。但对于大量存在的自然界形态,由于很难得到它们的数学表达式,于是人们想到用插值方法来拟合自然界的形态,但这时的插值并不是越光滑越好,而恰恰是它的反面。70年代Mandelbrot[1]首次提出分形的概念,而分形概念的提出正是从自然界的无规则方面提出来的,因此在用分形来拟合自然界形态就成为一种可能。1986年,美国数学家Barnsley[2]首先提出分形插值的概念,这给出了拟合数据的一种新思想,不仅为函数逼近论开辟了崭新的研究领域,而且为计算机图形学提供了有力的工具,目前已充分显示出其强大的生命力。在有关文献[3-5]中可以见到分形的随机生成方法的研究。分形的随机生成,可以给出在三维欧氏空间中优美的景观和非常逼真的景物。这为分形物体的直观描述和图形再现提供了有力的工具。但是,这种随机分形的生成方法,不能产生通过已知点的分形。因此,用随机方法生成的分形通常不能满足实际研究工作的需要。在实际工作中,往往已知研究对象的部分信息,需要通过这些部分信息和特征,拟合出研究对象的局部形态,从而对研究对象的局部细节进行研究,这就需要用到分形插值的理论和方法。拉格朗日插值方法是一种经典的数据插值方法,在插值区间中部其插值精度很高,但在靠近插值区间两端则会出现/龙格现象0,从而限制了其在数据处理和拟合中的应用。本文将分形插值方法和拉格朗日插值方法进行了插值精度比较,并分析了分形插值方法插值精度高的原因。

2 分形插值的基本原理称具有如下形式的点集为数据集{(xi,Fi)IR2:i=0,1,2,,,N}(1)其中x0<,xN]yR。点(xi,Fi)IR2叫做插值点。分形插值是基于分形理论框架下的迭代函数系统(IterativeFunctionSystems,IFS)理论而实现的。迭代函数系统的构造方法如下[2]:给定闭区间+=[x0,xN]任意一组实数,数据集{(xn,yn)I+@R,n=0,1,2,,,N}.记+n=[xn-1,xn],K=+@[a,b],(-]Ln(x0)=xn-1,Ln(xN)=xn(2)并且对某个0|Ln(c1)-Ln(c2)|[ln|c1-c2|,c1,c2I+(3)连续函数Fn:Ky[a,b],nI{1,2,,,N}满足条件Fn(x0,y0)=yn-1,Fn(xN,yN)=yn(4)并且对某个0|Fn(c,c1)-Fn(c,c2)|[qn|c1-c2|,cI+;c1,c2I[a,b](5)定义映射Xn:KyK为

Xn

x

f(x)=Ln(x)Fn(x,y),nI{1,2,,,N}(6)

则{K,Xn:n=1,2,,,N}构成一个迭代函数系统IFS.其中Xn为仿射变换:

Xn

xy=an0cndnx

y+enfn

(7)

其中an,cn,en,fn由条件Xn(x0,y0)=(xn-1,yn-1)和Xn(xN,yN)=(xn,yn)确定,0<|dn|<1是自由变量,称为垂直比例因子。设IFS:{K,Xn:n=1,2,,,N}及f(x)如前定义,那么G={(x,f(x)):xI+}是该IFS的唯一吸引子的充要条件为:Fn(x,y)=f(Ln(x))(8)对一切nI{1,2,,,N}成立[6].假设迭代函数系统、仿射变换及其系数如前所述。本文考虑等距插值问题,即

xn-xn-1=1N(xN-x0),n=1,2,,,N(9)设(x0,y0),(x1,y1),(x2,y2),,,(xN,yN)和(x0,yc0),(x1,yc1),(x2,yc2),,,(xN,ycN)是两组等距插值节点,用前面方法得到的分形插值函数分别为f和p,那么有

+f-p+[1+d1-dmax{|yn-ycn|:n=0,1,2,,,N}(10)

其中+f-p+=maxxI[x0,xN]|f(x)-p(x)|,d=max{|dn|:n=1,2,,,N}.从(14)式可以看出,当插值节点有一个小的扰动时,其对应的分形插值函数也仅有一小小的扰动,即分形插值是稳定的[7]。该结论就是垂直比例因子变化时分形插值的稳定性条件。在分形插值的实现过程中,垂直比例因子是一个关键参数,它的选取必须保证其是一个无量纲参数,因为垂直比例因子主要影响插值点的纵坐标,即插值函数值,所以本文中选取如下形式的垂直比例因子表达式,它可以兼顾对数据局部细节和待插值对象整体特征的影响。

dn=yn-yn-1E#(ymax-ymin)2+(yn-yn-1)2(11)其中,ymax,ymin是以待插值点为中心前后各扩展n0个点得到的区间中的最大和最小值。即,如果待插值点编号为ip,则有ymin,ymaxI[ip-n0,ip+n0],E=110+random(D),random(D)是计算机内部的随机函数,它用于产生一个0到1之间的随机数。由yn、yn-1体现局部信息,ymax、ymin体现全局信息,而随机数的产生保证了分形本身的性质。

#324#黑 龙 江 大 学 自 然 科 学 学 报 第25卷 3 分形插值数值实验及与朗格朗日插值的精度比较为了检验分形插值方法的有效性并比较其与拉格朗日插值方法的精度,利用地震学中的经典子波函数作为检验函数来做数值实验,所采用的实验函数是Ricker函数f(t)=[1-2(Pf(t-t0))2]e-(Pf(t-t0))2。从图1和图2的数值实验结果可以看出,本文提出的分形插值方法可以很好地拟合实验数据,由于对垂直比例因子采用了局部变化的策略,使得方法在整体上对原曲线的拟合非常接近。从总的结果来看,本文提出的垂直比例因子选取方案是一种非常好的表达方式,它使得拟合精度非常之高。垂直比例因子变化剧烈但拟合精度仍然很高,说明垂直比例因子的局部变化并不显著影响拟合数据曲线的整体形态,反而突出了数据的局部信息。

下面讨论拉格朗日插值的问题。考虑区间[a,b]上的函数f(x),区间[a,b]的一个等距划分为xi=a+2in,i=0,1,2,,,n(12)那么拉格朗日插值多项式为Ln(x)=Eni=0f(xi)li(x)(13)其中,li(x),i=0,1,2,,,n是n次拉格朗日插值基函数。其表达式为

#325#第3期李信富等:分形插值与拉格朗日插值的比较研究li(x)=Fnj=0jXix-xjxi-xj(14)取n=10,即利用十次拉格朗日插值多项式拟合,下面是数值拟合结果。图3中,实线表示f(x),虚线表示插值多项式Ln(x)的图形,从图中可以看出|f(x)-Ln(x)|在靠近区间端点处是很大的,而在靠近区间中部误差非常小,在靠近区间端点处Ln(x)不收敛于f(x)的现象称为龙格(Runge)现象。这种现象对等距节点的高次插值多项式是典型的。这样,对于局部变化比较剧烈的数据或者曲线,拉格朗日插值方法就不实用了。通过对比很容易看出本文提出的分形插值方法的有效性,它有效地克服了龙格现象,使得高精度高效率的数据插值和处理成为可能。

4 讨论和结论(1)分形插值克服了传统的插值方法不能反映两相邻已知点之间的局部特性的局限性,运用分形插值方法对数据处理和插值,可以得到比传统的插值方法更高的精度;(2)由于对垂直比例因子采用了局部变化的策略,克服了传统插值方法中整个计算过程采用同一垂直比例因子的缺陷,给出了垂直比例因子的局部显式表达式,使得本方法在整体上对原曲线的拟合精度远高于传统方法。数值实验证明本文提出的显式分形插值方法既能够突出数据的局部信息,又很好地保持了数据的总体变化趋势。该方法对数据的拟合精度整体上远高于拉格朗日插值方法,有效地避免了/龙格现象0;(3)拉格朗日插值方法是一种经典的数值方法,阶数越高,其插值精度越高,但相应的/龙格现象0也越严重,从而限制了它在局部信息凸显方面的应用。

参考文献[1] MandelbortBB.HowlongisthecoastlineofBritain?Statisticalself-similarityandfractaldimension[J].Science,1967,155:636-638.[2] BarsleyMF.Fractalfunctionsandinterpolation[J].ConstructiveConstructive,1986,(2):303-329.[3] 胡瑞安,胡纪阳,徐树公.分形的计算机图象及其应用[M].北京:中国铁道出版社,1995.6l-85.[4] 宋万寿,杨晋吉.一种地表造型方法[J].小型微型计算机系统,1996,(3):32-36.[5] XieHeping.FractalsinRockMechanics[M].Netherlands:ABalkemaPublishers,1993.70-78.[6] 龙晶凡.分形插值的条件[J].北京师范大学学报(自然科学版),2001,37(3):289-291.[7] 冯志刚,周其生.关于一类分形插值稳定性问题[J].安庆师范学院学报(自然科学版),1998,4(4):18-21.