第三章 函数逼近与曲线拟合

第三章 函数逼近与曲线拟合1 函数的逼近与基本概念1.1问题的提出多数计算机的硬件系统只提供加、减、乘、除四种算术运算指令，因此为了计算大多数有解析表达式的函数的值，必须产生可用四则运算进行计算的近似式，一般为多项式和有理分式函数.实际上，我们已经接触到两种逼近多项式，一种是泰乐多项式，一种是插值多项式.泰乐多项式是一种局部方法，误差分布不均匀，满足一定精度要求的泰乐多项式次数太高，不宜在计算机上直接使用.例如，设()f x 是[1,1]-上的光滑函数，它的Taylor 级数0()k k k f x a x ∞==∑，()(0)!k k f a k =在[1,1]-上收敛。

当此级数收敛比较快时，11()()()n n n n e x f x s x a x ++=-≈。

这个误差分布是不均匀的。

当0x =时，(0)0n e =，而x 离开零点增加时，()n e x 单调增加，在1x =±误差最大。

为了使[1,1]-的所有x 满足()()n f x s x ε-<，必须选取足够大的n ，这显然是不经济的。

插值函数出现的龙格现象表明，非节点处函数和它的插值多项式相差太大。

更重要的是，实际中通过观测得到的节点数据往往有各种误差，此时如果要求逼近函数过全部节点，相当于保留全部数据误差，这是不适宜的。

如图1所示，给出五个点上的实验测量数据，理论上的结果应该满足线性关系，即图1中的实线。

由于实验数据的误差太大，不能用过任意两点的直线逼近函数。

如果用过5个点的4次多项式逼近线性函数，显然误差会很大。

实验数据真函数插值多项式逼近精确的线性逼近图11.2范数与逼近一、线性空间及赋范线性空间要深入研究客观事物，不得不研究事物间的内在联系，给集合的元素之间赋予某种“确定关系”也正是这样的道理.数学上常把在各种集合中引入某些不同的确定关系称为赋予集合以某种空间结构，并将这样的集合称为空间.最常用的给集合赋予一种“加法”和“数乘”运算，使其构成线性空间.例如将所有实n 维数对组成的集合，按照“加法”和“数乘”运算构成实数域上的线性空间，记作n R ，称为n 维向量空间.类似地，对次数不超过n 的实系数多项式全体，按通常多项式与多项式加法及数与多项式乘法也构成数域R 上一个线性空间，用n H 表示，称为多项式空间.所有定义在[,]a b 上的连续函数集合，按函数加法和数与函数乘法构成数域R 上的线性空间，记作[,]C a b .类似地，记[,]p C a b 为具有p 阶连续导数的函数空间.在实数的计算问题中，对实数的大小、距离及误差界等是通过绝对值来度量的.实践中，我们常常会遇到对一般线性空间中的向量大小和向量之间的距离进行度量的问题，因此有必要在一般线性空间上，赋予“长度”结构，使线性空间成为赋范线性空间.定义1 设X 是数域K 上一个线性空间，在其上定义一个实值函数，即对于任意,x y X ∈及K α∈，有对应的实数x 和y ，满足下列条件(1) 正定性：0x ≥，而且0x =当且仅当0x =；(2) 齐次性：x x αα=；(3) 三角不等式：x y x y +≤+；称为X 上的范数，定义了范数的线性空间就称为赋范线性空间.以上三个条件刻划了“长度”、“大小”及“距离”的本质，因此称为范数公理.对n X 上的任一种范数，n X ∀∈x,y ，显然有±≥-x y x y .n R 上常用的几种范数有：(1) 向量的∞-范数：1max i i nx ∞≤≤=x(2) 向量的1-范数：11n i i x ==∑x(3) 向量的2-范数：12221()n i i x ==∑x (4) 向量的p -范数：11()n p pi p i x ==∑x其中[1,)p ∈∞，可以证明向量函数()p N x x ≡是nR 上向量的范数. 前三种范数是p -范数的特殊情况（lim p p ∞→∞=x x ）.我们只需表明(1).事实上1111111max max max n n p pp p i i i i i n i n i n i i x x x x ≤≤≤≤≤≤==⎛⎫⎛⎫≤≤≤ ⎪ ⎪⎝⎭⎝⎭∑∑及max 1p →∞=，故由数学分析的夹逼定理有1l i m ma x i p p i nx ∞→∞≤≤==x x 。

