几种常用的插值方法

几种常用的插值方法数学系信息与计算科学1班李平指导老师：唐振先摘要:插值在诸如机械加工等工程技术和数据处理等科学研究中有许多直接的应用,在很多领域都要用插值的办法找出表格和中间值,插值还是数值积分微分方程数值解等数值计算的基础。本文归纳了几种常用的插值方法,并简单分析了其各自的优缺点。关键词:任意阶多项式插值,分段多项式插值。引言:所谓插值,通俗地说就是在若干以知的函数值之间插入一些未知函数值,而插值函数的类型最简单的选取是代数多项式。用多项式建立插值函数的方法主要用两种：一种是任意阶的插值多项式,它主要有三种基本的插值公式：单项式,拉格朗日和牛顿插值；另一种是分段多项式插值,它有Hermite和spine插值和分段线性插值。一．任意阶多项式插值：1.用单项式基本插值公式进行多项式插值：多项式插值是求通过几个已知数据点的那个n-1阶多项式,即Pn-1(X)=A1+A2X+…AnXn-1,它是一个单项式基本函数X0,X1…Xn-1的集合来定义多项式,由已知n个点（X,Y）构成的集合,可以使多项式通过没数据点,并为n个未知系数Ai写出n个方程,这n个方程组成的方程组的系数矩阵为Vandermonde矩阵。虽然这个过程直观易懂,但它都不是建立插值多项式最好的办法,因为Vandermonde方程组有可能是病态的,这样会导致单项式系数不确定。另外,单项式中的各项可能在大小上有很大的差异,这就导致了多项式计算中的舍入误差。2.拉格朗日基本插值公式进行插值：先构造一组插值函数Li（x）=011011()()()()()()()()iiniiiiiinxxxxxxxxxxxxxxxx，其中i=0，…n.容易看出n次多项式Li（x）满足Li（x）=1，（i=j）；Li（x）=0，（i≠j），其中i=0，1…n，令Li（x）=0()niiiylx这就是拉格朗日插值多项式。与单项式基本函数插值多项式相比,拉格朗日插值有2个重要优点:首先,建立插值多项式不需要求解方程组；其次,它的估计值受舍入误差要小得多。拉格朗日插值公式结构紧凑,在理论分析中很方便,但是,当插值节点增加、减少或其位置变化时全部插值函数均要随之变化,从而整个插值公式的结构也将发生变化,这在实际计算是非常不利的。3.使用牛顿均差插值公式进行多项式进行插值：首先,定义均差,f在xi,xj上的一阶均差()()[,]jiijjifxfxfxxxx，其中(i≠j)。f在xi，xj，xk的二阶均差f[xi，xj，xk]=[,][,]ijjkjkfxxfxxxx，k阶均f[xi…xk]=010[][]kikkfxxfxxxx。由此得出牛顿均值插值多项式的公式为Pn(x)=f[x0]+f[x0-x1](x-x0)+…+f[x0，xn](x-x0)…(x-xn-1)。实际计算中经常利用下表给出的均差表直接构造牛顿插值公式,，xkF(xi)一阶均差二阶均差三阶均差……x0x1x2x3…F(x0)F(x1)F(x2)F(x3)…F[x0，x1]F[x1，x2]F[x2，x3]…F[x0，x1，x2]F[x1，x2，x3]…F[x0，x1，x2，x3]…凡是拉格朗日插值解决的问题牛顿插值多项式都可以解决,不仅如此,更重要的是牛顿均值克服了拉格朗日插值多项式的缺点,当需要提高近似值的精确度而增加结点时,它不必重新计算,只要在后面再计算一项均插即可,减少了计算量,不用计算全部系数,节约了大量人力,物力,财力。增加插值多项式的阶数并不一定能增加插值的精度,据定义,插值式,F(x)可以与结点(xi，yi)，i=1，…，n处的实际函数匹配,但却不能保证支点之间求F(x),还能很好的逼近产生(xi，yi)数据的实际函数F(x)。例如,如果F(x)为一个已知的解析函数,而且定义F(x)的节点集合中数据点的数目可以增加（多项式F(x)的阶数也增加）,但是,由于F(x)的起伏增加,那么插值式就可能在节点见振带,基于当实际函数F(x)平滑时,这种多项式摆动也可能发生,这种振荡不是由多项式摆动引起的,而是由多项式的项相加来求插值多项式时发生舍入误差造成的。有时多项式摆动可通过谨慎选择基础函数的取样来成为,但如果数据是由不容易重复实验取得的,就不能这么做了,这会司会用下面介绍分段插值法。二、分段插值多项式1、分段线性插值：分段线性插值最简单的插值方案,只要将每个相邻的节点用直线接起来,如此形成的一条新的折线就是分段线性插值函数,记作In(xj)=yi而且In(x)在每个区间[xjxj+1]上是线性函数（j=0,1…n-1）In(X)可以定义为In(xj)=0()niiiylx其中l0(x)=101xxxx，[0,1]xxx其他，l0(x)=0lj(x)=11jjjxxxx，1[,]jjxxx；nl()x=11jjjxxxx1,[,];jjxxx其他，lj(x)=0ln(x)=11nnnxxxx1,[,];nnxxx其他，ln(x)=0In(xj)具有很好的收敛性,即对于x∈[a,b]有：当n趋向于无穷大时,In(x)=g(x)成立。用In(x)计算x点的插值时,只用到x左右的两个节点,计算量与节点个数n无关,但n越大分段越多,插值误差就越小,但是,该方法折线在节点处显然不光滑,即In(X)在节点处导数不存在着影响它在需要光滑插值曲线的（如机械插值等领域中的应用）。2分段三次Hermite插值为清楚起见,先用三次Hermite插值的构造方法加以解释,三次Hermite插值的做法是,在[xkxk+1]上寻找一个次数不超过3的多项式H3(x)它满足插值条件H3(xk)=f(xk),H3(xk+1)=f(xk+1)'3()kHx=mk,'31()kHx=mk+1相应的插值基函数为211121111()12,()12,kkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxx2112111()(),()().kkkkkkkkkkxxxxxxxxxxxxxx于是有H3(x)=αk（x）f(xk)+αk+1（x）f(xk+1)＋mkβk(x)＋mk+1βk+1(x)。如果函数Ψ满足条件：（1）Ψ∈C1[a,b]（2）满足插值条件：Ψ（xk）=f(xk),''()()kkxfx,k=0,1,2,…,n.（3）在每个小区间[xk-1,xk],k=1,2,…,n上Ψ是三次多项式。则称Ψ为f的分段三次Hermite插值多项式。根据分段线性插值和三次Hermite插值公式可得到Ψ的表达式Ψ(x)='0[()()()()]nkkkkkfxxfxx其中20101010010112,[,]()0,[,]xxxxxxxxxxxxxxx21111211111112,[,]()12,[,]0,[,]kkkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxxxxxxxxxx21111112,[,]()0,[,]kknnnkkkknnxxxxxxxxxxxxxxx2100100101(),[,]()0,[,]xxxxxxxxxxxxx2111211111(),[,]()(),[,]0,[,]kkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxxxxxx21111(),[,]()0,[,]nnnnnnnnnxxxxxxxxxxxxxαk，βk，k=0,1,2,…,n，称为以节点x0，x1,…,xn的分段三次Hermite插值基函数，对于给定n个插值点x1＜x2＜…＜xn和其相应函数值f(xk)和一阶函数值f'(xk),k=0,1,2,…,n.显然,分段三次Hermite插值可以产生平滑变化的插值式,但它有一个明显的缺点,就是在每个界点处的函数斜率必须已知,而从实验中获得的数据,这个斜率就不存在。下面要介绍的三次样条插值可以解决这个问题,同时能得到插值式所期望的光滑度。3、三次样条插值1.样条函数在[a,b]上取n+1个插值结点a=x0x1…xn=b已知函数f(x)在这n+1个点的函数值为yk=f(xk)则在[a,b]上函数y=f(x)的m次样条插值函数S(x)满足:(1)S(x)在(a,b)上直到m-1阶导数连续;(2)S(xk)=yk,(k=01…n);(3)在区间[xk,xk+1](k=01…n-1)上,S(x)是m次多项式。2.三次样条函数在[a,b]上函数y=f(x)的三次样条插值函数S(x)满足:(1)在(a,b)上0、1、2阶导数连续,即:s'(xk-0)=s'(xk+0)，s″(xk-0)=s″(xk+0)(k=01…n-1)(2)S(xk)=yk(k=0，1，…n);(3)在区间[xkxk+1](k=0，1…n-1)上S(x)是三次多项式。3.三次样条函数的计算由二阶导数连续,设s″(xk)=mk,(k=0,1,…,n),mk是未知待定的数。因S(x)是分段三次多项式,则在每个区间[xkxk+1]内,S″(x)是分段一次多项式,记hk=xk+1-xk则:s″(xk)=111111kkkkkkkkkkkkkkxxxxxxxxmmmmxxkxxhh将上式在区间[xkxk+1]上积分两次,并且由S(xk)=ykS(xk+1)=yk+1,来确定两个积分常数。当x∈[xkxk+1]时,3322'11111()()()()()6666kkkkkkkkkkkkkkkkxxxxhxxhxxsxmmymymhhhh,利用S(x)一阶导数连续的性质,对上式求导,得:22'1111()()1()()()226kkkkkkkkkkkkxxxxhsxmmmmyyhhh在上式中,令x=xk得:'11(0)63kkkkkkkkhhyysxmmh将上式中的k换成k-1,得:s'(x)在[xk-1,xk]上的表达式,将x=xk代入,'11(0)63kkkkkkkkhhyysxmmh,而s'(xk+0)=s'(xk-0)联立上述两式,得到关于m的方程:1111111636kkkkkkkkkkkkkhhhhyyyymmmhh,两边乘以16kkhh得:11111111162()kkkkkkkkkkkkkkkkkhhyyyymmmhhhhhhhh,上式中,等式左边含未知量mk-1,mk,mk+1等式右边yk-1,yk,yk+1是已知的,令11kkkkhhh，11kkkkkhhh，11116()kkkkkkkkkyyyychhhh11111[,][,]66[,,]kkkkkkkkkfxxfxxfxxxhh则得:λkmk-1+2mk+μkmk+1=Ck(k=12…n-1)。三次样条插值的整体光滑性有提高,应用广泛,但其误差估计较困难,而且它的求解代价很大,起精确度受端点条件影响很大。总结:插值是数值分析领域的一个主要部分,选择插值策略的第一步是了解应用的需要：你要在表格中查些什么？是否需要反复计算近似值？在条件有限的情况下,构造固定的阶数的插值多项式可能会是一种更简单的方法有解决方案；当要反复计算逼近值时,推荐用牛顿多项式插值形式。对表格数据