《计算方法》第四章插值方法.ppt

《《计算方法》第四章插值方法.ppt》由会员分享，可在线阅读，更多相关《《计算方法》第四章插值方法.ppt（90页珍藏版）》请在三一办公上搜索。

1、计 算 方 法,华中科技大学数学与统计学院,第四章 插值方法,计算方法课程组,4 插值方法,4.1多项式插值问题的一般提法,4.2 拉格朗日(Lagrange)插值,4.3 差商与差分及其性质,4.4 牛顿插值公式,4.5 分段插值法,4.6曲线拟合的最小二乘法,4.0 引言,插值法是广泛应用于理论研究和生产实践的重要数值方法,它是用简单函数(特别是多项式或分段多项式)为各种离散数组建立连续模型；为各种非有理函数提供好的逼近方法。众所周知，反映自然规律的数量关系的函数有三种表示方法：,解析表达式,图象法,表格法,4.0 引言,许多数据都是用表格法给出的(如观测和实验而得到的函数数据表格)，可是

2、，从一个只提供离散的函数值去进行理论分析和进行设计，是极不方便的,甚至是不可能的。因此需要设法去寻找与已知函数值相符，并且形式简单的插值函数(或近似函数)。,另外一种情况是，函数表达式完全给定，但其形式不适宜计算机使用，因为计算机只能执行算术和逻辑操作，因此涉及连续变量问题的计算都需要经过离散化以后才能进行。如数值积分方法、数值微分方法、差分方程以及有限元法等，都必须直接或间接地应用到插值理论和方法。,4.1 多项式插值问题的一般提法,当精确函数 y=f(x)非常复杂或未知时，在一系列节点 x0 xn 处测得函数值 y0=f(x0),yn=f(xn)，由此构造一个简单易算的近似函数 p(x)f

3、(x)，满足条件:p(xi)=f(xi)(i=0,n)。这里的 p(x)称为f(x)的插值函数。,最常用的插值函数是?代数多项式、三角多项式、有理分式,插值函数 p(x)作为 f(x)的近似，可以选自不同类型的函数,如 p(x)为代数多项式、三角多项式、有理分式；其函数性态可以是光滑的、亦可以是分段光滑的。其中，代数多项式类的插值函数占有重要地位：,(a)结构简单、计算机容易处理、任何多项式的导数和积分也易确定，并且仍是多项式。,(b)著名的Weierstrass逼近定理(定义在闭区间上的任何连续函数 f(x),存在代数多项式p(x)一致逼近f(x),并达到所要求的精度)。,因此，我们主要考虑

4、代数多项式的插值问题。,x0,x1,xn 插值节点,函数 P(x)称为函数 y=f(x)的插值函数，区间 a,b 称为插值区间。,例题:,已知函数 f(x)有如下数据:,求 f(x)的插值多项式 p(x)，并求 f(x)在 x=0.5 处的近似值。,插值的几何意义,从几何上看，插值就是求一条曲线 使其通过给定的 个点，并且与已知曲线 有一定的近似度。,从几何上看,曲线 P(x)近似 f(x),插值方法的研究问题,曲线 P(x)近似 f(x),求 n 次多项式 使得:,条件：无重合节点，即,4.2 拉格朗日多项式/*Lagrange Polynomial*/,Vandermonde行列式,注意到

