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

《计算方法-插值与拟合.ppt》由会员分享，可在线阅读，更多相关《计算方法-插值与拟合.ppt（88页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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章章插值与拟合插值与拟合 设已知某个函数关系设已知某个函数关系y=f(x)在某些离散点处的函数值：在某些离散点处的函数值：插插值拟合合根据这些已知数据根据这些已知数据来构造函数来构造函数y=f(x)y=f(x)的的一个简单的近似函数一个简单的近似函数要求近似函数经过要求近似函数经过所有已知的数据点所有已知的数据点根据已知数据点所反根据已知数据点所反映的趋势

2、，构造一个映的趋势，构造一个近似的函数表达式，近似的函数表达式，不要求经过所有的点不要求经过所有的点求求求求x=tx=tx=tx=t点处的函数值点处的函数值点处的函数值点处的函数值f(t)f(t)f(t)f(t)插值与拟合的区别第第4章章 插值与拟合插值与拟合插值插值曲线经过所有曲线经过所有节点节点拟合拟合Lagrange插值插值Newton插值插值等距节等距节点插值点插值多项式多项式拟合拟合幂函数幂函数指数函指数函数数曲线只要反映曲线只要反映趋势即可趋势即可解决的解决的问题：求近似函数求近似函数以及以及这个函数在个函数在某点的近似某点的近似值我我们的的选择：代数插代数插值求一个多求一个多项式

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的多的多项式是唯

4、一的。式是唯一的。插值多项式插值多项式存在唯一性存在唯一性设所要构造的插值多项式为：设所要构造的插值多项式为：由插值条件由插值条件 得到如下线性代数方程组：得到如下线性代数方程组：插值多项式的存在唯一性：由插值多项式的存在唯一性：由n+1个互异节点构造的个互异节点构造的n次插值多项式是唯一的。次插值多项式是唯一的。此方程组的系数行列式为此方程组的系数行列式为 范得蒙行列式范得蒙行列式！当当 时时，D 0，因此，因此，Pn(x)由由a0,a1,an唯一确定。唯一确定。定理定理 (唯一性唯一性)满足满足 的的 n 阶插值阶插值多项式是唯一存在的。多项式是唯一存在的。插值多项式的唯一性注意：注意：当

5、由当由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 x1x2p2(x)f(x)f(x)2二次（二次（抛物）插值抛物）插值因过三点的二次曲线为抛物线，故称为抛物插值。因过三点的二次曲线为抛物线，故称为抛物插值。Lagrange二次插值多项式的表示形式要

6、求：要求：互异节点，即互异节点，即设连续函数设连续函数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,n4.3 拉格朗日插值拉格朗日插值求求n次多项式次多项式lk(x)k=0,1,n则则 i=0,1,2,n即即Pn(x)满足插值条件满足插值条件（4.2）根据根据lk(x)的表达式的表达式，xk以外所有的结点都是以外所有的结点都是lk(x)的根的根，1.构造插值基函数又由又

7、由lk(xk)=1，得得：因此令因此令从而得从而得n 阶拉格朗日（阶拉格朗日（Lagrange）插值公式：）插值公式：例例4.1 4.1 已知函数已知函数y=y=f f(x x)的观测数据如下表的观测数据如下表试求其试求其LagrangeLagrange插值多项式。插值多项式。k012xk012yk135解解 由由题题知知，共共有有3 3个个结结点点，所所以以n n=2=2，于于是是所所求求LagrangeLagrange插值多项式为：插值多项式为：例例4.2 4.2 已知函数已知函数y=y=f f(x x)的观测数据如下表的观测数据如下表k k0 01 12 23 3x xk k1 12 2

8、3 34 4y yk k4 45 514143737试求其试求其LagrangeLagrange插值多项式。插值多项式。解解 由由题题知知，共共有有4 4个个结结点点，所所以以n n=3=3，于于是是所所求求LagrangeLagrange插值多项式为：插值多项式为：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)内存在内存在,考察截断误差考察截断误差设节点设节点，且，

