教学课件：第三章-插值与逼近.ppt

《教学课件：第三章-插值与逼近.ppt》由会员分享，可在线阅读，更多相关《教学课件：第三章-插值与逼近.ppt（52页珍藏版）》请在三一办公上搜索。

1、1,第三章 插值与逼近,科学研究和工程计算中的问题：（1）难以得到解析式，但是可以得到自变量与相应函数值的数据（实验等方法得到）；（2）有时候虽有解析式，但是使用不便（计算机使用）；解决的方法：（1）最简单实用的方法就是插值，是一类的函数近似问题 本章主要介绍有关插值法的一些基本概念及多项式插值的基础理论和几个常用的插值方法：Lagrange插值、分段线性插值、Newton插值、Hermite插值。（2）数据拟合，函数近似问题，在本章的最后介绍曲线拟合方法最小二乘法。,2,第三章 插值与逼近,本章主要内容：第一节 引言第二节 拉格朗日插值第三节 差商、差分与牛顿插值第四节 逐次线性插值第五节

2、埃尔米特插值第六节 高次插值的缺点和分段低次插值第七节 三次样条插值第八节 曲线拟合,3,第一节 引言,一、问题的提出1、插值法 构造某个函数做为不便于处理或计算的函数的近似，然后通过处理简单函数获得不便处理或计算的函数的近似结果，当要求近似函数取给定的离散数据时，这种处理方法称为插值法。2、插值问题及相关概念 设函数y=f(x)在区间a,b上给出一系列的函数值：yi=f(xi),i=0,1,2,n或者给出一张函数表：其中：,4,第一节 引言,选择一个函数p(x)，满足：P（xi）yi，i=0,1,。,n并用p(x)代替f(x)，做为其近似表达式，称这种问题为插值问题。满足关系式的p(x)称为

3、f(x)的插值函数，而f(x)称为被插值函数，点x1,x2,xn称为插值节点，区间a，b称插值区间这样在给定点x计算插值函数p(x)的值作为被插值函数f(x)的近似值，这一过程称为插值，点x称为插值点。,条件,5,第一节 引言,插值的任务就是由已知的观测点,为物理量(未知量)建立一个简单的、连续的解析模型，以便能根据该模型推测该物理量在非观测点处的特性。3、插值的类型由于插值函数p(x)的选择不同，就产生不同类型的插值。若p(x)为代数多项式就称为代数插值若p(x)为三角多项式就称为三角多项式插值若p(x)为有理函数就称为有理函数插值选择不同的插值函数，近似的效果也不同。而由于代数多项式的结构

4、简单，数值计算及理论分析较为方便，获得广泛应用。本章讨论的就是代数插值多项式,6,第一节 引言,二、代数插值多项式的存在唯一性,且满足,-(1),7,第一节 引言,上述方程组的系数行列式为n+1阶Vandermond行列式,由于xi互异，所以(2)右端不为零，从而方程组的解 a0,a1,an 存在且唯一，（Cramer法则）,-(2),8,第一节 引言,则满足插值条件,的插值多项式,存在且唯一,虽然线性方程组(1)推出的插值多项式存在且唯一但通过解线性方程组(1)求插值多项式却不是好方法但遗憾的是方程组(1)是病态方程组,当阶数n越高时，病态越重。为此从另一途径来寻求获得Pn(x)的方法-La

5、grange插值和Newton插值。,定理1.,举例：p36，例31,9,第二节 拉格朗日插值,一、线性插值与抛物插值1、线性插值线性插值，n=1。这时插值问题就是求一次多项式：P1(x)=b+ax 使它满足条件：P1(x0)=y0,P1(x1)=y1 通过解方程组：ax0+b=y0 ax1+b=y1用直线近似地代替函数f(x)，则称这种插值为线性插值。可以解得直线的方程为：,10,11,第二节 拉格朗日插值,对该直线的方程进行变换可以得到：令:l0和l1具有的特点：l0(x0)=1,l0(x1)=0,l1(x0)=0,l1(x1)=1.即总结为：这样直线的方程可以表示为：l0(x),l1(x

6、)称为以x0,x1 为节点的插值基函数。,12,第二节 拉格朗日插值,线性插值仅仅用两个节点上的信息，精确度较差。为了提高精确度，我们进一步考察以下三点的插值问题。2、抛物插值 作二次多项式 P2(x)=a0+a1x+a2x2（1）使其满足条件：P2(x0)=y0,P2(x1)=y1,P2(x2)=y2 同样可以解一个三元一次线性方程组即可解得系数a0,a1,a2，即可以得到二次多项式的表达式。,13,第二节 拉格朗日插值,（2）同样也可以表示成基函数的形式其中l0(x)，l1(x)，l2(x)为二次多项式，只与x0，x1，x2有关，而且满足：如何求得l0(x)，l1(x)，l2(x)的表达式