5、插值节点,两两相异，而,故方程组(1)有惟一解,于是满足插值条件的多项式存在且惟一。,(唯一性),Return,n=1,已知 x0,x1;y0,y1，求,使得,1,1,1,0,0,1,),(,),(,y1,x1,L,y0,x0,L,=,=,可见 L1(x)是过(x0,y0)和(x1,y1)两点的直线。,4.2 拉格朗日多项式/*Lagrange Polynomial*/,线性插值基函数,1.构造线性插值基函数的方法:,线性插值与其基函数示意图,显然,是过、三点的一条抛物线。,已知,求，,n=2,使得,显然,是过、三点的一条抛物线。,已知,求，,n=2,使得,抛物线插值基函数,于是,抛物线基函数

6、,希望找到 li(x)，i=0,n 使得 li(xj)=ij；然后令,，则显然有 Pn(xi)=yi。,每个 li 有 n 个根 x0,xi,xn,，k=0,1,n.,k=0,1,n.,由 得:,设 函数表 则满足插值条件的多项式,（Lagrange）插值多项式,其中,.,以下的问题：如何分析插值的余项？,(1)先求插值基函数.(2)构造插值多项式.,构造插值多项式的方法：,已知连续函数 f(x)的函数表如下：,求方程 f(x)=0 在(-1,2)内的近似根。,例题,解：利用Lagrange插值法有,取初值x=0.5，利用牛顿法求解可得 f(x)在(-1,2)内的近似根为0.67433。,解方

7、程,已知连续函数f(x)的函数表如下：,求方程 f(x)=0 在(-1,2)内的近似根。,例题,，且 f 满足条件,Lagrange插值法插值余项,设节点,在a,b内存在,考察截断误差:,Lagrange插值法的插值余项,Lagrange插值法的插值余项,证明：由已知条件得到：,于是有：,其中 是与 x 有关的待定函数。,故,处均为零，,在,上有n+2个个零点，根据 Roll 定理,在 的每两个零点间至少有一个零点，故在 内至少有 一 个零点，对 再用Roll 定理，可知 在 内至少有 n 个零点，依此类推，在 内至少有一个零点，记为,使得:,由于 是不能确定，因此我们并不能确定误差的大小但如

8、能求出，那么用 逼近 的截断误差限是：当 时，当 时,当 f(x)为任一个次数 n 的多项式时，,可知，即插值多项式对于次数 n 的多项式是精确的。,注意,给定 xi=i+1,i=0,1,2,3,4,5.下面哪个是 l2(x)的图像？,问题,算例1,Lagrange插值法,已知，用线性插值及抛物线插值计算 的值并估计截断误差。,算例1,Lagrange插值法,已知，用线性插值及抛物线插值计算 的值并估计截断误差。,线性插值时取,解:,其截断误差为：其中,因为可取于是：,用抛物线插值时，取所有节点，得到,余项讨论：其中：,算例2,Lagrange插值法,利用 100，121 的开方计算.,由于:

9、,解:,利用Lagrange插值法有,于是,的精确值为 10.72380529,因此,近似值 10.71428 有3 位有效数字.,Return,4.3 差商与差分,Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x)都需重新算过。,由线性代数的知识可知：任何一个n次多项式都可以表示成,共 n+1 个线性无关的多项式的线性组合。,那么，是否可以将这 n+1 个多项式作为插值基函数呢？,设插值多项式P(x)具有如下形式：,再继续下去,待定系数的形式将更复杂,为此引入 差商和差分的概念.,P(x)应满足插值条件：,有：,4.3.1 差商的概念,从零阶差商出发，归纳地定义各阶

10、差商:,称 为函数 关于点 的一阶差商.,一般地，关于 的 k 阶差商:,记函数 在 的值，称 为 关于 的零阶差商。,一般地，关于 的 n 阶差商:,n 阶差商的概念,差商的基本性质,性质1：差商可表示为函数值的线性组合，即：性质2：差商关于所含节点是对称的，即：,可用归纳法证明,差商的基本性质,性质3：性质4：设 在 存在 n 阶导数，且 则，使得:,差商的计算-差商表,已知,计算三阶差商,解：列表计算,算例,4.3.2 差分,在前面的讨论中，节点是任意分布的，但实际上经常遇到等距节点的情况，这时插值公式可以得到简化，为此，我们先介绍差分的概念。设函数 在等距节点上的值 为已知，这里 为常

