计算方法-插值与拟合.ppt

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

1、考试地点：建环151-2：1F-319安全151：1F-214油159:1F-313考试时间：第16周周3第4大节15:25-16:55唯一有效证件学生证，无证不能参加考试第16周建环151-2的实验课调至第16周周3第2大节1C206,第4章 插值与拟合,已经测得在某处海洋不同深度处的水温如下：深度（M）466 741 950 1422 1634水温（oC）7.04 4.28 3.40 2.54 2.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米）处的水温,设已知某个函数关系y=f(x)在某些离散点处的函数值：,插值,拟合,根据这些已知数据来构造函数y=f(x)

2、的一个简单的近似函数要求近似函数经过所有已知的数据点,根据已知数据点所反映的趋势，构造一个近似的函数表达式，不要求经过所有的点,插值与拟合的区别,求x=t点处的函数值f(t),插值与拟合的区别,第4章 插值与拟合,4.1 插值法概述,设已知某个函数关系y=f(x)在某些离散点上的函数值：,插值问题：,根据这些已知数据来构造函数y=f(x)的一种简单的近似函数表达式，要求近似函数经过所有已知的数据点,(4.1),求x=t点处的函数值f(t),拟合问题：,根据数据点所反映的趋势，求近似的函数表达式，不要求经过所有的点,第4章 插值与拟合,解决的问题：求近似函数以及这个函数在某点的近似值,我们的选择

3、：代数插值求一个多项式,解决问题的原则：已知的点都在曲线上,4.1插值法概述,选取多项式 Pn(x)，使得,（4.2）,作为 f(x)的近似函数表达式。,满足关系（4.2）的函数Pn(x)为f(x)的一个插值函数，,x0,x1,xn 为插值节点，关系（4.2）为插值条件。,设 x0 x1 xn,记 a=x0,b=xn，则 a,b 为插值区间。,代数插值,代数插值的唯一性,由n+1个互异节点构造一个次数不超过n的多项式是唯一的。,插值多项式存在唯一性,设所要构造的插值多项式为：,由插值条件,得到如下线性代数方程组：,插值多项式的存在唯一性：由n+1个互异节点构造的n次插值多项式是唯一的。,此方程

4、组的系数行列式为,范得蒙行列式！,D 0，,因此，Pn(x)由a0,a1,an唯一确定。,多项式是唯一存在的。,插值多项式的唯一性,注意：当由n+1个节点构造的多项式次数超过n时，插值多项式将会有无穷多个。,4.2 线性插值和二次插值,1线性插值,x0,x1,(x0,y0),(x1,y1),P1(x),y=f(x),可见 P1(x)是过(x0,y0)和(x1,y1)两点的直线。,线性插值的两种形式,于是P1(x)可以表示为插值基函数的线性组合,x0,x1,x2,p2(x)f(x),f(x),2二次（抛物）插值,因过三点的二次曲线为抛物线，故称为抛物插值。,Lagrange二次插值多项式的表示形

5、式,设连续函数y=f（x）在a,b上对给定n+1个互异结点：,x0,x1,xn,分别取函数值,y0,y1,yn,其中 yi=f(xi)i=0,1,2,n,试构造一个次数不超过n的插值多项式,使之满足条件,i=0,1,2,n,4.3 拉格朗日插值,求n次多项式lk(x)k=0,1,n,则,i=0,1,2,n,即Pn(x)满足插值条件（4.2）,根据lk(x)的表达式，xk以外所有的结点都是lk(x)的根，,1.构造插值基函数,又由lk(xk)=1，得：,因此令,从而得n 阶拉格朗日（Lagrange）插值公式：,例4.1 已知函数y=f(x)的观测数据如下表,试求其Lagrange插值多项式。,