9、且 f 满足条件满足条件 存在存在 使得使得 。且且推广：推广：若若使得使得使得使得罗尔定理罗尔定理:若若 在在 连续，若连续，若 充分光滑，充分光滑，在在a,b连续连续,3.插值余项插值余项余项定理余项定理，Ln(x)是插值多项式，则对任意是插值多项式，则对任意定理定理4.1 设设在在a,b上连续，上连续，在在(a,b)内存在，节点满足内存在，节点满足，插值余项，插值余项 (4.10)其中其中 证证 (1)当当x=xi(i=0,1,2,n)时，由插值条件知时，由插值条件知Ln(xi)=yi,，结论成立。，结论成立。F(t)有有n+2个零点，反复应用个零点，反复应用Rolle定理，得定理，得

10、且且(i=0,1,2,n)，固定，固定x，考虑函数，考虑函数(2)任取任取注意：注意：通常不能确定通常不能确定 x,而是估计而是估计 ,x(a,b)将将 作为误差估计上限。作为误差估计上限。当当 f(x)为任一个次数为任一个次数 n 的多项式时，的多项式时，,可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项式是多项式是精确的。精确的。如何使余项减小？如何使余项减小？1、增加、增加n能否保证能否保证Rn(x)减小？减小？2、设法使、设法使 减小。减小。使用内插，少用外推。使用内插，少用外推。Lagrange 插值虽然易算，但若要增加一个插值虽然易算，但若要增加一个节点时，全部

11、基函数节点时，全部基函数 li(x)都需重新计算。都需重新计算。4.4 均差与牛顿基本插值公式均差与牛顿基本插值公式4.4 均差与牛顿基本插值公式均差与牛顿基本插值公式1均差（差商）的定义均差（差商）的定义设连续函数设连续函数y=f(x)在在n+1个互异节点个互异节点x0,x1,x2,xn上对应的函上对应的函数值为数值为y0,y1,y2,yn，为函数为函数f(x)关于关于xi,xj的一阶均差，记为的一阶均差，记为即即4.4.1 均差均差一般称一般称均差的定义均差的定义称为函数称为函数f(x)关于关于xi,xj,xk的的二阶均差二阶均差，记为，记为，即，即同理，可以依次定义下去。设同理，可以依次

12、定义下去。设与与分别为函数分别为函数f(x)关于关于x0,x1,xk-1及关于及关于x1,x2,xk的的k-1阶均差，阶均差，则称则称为函数为函数f(x)关于关于x0,x1,x2,xk的的k阶均差阶均差，即，即 均差具有对称性，即均差均差具有对称性，即均差与节点的排列次序无关与节点的排列次序无关 2.均差表y0y1y2yn 1ynf x0,x1f x1,x2 f xn 1,xn f x0,x1,x2 f xn 2,xn 1,xnf x0,xn xn+1 yn+1 f xn,xn+1 f xn 1,xn,xn+1 f x1,xn+1 f x0,xn+1xi yi 一阶均差一阶均差 二阶均差二阶均

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

14、式由此可以推测，插值多项式可能有如下的一般形式1.牛顿插值公式牛顿插值公式任取任取,(,(i i=0,1,2,=0,1,2,n n)，由一阶均差的定义有，由一阶均差的定义有于是于是由二阶均差的定义有由二阶均差的定义有于是于是这样依次做下去就有这样依次做下去就有将以上各式依次代入，可得将以上各式依次代入，可得记于是其中只要验证只要验证Pn(x)满足插值条件满足插值条件f(xi)=pn(xi)即可即可当当x=xi时，时，Rn(xi)=0牛顿插值公式的优点是：当增加一个节点时，只要再增加牛顿插值公式的优点是：当增加一个节点时，只要再增加一项就行了，即有递推式一项就行了，即有递推式:由插值的由插值的唯

15、一性可知唯一性可知 Pn(x)Ln(x)，故其余项也相同，即故其余项也相同，即均差与导数的关系公式均差与导数的关系公式 2.牛顿插值举例牛顿插值举例 例例4.3 根据已知数据根据已知数据i012345xi023561yi08271252161构造均差插值多项式。构造均差插值多项式。均差表均差表91牛顿基本插值公式牛顿基本插值公式3.牛顿插值的算法牛顿插值的算法均差的存储设计均差的存储设计y0y1=fx0,x1y2=fx1,x2y3=fx2,x3y4=fx3,x4y5=fx4,x5y0y1y2y3y4y5y0y1=fx0,x1y2=fx0,x1,x2y3=fx1,x2,x3y4=fx2,x3,x

16、4y5=fx3,x4,x5y0y1=fx0,x1y2=fx0,x1,x2y3=fx0,x1,x2,x3y4=fx1,x2,x3,x4y5=fx2,x3,x4,x5当当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）

17、构造均差表。）构造均差表。（2）写出相应的牛顿基本插值公式。）写出相应的牛顿基本插值公式。（3）求出当）求出当x=3.5时相应的时相应的y值。值。（4）求）求f(0)的值。的值。x134526y21017265374.5 差分与等距节点插值公式差分与等距节点插值公式 4.5.1 差分与差分表差分与差分表1.差分差分上函数值为上函数值为(k=0,1,2,n)，这里，这里，h为常数，称为步长。为常数，称为步长。上的增量上的增量 (k=0,1,2,n-1)，称为函数，称为函数y=f(x)在点在点xk上的一阶差分。上的一阶差分。函数在每一小区间函数在每一小区间定义定义4.2 设函数设函数y=f(x)在

18、在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)便得到差分与导数的关系便得到差分