11、数，称为步长。,下面来讨论差分的定义。,差分的定义,记号分别称为 在 处以 为步长的 向前差分、向后差分、中心差分符号、分别称为向前差分算子、向后差分算子、中心差分算子.,高阶差分,用一阶差分可以定义二阶差分一般地可定义 m 阶差分为：中心差分定义为:以此类推。,不变算子 I、移位算子 E,定义从而可得：于是得到：同理，由于：得到：由于：得到：由差分的定义及不变算子和移位算子有如下性质:,差分的性质,性质1：各阶差分均可用函数值表示，如：性质2：某点的函数可用各阶差分来表示：,性质3：差商与差分有如下关系：性质4：差分与导数有如下关系：,差分的计算,Return,4.4 牛顿插值公式,根据差商

12、的定义，把 看成 上的一点，可得：,4.4 牛顿插值公式,根据差商的定义，把 看成 上的一点，可得：,把后一式代入前一式,其中 显然 满足插值条件，且次数不超过,它就是插值多项式，其系数为：我们称 为牛顿插值多项式.,从表中可以看到4 阶差商几乎为0，故取4次插值多项式即可，于是：,解：列表计算,已知 的函数表，求4 次牛顿插值多项式,并求,算例,解：列表计算,已知 的函数表，求4 次牛顿插值多项式,并求,算例,截断误差为：,和 均是 n 次多项式,且均满足插值条件:由多项式的唯一性,因而,两个公式的余项是相等的,即 当插值多项式从 n-1 次增加到 n 次时,拉格朗日型插值必须重新计算所有的

13、基本插值多项式;而对于牛顿型插值,只需用表格再计算一个 n 阶差商,然后加上一项即可。,牛顿插值公式和Lagrange插值公式比较,Return,4.5 分段插值公式,在区间 a,b 上用插值多项式 P 逼近函数 f 时，f 和P 在每个节点上的差异(理论上)应该为零。自然，我们期望在一切中间点上也能很好地逼近 f，并且当插值点增加时这种逼近效果应该越来越好。但上述的期望不可能实现的。当认识到这一点时，在数学界曾引起强烈的震动。,20 世纪初，Runge就给出了一个等距节点插值多项式 不收敛到 的例子。,设函数，在该区间 上取 个等距节点,构造 的 次 拉格朗日插值多项式为,其matlab的l