6、解 由题知，共有3个结点，所以n=2，于是所求Lagrange插值多项式为：,例4.2 已知函数y=f(x)的观测数据如下表,试求其Lagrange插值多项式。,解 由题知，共有4个结点，所以n=3，于是所求Lagrange插值多项式为：,2.Lagrange全程插值算法,(1)输入插值节点(xi,yi)(i=0,1,2,n)及插值点t；(2)赋初值 s=0；(3)当i=0,1,2,n时 做 p=1 对j=0,1,2,n 当,时，,(4)输出s。,在(a,b)内存在,考察截断误差,推广：若,使得,罗尔定理:若 在 连续，若 充分光滑，,在a,b连续,3.插值余项,余项定理,证(1)当x=xi(

7、i=0,1,2,n)时，由插值条件知Ln(xi)=yi,，结论成立。,F(t)有n+2个零点，反复应用Rolle定理，得,注意：通常不能确定 x,而是估计,x(a,b)将 作为误差估计上限。,当 f(x)为任一个次数 n 的多项式时，,可知，即插值多项式对于次数 n 的多项式是精确的。,如何使余项减小？1、增加n能否保证Rn(x)减小？2、设法使 减小。使用内插，少用外推。,Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x)都需重新计算。,4.4 均差与牛顿基本插值公式,4.4 均差与牛顿基本插值公式,1均差（差商）的定义设连续函数y=f(x)在n+1个互异节点x0,

8、x1,x2,xn上对应的函数值为y0,y1,y2,yn，,为函数f(x)关于xi,xj的一阶均差，记为,即,4.4.1 均差,一般称,均差的定义,称为函数f(x)关于xi,xj,xk的二阶均差，记为,，即,同理，可以依次定义下去。设,与,分别为函数f(x)关于x0,x1,xk-1及关于x1,x2,xk的k-1阶均差，则称,为函数f(x)关于x0,x1,x2,xk的k阶均差，即,均差具有对称性，即均差与节点的排列次序无关,均差的性质,1.f(x)关于点x0,x1,x2,xk的k阶均差是f(x)在这些点上的函数值的线性组合，即 2.对称性：均差与节点的排列次序无关,2.均差表,y0y1y2yn1y

9、n,f x0,x1f x1,x2 f xn1,xn,f x0,x1,x2 f xn2,xn1,xn,f x0,xn,xn+1 yn+1 f xn,xn+1 f xn1,xn,xn+1 f x1,xn+1 f x0,xn+1,xi,yi,一阶均差,二阶均差,n 阶均差,由均差定义可知：高阶均差是两个低一阶均差的均差（差商）。,例4.3 根据已知数据 构造均差表,均差表,91,4.4.2 牛顿基本插值公式,设已知函数y=f(x)在n+1个互异结点x0,x1,x2,xn上的函数值为y0,y1,y2,yn。当n=1或2时，可分别有如下形式的插值多项式,和,由此可以推测，插值多项式可能有如下的一般形式,

10、1.牛顿插值公式,任取,(i=0,1,2,n)，由一阶均差的定义有,于是,由二阶均差的定义有,于是,这样依次做下去就有,将以上各式依次代入，可得,记,于是,其中,只要验证Pn(x)满足插值条件f(xi)=pn(xi)即可当x=xi时，Rn(xi)=0,2 牛顿插值公式,Pn(x),Rn(x),ai=,f x0,xi,牛顿插值公式的优点是：当增加一个节点时，只要再增加,一项就行了，即有递推式:,由插值的唯一性可知 Pn(x)Ln(x)，故其余项也相同，即,均差与导数的关系公式,2.牛顿插值举例,例4.3 根据已知数据,构造均差插值多项式。,均差表,91,牛顿基本插值公式,3.牛顿插值的算法,均差

11、的存储设计,当k=1时，对i=n,n-1,1,k=1,一阶均差,k=2，二阶均差,k=3，三阶均差,当k=2时，对i=n,n-1,2,3.牛顿插值的算法,(1)输入插值节点xi,yi(i=0,1,2,n)及插值点t；(2)当k=1,2,n时，对i=n,n-1,k 做,(3),对i=1,2,n 做,(4)输出p。,作业,已知表格函数如下：（1）构造均差表。（2）写出相应的牛顿基本插值公式。（3）求出当x=3.5时相应的y值。（4）求f(0)的值。,4.5 差分与等距节点插值公式,4.5.1 差分与差分表1.差分,上函数值为,(k=0,1,2,n)，这里，h为常数，称为步长。,上的增量,(k=0,

12、1,2,n-1)，称为函数y=f(x)在点xk上的一阶差分。,函数在每一小区间,定义4.2 设函数y=f(x)在n+1个等距节点,称为函数f(x)在xk上的二阶差分，记为,，即,(k=0,1,2,n-2),一般地，将,称为函数f(x)在xk上的m阶差分。,(k=0,1,2,n-m),2.差分表,2.差分表,各阶差分中所含的系数正好是二项式展开系数，所以n阶差分的计算公式为,其中,3差分与均差及导数的关系,依此类推，可得均差与差分的关系,再由均差与导数的关系(4.14)便得到差分与导数的关系,等距节点插值公式,令,，则,(k=0,1,2,n)，于是上式可改写为,其余项,如果要计算等距结点表尾附近