19、与导数的关系等距节点插值公式等距节点插值公式令令，则，则,(k=0,1,2,n)，于是上式可改写为，于是上式可改写为 其余项其余项如果要计算等距结点表尾附近点处的函数值，可将插值结如果要计算等距结点表尾附近点处的函数值，可将插值结点次序由大到小排列，即点次序由大到小排列，即,h仍为步长，此时仍为步长，此时代入牛顿基本插值公式，并令代入牛顿基本插值公式，并令，则得，则得 这就是牛顿向后插值公式。适合计算表尾处的函数值这就是牛顿向后插值公式。适合计算表尾处的函数值 例例4.5 已知函数表如下：已知函数表如下：k0123456xk0.00.20.40.60.81.01.2f(xk)0.00.2030

20、.4230.6841.031.5572.572求求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阶多项式阶多项式(直线直

21、线)逼近逼近 f(x):记记 ，易证：当，易证：当 时，时，一致一致失去了原函数的光滑性。失去了原函数的光滑性。yxoy=f(x)y=p(x)图 y=cos x的分段线性插值函数和节点的图形分段插值效果分段插值效果要求：要求：插值曲线即要简单，又要在曲线的连接处比较光滑。插值曲线即要简单，又要在曲线的连接处比较光滑。这样的分段插值函数在分段上要求多项式次数低，而这样的分段插值函数在分段上要求多项式次数低，而在节点上不仅连续，还存在连续的低阶导数，我们把满足在节点上不仅连续，还存在连续的低阶导数，我们把满足这样条件的插值函数，称为样条插值函数，它所对应的曲线这样条件的插值函数，称为样条插值函数，

22、它所对应的曲线称为样条曲线，其节点称为样点，这种插值方法称为称为样条曲线，其节点称为样点，这种插值方法称为样条插值。样条插值。4.7 样条函数插值样条函数插值解决的解决的问题：求近似函数求近似函数以及以及这个函数在个函数在某点的近似某点的近似值我我们的的选择：根据根据经验选择多多项式、式、指数函数、指数函数、幂函数等函数等解决解决问题的原的原则：曲曲线要反映已知点要反映已知点给出的出的趋势4.8 拟合合 插插值存在的存在的问题满足插足插值条件：条件：(xi)=yi所有所有节点都在曲点都在曲线上上节点很多点很多时，多，多项式次数式次数n很高，很高，会有会有龙格震格震荡现象象节点的点的测量量误差差

23、会会带到插到插值函数函数中中 高次插高次插值的缺陷和的缺陷和误差差问题特点特点缺点缺点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)i1234567xi1234567yi5321247插值的效果

24、本来的函数曲线的趋势就是一条抛物线，设一个二次的多项式就可以了。只只要要求求反反映映曲曲线线的的趋趋势势，而而不不要要求求经经过过所所有有的的节节点点，这这就就是是曲曲线线拟拟合合的的基基本本思思想想。确定a0,a1,a2的原则最理想的情况：所有点都在曲线上，即将xi带入函数等于yi。得到的方程组称为矛盾方程组方程的个数大于未知数的个数。方程无解求最优近似解。点离曲线尽可能地近。使使 Ri=(xi)yi 尽可能地小。尽可能地小。“使使 Ri=(xi)yi尽可能的小尽可能的小”有不同的准则有不同的准则很复杂不可导，求解困难最小二乘法最小二乘法不同的准则对应于不同的函数逼近的方法1 14 41.勒

