计算方法——插值法综述论述.doc

计算方法——插值法李晓东 在许多实际问题及科学研究中，因素之间往往存在着函数关系，然而，这种关系经常很难有明显的解析表达，通常只是一些离散数值。有时即使给出了解析表达式，却由于表达式过于复杂，使用不便，且不易于计算与分析。解决这类问题我们往往使用插值法：用一个“简单函数”逼近被计算函数，然后用的函数值近似替代的函数值。插值法要求给出的一个函数表，然后选定一种简单的函数形式，比如多项式、分段线性函数及三角多项式等，通过已知的函数表来确定作为的近似，概括地说，就是用简单函数为离散数组建立连续模型。 一、 理论与算法 （一）拉格朗日插值法 在求满足插值条件次插值多项式之前，先考虑一个简单的插值问题：对节点中任一点，作一n次多项式，使它在该点上取值为1，而在其余点上取值为零，即 （1.1） 上式表明个点都是次多项式的零点，故可设 其中，为待定系数。由条件立即可得 （1.2） 故 （1.3） 由上式可以写出个次插值多项式。我们称它们为在个节点上的次基本插值多项式或次插值基函数。 利用插值基函数立即可以写出满足插值条件的次插值多项式 （1.4） 根据条件（1.1），容易验证上面多项式在节点处的值为，因此，它就是待求的次插值多项式。 形如式（1.4）的插值多项式就是拉格朗日插值多项式，记为，即 （1.5） 为了便于上机，常将拉格朗日插值多项式（1.5）改写成： （1.6） 下图给出了利用式（1.6）计算x处函数值的程序流程图： y←0 输入xi,yi(i=1,2...,n)及n,x y←y+P*yk 输出x,y k=1,2,...,n P←1 j=1,2,...,n 是 j=k? P←P*(x-xj)/(xk-xj) 否 根据流程图用matlab语言编写的函数为： function y=lagrange(x0,y0,x) n=length(x0);m=length(x); for i=1:m s=0.0; for k=1:n p=1.0; for j=1:n if j~=k p=p*(x(i)-x0(j))/(x0(k)-x0(j)); end end s=p*y0(k)+s; end y(i)=s; end （二）分段线性插值法 由于高次的插值多项式有不收敛现象,有时会出现较大的误差,不能有效的逼近被插函数,所以人们提出了用分段的低次多项式逼近被插函数,这就是分段插值方法。常见的有分段线性插值和分段二次插值，本文使用的是分段线性插值法。 当给定了个点上的函数值后，若要计算点处函数值的近似值。可先选取两个节点与，使，然后在小区间上座线性插值，即得： （2.1） 相应的程序流程图如下： 输入xi ,yi(i=1,2,...,n)及n,x j=1,2,...,n-1 输出x,P1(x) 按公式（2.1）计算P1(x) x∈[xj,xj+1]? 是 否 根据流程图用matlab语言编写的函数为： function y=seg_linear(x0,y0,x) n = length(x0);m=length(x); for i=1:m for j=1:n-1 if x(i)=x0(j) if x(i)=x0(j+1) y(i)=y0(j)*(x(i)-x0(j+1))/(x0(j)-x0(j+1))+y0(j+1)*(x(i)-x0(j))/(x0(j+1)-x0(j)); end end end end （三）牛顿插值法 设有函数，,为一系列互不相等的点，称为关于点的一阶差商。一般的称 （3.1） 为关于点的k阶差商。 则 其中 （3.2） （3.3） 显然，是满足插值条件的至多n次的多项式。可得。 因而它是的n次的插值多项式。我们称为牛顿插值多项式。 在实际计算中，经常利用由式（3.1）构造出的差商表3.1计算差商，即由表3.1中加下划横线的差商值直接构造插值多项式（3.2） 表3.1 一阶差商 二阶差商 三阶差商 四阶差商 y←y+F(1,1) 输出F,y 输入xi,yi(i=1,2,...,n)及n,x j=2,3,...,n i=j,j+1,...,n F(i,j)