第三章 曲线拟合与函数逼近一．曲线拟合 1.问题提出：已知多组数据(),,1,2,,i i x y i N =，由此预测函数()y f x =的表达式。

数据特点：（1）点数较多。

（2）所给数据存在误差。

解决方法：构造一条曲线反映所给数据点的变化总趋势，即所谓的“曲线拟合”。

2.直线拟合的概念 设直线方程为y=a+bx 。

则残差为：ˆi i i e y y =-,1,2,,i N =，其中ˆi i ya bx =+。

残差i e 是衡量拟合好坏的重要标志。

可以用MATLAB 软件绘制残差的概念。

x=1:6;y=[3,4.5,8,10,16,20];p=polyfit(x,y,1); xi=0:0.01:7; yi=polyval(p,xi); plot(xi,yi,x,y, 'o'); y1=polyval(p,x); hold on for i=1:6plot([i,i],[y(i),y1(i)], 'r');end可以绘制出如下图形：三个准则： （1）max i e 最小 （2）1ni i e =∑最小（3）21N i i e =∑最小3.最小二乘法的直线拟合问题：对于给定的数据点(),,1,2,,i i x y i N =，求一次多项式y=a+bx ，使得总误差Q 最小。

其中()2211NNi i i i i Q e y a bx ====-+⎡⎤⎣⎦∑∑。

根据0,0.Q Qa b∂∂==∂∂ 22221222Ni i i i i i i Q y a b x y a y x b x ab =⎡⎤=++--+⎣⎦∑[]()12222Ni i i i i Q a y x b Na y b x a =∂=-+=-+∂∑∑∑ ()2212222Ni i i i i i i i i Q bx y x x a b x x y a x b =∂⎡⎤=-+=-+⎣⎦∂∑∑∑∑ 故有以下方程组（正则方程）：2i iii i i aN b x y a x b x x y ⎧+=⎪⎨+=⎪⎩∑∑∑∑∑ 例1.给定数据表，求最小二乘拟合一次多项式解：N=5，51i i x =∑=702，51i i y =∑=758，521i i x =∑=99864，51i i i x y =∑=108396。

---------------------------------------------------------------最新资料推荐------------------------------------------------------第三章函数逼近与快速傅里叶变换曲线拟合与最小二乘法第三章函数逼近与快速傅里叶变换曲线拟合与最小二乘法线性最小二乘拟合多项式拟合超定方程组的最小二乘解3.1 曲线拟合与最小二乘法一、拟合问题设变量 x, y 通过观测得 m 对数据我们希望用 m 对数据构造一个近似函数)(xp. 由于观测数据都带有观测误差, 而且一般m 也比较大, 用插值方法要求)(xp严格经过数据点不可取. 于是, 我们希望寻找的近似函数)(xp在各个 xi的函数值)(ixp与观测值yi尽可能接近, 这就是所谓的数据拟合问题. 二、最小二乘法的基本原理从整体考虑近似函数)(xp与所给数据点()),, 2 , 误差的大小，常用的方法有以下三种：一是误差绝对值的最大值imir0max，即误差向量的范数；二是误差绝对值的和=miir0||，即误差向量 r 的 1-范数；三是误差平方和=miir02的算术平方根，即考虑误差向量 r 的 2范数；前两种方法简单、自然，但不便于微分运算，后一种方法相当于考虑 2范数的平方，因此在曲线拟合中常采用误差平方和=miir02来度量误差的整体大小。

