计算方法—插值法

2020/5/19,1,第二章插值法,（Interpolation）,2.1引言,2.2拉格朗日插值,2.3均差与牛顿插值公式,2.5分段低次插值,2.6三次样条插值,2.4埃尔米特插值,Chapter2插值法,2020/5/19,2,Chapter2插值法,表示两个变量x,y内在关系一般由函数式y=f(x)表达。但在实际问题中的函数是多种多样的,有下面两种情况：,（1）由实验观测而得的一组离散数据(函数表)，显然这种函数关系式y=f(x)存在且连续，但未知。,（2）函数解析表达式已知，但计算复杂，不便使用。通常也列函数表，如y=sin(x),y=lg(x),2.1引言,2020/5/19,3,办法是：根据所给的y=f(x)的函数表，构造一个简单的连续函数P(X)近似替代f(x)。,Chapter2插值法,近似代替即逼近的方法有很多种：插值方法、最佳一致逼近、最佳平方逼近、曲线拟合。,由于问题的复杂性,直接研究函数f(x)可能很困难,但为了研究函数的变化规律,有时要求不在表上的函数值，怎么办？,？,简单连续函数P(x)指可用四则运算计算的函数:如有理函数(分式函数),多项式或分段多项式。,2020/5/19,4,Chapter2插值法,插值问题的数学提法：,已知函数y=f(x)在n+1个点x0,x1,xn上的函数值yi=f(xi)(i=0,1,n)，求一个简单函数y=P(x)，使其满足P(xi)=yi,（i=0,1,n）。即要求该简单函数曲线要经过y=f(x)上已知的这n+1个点(x0,y0),(x1,y1),(xn,yn),同时在其它xa,b上要估计误差R(x)=f(x)-P(x)。,2020/5/19,5,Chapter2插值法,重要术语,对于n+1个基点的插值问题，我们称：,f(x)为被插值函数；P(x)为插值函数；x0,x1,xn为插值基点或插值节点；P(xk)=f(xk),k=0,1,n为插值条件；a,b为插值区间。,注释：对于早期的插值问题来说，f(x)通常是已知的，比如对数函数，指数函数，三角函数等，这些问题现在已经不用插值法来计算了；对于现在的许多实际问题来说，我们并不知道f(x)的具体形式，所对应的函数值可能是由测量仪器或其他物理设备中直接读出来的，f(x)只是一个概念中的函数。,2020/5/19,6,Chapter2插值法,多项式插值,对于n+1个基点的插值问题，如果要求插值函数是次数不超过n的多项式，记为Pn(x)，则相应的问题就是多项式插值，并且把Pn(x)称为插值多项式。,实际上，我们所考虑的插值函数通常都是多项式函数或分段多项式函数。由于次数不超过n的多项式的一般形式为：,Pn(x)=a0+a1x+a2x2+anxn,所以只要确定了n+1个系数a0，a1，a2，an，我们便确定了一个插值多项式。,2020/5/19,7,Chapter2插值法,y,x,x0,x1,x2,xn-1,xn,y0,y1,y2,多项式插值的几何意义：,多项式Pn(x)，其几何曲线过给定的y=f(x)的n+1个点(xi,yi)i=0,1,2,n。,yn,yn-1,2020/5/19,8,Chapter2插值法,Lagrange插值,2020/5/19,9,Chapter2插值法,2-1插值多项式的唯一性,已知y=f(x)的函数表，,且xi(i=0,1,n)两两互异，xia,b。,求次数不超过n的多项式,使得Pn(xi)=yi,i=0,1,2,n,此问题中Pn(x)是否存在？存在是否唯一？如何求？,显然关键是确定多项式Pn(x)的系数a0,a1,an。,2020/5/19,10,Chapter2插值法,2-1插值多项式的唯一性,定理：在n+1个互异的插值节点x0,x1,xn上满足插值条件Pn(xi)=yi,i=0,1,2,n的次数不超过n的代数多项式Pn(x)存在且唯一。,分析：为求,主要考虑插值条件,2020/5/19,11,Chapter2插值法,2-1插值多项式的唯一性,证明：由插值条件，有,其系数矩阵的行列式为,关于未知量a0,a1,an的非齐次线性方程组,2020/5/19,12,Chapter2插值法,例给定f(x)的函数表，求f(x)的次数不超过3的插值多项式。,解：设,则，,解方程组得a0=10,a1=5,a2=-10,a3=2,即P3(x)=10+5x-10 x2+2x3,当n=20,在109次/秒的计算机上计算需几万年！,！,2020/5/19,13,Chapter2插值法,2-2线性插值与抛物插值,问题的提法：,已知函数y=f(x)的函数表求次数不超过1的多项式L1(x)=a0+a1x满足插值条件L1(xk)=yk,L1(xk+1)=yk+1。,分析:过两点(xk,yk),(xk+1,yk+1)作直线y=L1(x)线性插值,解:由点斜式方程,称为线性插值基函数,而L1(x)是它们的线性组合。,2020/5/19,14,Chapter2插值法,lg2.718L1(2.718)=0.43428,2020/5/19,15,Chapter2插值法,2-2线性插值与抛物插值,利用线性插值法对函数y=f(x)进行逼近时，即用直线y=L1(x)代替曲线y=f(x)。,显然当插值区间较大或曲线x0,x1凸凹变化大时，线性插值的误差很大。,为了减小这种误差，我们用简单的曲线(抛物线)去近似代替复杂曲线y=f(x)。二次多项式函数的曲线为抛物线，所以我们构造插值函数L2(x)，即n=2。,2020/5/19,16,Chapter2插值法,问题的提法：,已知y=f(x)的函数表，x0,x1,x2为互异节点，求一个次数不超过2的多项式L2(x)=a0+a1x+a2x2：L2(x0)=y0,L2(x1)=y1,L2(x2)=y2,几何意义:L2(x)为过三点(x0,y0),(x1,y1),(x2,y2)的抛物线。,方法：基函数法，构造基函数l0(x),l1(x),l2(x)(三个二次式)使L2(x)=y0l0(x)+y1l1(x)+y2l2(x)满足插值条件。,2020/5/19,17,Chapter2插值法,求二次多项式l0(x)：l0(x0)=1,l0(x1)=0,l0(x2)=0,l0(x)=C(x-x1)(x-x2)只须求C=?,由l0(x0)=1得C(x0-x1)(x0-x2)=1C=1/(x0-x1)(x0-x2),同理求得l1(x),l2(x),即抛物插值的插值基函数如下:,抛物插值问题的解:,2020/5/19,18,Chapter2插值法,2-3拉格朗日插值多项式,已知y=f(x)在两两互异节点x0,x1,xn的函数值y1,y2,yn,求n次多项式Ln(x)=a0+a1x+a2x2+anxn,满足插值条件Ln(xi)=yi.i=0,1,2,3,n。,基函数法：求n+1个n次多项式l0(x),l1(x),ln(x)使Ln(x)=y0l0(x)+y1l1(x)+ynln(x)。,Ln(x)须满足插值条件Ln(xi)=yii=0,1,2,3,n,即y0l0(xi)+y1l1(xi)+yili(xi)+ynln(xi)=yi,2020/5/19,19,Chapter2插值法,li(x0)=0,li(xi-1)=0,li(xi+1)=0,li(xn)=0,即li(x)有n个零点，x0,x1,xk-1,xk+1,xn。,求插值基函数li(x),与节点有关，而与f无关,2020/5/19,20,Chapter2插值法,于是，满足插值条件Ln(xi)=yi.i=0,1,2,3,n的插值多项式为：,上式即为拉格朗日（Lagrange）插值多项式。当n=1，或n=2时分别就是线形插值与抛物插值公式。,基函数的等价形式,2020/5/19,21,Chapter2插值法,2-4插值余项,函数y=f(x)与其Lagrange插值多项式Ln(x)：,(1)Ln(xi)=f(xi)=yi,i=0,1,2,n；,(2)而对于插值区间a,b内插值节点xi(i=1,2,n)以外的点x,一般Ln(x)f(x)，存在误差。,Def:对于一般的n+1个基点的多项式插值问题，设f(x)为被插值函数,Ln(x)为相应的插值多项式,记Rn(x)为f(x)与Ln(x)的差,即,Rn(x)=f(x)-Ln(x),则Rn(x)就是用Ln(x)近似替代f(x)的误差,我们称它为插值余项。,显然，由插值多项式的唯一性可以导出插值余项的唯一性。,2020/5/19,22,Chapter2插值法,利用Lagrange插值公式Ln(x)来计算，结果是否可靠，要看余项Rn(x)是否足够小。,Rn(x)=？,设ax0x1xnb，且满足条件fcna,b,f(n+1)在a,b内存在,考察插值误差，Rn(x)=f(x)-Ln(x)。,Rn(x)至少有个n+1根,把x看作是（任意）固定的点，作辅助函数,(t)有n+2个不同的根x0,xn,x,注意：此处是对t求导,2020/5/19,23,Chapter2插值法,定理：设ax0x1插值多项式Pn(x)的次数很高(高次插值),我们已经知道：f(x)在n+1个节点xi(i=0,1,2,n)上的n次插值多项式Pn(x)的余项,设想当节点数增多时会出现什么情况?,是否插值多项式Pn(x)的次数越高越好?,2020/5/19,64,Chapter2插值法,例,并作图比较。,定义在区间-5，5上，这是一个光滑函数，它的任意阶导数都存在。,分析：,龙格(Runge)现象,2020/5/19,65,Chapter2插值法,解：,龙格(Runge)现象,2020/5/19,66,%lagrangen.mfunctiony=lagrangen(x0,y0,x)n=length(x0);m=length(x);fori=1:mz=x(i);s=0;fork=1:nL=1;forj=1:nifj=kL=L*(z-x0(j)/(x0(k)-x0(j);endends=s+L*y0(k);endy(i)=s;endy;,Chapter2插值法,龙格(Runge)现象,2020/5/19,67,%Chazhibijiao.mx=-5:0.1:5;z=0*x;y=1./(1+x.2);plot(x,z,k,x,y,r)axis(-55-1.52);pause,holdonforn=2:2:10 x0=linspace(-5,5,n+1);y0=1./(1+x0.2);x=-5:0.1:5;y1=lagrangen(x0,y0,x);plot(x,y1),pauseendy2=1./(1+x0.2);y=interp1(x0,y2,x);plot(x,y,k),holdoffgtext(n=2),gtext(n=4),gtext(n=6)gtext(n=8),gtext(n=10)gtext(f(x)=1/(1+x2),Chapter2插值法,龙格(Runge)现象,2020/5/19,68,Chapter2插值法,不同次数的Lagrange插值多项式的比较图,2020/5/19,69,Chapter2插值法,结果表明,并不是插值多项式的次数越高,插值效果越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由Runge发现,故称为Runge现象.,从图中，可见，在靠近-5或5时，余项会随n值增大而增大；在0附近插值效果是好的，即余项较小；另一种现象是插值多项式随节点增多而振动更多。,龙格(Runge)现象,2020/5/19,70,上述现象和定理，告诉我们用高次插值多项式是不妥当的，从数值计算上可解释为高次插值多项式的计算会带来舍入误差的增大，从而引起计算失真。因此，实践上作插值时一般只用一次、二次最多用三次插值多项式。那么如何提高插值精度呢？采用分段插值是一种办法。,Chapter2插值法,这个任意阶可导的光滑函数之所以出现这种现象，跟它在复平面上有x=1是奇点有关。,2020/5/19,71,Chapter2插值法,随着插值节点数增加，插值多项式的次数也相应增加，而对于高次插值容易带来剧烈振荡，带来数值不稳定。为了既要增加插值节点，减小插值区间，以便更好的逼近被插值函数，又要不增加插值多项式的次数，以减小误差，我们可以采用分段插值的办法。,在区间a,b上取n=1个节点x0=a，x1，xn=b，对应的函数值f(x)=y0，f(x1)=y1，f(xn)=yn，构造函数Ih(x)满足：,（1）插值条件：Ih(xk)=yk,(k=0,1,n);（2）在每个区间xk,xk+1(k=0,1,n-1)上，Ih(x)是低次多项式；（3）在整个区间x0,xn上Ih(x)连续。,Ih(x)称为分段低次插值函数。,2020/5/19,72,Chapter2插值法,分段线性插值,所谓分段线性插值就是通过插值点，用折线段连接起来逼近函数f(x)。设已知节点a=x0x1xn=b上的函数值f0,fn，记hk=xk+1-xk，h=maxhk,求一折线函数Ih(x)，满足：,（1）插值条件：Ih(xk)=yk,(k=0,1,n);（2）在每个区间xk,xk+1(k=0,1,n-1)上，Ih(x)是线性函数；（3）在整个区间x0,xn上Ih(x)连续。,几何上看，Ih(x)是由点(xi,fi)(i=0,1,n)连成的一条折线，在整个区间连续，在节点处1阶导数不连续。,2020/5/19,73,Chapter2插值法,由定义可得Ih(x)在每个小区间xk,xk+1上的表达式为:,在每个区间xk,xk+1(k=0,1,n-1)上，Ih(x)是线性函数；且I(xk)=fk，I(xk+1)=fk+1。,2020/5/19,74,Chapter2插值法,2020/5/19,75,Chapter2插值法,为了紧凑，也可通过分段插值基函数li(x)(i=0,1,2,n)的线性组合将分段线性插值函数表示为一个表达式。,每个插值结点上所对应的插值基函数li(x)应当满足：,(1)li(x)是分段线性函数；,2020/5/19,76,Chapter2插值法,每个插值结点上所对应的插值基函数li(x)应当满足：,(3),2020/5/19,77,Chapter2插值法,分段线性插值基函数li(x)只在xi附近不为零，在其他地方均为零，这种性质称为局部非零性质。,在区间xk,xk+1上，只有lk(x),lk+1(x)是非零的，其它基函数均为零，即,因此：表达式,与表达式,是相同的。,2020/5/19,78,Chapter2插值法,-(1),-(2),显然,我们称由(1)(2)式构成的插值多项式为分段线性Lagrange插值多项式,2020/5/19,79,Chapter2插值法,内插,外插,外插,2020/5/19,80,Chapter2插值法,例:已知函数,在区间0,5上取等距插值节点（如下表），,并利用它求出的近似值。,解：在每个分段区间,上，,2020/5/19,81,Chapter2插值法,分段线性插值的误差估计,根据拉格朗日一次插值函数的余项,可以得到分段线性插值函数的插值误差估计。,定理：设f(x)在a,b上有二阶连续导数f(x)，且|f(x)|M2,记,h=max|xi+1-xi|,就有估计：,证明：,n次Lagrange插值多项式的余项为,2020/5/19,82,Chapter2插值法,分段线性插值的误差估计,2020/5/19,83,收敛性证明：,Chapter2插值法,当xxk,xk+1时,另一方面，这时,现在证明,考虑：,这里(h)是函数f(x)在区间a,b上的连续模，即对任意两点x，xa,b，只要,|xx|h，就有,称(h)为f(x)在a,b上的连续模，当f(x)Ca,b时，就有,2020/5/19,84,Chapter2插值法,由前式可知，当xa,b时有,收敛性证明：,因此，只要f(x)Ca,b，就有,在a,b上一致成立，故Ih(x)在a,b上一致收敛到f(x)。,2020/5/19,85,Chapter2插值法,例：设-1x1(1)将-1，110等份，用分段线性插值近似计算f(-0.96)。(2)将-1，1n等份，用分段线性插值近似计算,问如何选择步长h可使近似计算误差R10-4?解：(1)插值节点为xi=-1+i/5(i=0,1,10),h=1/5因为-0.96-1,-0.8,取此区间为线性插值区间，其上的插值函数为,所以f(-0.96)Ih(-0.96)=0.04253,2020/5/19,86,Chapter2插值法,(2)插值节点为xi=-1+ih(i=0,1,n),h=(b-a)/n=2/n由分段线性插值的余项估计：|f(x)-Ih(x)|=|R(x)|M2h2/8,2020/5/19,87,Chapter2插值法,Spline,样条插值,2020/5/19,88,Chapter2插值法,什么是样条:是指飞机或轮船等的制造过程中为描绘出光滑的外形曲线(放样)所用的工具。它是有弹性的细长木条,绘图时,用细木条连接相近的几个节点,然后再进行拼接,连接全部节点,使之成为一条光滑曲线,且在节点处具有连续的曲率。,当曲线上每一点处都具有切线，且切线随切点的移动而连续转动，这样的曲线称为光滑曲线。,2020/5/19,89,Chapter2插值法,1946年,Schoenberg将样条引入数学,即所谓的样条函数。样条函数就是对这样的曲线进行数学模拟得到的。它除了要求给出各个结点处的函数值外,只需提供两个边界点处导数信息,便可满足对光滑性的不同要求。,样条本质上是一段一段的三次多项式拼合而成的曲线，在拼接处,不仅函数是连续的,且一阶和二阶导数也是连续的。,2020/5/19,90,Chapter2插值法,三次样条的应用,2020/5/19,91,Chapter2插值法,三次样条插值函数,定义设给定区间a,b上n+1个点a=x0x1xn=b，以及相应的函数值yi=f(xi),i=0,1,n。,如果函数S(x)满足:,(1)在每个子区间xk,xk+1(k=0,1,n-1)上，S(x)是不超过三次的多项式，且S(xi)=yi,i=0,1,n；,则称S(x)是f(x)在基点x0,x1,x2,xn上的三次样条插值函数.,称xoy平面上的点(xi,yi)(i=0,1,n)为样点。,2020/5/19,92,Chapter2插值法,2020/5/19,93,Chapter2插值法,2020/5/19,94,Chapter2插值法,例给定区间0,3上3个点的函数值f(0)=0，f(1)=2，f(3)=4,试求数a,b,c,d,使函数S(x)为给定点上的三次样条插值函数。,解设,根据定义，由,得d=0，故,则,由,由,由,由,求得,2020/5/19,95,Chapter2插值法,一般使用第一、二类边界条件,常用第二类边界条件。,2020/5/19,96,Chapter2插值法,加上任何一类边界条件(至少两个)后,或,但是求解4n个方程的线性方程组，其计算量太大。,2020/5/19,97,Chapter2插值法,三次样条插值函数的求法三转角方程,参见教材P29页(7.5)式,得,2020/5/19,98,Chapter2插值法,2020/5/19,99,Chapter2插值法,2020/5/19,100,Chapter2插值法,并化简得方程:,2020/5/19,101,Chapter2插值法,当i取遍1,2,n-1时,便得到了含(n-1)个