25、让德勒让德 法国数学家勒让德于法国数学家勒让德于1806年首次发年首次发表最小二乘理论表最小二乘理论 2.高斯高斯 1795年，年仅年，年仅18岁的德国伟大的数学岁的德国伟大的数学家家Gauss，应用最小二乘方法准确地，应用最小二乘方法准确地预测谷神星预测谷神星(Ceres)的运行轨道，迟至的运行轨道，迟至1809年才正式发表年才正式发表 3.广义最小二乘法广义最小二乘法 广义最小二乘问题的理论和计算广义最小二乘问题的理论和计算科学出版社科学出版社 华东师范大学华东师范大学 魏木生魏木生 2006年年8月出版月出版2 23 34.广泛的应用广泛的应用 统计、数学规划、经济、控制、最优化统计、数

26、学规划、经济、控制、最优化以及社会科学的各个领域以及社会科学的各个领域 最小二乘法最小二乘法最小二乘法最小二乘法最小二乘法设有矛盾方程组表示为和式的形式：记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)就是对应于矛盾方程组(4.26)的正规方程组，它的解是矛盾方程组的最优近似解已知矛盾方程组可以直接写出对应的正规方程组矛盾方程组的增广矩阵为对应的正规方程组的增广矩阵为（）例4.7 用最小二乘

27、法求矛盾方程组的最优近似解。解 建立对应的正规方程组：将数据代入得即正规方程组为解正规方程组得即为矛盾方程组的最优近似解。4.8.2 多项式拟合 根据实验数据(x1,y1),(x2,y2),(xN,yN)确定x,y间的近似函数关系(经验公式)最简单的办法是设所求的表达式为一个次数低于N-1的多项式。设其中mN-1。只要确定了系数ak(k=0,1,m)，就确定了所要求的经验公式。将已知的N组实验数据分别代入所设多项式，可得其中未知数为ak(k=0,1,m)，共有m+1个，而方程的个数为N，由mN-1可知此方程组为矛盾方程组。依据最小二乘法原理，其对应的正规方程组为 可以证明，正规方程组(4.31

28、)的矩阵行列式不为0，因此该方程组有唯一解。但m取为多少，应由数据所反映的趋势来定。例4.8 已知一组实验数据i1234xi2468yi2112848用最小二乘法求其多项式型经验公式。o 2 4 6 8 xy10203040图4-2解(1)作草图，由草图可以看出总趋势是一条直线。(2)造型：由草图可设拟合曲线为 (3)建立正规方程组将方程组中要用到的数据列于下表中：ixiyixiyixi21224424114416362816836484838464和2089600120于是，正规方程组为由此解得即所求多项式型经验公式为y=-16.5+7.75x检验经验公式的优劣检验经验公式的优劣称为经验公式

29、的拟合度称为经验公式的拟合度拟合相对偏差拟合相对偏差“坏点坏点”检验。所谓检验。所谓“坏点坏点”是指是指超过允许绝对误差限超过允许绝对误差限超过允许相对误差限的点。超过允许相对误差限的点。拟合绝对偏差拟合绝对偏差 设经验公式在各结点处的函数值为设经验公式在各结点处的函数值为，则，则 设经验公式在各结点处的函数值为设经验公式在各结点处的函数值为，则，则例例4.9 已知一组实验数据，已知一组实验数据，求其多项式型经验公式。求其多项式型经验公式。i1234567xi1234567yi5321247解解 (1)做草图，从图可以看出曲线所反映的趋势为抛物做草图，从图可以看出曲线所反映的趋势为抛物线。线。

30、(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)输出经验公式 (5)(5)如有必要，计算并输出拟合度、拟合绝对偏差、如有必要，计算并输出拟合度、拟合绝对偏差、拟合相对偏差、拟合相对偏差、“坏点坏点”检验等信息。检验等信息。第5次作业求与下列数据相拟合的多项式。求与下列数据相拟合的多项式。X

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