数据拟合的具体作法：1 / 11对给定数据，在取定的函数类中,求 )(xp, 使误差的平方和最小，即min])([0202==i=i=miimiyxpr 从几何意义上讲，就是寻求与给定点的距离平方和为最小的曲线)(xpy =。

函数)(xp称为拟合函数或最小二乘解，求拟合函数)(xp的方法称为曲线拟合的最小二乘法。

在曲线拟合中，函数类可有不同的选取方法. 多项式拟合形式比较规范，方法也比较简单，但在实际应用中，针对所讨论问题的特点，拟合函数可能为其他类型，如指数函数、有理函数、三角函数等，这就是一般最小二乘拟合问题。

函数逼近与曲线拟合3.１函数逼近的基本概念3.1.1 函数逼近与函数空间在数值计算中常要计算函数值，如计算机中计算基本初等函数及其他特殊函数；当函数只在有限点集上给定函数值，要在包含该点集的区间上用公式给出函数的简单表达式，这些都涉及到在区间上用简单函数逼近已知复杂函数的问题，这就是函数逼近问题．上章讨论的插值法就是函数逼近问题的一种．本章讨论的函数逼近，是指“对函数类Ａ中给定的函数，记作，要求在另一类简单的便于计算的函数类Ｂ中求函数，使与的误差在某种度量意义下最小”．函数类Ａ通常是区间上的连续函数，记作，称为连续函数空间，而函数类Ｂ通常为n次多项式，有理函数或分段低次多项式等．函数逼近是数值分析的基础，为了在数学上描述更精确，先要介绍代数和分析中一些基本概念及预备知识．数学上常把在各种集合中引入某些不同的确定关系称为赋予集合以某种空间结构，并将为样的集合称为空间．例如将所有实n维向量组成集合，按向量加法及向量与数的乘法构成实数域上的线性空间，记作，称为n维向量空间．类似地，对次数不超过n（n为正整数）的实系数多项式全体，按通常多项式与多项式加法及数与多项式乘法也构成数域上的一个线性空间，用表示，称为多项式空间．所有定义在上的连续函数集合，按函数加法和数与函数乘法构成数域上的线性空间，记作．类似地，记为具有p阶的连续导数的函数空间．定义１设集合Ｓ是数域Ｐ上的线性空间，元素，如果存在不全为零的数，使得， (3.1.1)则称线性相关．否则，若等式(3.1.1)只对成立，则称线性无关．若线性空间Ｓ是由n个线性无关元素生成的，即对都有则称为空间Ｓ的一组基，记为，并称空间Ｓ为n维空间，系数称为x在基下的坐标，记作，如果Ｓ中有无限个线性无关元素，…，则称Ｓ为无限维线性空间．下面考察次数不超过n次的多项式集合，其元素表示为， (3.1.2）它由个系数唯一确定．线性无关，它是的一组基，故，且是的坐标向量，是维的．对连续函数，它不能用有限个线性无关的函数表示，故是无限维的，但它的任一元素均可用有限维的逼近，使误差（为任给的小正数），这就是著名的Weierstrass定理．定理１（Weierstrass）设，则对任何，总存在一个代数多项式，使在上一致成立．这个定理已在“数学分析”中证明过．这里需要说明的是在许多证明方法中，伯恩斯坦１９１２年给出的证明是一种构造性证明．他根据函数整体逼近的特性构造出伯恩斯坦多项式， (3.1.3)其中，其中，并证明了在上一致成立；若在上阶导数连续，则．这不但证明了定理１，而且由(3.1.3)给出了的一个逼近多项式．它与拉格朗日插值多项式很相似，对，当＝１时也有关系式． (3.1.4)这只要在恒等式中令就可得到．但这里当时还有，于是是有界的，因而只要对任意成立，则有界，故是稳定的．至于拉格朗日多项式，由于无界，因而不能保证高阶插值的稳定性与收敛性．相比之下，多项式有良好的逼近性质，但它收敛太慢，比三次样条插值效果差得多，实际中很少被使用．更一般地，可用一组在上线性无关的函数集合来逼近，元素，表示为． (3.1.5) 函数逼近问题就是对任何，在子空间中找一个元素，使在某种意义下最小．3.1.2 范数与赋范线性空间为了对线性空间中元素大小进行衡量，需要引进范数定义，它是空间中向量长度概念的直接推广．定义2.1.2 设为线性空间，，若存在唯一实数，满足条件：（1）正定性：，（2）当且仅当时，（3）；（4）齐次性：，（5）；（6）三角不（7）等式：，（8）．则称为线性空间上的范数，与一起称为赋范线性空间，记为．例如，在上的向量，三种常用范数为类似地对连续函数空间，若可定义三种常用范数如下：可以验证这样定义的范数均满足定义3.1.2中的三个条件．3.1.3 内积与内积空间在线性代数中，中两个向量及的内积定义为．若将它推广到一般的线性空间，则有下面的定义．定义3.1.3设是数域上的线性空间，对，有中一个数与之对应，记为，它满足以下条件：（１）；（２）；（３）；（４），当且仅当时，．则称为上与的内积．定义了内积的线性空间称为内积空间．定义中（１）的右端称为的共轭，当为实数域时．如果＝０，则称与正交，这是向量相互垂直的概念的推广．关于内积空间性质有以下重要定理．定理3.1.2设为一个内积空间，对，有(3.1.6) 称为Cauchy-Schwarz不等式．［证明］当时(3.1.6)式显然成立．现设，则，且对任何数有．取，代入上式右端，得，即得时．定理证毕定理3.1.2设为一个内积空间，，矩阵（3.1.7）称为Gram矩阵，则Ｇ非奇异的充分必要条件是线性无关．［证明］Ｇ非奇异等价于，其充分必要条件是齐次方程组(3.1.8) 只有零解．而(3.1.9) 从以上的等价关系可知，等价于从(3.1.8)推出．而后者等价于从(3.1.9)推出，即线性无关．定理证毕在内积空间上可以由内积导出一种范数，即对于，记(3.1.10) 容易验证它满足范数定义的三条性质，其中三角不等式(3.1.11)可由定理3.1.2直接得出，即两端开方即得(3.1.11）．例１与的内积．设，，，则其内积定义为(3.1.12)由此导出的向量２－范数为．若给定实数，称为权系数，则在上可定义加权内积为(3.1.13)相应的范数为．不难验证(3.1.13)给出的满足内积定义的４条性质，当时，(3.1.13)就是(3.1.12)．如果，带权内积定义为(3.1.14) 这里仍为正实数序列，为的共轭．在上也可以类似定义带权内积，为此先给出权函数的定义．定义３.1.4 设是有限或无限区间，在上的非负函数满足条件：（１）存在且为有限值；（２）对上的非负连续函数，如果，则．则称为上的一个权函数．例２上的内积．设，是上给定的权函数，则可定义内积． (3.1.15)容易验证它满足内积定义的４条性质，由此内积导出的范数为． (3.1.16)称(3.1.15)和(3.1.16)为带权的内积和范数．特别常用的是的情形，即若是中的线性无关函数族，记，它的Gram矩阵为(3.1.17)根据定理3.1.3可知线性无关的充分必要条件是．3.2 正交多项式正交多项式是函数逼近的重要工具，在数值积分中也有着重要的应用．3.2.1 正交函数族与正交多项式定义3.2.1 若，为上的权函数且满足， (3.2.1)则称与在上带权正交．若函数族满足关系(3.2.2)则称是上带权的正交函数族；若，则称之为标准正交函数族．例如，三角函数族就是在区间上的正交函数族．因为对有，而对，当时有定义3.2.2 设是上首项系数的次多项式，为上权函数，如果多项式序列满足关系式(3.2.2)，则称多项式序列为在上带权正交，称为上带权的次正交多项式．只要给定区间及权函数，均可由一族线性无关的幂函数，利用逐个正交化手续构造出正交多项式序列；，(3.2.3) 这样得到的正交多项式序列有以下性质：（１）是具有最高次项系数为１的次多项式．（２）任何次多项式均可表示为的线性组合．（３）当时，，且与任一次数小于的多项式正交．（４）成立递推关系．其中这里．（５）设是在上带权的正交多项式序列，则的个根都是在区间内的单重实根．3.2.2 勒让德多项式当区间为［－１，１］，权函数时，由正交化得到的多项式就称为勒让德(Legendre)多项式，并用表示．这是勒让德于１７８５年引进的，１８１４年罗德利克(Rodrigul)给出了简单的表达式由于是２次的多项式，求阶导数后得，于是得首项系数为，显然最高项系数为１的勒让德多项式为．(3.2.6) 勒让德多项式有下述几个性质：性质１正交性(3.2.7) ［证明］令，则．设是在区间[-1,1]上的阶连续可微的函数，由分部积分知下面分两种情况讨论：（１）若是次数小于的多项式，则，故得（２）若，则，于是由于，故，于是(3.2.7)得证．性质２奇偶性（3.2.8）［证明］由于是偶次多项式，经过偶次求导仍为偶次多项式，经过奇次求导则为奇次多项式，故为偶数时为偶函数，为奇数时为奇函数，于是(3.2.8)成立．性质３递推关系(3.2.9) ［证明］考虑＋１次多项式，它可表示为两边乘以，并从－１到１积分，得．当时，的次数小于－１，上式左端积分为０，故得．当时．为奇函数，左端积分仍为０，故．于是．其中，代入上式整理可得(3.2.9)．例１由利用性质３可得性质４在区间[-1,1]内有个不同的实零点．3.2.3 切比雪夫多项式当权函数，区间为[-1,1]时，由序列正交化得到的多项式就称为切比雪夫(Chebyshev)多项式，它可表示为(3.2.10)若令，则．切比雪夫多项式有很多重要性质：性质１递推关系(3.2.11) 这只要由三角不等式．令即得．由(3.2.11)就可推出由递推关系(3.2.11)还可得到的最高次项系数是．性质６切比雪夫多项式在区间［－１，１］上带权正交，且(3.2.12) 事实上，令，则，于是性质７只含的偶次幂，只含有的奇次幂．这性质由递推关系直接得到．性质８在区间［－１，１］上的个零点此外，实际计算中时常要求用的线性组合，其公式为． (3.2.13) 例如：结果如下：3.2.4 其他常用的正交多项式一般说，如果区间及权函数不同，则得到的正交多项式也不同．除上述两种最重要的正交多项式外，下面再给出三种较常用的正交多项式．第二类切比雪夫多项式在区间［－１，１］上带权的正交多项式称为第二类切比雪夫多项式，其表达式为． (3.2.14)令，可得即是［－１，１］上带权的正交多项式族．还可得到递推关系式．拉盖尔多项式在区间上带权的正交多项式称为拉盖尔（Laguerre）多项式，其表达式为. (3.2.15)其正交性为和递推关系．３. 埃尔米特多项式在区间上带权的正交多项式称为埃尔米特多项式．其表达式为， (3.2.16)其正交性为递推关系为．3.3 最佳一致逼近多项式3.3.1 基本概念及其理论本节讨论，在中求多项式，使其误差．这就是通常所谓最佳一致逼近或切比雪夫逼近问题．为了说明这一概念，先给出以下定义．定义3.3.1 设，，称． (3.3.1) 为与在上的偏差．显然，的全体组成一个集合，记为｛｝，它有下界０．若记集合的下确界为(3.3.2)则称之为在上的最小偏差．定义3.3.2 假定，若存在，使得， (3.3.3)则称是在上的最佳一致逼近多项式或最小偏差逼近多项式，简称最佳逼近多项式．注意，定义并未说明最佳逼近多项式是否存在，但可证明下面的存在定理．定理４若，则总存在，使．为了研究最佳逼近多项式的特性，先引进偏差点的定义．定义3.3.3设，，若在上有，就称是的偏差点．若，称为“正”偏差点．若，称为“负”偏差点．由于函数在上连续，因此，至少存在一个点，使，也就是说的偏差点总是存在的．下面给出反映最佳逼近多项式特征的切比雪夫定理．定理3.3.2是的最佳逼近多项式的充分必要条件是在上至少有个轮流为“正”、“负”的偏差点，即有个点，使． (3.3.4) 这样的点组称为切比雪夫交错点组．［证明］只证充分性．假定在上有个点使(3.3.4)成立，要证明是在上的最佳逼近多项式．用反证法，若存在，使．由于在点上的符号与一致，故也在个点上轮流取“＋”、“－”号．由连续性质，它在内有个零点，但因是不超过次的多项式，它的零点不超过．这矛盾说明假设不对，故就是所求最佳逼近多项式．充分性得证，必要性证明略，可参看［５］．定理５说明用逼近的误差曲线是均匀分布的．由这定理还可得以下重要推论．推论１若，则在中存在唯一的最佳逼近多项式．证明略．利用定理５可直接得到切比雪夫多项式的一个重要性质，即定理3.3.3 在区间［－１，１］上所有最高次项系数为１的次多项式中与零的偏差最小，其偏差为．［证明］由于，且点是的切比雪夫交错点组，由定理５可知，区间［－１，１］上在中最佳逼近多项式为，即是与零的偏差最小的多项式．定理证毕例３求在［－１，１］上的最佳２次逼近多项式．解由题意，所求最佳逼近多项式应满足由定理3.3.3可知，当时，多项式与零偏差最小，故就是在［－１，１］上的最佳２次逼近多项式．3.3.2 最佳一次逼近多项式定理3.3.2给出了最佳逼近多项式的特性，但要求出却相当困难．下面讨论的情形．假定，且在内不变号，我们要求最佳一次逼近多项式．根据定理3.3.2可知至少有３个点，使由于在内不变号，故单调，在内只有一个零点，记为，于是，即．另外两个偏差点必是区间端点，即，且满足由此得到(3.3.5) 解出， (3.3.6) 代入(3.3.5)得． (3.3.7)这就得到了最佳一次逼近多项式，其几何意义如图３－３所示．直线与弦MN平行，且通过MQ的中点D，其方程为．图３－３一次最佳一致逼近多项式几何意义例4 求在上的最佳一次逼近多项式。

第三章 函数逼近与曲线拟合1 函数的逼近与基本概念1.1问题的提出多数计算机的硬件系统只提供加、减、乘、除四种算术运算指令，因此为了计算大多数有解析表达式的函数的值，必须产生可用四则运算进行计算的近似式，一般为多项式和有理分式函数.实际上，我们已经接触到两种逼近多项式，一种是泰乐多项式，一种是插值多项式.泰乐多项式是一种局部方法，误差分布不均匀，满足一定精度要求的泰乐多项式次数太高，不宜在计算机上直接使用.例如，设()f x 是[1,1]-上的光滑函数，它的Taylor 级数0()kk k f x a x∞==∑，()(0)!k k f a k =在[1,1]-上收敛。

当此级数收敛比较快时，11()()()n n n n e x f x s x a x ++=-≈。

这个误差分布是不均匀的。

当0x =时，(0)0ne=，而x 离开零点增加时，()n e x 单调增加，在1x =±误差最大。

为了使[1,1]-的所有x 满足()()nf x s x ε-<，必须选取足够大的n ，这显然是不经济的。

插值函数出现的龙格现象表明，非节点处函数和它的插值多项式相差太大。

更重要的是，实际中通过观测得到的节点数据往往有各种误差，此时如果要求逼近函数过全部节点，相当于保留全部数据误差，这是不适宜的。

如图1所示，给出五个点上的实验测量数据，理论上的结果应该满足线性关系，即图1中的实线。

由于实验数据的误差太大，不能用过任意两点的直线逼近函数。

如果用过5个点的4次多项式逼近线性函数，显然误差会很大。

1.2范数与逼近实验数据 真函数 插值多项式逼近 精确的线性逼近图1一、线性空间及赋范线性空间要深入研究客观事物，不得不研究事物间的内在联系，给集合的元素之间赋予某种“确定关系”也正是这样的道理.数学上常把在各种集合中引入某些不同的确定关系称为赋予集合以某种空间结构，并将这样的集合称为空间。

最常用的给集合赋予一种“加法”和“数乘”运算，使其构成线性空间.例如将所有实n 维数对组成的集合，按照“加法”和“数乘”运算构成实数域上的线性空间，记作n R ，称为n 维向量空间.类似地，对次数不超过n 的实系数多项式全体，按通常多项式与多项式加法及数与多项式乘法也构成数域R 上一个线性空间，用nH 表示，称为多项式空间。