7、？由l0(x0)=1,l0(x1)=0,l0(x2)=0,l1(x0)=0,l1(x1)=1,l1(x2)=0,l2(x0)=0,l2(x1)=0,l2(x2)=1.这样 l0(x)含有 x-x1,x-x2 两个因子，令 l0(x)=(x-x1)(x-x2),利用 l0(x0)=1 确定其中的系数，得：,14,第二节 拉格朗日插值,同样的方法可以得到：则可以得到抛物插值的表达式：其中l0(x),l1(x),l2(x)称为以 x0,x1,x2为节点的插值基函数。,15,第二节 拉格朗日插值,举例：P39例32：例33：,16,第二节 拉格朗日插值,二、拉格朗日插值多项式 将n=1和n=2的线性插

8、值和抛物插值推广到一般情况，即n次插值，也就是拉格朗日插值。对于有n+1个插值点时，插值函数可以表达成一个n次多项式：Pn(x)=a0+a1x+a2x2+anxn,其满足：Pn(x0)=y0,Pn(x1)=y1,.,Pn(xn)=yn同样该n次多项式也可以表示为：其中l0(x),l1(x),，ln(x)为以 x0,x1,xn为节点的插值基函数,17,第二节 拉格朗日插值,它们同样满足：则可以计算出：则，拉格朗日插值函数可以表示为：,拉格朗日插值多项式,18,第二节 拉格朗日插值,三、插值余项（1）用插值多项式表示函数，则必然存在误差若在区间a,b上，用Ln(x)表示f(x)，则其截断误差Rn(

9、x)=f(x)-Ln(x)，也称为插值多项式的余项，插值余项为多少？（2）定理：设n(x)是过点x0，x1，x2，xn的 n 次插值多项式，f(n)(x)在区间a,b上连续，f(n+1)(x)在a，b上存在，则对任意给定的xa，b，总存在一点（a，b）（依赖于x）使 其中，f(n+1)()是f(x)的n+1阶导数在 的值。,19,第二节 拉格朗日插值,（3）证明：回顾罗尔定理：,推广：若,使得,罗尔定理:若 在 连续，在 充分光滑，,20,第二节 拉格朗日插值,证明：记 Rn(x)=f(x)-n(x)重要，后面还会用到这种方法显然 Rn(xi)=0,i=0,1,n,故可设 Rn(x)=K(x)

10、n+1(x)现在a,b上任意固定一点x,引进辅助函数 g(t)=f(t)-n(t)-K(x)n+1(t),则由n(xi)=0(i=0,1,2,n)及g(x)=0，知在 t=x0,x1,xn,x诸点处皆等于零,即g(t)在a,b中有n+2个零点,g(t)在a,b上具有n阶连续导数，在(a,b)内存在n+1阶导数，由Rolle定理知g(t)在a,b中有n+1个零点,如此反复，最后可推知g(n+1)(t)在a,b中至少有1个零点,设为，即有：g(n+1)()=0,a b同时因为n+1(t)是n+1次多项式，n+1(n+1)(t)=(n+1)!,又因为n(t)是次数为n的多项式,因此n(n+1)(t)

11、=0。则根据辅助函数式可以得到：,21,第二节 拉格朗日插值,则可以推出：代入Rn(x)=K(x)n+1(x),定理得证应当指出，余项表达式只有在 f(x)的高阶导数存在时才能应用。在（a，b）内的具体位置通常不可能给出，如果可以求出那么插值多项式Ln(x)逼近f(x)的截断误差是：,22,第二节 拉格朗日插值,讨论：（1）当n=1时候可得到线性插值的误差估计（2）当n2时候可得到二次插值的误差估计,23,第二节 拉格朗日插值,例1:已给sin0.32=0.314567,sin0.34=0.333487,sin0.36=0.352274,用线性插值及抛物插值计算 sin0.3367 的值并估计

