测量数据处理第2章插值与拟合.ppt
2023/11/3,1,实用测量数据处理方法,王磊电话邮箱,东南大学交通学院测绘工程系,2023/11/3,2,第二章 插值与拟合,第一节 概述第二节Lagrange插值第三节Newton插值第四节插值多项式的余项第五节 Hermite插值第六节 样条函数插值第七节 曲线拟合的最小二乘法,2023/11/3,3,第一节 概述,在生产实际及科学研究中,经常要研究变量之间的函数关系y=f（x）,而函数y=f（x）往往不能直接写出其表达式，只知道它在区间a，b中某些点的函数值，而往往要求f（x）在 a，b中其它点的值。,一、问题的提出,2023/11/3,4,1、问题1,2、问题2,在解决实际问题时，虽然可以断定考虑的函数 在 上存在且连续，但却很难找到它的解析解，只能通过实验和观测得到在有限个点上的函数值。,在有些情况下，虽然可以写出函数 在 的解析表达式，但由于结构太复杂，使用起来很不方便。,2023/11/3,5,3、目的,面对上述问题，希望找到一个简单函数 作为 的近似，便于计算、分析函数的性态。,上述问题称为数值逼近问题，函数 被称为被逼近函数，称为逼近函数，两者之差 称为 逼近 的误差或余项。,2023/11/3,6,常用的逼近方式有两种：插值逼近与平方逼近（拟合）插值逼近：要求误差R(x)在区间a,b上的已知点xi处的值等于零，即,平方逼近：即要求误差R(x)在区间a,b上的已知点xi处的值的平方和达到最小，即,2023/11/3,7,插值逼近与平方逼近的几何意义：插值逼近：精确通过已知点平方逼近：尽量符合总体轮廓插值逼近与平方逼近的应用：求积，地球重力场解析表达式的构建，数字地面模型中的应用（内插计算），机械加工等等,2023/11/3,8,问 题 实 例,机械加工,2023/11/3,9,第二节Lagrange插值,一、代数插值问题,求 解 插 值 问 题 的 基 本 思 路,2023/11/3,10,2023/11/3,11,二、代数插值多项式的存在唯一性,2023/11/3,12,2023/11/3,13,插值多项式的存在唯一性定理,结论 若节点 互不相同，则满足插值条件（1）式的n次插值多项式（2）存在且唯一。,插值条件：,插值多项式：,2023/11/3,14,N次插值多项式的几何意义,2023/11/3,15,2023/11/3,16,值得注意的是，尽管 p(x)唯一，一般不宜直接求解方程组，因为计算量较大。我们希望根据给定的函数表，做一个既反映f(x)的特性，又便于计算的简单函数p(x)近似f(x),通常选一类较简单的代数多项式或分段代数多项式来做,2023/11/3,17,二、基本插值多项式,为了构造满足插值条件的便于使用的简单插值多项式,我们考虑一个简单的插值问题:求一个n次插值多项式，使它在各个节点 上的值为：,2023/11/3,18,2023/11/3,19,三、Lagrange插值多项式,以n+1个n次基本插值多项式 为基础，能直接写出满足插值条件的 n次基本插值多项式,2023/11/3,20,四、线性插值与二次插值,（一）、线性插值,假设,2023/11/3,21,2023/11/3,22,线性插值，虽然计算方便，应用很广，但由于它是用直线去代替曲线，因而一般要求插值区间x0,x1比较小，且f(x)在x0,x1上变化比较平稳。否则，线性插值的误差可能很大。见下图,为了克服这一缺点，我们用简单的曲线去近似地代替复杂的曲线，而抛物线是最简单的二次曲线之一，下面就来研究用抛物线去逼近已知曲线的情形,2023/11/3,23,（二）、抛物线插值,令,2023/11/3,24,把n=1和n=2代入Lagrange插值多项式，即可得出线性插值与二次插值,2023/11/3,25,线性插值的几何意义,2023/11/3,26,二次插值的几何意义,2023/11/3,27,我国古代天文学家在制定历法的过程中曾对插值方法做出过杰出的贡献。譬如，隋朝刘焯的杰作皇极历（公元600）、唐僧一行所造大衍历（公元727年）都使用了二次插值，特别是，晚唐徐唐造宣明历（公元822年）所使用的插值术是二阶有限差分方法，而这方面的工作比西方超前了上千年。现代数值计算中，中国的数值计算技术反过来比西方又落后了许多,2023/11/3,28,2-3 Newton插值/*Newtons Interpolation*/,2023/11/3,29,称如下形式的多项式为牛顿（Newton）插值多项式。,优点：克服了随节点的增加，计算量的增加；减少了乘除法运算。是Lagrange插值多项式的另一种表示形式；用到差分和差商等重要的数值计算的其它概念。,关键：确定上述插值多项式中的系数。,2023/11/3,30,设 为任意 个不同的节点，取：作为多项式空间的基底，作多项式：将 依次代入得：,2023/11/3,31,算得：,2023/11/3,32,一、差商,零阶差商：,2023/11/3,33,显然,依此类推,2023/11/3,34,),(,),(,),(,),(,),(,3,3,2,2,1,1,0,0,x,f,x,x,f,x,x,f,x,x,f,x,x,f,x,k,k,三阶差商,二阶差商,一阶差商,差商的计算方法(差商表):,零阶差商,2023/11/3,35,2023/11/3,36,2023/11/3,37,2023/11/3,38,性质1 K阶差商 可表示为函数值,的线性组合，即其中:证明：由于，即：,比较 的系数的系数，可得：,2023/11/3,39,把 代入如下形式的多项式即得牛顿（Newton）插值多项式优点：Newton插值多项式有递推关系式：算例见书p28，例2.2,2023/11/3,40,三、差分、等距节点下的Newton插值多项式,当节点等距分布时:,h步长,这时，Newton插值多项式中：另外：均可以简化.,2023/11/3,41,1差分记：，（半分点）定义：一阶差分：,2023/11/3,42,二阶差分：一阶差分的差分：一般地：,2023/11/3,43,差分的性质：（1）常数的差分为零（2）各阶差分与函数值之间的关系如下,其中 表示二项式展开系数.,2023/11/3,44,（3）差分和差商的关系如下：（1）（2）（3）,2023/11/3,45,数学归纳法证明（1）式：设 成立，证 也成立.,2023/11/3,46,被插值点。,以下推导以 为节点的等距插值公式。,作变换,1、公式,2牛顿向前插值，向后插值公式,2023/11/3,47,代入：,（牛顿前插公式或表初公式）：,即得牛顿向前插值公式,2023/11/3,48,作变换,又,则,再由,（牛顿后插公式或表末公式）：,即得牛顿向后插值公式,2023/11/3,49,注：（1）（2.2）、(2.3)使用于等距节点。,（2）（2.2）、(2.3)的系数分别为，,差分表2-7,求解方法见表2-7。,(2.2)的系数,(2.3)的系数,2023/11/3,50,说明:节点的取法：取与x尽量接近的节点。注意两点，首先，若,2、计算量,（1）计算差分（计算量忽略不记）；,（2）由前插（后插）公式计算近似值：,（计算步骤）,乘除法次数大约为:+,秦九韶算法,达到了误差要求，则其他一些节点就用不到了，因此，表中的n,可以相当大，牛顿插值公式中的n不一定就是表中的n；另外,表初,式计算。,在公式中的比重是一样的。若x不在表初、表末而在表中间，则有,实例。例中还有另外的选取节点的方法，也可以用牛顿向后插值公,公式中 似乎占有较大比重，而从误差公式的对称性知,2023/11/3,51,2023/11/3,52,表2-8,2023/11/3,53,表2-9,精确值：,说明：也可取节点为,利用牛顿向后插值公式（2.3）计算。,2023/11/3,54,由于插值函数 通常只是近似地刻画了原来的函数，在插值点x处计算 作为 的函数值，因而总是会有误差的，因此 称为插值函数的截断误差，或称为插值余项，利用简单的插值函数 替代原来很复杂的函数，这种方法是否有效，关键要分析截断误差是否满足所要求的精度。,2023/11/3,55,2-4插值多项式的余项,一、插值余项,满足,不会完全成立,因此,插值多项式存在着截断误差,那么我们怎样估计这个截断误差呢？,2023/11/3,56,则称 为 的插值余项或截断误差,设,其中,2023/11/3,57,2023/11/3,58,根据Rolle定理,再由Rolle定理,依此类推,由于,因此,2023/11/3,59,所以,定理1.,Lagrange型余项,2023/11/3,60,设,则,-(1),的确切值为未知，但可用以：（1）估计误差界（2）推导求积公式精度估计（3）分析外推插值误差大于内插,2023/11/3,61,例1:,解:,2023/11/3,62,二、关于插值余项的进一步分析,2023/11/3,63,高次插值的龙格现象 插值多项式余项公式说明插值节点越多，一般说来误差越小，函数逼近越好，但这也不是绝对的，因为余项的大小既与插值节点的个数有关，也与函数f(x)的高阶导数有关。换句话说，适当地提高插值多项式的次数，有可能提高计算结果的准确程度，但并非插值多项式的次数越高越好。当插值节点增多时，不能保证非节点处的插值精度得到改善，有时反而误差更大。,2023/11/3,64,考察函数,右图给出了和 的图像,当n增大时,在两端会发出激烈的振荡,这就是所谓龙格现象。该现象表明,在大范围内使用高次插值,逼近的效果往往是不理想的,2023/11/3,65,另外，从舍入误差来看，高次插值误差的传播也较为严重，在一个节点上产生的舍入误差会在计算中不断扩大，并传播到其它节点上。因此，次数太高的高次插值多项式并不实用，因为节点数增加时，计算量增大了，但插值函数的精度并未提高。为克服在区间上进行高次插值所造成的龙格现象，采用分段插值的方法，将插值区间分成若干个小的区间，在每个小区间进行线性插值，然后相互连接，用连接相邻节点的折线逼近被插函数，这种把插值区间分段的方法就是分段线性插值法。,2023/11/3,66,三、事后估计,满足余项估计式(1)的使用条件是知道被插值函数,-(2),2023/11/3,67,-(3),当 与 比较接近，且 连续且变化不大时，可以认为：,则有,整理得,-(4),2023/11/3,68,式(4)称为插值余项的事后估计式,例2:,设,试用线性插值法计算 的值，并用事后估计式(4)估计误差,解:,用结点 作线性插值，经计算得,再用结点 作线性插值，经计算得,2023/11/3,69,由事后估计式(4)得,将误差估计值加到 中去，可得修正后的近似值,它作为精确值 的近似值具有四位有效数字，而 只有三位有效数字,2023/11/3,70,第五节 埃尔米特插值,在某些问题中，为了保证插值函数能更好地密合原来的函数，不但要求“过点”，即两者在节点上具有相同的函数值，而且要求“相切”，即在节点上还具有相同的导数值，这类插值称之为切触插值，或称为埃尔米特（Hermite）插值，这是泰勒插值和拉格朗日插值的综合和推广。,2023/11/3,71,Hermite插值也叫带指定微商值的插值,它要构造一个插值函数,不但在给定节点上取函数值,而且取已知微商值，使插值函数和被插函数的密和程度更好。,2023/11/3,72,Hermite插值多项式的构造,2023/11/3,73,Hermite插值多项式的构造,2023/11/3,74,2023/11/3,75,2023/11/3,76,2023/11/3,77,2023/11/3,78,2023/11/3,79,2023/11/3,80,2023/11/3,81,2023/11/3,82,2023/11/3,83,2023/11/3,84,一、问题的提出,我们知道,给定n+1个节点上的函数值可以作n次插值多项式,但当n较大时,高次插值不仅计算复杂,而且可能出现Runge现象,采用分段插值虽然计算简单、也有一致收敛性,但不能保证整条曲线在连接点处的光滑性,如分段线性插值,其图形是锯齿形的折线,虽然连续,但处都是“尖点”,因而一阶导数都不存在,这在实用上,往往不能满足某些工程技术的高精度要求。如在船体、飞机等外形曲线的设计中,不仅要求曲线连续,而且要有二阶光滑度,即有连续的二阶导数。这就要求分段插值函数在整个区间上具有连续的二阶导数。因此有必要寻求一种新的插值方法,这就是样条函数插值法,第六节 样条函数插值,2023/11/3,85,就是按一定光滑性要求“装配”起来的分段多项式。设 为区间 的一个分划.若 满足以下条件：（1）在每个子区间 上是 次多项式（2）及其直到 阶导数在 上连续则称 为关于分划 的 次样条函数，样条函数的全体记做内节点,样条函数-所谓样条函数，从数学角度理解，,二、样条函数的定义,2023/11/3,86,定义（3次样条函数）,多项式。,，即具有连续的一阶，二阶导数。,满足下述条件：,的一个3次样条函数。,提出问题：,如何计算？误差估计？,二、样条函数的定义,2023/11/3,87,分析：,已有条件：,4n个待定系数:,个条件,内部条件：,个条件,2023/11/3,88,常见边界条件有三种：,第1种边界条件：,第2种边界条件：,已知,即,已知,即,第3种边界条件（周期边界条件）：,为周期函数，,此时称,为周期样条函数。,三次样条插值函数的表达式,基本思路：,以分段三次Hermite插值为基础，由(1)函数表,；(3)三种边界条件中,的某一种推导3次样条插值函数。,2023/11/3,89,三次样条插值函数的求法,推导方法：,该方法即为3次样条插值函数的一阶导数表示。,该方法即为3次样条插值函数的二阶导数表示。,（一阶导数表示）,三次样条插值函数的表达式,（一）、推导公式：,2023/11/3,90,2023/11/3,91,2023/11/3,92,(1)增加第1种边界条件：,2023/11/3,93,上式简记为,可得两个方程:,2023/11/3,94,(3)增加第3种边界条件：,2023/11/3,95,异矩阵，则方程组（2.6.7）、（2.6.8）或（2.6.9）有唯一解,可用追赶法求解,从而给出,为3次样条插值函数)。,说明：,方程组（）、（2.6.8）或（）系数矩阵都是严格,对角占优矩阵，由前面所学的知识可知这些方程组的系数阵为非奇,计算步骤:,先计算,或第三类边界条件，要计算）。,（2）用追赶法求解方程组(2.6.7)(2.6.8)或(2.6.9)求。,x所在的区间。),2023/11/3,96,三、三次样条插值函数的性质,一是计算稳定性二是最佳逼近性三是一致收敛性,2023/11/3,97,注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f 在所有插值点的导数值。,f(x),H(x),S(x),三次样条插值的实质：分段插值。,三次样条插值的特点：插值函数具有二阶连续导数。,2023/11/3,98,插值模型与样条插值法,例3.6 地形模型：平面区域上的海拔高程 h(x,y)xy 0 400 800 1200 1600 20000 370 470 550 600 670 690400 510 620 730 800 850 870800 650 760 880 970 1020 10501200 740 880 1080 1130 1250 12801600 830 980 1180 1320 1450 14202000 880 1060 1230 1390 1500 1500给出这个平面区域内地形的模型。,2023/11/3,99,插值模型与样条插值法,假设：1.观测点的高程数值是准确的。2.地形的各观测点之间没有剧烈的变化。3.相邻观测点之间的高程的变化是线性的。模型：拟合坐标轴方向相邻观测点间的高程.给出地形变化的等高线图.,2023/11/3,100,插值模型与样条插值法,令 hij=h(xi,yj),考虑点(xi,yj),(xi+1,yj)间高程的变化。记 hi=hij,hi+1=hi+1j.则由直线方程的两点式可得椐此就可在坐标系中画出平面区域的地形图,2023/11/3,101,插值模型与样条插值法,3.插值技术x=0:4:20;%给出X轴的坐标y=0:4:20;%给出Y轴的坐标z=37 51 65 74 83 88;47 62 76 88 98 106;69 87 105 128 142 150;%给出（x，y）点的高程X，Y=meshgrid(0:1:20,0:1:20);%给出新的插值坐标Z=interp2(x,y,z,X,Y,spline);%在新的坐标上进行样条插值clf;%清空图形坐标系中的内容axis xy;%设置坐标的单位一致mesh(X,Y,Z)%用网格画出插值的结果hold on%打开在同一坐标系中画图的功能contour(X,Y,Z)%画平面等高线contour3(X,Y,Z)%画三维等高线,2023/11/3,102,插值模型与样条插值法,2023/11/3,103,一、问题的提出如果已知函数f(x)在若干点xi(i=1,2,n)处的值yi,便可根据插值原理来建立插值多项式作为f(x)的近似。但在科学实验和生产实践中，往往会遇到这样一种情况，即节点上的函数值并不是很精确的，这些函数值是由实验或观测得到的数据，不可避免地带有测量误差，如果要求所得的近似函数曲线精确无误地通过所有的点(xi,yi),就会使曲线保留着一切测试误差。当个别数据的误差较大时,插值效果显然是不理想的。此外,由实验或观测提供的数据个数往往很多,如果用插值法,势必得到次数较高的插值多项式，这样计算起来很烦琐。,第七节 曲线拟合的最小二乘法,2023/11/3,104,为此,我们希望从给定的数据(xi,yi)出发,构造一个近似函数,不要求函数 完全通过所有的数据点，只要求所得的近似曲线能反映数据的基本趋势，如图5-7所示。,图5-7 曲线拟合示意图,换句话说:求一条曲线,使数据点均在离此曲线的上方或下方不远处,所求的曲线称为拟合曲线,它既能反映数据的总体分布,又不至于出现局部较大的波动,更能反映被逼近函数的特性,使求得的逼近函数与已知函数从总体上来说其偏差按某种方法度量达到最小,这就是最小二乘法。,2023/11/3,105,与函数插值问题不同,曲线拟合不要求曲线通过所有已知点,而是要求得到的近似函数能反映数据的基本关系。在某种意义上,曲线拟合更有实用价值。在对给出的实验(或观测)数据作曲线拟合时,怎样才算拟合得最好呢？一般希望各实验(或观测)数据与拟合曲线的偏差的平方和最小,这就是最小二乘原理。两种逼近概念:插值:在节点处函数值相同.拟合:在数据点处误差平方和最小,2023/11/3,106,二、最小二乘法概念,（一）基本概念：残差,（二）残差的选取方法（原则）,1、选取，使偏差绝对值之和最小，即,拟合的目的：使得残差最小，其中 为所要找的函数。,2023/11/3,107,3、选取，使偏差平方之和最小，即,2、选取，使偏差最大绝对值最小，即,2023/11/3,108,最小二乘原则（方法）,1、定义：使“偏差平方和最小”的原则称为最小二乘原则。,2、定义：按照最小二乘原则选取拟合曲线的方法，称为最小二乘法。,2023/11/3,109,3、线性最小二乘问题的提法,式中，是函数类 中任一函数。,2023/11/3,110,满足上述关系式的函数，称为上述最小二乘问题的最小二乘解。,分析：如何求解最小二乘问题？有两个基本环节：,1、确定函数类（原则：根据实际问题与所给数据点的变化规律）；2、求解方程：,2023/11/3,111,三 最小二乘解的求法,（一）求解的基本原理：极小值原理,点 是多元函数的极小值点，从而有 满足方程组,2023/11/3,112,2023/11/3,113,（二）正规（法）方程,写成矩阵形式即为,2023/11/3,114,作为一种应用，通常拟合曲线假设为代数曲线，即取:,于是正规（法）方程组为：,2023/11/3,115,此时,称它为数据拟合多项式,上述拟合称为多项式拟合,2023/11/3,116,四、正交函数系的最小二乘拟合,用最小二乘法得到的方程组其系数矩阵G是病态的,但如果,是关于点集xi带,权i(i=0,1,m)正交函数族,即,2023/11/3,117,则方程(2.7.3)化为,解得,2023/11/3,118,2023/11/3,119,2023/11/3,120,本章小结,本章介绍的插值法和曲线拟合的最小二乘法都是实用性很强的方法。它们解决的实际问题虽然各式各样，但抽象为数学问题却有它的共性，即利用已知的数据去寻求某个较为简单的函数P(x)来逼近f(x)。插值法和曲线拟合的最小二乘法分别给出了寻求这种近似函数的两类不同的原则，以及构造近似函数的几种具体方法。其中插值法要求近似函数在已知的数据点必须与f(x)完全一致，曲线拟合法不要求点点一致而只须满足一定的整体逼近条件。,2023/11/3,121,插值法中的拉格朗日插值多项式是研究数值微积分与微分方程数值解的重要工具。牛顿插值多项式是拉格朗日插值多项式的变形，具有承袭性，比拉格朗日插值多项式节省计算量。埃尔米特插值多项式属于重节点的插值公式，当n+1节点上的函数值和导数值给定时，可构造2n+1次带导数的插值多项式。分段低次多项式插值由于具有良好的稳定性与收敛性，且算法简单，便于应用。特别是应用广泛的三次样条插值，不但有较好的稳定性和收敛性，而且具有较好的光滑性，从而满足了许多实际问题的要求。需对样条函数作进一步了解的同学可参阅有关文献,2023/11/3,122,曲线拟合的最小二乘法是处理实验数据的常用方法。本章主要介绍了最小二乘法的基本原理和线性最小二乘问题的求解方法。多项式拟合是线性最小二乘拟合问题的一种特殊情况,其特点是拟合多项式形式简单,但当n较大时,法方程组往往是病态的。用离散正交多项式进行曲线拟合,不用解线性方程组,只需按递推式进行计算,避免了法方程组病态所造成的麻烦,并且当逼近次数增加一次时,只要在原基础上增加一项,使计算程序十分简单。关于非线性最小二乘曲线拟合问题,一般求解比较困难,但对一些特殊情形,可以转换为线性最小二乘拟合问题。在实际计算时,要选择合理的拟合多项式的次数,有时是十分困难的。一般可对数据作分析,例如在方格低上作草图,从草图中观察应作几次多项式精度较好。以选择最佳的拟合多项式的次数。,
