数值分析06-函数逼近.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,阜师院数科院,第六章 函数逼近,6-,*,W Y,第六章,函数逼近,（,曲线拟合）,6-,1,阜师院数科院,第六章 函数逼近,第六章目录,1,最小二乘法原理和多项式拟合,2,一般最小二乘拟合,2.1,线性最小二乘法的一般形式,2.2,非线性最小二乘拟合,3,正交多项式曲线拟合,3.1,离散正交多项式,3.2,用离散正交多项式作曲线拟合,4,函数的最佳平方逼近,5,最佳一致逼近,2,阜师院数科院,第六章 函数逼近,函数逼近,（曲线拟合）,概述,用简单的计算量小的函数,P,(,x,),近似地替代,给定的函数,f,(,x,),（,或者是以离散数据形式给,定的函数），以便迅速求出函数值的近似值,，是计算数学中最基本的概念和方法，称为,函数逼近,。通常被逼近的函数一般较复杂，,或只知道离散点处的值，难于分析，而逼近,函数则比较简单，如选用多项式，有理函数,，分段多项式，三角多项式等。,3,阜师院数科院,第六章 函数逼近,函数逼近,（曲线拟合）,概述（续）,在大量的实验数据,(,x,i,y,i,)(,i,=1,2,n,),中寻找其函数关系,y,=,f,(,x,),的近似函数,P,(,x,),，,是在实践中常遇到的。上一章介,绍的插值方法就是一种逼近，要求在给定的节点处,P,(,x,),与,f,(,x,),相等（甚至导数值相等），因此在节点附近，逼近效,果较好，而在远离节点的地方，由,Runge,现象,知道，有时,效果会很差，另一方面，由观测得到的实验数据不可避免,地带有误差，甚至是较大的误差，此时要求近似函数,P,(,x,),过全部已知点，相当于保留全部数据误差，所以使用插值,法不合适。因此，对逼近函数,P,(,x,),不必要求过给定的点，,即不要求,P,(,x,i,)=,y,i,(,i,=1,2,n,),，,只要求,P,(,x,i,),y,i,总体上尽,可能小,即要求,P,(,x,),尽可能反映给定数据点的,总体趋势,，,在某种意义（要求或标准）下与函数最“,逼近,”。,下面先举例说明。,4,阜师院数科院,第六章 函数逼近,函数逼近举例,给定一组实验数据如上，求,x,y,的函数关系。,例,1,1,2,3,4,2,4,6,8,1.1,2.8,4.9,7.2,i,x,i,y,i,解,先作草图如图,6-1,所示这些点的分布接近一条直线，因,此可设想，,y,为,x,的一次函数。设,y,=,a,0,+,a,1,x,，,从图中不难看,出，无论,a,0,，,a,1,取何值，直线都不可能同时过全部数据点。,怎样选取,a,0,，,a,1,才能使直线“最好”地反映数据点的总体趋,势？首先要建立好坏的标准。,假定,a,0,，,a,1,已经确定，,y,i,*=,a,0,+,a,1,x,i,(,i,=1,2,n,),是由近似,函数求得的近似值，它与观测值,y,i,之差,r,i,=,y,i,y,i,*=,y,i,a,0,a,1,x,i,(,i,=1,2,n,),称为,偏差,。显然，,偏差的大小可作为衡量近似函数好坏的标准。偏差向量,r,=(,r,1,r,2,r,n,),T,，,y,x,8,6,4,2,2,4,6,8,*,*,*,*,图,6-1,5,阜师院数科院,第六章 函数逼近,例,1,（续）,（,1,）,使偏差的绝对值,之和最小，即,:,（,2,）,使偏差的最大绝对 值达到最小，即,:,（,3,）,使偏差的平方和最小，即,:,在离散情况下,也称为曲线拟合的最小二乘法,是实践中常用的一种函数逼近方法。,常用的,准则,有以下三种：,准则,（,1,）,的提出很自然也合理，但实际使用不方便，,按准则,（,2,）,求近似函数的方法称为函数的最佳一致逼近；,按准则,（,3,）,确定参数，求近似函数的方法称为最佳平方逼近,r,i,=,y,i,y,i,*=,y,i,a,0,a,1,x,i,6,阜师院数科院,第六章 函数逼近,函数的近似替代，求近似函数称为逼近,要求（准则或标准）不一样，逼近的意义不一样，因此，方法不一样，结果也不一样。,插值是逼近，满足条件,L,n,(,x,i,)=,y,i,是,在“过给定点”意义下的逼近。,要求,L,n,(,x,i,)-,y,i,总体上尽可能小,称为最佳平方逼近,在离散情况下,也称为曲线拟合的最小二乘法,.,7,阜师院数科院,第六章 函数逼近,1,最小二乘法原理和多项式拟合,一、曲线拟合的最小二乘法基本原理,对给定的数据,(,x,i,y,i,)(,i,=1,2,n,),，,选取近似函数形式，,即在给定的函数类,中，求函数,(,x,),，,使偏差,r,i,=,(,x,i,),y,i,(,i,=1,2,n,),的平方和为最小，即,:,亦即,:,从几何上讲，就是求在给定的点,x,1,x,2,x,n,处与点,(,x,1,y,1,),(,x,2,y,2,),(,x,n,y,n,),的距离平方和最小的曲线,y,=,(,x,),。,这种求,近似函数的方法称为离散数据曲线拟合的最小二乘法，函,数,(,x,),称为这组数据的最小二乘拟合函数。通常取,为一,些较简单函数的集合如低次多项式，指数函数等。例,1,中取,为一次多项式集合。,8,阜师院数科院,第六章 函数逼近,二、多项式拟合,对于给定的一组数据,(,x,i,y,i,)(,i,=1,2,n,),，,求一多项式,(,m,n,),使得,:,为最小，即选取参数,a,j,(,j,=0,1,m,),使得,:,其中,为不超过,m,次多项式的集合。这就是数据的多项,式拟合，,P,m,(,x,),称为这组数据的,m,次拟合多项式。,与求解矛盾线性方程组的最小二乘法的方法相同，由多,元函数求极值的必,要条件，得方程组,:,移项得,:,（紧接下屏）,9,阜师院数科院,第六章 函数逼近,多项式拟合（续）,打开和式,即：,这是最小二乘拟合多项式的系数,a,k,(,k,=0,1,m,),应满足的方程组，,称为正规方程组或法方程组。由函数组,1,x,x,2,x,m,的线性无关性可,以证明，上述法方程组存在唯一解，且解所对应的,m,次多项式,P,m,(,x,),必定是已给数据,(,x,i,y,i,)(,i,=1,2,n,),的最小二乘,m,次拟合多项式。,如图,6-1,表明，可用一次多项式,P,1,(,x,)=,a,0,+,a,0,x,拟合例,1,中数据组所,给定的函数关系，将所给数据代入正规方程组可得：,其解为,a,0,=,1.1,a,1,=1.02,，,所以：,y,=,1.1+1.02,x,就是所给数据组,的最小二 乘拟合多项式。,10,阜师院数科院,第六章 函数逼近,最小二乘二次拟合多项式举例,例,2,求,下面数据表的最小二乘二次拟合多项式：,i,1,2,3,4,5,6,7,8,9,x,i,-1,-0.75,-0.5,-0.25,0,0.25,0.5,0.75,1,y,i,-0.2209,0.3295,0.8826,1.4392,2.0003,2.5645,3.1334,3.7601,4.2836,解：设二次拟合多项式,为,P,2,(,x,)=,a,0,+,a,1,x,+,a,2,x,2,，,将数据表直接代 入正,规方程组：,其解为,a,0,=2.0034,a,1,=2.2625,a,2,=0.0378,。,所以此数据组的,最小二乘二次拟合多项式为：,11,阜师院数科院,第六章 函数逼近,2,一般最小二乘拟合,上节介绍了,多项式拟合,问题及其解法。在实际应用中，针对所讨论问题的特点，,拟合函数可能为其他类型的函数，如指数函数，三角函数，有理函数等,，,待定参数也可能会出现在指数上，分母中等,，对,观测数据，由于它们的精度不一样，还会引入权系数,，这都属于一般,最小二乘拟合问题,。,12,阜师院数科院,第六章 函数逼近,2.1,线性最小二乘法的一般形式,作两个推广：,1.,函数系由,x,m,m,(,x,),线性无关,2.,加权系数,i,(,i,=1,2,n,),即对,(,x,i,y,i,)(,i,=1,2,n,),选取函数,(,x,),：,达到最小，对,a,j,求,偏导数令其为,0,正规方程组：,13,阜师院数科院,第六章 函数逼近,正规方程组,的几种形式：,首先，可用向,量和矩阵表示,正规方程组,正规方程组的几种形式,如果,G,的列向量线性无关，则正规方程组存在唯一解向量,a,，,从而可确定：,14,阜师院数科院,第六章 函数逼近,其次可引进,内积,表示正规方程组：,正规方程组的几种形式（续）,15,阜师院数科院,第六章 函数逼近,正规方程组的几种形式（续）,k,(,x,),线性无关,系数矩阵非奇异,唯一解,:,令,j,=0,1,2,m,，,则正规方程组为,:,在,(6-4),中打开和式,16,阜师院数科院,第六章 函数逼近,最小二乘拟合函数,定理,定理,2,17,阜师院数科院,第六章 函数逼近,定理,2,（续）,所以,(,x,),是数据组,(,x,i,y,i,)(,i,=1,2,n,),的最小二乘拟合函数。,特别地，当取,k,(,x,)=,x,k,(,k,=1,2,m,),时，即为多项式拟合，所以多项式拟合为一般线性最小二乘拟合的一种特殊情况。,注意到,(,x,),与,(,x,),的表示式，由正规方程组，,上式中 间项为：,18,阜师院数科院,第六章 函数逼近,最小二乘法求其拟合函数,举例,例,3,已知一组数据如表，用最小二乘法求其拟合函数。,x,0,0.1,0.2,0.3,0.4,0.5,0.6,y,2,2.20254,2.40715,2.61592,2.83096,3.05448,3.28876,19,阜师院数科院,第六章 函数逼近,最小二乘法求其拟合函数,举例（续）,例,4,已知数据如下表，求一个二次多项式，使之与所给数据拟合：,x,i,-1,-0.5,0,0.5,1,y,i,1,0.495,0.001,0.480,1.01,解：,从函数值的分布情况看，该函数可能为一偶函数，故考虑用,偶次多项式作拟合函数，为此，取,0,(,x,)=1,1,(,x,)=,x,2,于是所求二次,多项式可设为：,(,x,)=,a,0,+,a,1,x,2,而,G,为,:,从此例题看到，通过对数据特,点进行分析，确定选用不带一次项,的二次多项式为拟合函数，不仅符,合原来函数的 特征，而且使 计算,更加简单。可见，在实际问题中选,择 合适的函数类型是十分重要的。,20,阜师院数科院,第六章 函数逼近,2.2,非线性最小二乘拟合,当最小二乘拟合所取函数类,中的函数,F,=,(,x,a,0,a,1,a,m,),关于参数,a,0,a,1,a,m,是非线性时，称为非线性最小二乘拟合问题。,对非线性最小二乘拟合问题，虽然仍可由偏差平方和对,a,j,求偏导生成方程组,:,但是，与线性最小二乘问题不同的是，上述方程组是关于,a,k,(,k,=0,1,m,),的非线性方程组，要求解是很困难的，因此，一般的非线性最小二乘拟合问题不作详细讨论。,21,阜师院数科院,第六章 函数逼近,可化为线性拟合问题的常见函数类,但对于一些较特殊的非线性拟合函数类型，可以通过适当,的变量代换后化为线性最小二乘问题，下表列出了部分这,样的拟合函数类型。,可化为线性拟合问题的常见函数类,:,拟合函数类型 变量代换 化成的拟合函数,22,阜师院数科院,第六章 函数逼近,非线性拟合举例,例,5,在某化学反应里，根据实验所得生成物的浓度与时间,关系数据见下表，求浓度,y,与时间,t,的拟合曲线,y,=,F,(,t,),：,t,i,1,2,3,4,5,6,7,8,y,i,(*10,-3,),4.00,6.40,8.00,8.80,9.22,9.50,9.70,9.86,t,i,9,10,11,12,13,14,15,16,y,i,(*10,-3,),10.00,10.20,10.32,10.42,10.52,10.55,10.58,10.60,解：,将数据标在坐标纸上如,图,6-2,由图看到开始时浓度增加,较快，后来逐渐减弱，到一定时间就基本稳定在一个数值,上。即当,t,时，,y,超于某个定数，故有一水平渐近线。,t,0,时，反应未开始，生成物的浓度为零。根据这些 特,点，可设想,y,=,F,(,t,),是,双曲线型,或,指数型曲线,。,（紧接下屏）,23,阜师院数科院,第六章 函数逼近,非线性拟合举例（续,1,）,可见,y,关于参数,a,b,是非线性的为确定,a,b,可令：,6,10,8,6,4,2,2,y,x,18,16,14,12,10,8,4,0,图,6-2,（,1,）取拟合函数为,双曲线型：,24,阜师院数科院,第六章 函数逼近,非线性拟合举例（续,2,）,则拟合函数化为,y,=,a,+,b t,，,而将数据,(,t,i,y,i,),相应地变,为,(,t,i,y,i,),，,如下表：,t,i,1,1/2,1/3,1/4,1/5,1/6,1/7,1/8,y,i,(*10,-3,),0.2500,0.15625,0.12560,0.11364,0.10846,0.10526,0.10309,0.10142,t,i,1/9,1/10,1/11,1/12,1/13,1/14,1/15,1/16,y,i,(*10,-3,),0.10142,0.09804,0.09690,0.09597,0.09524,0.09479,0.09452,0.09434,25,阜师院数科院,第六章 函数逼近,非线性拟合举例（续,3,）,（,2,）取拟合函数为,指数型,那么，怎样比较两个数学模型的好坏呢？一般可通过比较,拟合函数与所给数据误差大小来确定。对此例可计算得：,同拟合函数为双曲线型过程类似，先由,(,t,i,y,i,),算出相应的,(,t,i,y,i,),，,然后进行多项式拟合，解得,a,=4.48072,b,=,1.05669,，,从而得,a,=,e,a,=1.1325310,2,，,所以拟合函数：,26,阜师院数科院,第六章 函数逼近,非线性拟合举例（续,4,）,而均方误差为：,可见,y,=,F,2,(,t,),的误差比较小，,用它作为拟合曲线更好。,从此例也可看到，选拟合曲线的类型，并不是一开始,就能选好，往往要通过分析若干模型的误差后，再经过实,际计算才能选到较好的模型。,27,阜师院数科院,第六章 函数逼近,3,正交多项式曲线拟合,求解线性最小二乘问题，必须求解正规方程组，然而困,难的是最小二乘法的正规方程组往往是病态的，在（,6-5,）,中，当,k,(,x,)=,x,k,时，正规方程组的系数矩阵：,与矩阵：,（紧接下屏）,28,阜师院数科院,第六章 函数逼近,正交多项式曲线拟合（续）,是病态阵一样，,m,不大时还好，当,m,较大时为病态,阵（,m,太大，大小都为病态的）。因此，在实际应,用时，,m,不能太大，也即曲线拟合的多项式的次数,不会太大，多用低次的。,因此，一般情况下，对线性最小二乘问题，要,得到最小二乘拟合多项式,就面临着要求解病态方,程组这一困难，要克服这一困难。可以选用适用于,病态方程组求解的数值方法如奇异值分解法等去求,解法方程组。也可以通过生标的平移和伸缩变换，,去降低法方程组的病态程度。,本节考虑用,正交多项式,来进行曲线拟合,29,阜师院数科院,第六章 函数逼近,3.1,离散正交多项式,对多项式,k,(,x,),和,j,(,x,),，,式（,6-4,）定义了在离散情况下的,内积：,利用内,积，可以有,:,定义,6.1,如果两个多项式,k,(,x,),、,j,(,x,),满足,:,则称,k,(,x,),与,j,(,x,),在点集,x,1,x,2,x,n,上是带权,i,离散正交的,。设,0,(,x,),1,(,x,),m,(,x,),为多项式系，,k,(,x,),为,k,次多项式,，如果满足,正交条件：,则称,0,(,x,),1,(,x,),m,(,x,),为点集,x,1,x,2,x,n,上的带权,i,的,离散正交多项式系,。,30,阜师院数科院,第六章 函数逼近,这样的,k,(,x,),是首项系数为,1,的,k,次多项式，下面的定理给出了,k,(,x,),的正交性证明。,对于给定的节点,x,1,x,2,x,n,，,可以按下列公式（,称为三项递推式,）构造离散正交多项式系：,0,(,x,),1,(,x,),m,(,x,)(,m,n,),：,离散正交多项式（续）,31,阜师院数科院,第六章 函数逼近,构造离散正交多项式,定理,6.2,按式（,6-6,），（,6-7,）构造的多项式系,0,1,n,是点集,x,1,x,2,x,n,上关于,i,的离散正交多项式。,证明,:,用数学归纳法证明,当,k=1,时,，利用式（,6-6,）中第二式得,:,从而证明了,0,(,x,),与,1,(,x,),的离散正交性,;,（紧接下屏）,32,阜师院数科院,第六章 函数逼近,构造离散正交多项式（续,1,）,由,归纳假设,：对,待证,：,33,阜师院数科院,第六章 函数逼近,定理,6.2,证明（续,2,）,归纳证明,（紧接下屏）,34,阜师院数科院,第六章 函数逼近,定理,6.2,证明（续,2,）,对,j,=1,2,m,-3,，,有,由归纳法原理，对一切自然数，多项式系,0,1,m,满足正交条件，因此是点集,x,i,上关于,i,的正交多项式系。,证毕！,因此对,k,=,m,成立。,35,阜师院数科院,第六章 函数逼近,构造离散多项式举例,例,6,试构造点集,0,1,2,3,4,5,上的离散正交多项式系,0,(,x,),1,(,x,),2,(,x,),3,(,x,),解,：,若没有给出,i,，,一般认为,i,=1,，,由三项递推式（,6-6,）,，（,6-7,）进行构造，计算中，在求出每个,k,(,x,),的同时，,将其在所给节点上的值求出列入表,6-1,中，以便求下一个,k,+1,(,x,),时使用。,x,0,1,2,3,4,5,1,1,1,1,1,1,-2.5,-1.5,-0.5,0.5,1.5,2.5,10/3,-2/3,-8/3,-8/3,-2/3,10/3,表,6-1,36,阜师院数科院,第六章 函数逼近,3.2,用离散正交多项式作曲线拟合,设,(,x,i,y,i,)(,i,=1,2,n,),为给定数据。,i,为对应的权系数,(,i,=1,2,n,),，,若未给出,i,，,则认为,i,=1,，,0,(,x,),1,(,x,),m,(,x,),为点集,x,i,上的离散正交多项式系，,为由其所有线,性组合生成的多项式集合,:,=,Span,0,(,x,),1,(,x,),m,(,x,),使其满足式（,6-2,），利用多项式,0,(,x,),1,(,x,),m,(,x,),的离散正交性易知，此时正规方程组（,6-5,）的系数矩阵为对角阵：,用离散正交多项式进行最小二乘曲线拟合,亦即求：,（紧接下屏）,37,阜师院数科院,第六章 函数逼近,用离散正交多项式作曲线拟合（续）,可见，不用解线性方程组，,可减少含入误差，避免病态,情况出现，直接计算可得,:,这样可总结利用离散正交多项式求给定,(,x,i,y,i,),(,i,=1,2,n,),带权,i,(,i,=1,2,n,),的,拟合多项式的步骤,（逐步构造,k,(,x,),法）：,（紧接下屏）,38,阜师院数科院,第六章 函数逼近,求给定,(,x,i,y,i,),带权,i,的拟合多项式的步骤,1.,按三项递推式（,6-6,）（,6-7,）构造离散正交多项式系,0,(,x,),1,(,x,),m,(,x,),；,2.,按（,6-8,）计算内积并由此得正规方程的解；,3.,按（,6-9,）写出拟合多项式,(,x,),。,39,阜师院数科院,第六章 函数逼近,拟合多项式举例,利用离散正交多项式求例,2,所给数据表的二次拟合,多项式,例,6,解：,按三项递推式及,k,k,的计算公式可得：,而由系数,a,k,的计算公式有：,i,1,2,3,4,5,6,7,8,9,x,i,-1,-0.75,-0.5,-0.25,0,0.25,0.5,0.75,1,y,i,-0.2209,0.3295,0.8826,1.4392,2.0003,2.5645,3.1334,3.7601,4.2836,40,阜师院数科院,第六章 函数逼近,拟合多项式举例（续）,这与例,2,的计算法结果相同，但不必要解正规方程组，,而只需要计算内积，避免出现病态方程组的可能。并且当,逼近次数增加一次时，只需在原有的多项式中增加,一项，即在上例还可求三次、四次拟合多项式。,由此可得最小二乘二次拟合多项式为：,41,阜师院数科院,第六章 函数逼近,第六章,结 束,6-,42,阜师院数科院,第六章 函数逼近,上机练习题：,不同拟合模型的比较,已知观测数据如下表所示，按下述方案,求最小二乘拟合函数,，并求出,偏差平方和,Q,，,比较拟合曲线的优劣。,方案,I,拟合函数取为如下形式的三次多项式：,方案,II,用离散正交多项式求三次拟合多项式,方案,III,用离散正交多项式求四次拟合多项式,方案,IV,拟合函数取为如下形式的函数：,43,阜师院数科院,第六章 函数逼近,x,0,0.2,0.6,1.0,1.3,1.6,1.7,1.8,1.9,y,0,2.5,4.0,5.7,3.5,2.0,1.0,2.0,3.5,x,2.2,2.3,2.5,2.6,2.9,3.1,3.4,3.8,4.1,y,4.0,7.0,7.5,9.9,10.9,11.9,13.5,13.0,11.9,x,4.4,4.7,4.8,4.9,5.0,5.1,5.3,y,9.0,6.5,4.0,1.5,0.0,2.5,5.0,观测数据表,44,阜师院数科院,第六章 函数逼近,