13、点处的函数值，可将插值结点次序由大到小排列，即,h仍为步长，此时,代入牛顿基本插值公式，并令,，则得,这就是牛顿向后插值公式。适合计算表尾处的函数值,例4.5 已知函数表如下：,求f(0.3)与f(1.1)。,计算f(0.3)时用牛顿向前插值公式，取,，于是,利用公式(4.15)可得,所以有,再利用牛顿向后插值公式计算f(1.1)处的值。取,h=0.2，于是,由公式(4.16)可得,4.6 分段低次插值,例：在5,5上考察 的Ln(x)。取,n 越大，端点附近抖动越大，称为Runge 现象,分段线性插值,在每个区间 上，用1阶多项式(直线)逼近 f(x):,失去了原函数的光滑性。,y=f(x)

14、,y=p(x),图 y=cos x的分段线性插值函数和节点的图形,分段插值效果,要求：插值曲线即要简单，又要在曲线的连接处比较光滑。,这样的分段插值函数在分段上要求多项式次数低，而在节点上不仅连续，还存在连续的低阶导数，我们把满足这样条件的插值函数，称为样条插值函数，它所对应的曲线称为样条曲线，其节点称为样点，这种插值方法称为样条插值。,4.7 样条函数插值,解决的问题：求近似函数以及这个函数在某点的近似值,我们的选择：根据经验选择多项式、指数函数、幂函数等,解决问题的原则：曲线要反映已知点给出的趋势,4.8 拟合,插值存在的问题,满足插值条件：(xi)=yi所有节点都在曲线上,节点很多时，多

15、项式次数n很高，会有龙格震荡现象,节点的测量误差会带到插值函数中,高次插值的缺陷和误差问题,特点,缺点1,缺点2,例题,已知实验数据如下，求形式简单的函数(x)，近似原来的函数关系y=f(x).使用牛顿插值公式求出一个6次的多项式=5-2*(x-1)+0.5*(x-1)*(x-2)-0.166667*(x-1)*(x-2)*(x-3)+0.125*(x-1)*(x-2)*(x-3)*(x-4)-0.05*(x-1)*(x-2)*(x-3)*(x-4)*(x-5)+0.013889*(x-1)*(x-2)*(x-3)*(x-4)*(x-5)*(x-6),插值的效果,本来的函数曲线的趋势就是一条抛

16、物线，设一个二次的多项式就可以了。,只要求反映曲线的趋势，而不要求经过所有的节点，这就是曲线拟合的基本思想。,确定a0,a1,a2的原则,最理想的情况：所有点都在曲线上，即将xi带入函数等于yi。得到的方程组称为矛盾方程组方程的个数大于未知数的个数。方程无解求最优近似解。点离曲线尽可能地近。使 Ri=(xi)yi 尽可能地小。,“使 Ri=(xi)yi尽可能的小”有不同的准则,很复杂,不可导，求解困难,最小二乘法,不同的准则对应于不同的函数逼近的方法,1,4,1.勒让德 法国数学家勒让德于1806年首次发表最小二乘理论,2.高斯 1795年，年仅18岁的德国伟大的数学家Gauss，应用最小二乘