14、agrange.m文件及相关图形如下.,Runge 现象,%lagrange.mfunction y=lagrange(x0,y0,x)n=length(x0);m=length(x);for i=1:m z=x(i);s=0;for k=1:n L=1;for j=1:n if j=k L=L*(z-x0(j)/(x0(k)-x0(j);end end s=s+L*y0(k);end y(i)=s;endy;,Lagrange插值多项式求插值的Matlab程序.,%Compare_Runge.mx=-5:0.1:5;z=0*x;y=1./(1+x.2);plot(x,z,k,x,y,r)ax

15、is(-5 5-1.5 2);pause,hold onfor n=2:2:20 x0=linspace(-5,5,n+1);y0=1./(1+x0.2);x=-5:0.1:5;y1=lagrange(x0,y0,x);plot(x,y1),pauseendy2=1./(1+x0.2);y=interp1(x0,y2,x);plot(x,y,k),hold offgtext(n=2),gtext(n=4),gtext(n=6)gtext(n=8),gtext(n=10)gtext(f(x)=1/(1+x2),比较不同的插值多项式次数对插值的影响,不同次数的Lagrange插值多项式的比较图,R

16、unge现象,令，则，下表列出了 和 的值。,结果表明,随着 的增加，的绝对值几乎成倍地增加，这说明当 时 在 上不收敛。Runge证明了，存在一个常数,使得当 时，;而当 时 发散。说明:并不是插值多项式的次数越高,插值效果越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由Runge发现,故称为Runge现象.,分段线性插值特别简单，从几何上看，就是用折线逼近曲线。分段线性插值的数学定义 设 是区间 上的函数，在节点 上的函数值为，求一分段折线函数 满足：（1）（2）在 上，是一次多项式。（3）则称 为 的分段线性插值函数。,4.5.1 分段线性插值,易知,P(x)是个折线函数，

17、在每个区间,上,有,在 a,b 上是连续的，但其一阶导数是不连续的.,当 时,当 时,4.5.1 分段线性插值的基函数,当 时,显然 是 的线性组合：在区间 上的值为：,，,算例,解:在每个分段区间,于是，,实际值:,当n=7 时，P(4.5)=0.04762270321996;当n=10时，P(4.5)=0.04705882352941由此可见，对于光滑性要求不高的插值问题，分段线性插值的效果非常好！计算也简单!,埃尔米特(Hermite)插值,拉格朗日和牛顿均只保证函数插值；实际问题有时需要导数也插值；满足这种需要的插值称为埃尔米特插值.,埃尔米特插值的一般提法为：设函数在节点 的函数值与

18、导数值为：其中 是正整数，寻求一个次数尽可能低的多项式，满足：,埃尔米特插值的一般提法,以如下数据构建埃尔米特插值,埃尔米特插值,算例,以如下数据构建埃尔米特插值,埃尔米特插值,算例,共有 个条件，可唯一确定一个次数不超过 的多项式，其形式为：目标：求出所有的,方法：基函数法.,这样 可表示为：,显然有：,现在求 及，令其中从而有：由此得：，故：，,由 的表达式可得：于是得到：同理可得,解：,n=1,分别利用x0,x1 以及 x1,x2 计算,利用,这里,而,sin 50=0.7660444,外推/*extrapolation*/的实际误差 0.01001,利用,内插/*interpolati

19、on*/的实际误差 0.00596,内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。,n=2,sin 50=0.7660444,2次插值的实际误差 0.00061,高次插值通常优于低次插值,Return,巴尔末(，1825-1898),特殊爱好:数字游戏,职 业:数学教师，瑞士某女子中学，,兼巴塞尔大学无薪讲师,“我能用公式把任意4个数字有规律地联系起来”,4 Why?,信息量?,道家:1生2，2生3，3生万物,4 万物？全部信息量?!,4 条谱线的波长数据,实验:氢光谱谱线的波长数据,巴尔末公式:,艰苦努力+天才,引子,1884年,4.6 曲线拟合的最小二乘法,物理实验,

20、实验数据,经验公式,天才,数学:一般方法？,引子(续）,问题,已知:,求:,特点,实验数据,n 1,实验值 yi 有误差，个别点可能误差还比较大。,方法:,多项式插值,点点通过,高次插值效果不好,?,启发,手工!,实例,某种纤维的强度 y 与 其拉伸倍数 x 的关系,实验数据:24个纤维样品,实例,x,y,坐标纸 后勤集团印制,1981,1.描点,手工方法:,2.画直线,3.求出 a0,a1,直线应该与所有点靠得比较近,或者说:所有点应该尽量靠近直线,实例(续1),注意:,xi,数学方法:,所有点应该尽量靠近直线,xi 点误差：,(a0+a1 xi)-yi,=,实例(续2),i=1,2,n,尽

21、量小,误差向量,向量大小:,残差,范数,min,min,min,实例(续3),F(a0,a1),=,min,即:求 a0,a1,使误差平方和取最小值!,二元函数求极值问题,解出 a0,a1,最小二乘解,实例(续4),实例求解:,y=0.1505+0.8587 x,即为最小二乘解,平方误差为,一般地:,一般,已知:,求:,y=a0+a1 x+a2 x2+am xm=,m次多项式,多项式拟合的最小二乘法,使,F(a0,a1,am),=,min,取极小。,即,类似地 m+1 元函数求极值,一般(续),k=0,1,m,得,即,解出 a0,a1,am,得:,y=a0+a1 x+a2 x2+am xm,法方程组,例1,例1,用最小二乘法求一个形如y=a+bx2的经验公式，使与下列数据相拟合:,a=0.972577,b=0.050035,y=0.972577+0.050035x2,拟合曲线为非线性模型,Return,