12、截断误差。解：由题意取x0=0.32,y0=0.314567,x1=0.34,y1=0.333487,x2=0.36,y2=0.352274（1）用线性插值计算，取 x0=0.32 及 x1=0.34,由线性插值公式：,24,第二节 拉格朗日插值,其截断误差为：其中：因 f(x)=sinx，f/(x)=-sinx，可取于是R1(0.3367)=sin 0.3367 L1(0.3367)1/2*(0.3335)*(0.0167)*(0.0033)0.92105，（2）若取x1=0.34，x2=0.36为节点，则线性插值为：,25,第二节 拉格朗日插值,其截断误差为：其中：因 f(x)=sinx，

13、f/(x)=-sinx，可取于是R1(0.3367)=sin 0.3367 L1(0.3367)1/2*(0.3523)*(0.0023)*(0.0233)1.36105，（3）用抛物插值计算,26,第二节 拉格朗日插值,这个结果与六位有效数字的正弦函数表完全一样，这说明查表时用二次插值精度已相当高了。其截断误差得其中于是,27,第二节 拉格朗日插值,例2:已测得某地大气压强随高度变化的一组数据解：设x为高度，y为大气压强的值，选取(1000,0.8515),(1500,0.7984),(2000,0.7485)三点构造二次插值多项式：,高度(m)0 100 300 1000 1500 200

14、0 压强(kgf/m2)0.9689 0.9322 0.8969 0.8515 0.7984 0.7485 试用二次插值法求1200米处的压强值.,L2(1200)=0.8515(1200-1500)(1200-2000)/(1000-1500)(1000-2000)+0.7984(1200-1000)(1200-2000)/(1500-1000)(1500-2000)+0.7485(1200-1000)(1200-1500)/(2000-1000)(2000-1500)=300*800*0.8515/500/1000+200*800*0.7984/500/500-200*300*0.7485

15、/500/1000=0.82980所以 y(1200)p2(1200)=0.82980(kgf/m2),28,第三节 差商、差分与牛顿插值,拉格朗日插值多项式形式对称，计算较方便但由于L(x)依赖于全部基点，若算出所有L(x)后又需要增加基点，则必须重新计算,为了克服这个缺点，我们引进牛顿插值多项式。一、差商与牛顿插值多项式1、差商定义（1）设有函数f(x)以及自变量的一系列互不相等的x0 x1,xn（即在i j时，x i xj）的值 f(xi),称 为f(x)在点xi,xj处的一阶差商，并记作f xi,xj,29,第三节 差商、差分与牛顿插值,（2）二阶差商 称：为f(x)在点xi,xj,x

16、k处的二阶差商。（3）k阶差商 称：为f(x)在点x0,x1,xk处的k阶差商。（4）0阶差商,由差商定义可知：高阶差商是两个低一阶差商的差商。,30,第三节 差商、差分与牛顿插值,举例：根据差商定义计算,31,第三节 差商、差分与牛顿插值,2、差商具有如下性质(1)差商与函数值的关系为,32,第三节 差商、差分与牛顿插值,(2)差商与结点排列顺序无关(3)设f(x)在a,b上有n阶导数，且x0,x1,xn属于a,b，则存在使得：,33,第三节 差商、差分与牛顿插值,3、牛顿插值多项式设x0,x1,xn 为n+1个插值节点，根据差商定义有：f(x)=fx0+(x-x0)fx,x0 fx,x0=

17、fx0,x1+(x-x1)fx,x0,x1 fx,x0,x1=fx0,x1,x2+(x-x2)fx,x0,x1,x2.fx,x0,xn-2=fx0,xn-1+(x-xn-1)fx,x0,.,xn-1 fx,x0,xn-1=fx0,xn+(x-xn)fx,x0,.,xn将以上各式，由下而上逐步代入，得到f(x)=fx0+(x-x0)fx0,x1+(x-x0)(x-x1)fx0,x1,x2+(x-x0)(x-xn-1)fx0,xn+(x-x0)(x-xn-1)(x-xn)fx,x0,xn,(5),34,第三节 差商、差分与牛顿插值,记 Nn(x)=f(x0)+(x-x0)fx0,x1+(x-x0)

18、(x-x1)fx0,x1,x2+(x-x0)(x-xn-1)fx0,xn Rn(x)=(x-x0)(x-xn)fx,x0,xn=fx,x0,xnwn+1(x)则(5)可表示为 f(x)=Nn(x)+Rn(x)显然,Nn(x)是次数不超过n的多项式,且有 Rn(xi)=fx,x0,xnwn+1(xi)=0,i=0,1,n即 Nn(xi)=f(xi),i=0,1,n由此可知,如此构造的函数Nn(x)就是问题1(P35)的解,且 ci=fx0,xi,i=0,1,n,牛顿插值公式具有承袭性,(6),(7),35,第三节 差商、差分与牛顿插值,结论：公式(6)称为函数f(x)在节点x0,xn上的n阶Ne