17、方法准确地预测谷神星(Ceres)的运行轨道，迟至1809年才正式发表,3.广义最小二乘法 广义最小二乘问题的理论和计算科学出版社 华东师范大学 魏木生 2006年8月出版,2,3,4.广泛的应用 统计、数学规划、经济、控制、最优化以及社会科学的各个领域,最小二乘法,最小二乘法,设有矛盾方程组表示为和式的形式：记,mN,让误差的平方和最小,最小二乘原理,求一组x1,x2,xn 使最小根据多元函数极值的必要条件可知，在最小值点满足,对xk求偏导。,令,(k=1,2,m)，则有,则有,(k=1,2,m),(k=1,2,m)，其中,(k,j=1,2,m),(k=1,2,m),(4.28)就是对应于矛

18、盾方程组(4.26)的正规方程组，它的解是矛盾方程组的最优近似解,已知矛盾方程组可以直接写出对应的正规方程组,矛盾方程组的增广矩阵为,对应的正规方程组的增广矩阵为（,）,例4.7 用最小二乘法求矛盾方程组的最优近似解。,解 建立对应的正规方程组：,将数据代入得,即正规方程组为,解正规方程组得,即为矛盾方程组的最优近似解。,4.8.2 多项式拟合,根据实验数据(x1,y1),(x2,y2),(xN,yN)确定x,y间的近似函数关系(经验公式),最简单的办法是设所求的表达式为一个次数低于N-1的多项式。设,其中mN-1。只要确定了系数ak(k=0,1,m)，就确定了所要求的经验公式。,将已知的N组

19、实验数据分别代入所设多项式，可得,其中未知数为ak(k=0,1,m)，共有m+1个，而方程的个数为N，由mN-1可知此方程组为矛盾方程组。,依据最小二乘法原理，其对应的正规方程组为,可以证明，正规方程组(4.31)的矩阵行列式不为0，因此该方程组有唯一解。但m取为多少，应由数据所反映的趋势来定。,例4.8 已知一组实验数据,用最小二乘法求其多项式型经验公式。,解(1)作草图，由草图可以看出总趋势是一条直线。,(2)造型：由草图可设拟合曲线为,(3)建立正规方程组,将方程组中要用到的数据列于下表中：,于是，正规方程组为,由此解得,即所求多项式型经验公式为y=-16.5+7.75x,检验经验公式的

20、优劣,称为经验公式的拟合度,拟合相对偏差,“坏点”检验。所谓“坏点”是指,超过允许绝对误差限,超过允许相对误差限的点。,拟合绝对偏差,例4.9 已知一组实验数据，求其多项式型经验公式。,解(1)做草图，从图可以看出曲线所反映的趋势为抛物线。(2)造型：设拟合曲线为,(3)建立正规方程组（其中）,根据计算，得正规方程组为,即所求经验公式为,多项式型经验公式算法：(1)输入样点(xi,yi)(i=1,2,N)，拟合多项式的次数m；(2)求正规方程组的增广矩阵。当i=0,1,m时 做,对j=0,1,2,m 做,(3)用列主元高斯消去法求正规方程组的解ti(i=0,1,2,m)。(4)输出经验公式,(

21、5)如有必要，计算并输出拟合度、拟合绝对偏差、拟合相对偏差、“坏点”检验等信息。,第5次作业,求与下列数据相拟合的多项式。X-3-2-1 0 1 2 3Y 11 6 2 1 2 4 9（1）描点做出草图，确定曲线的趋势。（2）根据曲线的趋势，设出曲线的一般形式。（3）写出正规方程组。（4）求解，计算结果最少保留两位小数，最后写出求得的多项式结果。,幂函数型、指数函数型经验公式,拟合函数是关于待定参数的非线性函数，根据最小二乘法原理建立的正规方程组将是关于待定参数的非线性方程组，这类数据拟合问题称为非线性最小二乘问题。其中有些简单情形可以转化为线性最小二乘问题求解。,幂函数经验公式举例,例4.10 求一函数较好地拟合下面的数据。,解 根据这组数据画出草图,据图可取拟合函数为幂函数,幂函数经验公式举例,其中a,b为待定参数。两边取对数得lgy=lga+blgx 令 Y=lg y,X=lg x,A=lg a则原式变为Y=A+bX,相应的正规方程组为,幂函数经验公式举例,由此解得,再求出 a=10A=1.584893，便得所求函数为,