第4、5章插值与拟合

第四、五章插值与曲线拟合,一插值与曲线拟合问题,二拉格朗日插值,三牛顿插值,四曲线拟合的最小二乘法,小结,插值问题的提出,对上述问题中的函数建立一个简单的便于计算和处理的近似表达式，即用一个简单的函数来近似代替这些不便处理的函数插值函数。,插值与曲线拟合,拟合问题的提出,实际问题中通过测量得到的数据比较多，而且这些数据本身含有一定误差，根据这些数据求取近似函数的方法是曲线拟合。,插值要求找到的近似函数的曲线通过所有的数据点。曲线拟合不要求近似函数的曲线通过所有数据，只要求该曲线能反映数据变化的基本趋势。拟合的主要目的是：去掉测量数据所含的测量误差。,插值与拟合的区别,4.1插值问题的数学提法,当精确函数y=f(x)非常复杂或未知时，在一系列节点x0xn处测得函数值y0=f(x0),yn=f(xn)，由此构造一个简单易算的近似函数P(x)f(x)，满足条件：P(xi)=f(xi)(i=0,n)。这里的P(x)称为f(x)的插值函数，称为插值节点。所以所谓插值就是根据已知点的函数值求其余点的函数值。,4.1插值问题的数学提法,求简单函数Pn(x)，使得,计算f(x)可通过计算P(x)来近似代替。如下图所示。,P(x)f(x),这就是插值问题,(*)式为插值条件,称为插值节点,由于插值函数的选择不同，就产生不同类型的插值。若为代数多项式，就是代数插值，若为三角多项式就称为三角多项式插值，若为有理函数就称为有理函数插值。由于代数多项式结构简单，本章主要介绍代数多项式插值问题。,2.满足插值条件的多项式P(x)是否存在且唯一？,3.用P(x)代替f(x)的误差估计，即截断误差的估计；,对于多项式插值，我们主要讨论以下几个问题：,4.当插值节点无限加密时，插值函数是否收敛于f(x)。,1.如何构造出插值多项式P(x);即插值多项式的常用构造方法有哪些？,4.2拉格朗日插值,可见P(x)是过(x0,y0)和(x1,y1)两点的直线。这种插值称为线性插值，显然在节点上插值误差为0。,拉格朗日,线性插值（两点插值）,于是线性插值函可以表示为函数值与基函数的线性组合,与称为线性插值基函数。它有如下性质：,即：,所以,例1已知用线性插值求近似值。,插值多项式为,抛物线插值（三点二次插值）,已知在节点上的函数值，求二次多项式，使之满足根据要满足的三个条件，确定三个未知数，因此可采用待定系数法。即,为避免解线性方程组，下面仿线性插值，用基函数的方法求解方程组。设方程组满足条件的方程为,其中基函数应满足:,同理,所以,抛物线插值是三个二次式的线性组合，是x的（不高于）二次式，在节点上插值多项式的值和已知函数值相等。,设函数在区间上有节点上的函数值，构造一个次数不超过次的代数多项式，使。即次代数插值满足在个节点上插值多项式和被插值函数相等，而且插值多项式的次数不超过次。,n次代数插值,这样的插值多项式能构造出来吗？唯一吗？,插值多项式的存在性和唯一性定理,则由插值条件式Pn(xi)=yi(i=0,1,.,n)可得关于系数a0,a1,an的线性代数方程组,此方程组有n+1个方程,n+1个未知数,其系数行列式是范德蒙行列式，即：,反证：若不唯一，则除了P(x)外还有另一n阶多项式Q(x)满足Q(xi)=yi。,考察则S的阶数,n,而S(x)有个不同的根,唯一性定理,矛盾,只有S(x)0,所以P(x)Q(x)唯一性说明不论用哪种方法构造的插值多项式，只要满足同样的插值条件，其结果都是互相恒等的。,拉格朗日插值多项式,要求n阶插值多项式，可以通过求方程组的解得到。但由于解线性代数方程组的计算量比较大，构造插值多项式时，仍用基函数构造。,希望能找到满足以下条件的n次多项式li(x),然后令,，则显然有P(xi)=yi。,基函数的构造,其中A为常数,由li(xi)=1可得,称之为拉格朗日基函数。,除xi点外,其余xj都是li(x)的根，可设,与有关，而与无关,节点,f,拉格朗日插值多项式,特别地,当n=1时又叫线性插值,其几何意义为过两点的直线.当n=2时又叫抛物插值,其几何意义为过三点的抛物线.,应注意,对于插值节点,只要求它们互异,与大小次序无关。,5插值余项,截断误差R(x)=f(x)-P(x)也称为插值多项式的余项。以下为拉格朗日余项定理。,注意这里是对t求导,RollesTheorem:若充分光滑，则存在使得。,推广：若,使得,R(x)至少有个根,n+1,(t)有n+2个不同的根x0xnx,0=,证毕,常用余项定理研究插值的误差估计。,其中,Lagrange插值公式的标准型公式:,插值余项：,线性插值，余项，其中：对求极值：得为极小值。即取，则。取绝对值：，则：所以其中：,用余项定理求线性插值余项及其估计式。,解,插值为多项式,于是,因为,可得,误差估计,解：,n=1,分别利用x0,x1以及x1,x2计算,利用,这里,而,sin50=0.7660444,外推的实际误差0.01001,利用,内插的实际误差0.00596,内插通常优于外推。选择要计算的x所在的区间的端点，插值效果较好。,1LagrangePolynomial,n=2,sin50=0.7660444,2次插值的实际误差0.00061,高次插值通常优于低次插值,如果是次数不超过次的多项式，取个节点插值时，插值多项式就是其自身。,插值多项式只与数据，有关，与节点排列顺序无关。,个节点的插值多项式不超过次。,拉格朗日插值小结：,内插比外插精度高。当求某点的函数值时，插值节点应尽可能靠近该点，此时余项小。,当节点数变化时，需重新计算全部基函数。,Lagrange插值算法特点&局限性,优点：公式简洁,理论分析方便直观；对称；容易编程上机等。,缺点：基函数计算复杂，计算量大每增加一个节点，插值多项式的所有系数都得重算；计算量为。,下一节提出的Newton插值法就是克服了上缺点。,4.4牛顿插值,拉格朗日插值的优点是插值多项式特别容易建立，缺点是增加节点时原有多项式不能利用，必须重新建立，即所有基函数都要重新计算，这就造成计算量的浪费；,牛顿插值,本节介绍这种插值公式的建立、特点和应用。这要用到差商的概念。,一、差商及其基本性质,定义1,差商的计算步骤与结果可列成差商表，如下,由此可知高阶差商是由比它低一阶的两个差商组成。,利用差商的递推定义，可以用递推来计算差商,所以f1,3,4,7=-1.25,fx0,x1,x2,.,xn,=fx1,x2,.,xn,x0,性质1差商可以表示为函数值的线性组合，即,=fx1,x0,x2,.,xn,=,这一性质称之为差商的对称性。,性质2(对称性)差商与节点的顺序无关，如,这一性质可以用数学归纳法证明。（P124）,性质3若是x的n次多项式，则：一阶差商是x的n-1次多项式，二阶差商是x的n-2次多项式；一般地，函数f(x)的k阶差商是x的n-k次多项式(kn)。而kn时，k阶差商为零。,二、牛顿插值多项式,如此继续下去，可得一系列等式,设x是a，b上一点，由一阶差商定义,得,依次把后式代入前式，,P(x),R(x),最后得,牛顿插值公式特点,：是x的n次多项式，称为牛顿插值多项式,：是最后一项，称为牛顿插值余项。,增加一个节点时，只需再增加一项，其余各项都不变。,牛顿插值公式特点(续),取n1个节点时，牛顿插值多项式次数不超过n次，各项系数是各阶差商。,由插值多项式的唯一性知,拉格朗日插值多项式和牛顿插值多项式是相等的。只是算法不同。,解：在例1中，我们已计算出,则牛顿三次插值多项式为,4.8分段低次插值,分段低次插值,问题的提出：,在拉格朗日插值法中，为了使插值多项式更好的逼近被插函数，往往要增加插值节点，提高插值多项式的次数。当插值区间较大时，对于高次插值在插值区间两端会发生剧烈振荡。高次代数插值所发生的这种现象称为Runge现象.在上个世纪初由Runge发现.,一、高阶插值的龙格现象,例：在5,5上考察的Pn(x)。取,n越大，端点附近抖动越大，称为Runge现象,分段低次插值,既要增加插值节点，减小插值区间，又不增加插值多项式的次数以减少误差，我们可以采用分段插值的办法。,二、分段线性插值,原理：将插值区间分成若干个小的子段，在每个子段上进行低次插值，然后相互连接，用连接相邻节点的折线逼近被插函数。,定义,S(x)在a,b上连续；,S(xi)=yi，i0,1,n,S(x)在每个子段是线性函数。,称函数S(x)为分段线性插值函数。,S(x)在子段上有（线性插值）：,在区间上有：,其中,显然,失去了原函数的光滑性。,分段线性插值特点,算法简单，能保证收敛。,能获得任意精度的插值。,局部性质。,解在每个小区间上，,于是,4.3逐次线性插值（本节为了解内容）,逐次线性插值解决拉格朗日插值为提高精度增加插值节点时，要重新计算全部基函数，整个插值多项式的结构都会改变的问题。为使计算有“承袭性”，可用逐次线性插值或称迭代插值的办法解决。逐次线性插值是重复地进行线性插值产生从低次到高次的拉格朗日插值多项式序列，直到获得合适的计算结果，避免增加节点从头开始计算，常用的埃特金(Aitken)算法和内维尔(Neville)算法。,4.3.1三个节点的情形,已知f(x)在三个互异节点x0,x1,x2的函数值y0,y1,y2用（x0,y0),(x1,y1)做插值,用（x0,y0),(x2,y2)做插值,用（x1,P01),(x2,P02)做插值,上式即是拉格朗日二次插值多项式。两个线性插值的结果再进行线性插值，得到抛物线性插值。,三个节点的情形写成表格的形式,4.3.2埃特金算法两个线性插值的结果，再进行线性插值可得抛物线插值，这个过程可以继续下去，一般地，利用两个次插值和进行线性插值，可得次插值，用基函数的形式表示当，时，得到，当，时，得到，当，时，得到。反复执行这一算式，可以逐步构造出如下的插值顺序。按这个顺序可求出某点的插值。,埃特金插值表,埃特金插值特点,埃特金插值是将一个高次插值过程归结为线性插值的多次重复。埃特金插值的每个数据均为插值结果，从这些数据的一致程度即可判断插值结果的精度。这样可以逐步生成插值结果，每做一步检查一下计算结果的精度，如不满足要求，则增加一个节点再算，直到满足要求为止。在节点较多时，用这种方法可降低插值次数,的近似值为1.5。,已知f(x)在三个互异点0,1,2的函数值1,3,9用（0,1),(1,3)作插值,用（0,1),(2,9)作插值,用（1,P01),(2,P02)作插值,一般得到的观测数据本身不一定完全可靠，个别数据的误差甚至可能很大，且数据很多。曲线拟合是从已知的一大堆数据中找出规律，即设法构造一条曲线（拟合曲线）反映数据点总的趋势。,第五章曲线拟合的最小二乘法,曲线拟合问题,曲线拟合同插值法的区别:曲线拟合考虑实验数据带有测量误差，同时测量数据又多，若用插值法时得到的插值多项式次数将很高，不实用。曲线拟合得到的多项式不必通过每一点。,设已知某物理过程（函数关系）的一组观测（实验）数据，要求在某特定函数类（例如多项式）中找出一个函数，作为的近似函数，使得在上的误差（或称残差）按某种度量标准为最小，这就是拟合问题，也称曲线拟合。,曲线拟合的定义,一、最小二乘拟合原理,最小二乘法的几何意义,求在给定点x0,x1,xm处与点(x0,y0),(x1,y1),(xm,ym)的距离平方和最小的曲线：y=F(x),二、多项式拟合,这样的曲线拟合叫多项式拟合。满足上式的y叫最小二乘拟合多项式.特别地,当m=1时,一次多项式拟合又叫直线拟合。当N=m+1时，所得的拟合多项式就是拉格朗日或牛顿插值多项式。,目标函数,由求极值的必要条件,得,即,对a0偏导,对a1偏导,例,上述方程组是关于aj的线性方程组，通常称为正则方程组。它有唯一解。由方程组可求出系数aj。,多项式拟合的一般方法可归纳为以下几步：,写出正则方程组，求出系数，得到拟合多项式,由已知数据画出函数粗略的图形散点图，确定拟合多项式的次数m；,列表计算,解：把表中数据画在坐标纸上，会看到数据点的分布可用一条直线来近似描述。因此用线性函数拟合。,列表如下,正规方程组为,解方程组得,得正规方程组,解得,故拟合多项式为,三、超定方程组的最小二乘解,当方程组中方程的个数多于未知量的个数时，称此方程组为超定方程组。一般来说，超定方程组无解（此时为矛盾方程组），这时需要寻找方程组的一个“最近似”的解。,设线性方程组,(mn),把方程组写成矩阵形式,如果有向量x使得,达到最小，则称x为超定方程组的最小二乘解。,定义残差向量,取目标函数,曲线拟合的最小二乘法可以看成求超定方程组的最小二乘解的问题。,利用矩阵运算可得,从而有正则方程组,解以上方程组可得超定方程组的解。,将给定的数据(xi,yi)(i=1,n),代入m次多项式,得到矛盾方程组,写成矩阵形式,对应正则方程组,求正则方程组可得到所给数据的拟合多项式。,要求熟练掌握的内容：线性插值、抛物线插值的算法。拉格朗日插值多项式的构成，基函数及其特点；最小二乘法拟合原理及多项式拟合的算法。要求掌握的内容：拉格朗日插值多