19、wton插值公式,公式(7)称为Newton插值公式余项，即截断误差。注意到余项表达式(7)只要求被插值函数f(x)在插值区间a,b上连续。由函数f(x)的插值多项式的惟一性，函数f(x)的Newton插值多项式与Lagrange插值多项式实为同一个多项式，即 Nn(x)Ln(x)两者不过是表现形式不同而已。由此有:若x a,b，则有 Rn(x)=fx,x0,xnwn+1(x)=,差商的性质3得证,36,第三节 差商、差分与牛顿插值,4、差商表运用Newton插值公式(6)进行计算时,先计算f(x)关于节点x0,xn的各阶差商.计算过程如下表所示：,xk f(xk)一阶差商 二阶差商 三阶差商

20、 n 阶差商,37,第三节 差商、差分与牛顿插值,举例：P45,例题3-6,解：先造差商表,X0X1X2X3x4,38,第三节 差商、差分与牛顿插值,由Newton公式得四次插值多项式为：,39,40,第三节 差商、差分与牛顿插值,例2 例:给定f(x)=lnx的数据表 xi 2.20 2.40 2.60 2.80 3.00 f(xi)0.78846 0.87547 0.95551 1.02962 1.09861（1）构造差商表（2）写出四次Newton插值多项式N4(x)解：（1）差商表,41,第三节 差商、差分与牛顿插值,（2）P4(x)=0.78846+0.43505(x-2.20）-0

21、.087375(x-2.20)(x-2.40)+0.0225(x-2.20)(x-2.40)(x-2.60)-0.00755(x-2.20)(x-2.40)(x-2.60)(x-2.80),42,第六节 高次插值的缺点和分段低次插值,一、高次插值多项式的缺点,例：在5,5上考察 的Ln(x)。取,P5(x),f(x),P10(x),n 越大，端点附近抖动越大，称为Runge 现象,43,第六节 高次插值的缺点和分段低次插值,二、分段低次插值1、分段线性插值,在每个区间 上，用1阶多项式(直线)逼近 f(x):,44,第六节 高次插值的缺点和分段低次插值,2、分段三次插值不少实际问题不但要求插值

22、函数P(x)在节点处的值与相应节点处的函数值相等，而且还要求在节点处的导数值也相等。Newton插值和Lagrange插值虽然构造比较简单，但都存在插值曲线在节点处有尖点，不光滑，插值多项式在节点处不可导等缺点,-(1),45,第六节 高次插值的缺点和分段低次插值,共2n+2个方程，可以解出2n+2个待定系数；因此P(x)的最高次数可以为2n+1次的多项式；两个节点就可以用21+1=3次多项式作为插值函数。,46,第六节 高次插值的缺点和分段低次插值,结论：称满足(1)或(2)式的插值问题为Hermite插值，称满足(1)或(2)式的插值多项式P(x)为Hermite插值多项式，记为Hk(x)

23、,k为多项式次数。一般，k次Hermite插值多项式Hk(x)的次数k如果太高会影响收敛性和稳定性（Runge现象），因此k不易太大，仍用分段插值。,47,第六节 高次插值的缺点和分段低次插值,3、两点三次Hermite插值多项式考虑只有两个节点的插值问题：设f(x)在节点x0,x1处的函数值为y0，y1，在节点x0,x1处的一阶导数值为两个节点最高可以用3次Hermite多项式作为插值函数,48,第六节 高次插值的缺点和分段低次插值,给出2点3次Hermite多项式插值函数：,49,第六节 高次插值的缺点和分段低次插值,4、推广分段两点三次Hermite插值多项式：,可构造两点三次Hermite插值多项式,50,第六节 高次插值的缺点和分段低次插值,其中,称,为分段三次Hermite插值多项式,51,第六节 高次插值的缺点和分段低次插值,例：,解:,52,第六节 高次插值的缺点和分段低次插值,作为多项式插值,三次已是较高的次数，次数再高就有可能发生Runge现象,因此，对有n+1节点的插值问题，我们可以使用分段两点三次Hermite插值,