第3章函数逼近与快速傅里叶变换.ppt

《第3章函数逼近与快速傅里叶变换.ppt》由会员分享，可在线阅读，更多相关《第3章函数逼近与快速傅里叶变换.ppt（123页珍藏版）》请在三一文库上搜索。

1、第3章 函数逼近与快速傅里叶变换,3.1 函数逼近的基本概念 3.2 正交多项式 3.3 最佳平方逼近 3.4 曲线拟和的最小二乘法 3.5* 有理逼近 3.6* 三角逼近与快速傅里叶变换,本章基本内容,在数值计算中经常要计算函数值，如计算机中计算基本初等函数及其他特殊函数；当函数只在有限点集上给定函数值，要在包含该点集的区间上用公式给出函数的简单表达式，这些都涉及在区间a, b上用简单函数逼近已知复杂函数的问题，这就是函数逼近问题. 第2章讨论的插值法就是函数逼近的一种.,3.1 函数逼近的基本概念,3.1.1 函数逼近与函数空间,本章讨论的函数逼近，是指“对函数类A中给定的函数f(x)，记

2、作f(x)A，要求在另一类简单的便于计算的函数类B中求函数p(x)B，使 p(x)与 f(x)的误差在某种度量意义下最小”. 函数类A通常是区间a, b上的连续函数，记作Ca, b，称为函数逼近空间;而函数B通常为n次多项式,有理函数或分段低次多项式等.为了在数学上描述更精确，先要介绍代数和分析中一些基本概念及预备知识.,数学上常把在各种集合中引入某一些不同的确定关系称为赋予集合以某种空间结构，并将这样的集合称为空间。,例1 所有实n维向量集合，按向量的加法和数乘构成实数域R上的线性空间-Rn,称为n维向量空间.,例2 对次数不超过n的（n为正整数）实系数多项式全体，按多项式加法和数乘构成数域

3、R上的多项式线性空间-Hn,称为多项式空间.,例3 所有定义在 a,b 集合上的连续函数全体，按函数的加法和数乘构成数域R上的连续函数线性空间 Ca, b,称为连续函数空间. 类似地记Cpa, b为具有p阶连续导数的函数空间.,则称x1,x2,xn 线性相关，否则称x1,x2,xn 线性无关，即只有当a1=a2=an=0时等式(1.1)才成立.,定义1 设集合S是数域P上的线性空间，元素x1,x2,xnS，如果存在不全为零的数a1,a2,anP，使得,则x1,xn称为空间S的一组基, 记为S=spanx1,xn,并称空间S为n维空间，系数a1,an为x在基x1,xn下的坐标，记作(a1,an)

4、，如果S中有无限多个线性无关元素x1,xn,，则称S为无限维线性空间.,若线性空间S是由n个线性无关元素x1,xn生成的，即对任意xS，都有,它由n+1个系数(a0, a1,an)唯一确定. 1,x,xn 线性无关，它是Hn的一组基，故集合 Hn=span1, x,xn， 且(a0, a1,an)是p(x)的坐标向量，Hn是n+1维的.,下面考虑次数不超过n实系数多项式集合Hn，其元素p(x)Hn表示为,其中为任意给的小正数，即精度要求. 这就是下面著名的魏尔斯特拉斯（Weierstrass）定理.,对连续函数f(x)Ca, b，它不能用有限个线性无关的函数表示，故Ca, b是无限维的，但它的

5、任一元素f(x)Ca, b均可用有限维的p(x)Hn逼近，使误差,在a, b上一致成立. （证明略，见书p52有说明.）,定理1 设f(x)Ca, b，则对任何0，总存在一个代数多项式p(x) ，使,由(1.3)式给出的Bn(f, x)也是f(x)在0, 1上的一个逼近多项式，但它收敛太慢，实际中很少使用.,更一般地，可用一组在Ca, b上线性无关的函数集合 来逼近f(x)Ca, b，元素表示为,函数逼近问题就是对任何f(x)Ca, b，在子空间中找一个元素*(x)，使f(x)-*(x)在某种意义下最小.,3.1.2 范数与赋范线性空间,为了对线性空间中元素大小进行衡量，需要引进范数定义，它是

6、Rn空间中向量长度概念的直接推广.,定义2 设S为线性空间，xS，若存在唯一实数，满足条件： (1) x0;当且仅当x0时, x=0; (正定性) (2) x=|x, R; (齐次性) (3) x+yx+y, x,yS. (三角不等式) 则称为线性空间S上的范数，S 与一起称为赋范线性空间，记为X.,对Rn上的向量 x(x1,x2,xn)T, 三种常用范数为：,类似的对连续函数空间Ca, b, 若fCa, b可定义以下三种常用函数的范数,可以验证这样定义的范数均满足定义2中的三个条件.,3.1.3 内积与内积空间,在线性代数中，Rn上的两个向量 x(x1,x2,xn)T与y(y1,y2,yn)

7、T的内积定义为 (x, y)= x1 y1 +x2 y2 +xn yn. (1.5) 若将它推广到一般的线性空间X，则有下面的定义.,定义3 设X是数域K(R或C)上的线性空间，对任意u,vX，有K中一个数与之对应，记为(u, v)，它满足以下条件：,则称(u, v) 为X上u与v的内积，对应了内积的线性空间称为内积空间. 定义中(1)当K为实数域R时为 (u, v)(v, u) .,如果(u, v)=0，则称u与v正交(记为uv)，这是向量相互垂直概念的推广. 关于内积空间有以下重要定理.,定理2 设X为一个内积空间,对任意u, vX有如下不等式成立,它称为柯西施瓦茨(Cauchy-Schw

8、arz)不等式.,证明 当v=0时,显然成立. 设v0，则 (v, v)0,且对任何数t 有(这里设为实空间),取 t=-(u, v)/(v, v),代入上式右端，得,即得v0时有,定理3 设X为一个内积空间，u1,u2,unX，矩阵,称为格拉姆(Gram)矩阵,则G非奇异的充分必要条件是u1,u2,un线性无关.,证明 G非奇异等价于detG0，其充分必要条件是下面齐次线性方程组只有零解,而,从以上的等价关系可知道，detG0等价于从方程(1.8)推出a1=a2 =an=0，而后者等价于从方程(1.9)推出a1=a2=an=0，即u1,u2,un线性无关. 证毕,在内积空间X上可以由内积导出

9、一种范数，即对于uX ，记,容易验证它满足范数定义的三条性质,其中三角不等式,可由定理2直接得出，即,两端开方即得(1.11).,例1 Rn的内积，设x, yRn， x(x1,x2,xn)T，y(y1,y2,yn)T，则其内积定义为,由此导出的向量2-范数为,若给定实数i0(i=1,n)，i称为权函数，则在Rn上可定义加权内积为,相应的向量2-范数为,不难验证(1.13)给出的(x, y)满足内积定义的四条性质. 当i=1 (i=1,n)时， (1.13)就是(1.12).,如果x, y Cn，带权内积定义为,这里i仍为正实数序列.,在Ca, b上也可以类是定义带权内积，为此先给出权函数定义.

10、,定义4 设a, b是有限或无限区间，在a, b上的非负函数(x)满足条件：,则称(x)为a, b上的一个权函数. 它的物理意义可以解释为密度函数.,例2 Ca, b上的内积，设f(x), g(x)Ca, b，(x)是上给定的权函数，则可内积定义为,容易验证它满足内积定义的4条，由此内积导出的范数,称(15)和(16)为带权(x)的内积和范数，特别常用的是(x)1的情形，即,若0,1,n是Ca, b中的线性无关函数族，记=span0,1,n，它的拉姆(Gram)矩阵为,根据定理3知 0,1,n 线性无关的充分必要条件是 detG(0,1,n)0.,3.1.4 最佳逼近,则称P*(x)是f(x)

11、在a, b上的最佳逼近多项式. 如果P(x)=span0,1,n，则称相应的P*(x)为最佳逼近函数. 通常范数取为或2. 若取 ,即,函数逼近主要讨论给定f(x)Ca, b，求它的最佳逼近多项式. 若P*(x)Hn=span1,x,xn，使误差,则称P*(x)是f(x)在a, b上的最佳一致逼近多项式. 这时求P*(x)就是求a, b上使得最大误差最小的多项式.,如果范数取为2，即,则称P*(x)为f(x)在a, b上的最佳平方逼近多项式.,若f(x)是a, b上的一个列表函数，在区间节点ax0 x1xmb上给出(xi)(i=0,1, ,m)，要求P*(x)使,本章将着重讨论实际应用多便于计

12、算的最佳平方逼近与最小二乘拟合.,则称P*(x)为f(x)在a, b上的最小二乘拟合.,3.2.1 正交函数族与正交多项式,3.2 正交多项式,则称k(x)是区间a,b上带权(x)的正交函数族.若Ak1，则称为标准正交函数族.,定义5 如果函数f(x), g(x)在a,b上连续,满足,正交多项式是函数逼近的重要工具，啊数值积分中也有重要应用.,例如, 三角函数族 1, cosx, sinx, cos2x, sin2x, 是在区间-,上的正交函数系，因为对k=1,2,有,实际上，这就是付里叶(Fourier)逼近的基函数.,而对k, j=1,2,，当kj 时有,则称多项式序列n(x)为在a,b上

13、带权(x)的正交，称n(x)为a,b上带权(x)的n次正交多项式.,定义6 设n(x)是a,b上首项系数an0的n次多项式，(x)为a,b上权函数，如果多项式序列n(x)满足关系式,如何构造正交多项式？,只要给定区间a, b及权函数,均可由一族线性无关的幂函数1,x, xn,利用逐个正交化手续构造出正交多项式序列,此即Smith正交化方法.,这样得到的正交多项式n(x)，其最高次项系数为1. 反之，若 n(x)是正交多项式，则 0,1,n在区间a, b上是线性无关的.,事实上，若,用(x)j(x)(j=0,1, ,n)乘上式并积分得,利用正交性有,由于,故cj=0对j=0,1, ,n成立.由此

14、得0,1,n线性无关，于是可直接得到正交多项式的以下性质.,(1) 对任何多项式P(x)Hn均可表示为函数族0(x),1(x),n(x) 的线性组合，即,(2) n(x)与任何次数小于n的多项式P(x)Hn-1都正交，即,关于正交多项式还有一些重要性质.,定理4 设n(x)是a, b上带权(x)的正交多项式，对n0成立递推关系,这里,定理5 设n(x)是a, b上带权(x)的正交多项式，则n(x)(n1)在区间(a, b)内有n个不同的零点.,证明 假定n(x)在(a, b)内的零点都是偶数重的，则n(x)在a, b上符号保持不变，这与.,矛盾. 故n(x)在(a, b)内的零点不可能全是偶重

15、的，现设xi(i=1,2, ,l)为n(x)在(a, b)内的奇数重零点，不妨设,则n(x)在xi(i=1,2, ,l)为处变号. 令,于是假定n(x)q(x)在a, b上符号保持不变，则得,与(n, q)0矛盾，故ln. 而n(x)只有n个零点，故l=n，即n个零点都是单重的. 证毕.,若ln，由n(x)的正交性可知,例题：利用 Gram-schmidt 方法构造 0,1 上带权 的前3个正交多项式,解：利用正交化公式来求,于是,于是,3.2.2 勒让德多项式,当区间-1,1, 权函数(x)1时, 由1,x,xn,正交化得到的多项式就称为勒让德(Legendre)多项式,并用P0(x),P1

16、(x),Pn(x),表示. 这是勒让德于1785年引进的. 1814年罗德利克(Rodrigul)给出了简单的表达式为,由于(x2-1)n是2n次多项式，求n阶导数后得,显然得到最高项系数为1的勒让德多项式为,于是得Pn(x)的首项xn的系数为,勒让德多项式有下述几个重要性质：,性质1(正交性),令 ，则,设Q(x)是在区间-1, 1上有连续n阶可微的函数，有分部积分法知(用(2.5)式),下面分两种情况讨论,(1) 若Q(x)的次数小于n，则Q(n)(x)0，得,(2) 若,则,于是,由于,故,于是(2.7)式得证.,性质2(奇偶性),由于(x)=(x2-1)n是偶次多项式，经过偶次求导仍为

17、偶次多项式，经过奇次求导仍为奇次多项式，故n为偶数时Pn(x)为偶函数，n为奇数时Pn(x)为奇函数，于是(2.8)式成立.,性质3(递推关系),考虑n+1次多项式xPn(x)，它可表示为,两边乘Pk(x)，并从-1到1积分，利用正交性得,当kn-2时，xPk(x)次数小于等于n-1，上式左端积分为0，故得ak=0. 当k=n时，xP2n(x)为奇函数，左端积分仍为0，故得an=0. 于是,其中,代入上式整理即得递推公式(2.9).,由P0(x)=0, P1(x)=x，利用(2.9)式就可推出,性质4 Pn(x)在区间-1,1内有n个不同的实零点.,3.2.3 切比雪夫多项式,区间为-1,1时

18、,取权函数,由序列1,x,xn,正交化得到的多项式就是切比雪夫多项式，它可表示为,若令x=cos，则Tn(x)=cosn，0.,Tn(x)=cos(narccosx), |x| 1. (2.10),切比雪夫多项式有很多重要性质：,性质1(递推关系),这只要由三角恒等式,令x=cos 即得，由(2.11)式就可以推出,于是得Tn(x)的首项系数为 an=2n-1 (n1).,性质2 切比雪夫多项式Tk(x)在区间-1,1上带权,正交且,事实上，令x=cos，则dx=-sind ，于是得,性质3 T2k(x)只含x的偶次幂,T2k+1(x)只含x的奇次幂.,此性质可由递推关系直接得到.,性质4 T

19、n(x)在区间-1,1上有n个零点.,性质5 Tn(x)的首项xn的系数为2n-1 (n=1,2, .) .,若将xn用T0(x),T1(x), ,Tn(x)的线性组合表示，则其公式为,这里规定T0(x)=1. n=1,2, ,6时的结果如下,若令 ，则多项式 是首项系数为 1 的切比雪夫多项式. 若记 为所有次数小于等于n的首项系数为 1 的多项式集合，对 有以下性质.,定理6 设 是首项系数为 1 的切比雪夫多项式，则,且,定理的证明可参看文献22. 定理6表明在所有首项系数为1的n次多项式集合 中,所以 是 中最大值最小的多项式，即,利用这一结论，可求P(x)Hn在Hn-1中的最佳(一致

20、)逼近多项式.,例3 求f(x)=2x3+x2+2x-1在 -1,1上的最佳2次逼近多项式.,解 由题意，所求最佳逼近多项式P2*(x)应满足,由定理6可知，当,时，多项式f(x)P2*(x)与零偏差最小，故,就是f(x)在 -1,1上的最佳2次逼近多项式.,则当x在 0, 1 变化时，此时函数为,解：作变量变换，令t=2x-1，t-1, 1，,设P3*(x)为f(x)在 0,1 上的三次最佳一致逼近多项式,由于,例 求f(x)=x4+3x3-1在0,1上的三次最佳逼近多项式.,由于切比雪夫多项式是在区间-1,1上定义的，对于一般区间a, b，要通过变量替换变换到-1,1, 可令,则可将xa,

21、 b变换到t-1,1.,即,从而,3.2.4 切比雪夫多项式零点插值,切比雪夫多项式Tn(x)在区间-1,1上有n个零点.,和n+1个极值点(包括端点).,这两组点称为切比雪夫点，它们在插值中有重要作用.(几何意义见书p63),利用切比雪夫点做插值，可使插值区间最大误差最小化. 下面设插值点 x0,x1,xn-1,1, fCn+1-1,1, Ln(x)为相应的n次拉格朗日插值多项式,那么插值余项,于是,其中,是由被插值函数确定的.,如果插值节点为Tn+1(x)的零点,则由(2.13)式可得,由此可导出插值误差最小化的结论.,定理7 设插值节点 x0,x1,xn 为切比雪夫多项式Tn+1(x)的

22、零点，被插函数fCn+1-1,1， Ln(x)为相应的插值多项式，则,对于一般区间a, b上的插值只要利用变换(2.14)式则可得到相应结果，此时插值节点为,解 利用T5(x)的零点和区间变换可知节点,例4 求f(x)=ex在0, 1上的4次拉格朗日插值多项式L4(x)，插值节点用T5(x)的零点，并估计误差,即,对应的拉格朗日插值多项式为,利用(2.15)式可得误差估计,而,于是有,在第2章中已经知道，由于高次插值出现龙格现象，一般Ln(x)不收敛于f(x)，因此它并不适用. 但若用切比雪夫多项式零点插值却可避免龙格现象，可保证整个区间上收敛. 见书p65例5.,3.2.5 其他常用的正交多

23、项式,一般说，如果区间a, b及权函数(x)不同, 则由1,x,xn,正交化得到的多项式也不同. 除上述两种最重要的正交多项式外，下面再给出三种较常用的正交多项式.,1. 第二类切比雪夫多项式,区间为-1, 1时,取权函数,由序列1,x,xn,正交化得到的多项式就称为第二类切比雪夫多项式，其表达式为,令x=cos，可得,即Un(x)为-1,1上正交多项式族，且有递推关系式为,2. 拉盖尔多项式,区间为0, +)时,取权函数,由序列1,x,xn,正交化得到的多项式就称为拉盖尔(Laguerre)多项式，其表达式为,它也具有正交性质,和递推关系式,3. 埃尔米特多项式,区间为(-,+)时,取权函数

24、,由序列1,x,xn,正交化得到的多项式就称为埃尔米特(Hermite)多项式，其表达式为,它也具有正交性质,和递推关系式,3.3 最佳平方逼近,3.3.1 最佳平方逼近及其计算,现在我们研究区间a, b上一般的最佳平方逼近问题. 对函数f(x)Ca, b及集合Ca, b中的一个子集 =span0(x),1(x),n(x), 若存在S*(x),使,则称 S*(x)是f(x)在子集 中的最佳平方逼近函数.,为了求S*(x), 由(3.1)式可知该问题等价于求多元函数,的最小值. 由于I(a0,a1,an)是关于a0,a1,an的二次函数，利用多元函数求极值的必要条件有,即,于是有,是关于a0,a

25、1,an的线性方程组，称为法方程，即,由于函数组,线性无关，故系数矩阵的行列式非零，即,从而得到最佳平方逼近函数,于是方程组有唯一解,下面证明S*(x)必定满足最佳平方逼近的定义，即,但我们只需证明对任意的S(x)有,为此我们只要考虑,由于S*(x)的系数ak*是法方程(3.3)的解，故,从而上式第二项积分为0. 于是可得,即得S*(x)必定是所求函数f(x)的最佳平方逼近函数.,根据以上推论，也可得出最佳函数逼近的求法。,另外，由证明第二项积分为0. 我们可得,推论：C a, b是内积空间，Ca, b是其有限维子空间，f(x)Ca, b，中S*(x)是f(x)的的最佳平方逼近函数的充要条件是

26、f -S*与中任一函数正交.,设,则对任意函数S，有,由推论得,也得法方程为,若记余项(x)=f(x)-S*(x)，则平方误差为,若取 则要在Hn中求n次最佳平方逼近多项式,此时,若用H表示 对应的矩阵，即,则称H为希尔伯特(Hilbert)矩阵，若记向量,则法方程为,其解ak= ak*(k=0,1,n), 即得所求最佳平方多项式为 的系数.,解 由公式有,得法方程组,例6 求 在 0,1上的一次最佳平方逼近多项式(注意与例4的区别).,解出,故得所求的一次最佳平方逼近多项式为,平方误差为,最大误差为,若用1,x,xn做基，求最佳平方多项式，计算简单，但当n较大时, 系数矩阵H是高度病态的(见

27、第5章),因此直接求解法方程是相当困难的，故通常是采用正交多项式做基底构造最佳平方多项式.,解：,法方程组为：,于是,解得,3.3.2 用正交函数族作最佳平方逼近,设f(x)Ca, b，,若 是正交函数族，即满足,故法方程(3.3),的系数矩阵为非奇异对角阵，即,立刻得到法方程的解为,于是f(x)Ca, b在中的最佳平方逼近函数为,可得均方误差为,由此可得贝塞尔(Bessel)不等式,得级数,证明略，可见文献23.,定理8 设f(x)Ca, b，S*(x)是f(x)的最佳平方逼近多项式，其中 是正交多项式族，则有,下面考虑函数f(x)C-1, 1，按勒让得多项式P0(x),P1(x),Pn(x

28、)展开，由公式可得,其中,根据(3.10)式，平方逼近的误差为,由定理8可得,证明略，可见文献23.,定理9 设f(x)C2-1, 1，Sn*(x)由(3.13)式给出,则对任意x-1, 1和任意0，当n充分大时有,如果f(x)满足光滑性条件还可得到S*(x)一致收敛于f(x)的结论.,对首项系数为1的勒让德多项式 有以下性质,定理10 在所有最高次项系数为1的n次多项式中,勒让德多项式 在-1, 1上与零的平方误差最小.,即可以理解为 最小等价于,与零的平方误差最小.,证明 设Qn(x)是任意一个最高次项系数为1的n次多项式，它可表示为,于是,因此当且仅当 时等号才成立，即当 时平方误差最小

29、.,解 先计算(f(x), Pk(x) (k=0,1,2,3),例7 求f(x)=ex在-1,1上的三次最佳平方逼近多项式.,由公式 解得,得三次最佳平方逼近多项式为,可得均方误差为,可得最大误差为,如果f(x)Ca, b，求a, b上的最佳平方逼近多项式，做变换,于是 在-1, 1上可用勒让德多项式做最佳平方逼近多项式 S*(t)， 从而可得到区间a, b上的最佳平方逼近多项式,由于勒让德多项式Pk(x)是在-1, 1上由多项式基1,x,xn,正交化得到的，因此利用函数的勒让德展开部分和得到最佳平方逼近多项式与由,直接通过解法方程得到Hn中的最佳平方逼近多项式是一致的，只有当n较大时法方程出

30、现病态，计算误差较大，不能使用，而用勒让德展开不用解线性方程组，不存在病态问题，计算公式比较方便，因此通常都用这种方法求最佳平方逼近多项式.,3.3.3 切比雪夫级数,其中系数根据(3.8)式，由(2.12)式得到,如果设f(x)C-1, 1，按Tk(x)展成广义傅里叶级数，由 (3.12)式可得级数,这里 Tk(x)=cos(karccosx), |x|1.,级数(2.16)称为f(x)在-1, 1上的切比雪夫级数.,若令x=cos, 0，则(3.16)式就是f(cos)的傅里叶级数，其中,取它的部分和,于是根据傅里叶级数理论知，只要(x)在-1, 1上分段连续，则f(x)在-1, 1上的切

31、比雪夫(3.16)一致收敛于f(x). 从而可表示为,其误差为,解 由(3.18)式得,例8 求f(x)=ex在-1, 1上的切比雪夫级数部分和,它可用数值积分(见第4章)求得,由(3.20)式及Tk(x)的表达式可求得,及误差,3.4 曲线拟合的最小二乘法,最小二乘法的基本原理,具体的做法是求 p(x) 使,几何意义: 求在给定点 x0, x1, xm 处与点(x0,y0), (x1,y1), ,(xm, ym) 的距离平方和最小的曲线y =p(x),这就是最小二乘曲线拟合问题.,3.4.1 最小二乘法及其计算,中找一函数y=S*(x)使误差平方和,这就是一般的最小二乘逼近，用几何语言说，就

32、称为曲线拟合的最小二乘法.,这里,用最小二乘法求拟合曲线时，首先要确定S(x)的形式. 这不是单纯的数学问题，还要与所研究问题的运动规律及所得观测数据(xi, yi) 有关；通常要从问题的运动规律及所给定数据描图，确定S(x)的形式并通过实际计算选出较好的结果，这点将从下面的例题得到说明.,S(x)的一般表达式为(4.2)式表示的线性形式. 若 k(x)是k次多项式，S(x)就是n次多项式. 为了使问题的提法更有一般性，通常在最小二乘法中误差平方和都考虑加权平方和，即,这里(x)0是a, b上的权函数,它表示不同点(xi, f(xi)处的数据比重不同，例如，(xi)可表示在点(xi, f(xi

33、)处重复观测的数据.,用最小二乘法求拟合曲线的问题,就是在形如(4.2)的S(x)中求一函数y=S*(x)，使加权平方和(4.3)式,取得最小. 它转化为求多元函数,的极小点 问题. 这与第4节讨论的问题完全类似.,由求多元函数极值的必要条件,有,若记,上式可改写为,这方程称为法方程,可写成矩阵形式,其中,要使法方程(6)有唯一解 ，就要求矩阵G 非奇异.,必须指出， 在a, b上线性无关不能推出矩阵G非奇异.,例如，令,显然 在0, 2上线性无关，但若取点 xk=k, k=0,1,2(n=1,m=2)，那么有,由此得出,为保证(4.6)的系数矩阵G非奇异,必须加上另外的条件.,定义7 设 的

34、任意线性组合在点集 上至多只有n个不同的零点, 则称 在点集 上满足哈尔(Haar)条件 .,显然1,x,xn在任意m(mn)个点上满足哈尔条件.,可以证明，如果 在点集 上满足哈尔(Haar)条件，则法方程(4.6)的系数矩阵(4.7)非奇异，于是法方程(4.6)存在唯一的解 从而得到函数f(x)的最小二乘解为,可以证明这样得到的S*(x), 对任何形如(4.2)式的S(x),都有,即S*(x)必为所求的最小二乘解.,它的证明与证明(3.4)式相似，自己做练习.,给定f(x)的离散数据(xi,yi),i=0,1,m，要确定集合 是困难的，所以一般取=span1,x,xn. 但这样做当n3时，

35、与连续情形一样求解方程(4.6)时将出现系数矩阵G为病态的问题，通常对n=3的简单情形都可通过求解方程(4.6)得到S*(x). 有时根据给定数据图形，其拟合函数y=S(x)表面上不是(4.2)式的形式，但通过变换仍可化为线性模型. 例如, S(x)=aebx,若两边取对数得 lnS(x)=lna+bx.,它就是形如(4.2)式的线性模型，具体见例10.,解 根据所给数据，在坐标纸上标出各点，见图. 从图中看到各点在一条直线附近，故可选择线性函数做拟合曲线，即令,例9 已知一组实验数据如下，求它的拟合曲线.,解得a0=2.5648,a1=1.2037. 于是所求拟合曲线为,由(4.6)得法方程

36、,例10 设数据(xi, yi)(i=0,1,2,3,4)由下表给出，表中第4行为lnyi=zi，可以看出数学模型为y=aebx，用最小二乘法确定a及b.,解 根据给定数据(xi, yi)(i=0,1,2,3,4)描图可确定拟合曲线方程为y=aebx，它不是线性形式.,对方程y=aebx 两边取对数得lny=lna+bx，如果令z=lny,A=lna，则z=A+bx,=1,x. 为确定A和b，先将数据(xi, yi)可转化为(xi, zi) ，见数据表.,根据最小二乘法，取,得,故有法方程,解得A=1.122, b=0.505, a=eA=3.071. 于是得最小二乘拟合曲线为,现在很多计算机

37、配有自动选择数学模型的程序，其方法与本例相同. 程序中因变量与自变量变换的函数类型较多，通过计算比较误差找到拟合得较好的曲线，最后输出曲线图形及数学表达式.,解 作散点图如右，,从右图可以看出这些点接近一条抛物线，因此设所求公式为,例 已知一组观测数据如表所示，试用最小二乘法求一个多项式拟合这组数据。,代入法方程(4.6)式有,代入数据得,解之可得,故所求拟合多项式为,3.4.2 用正交多项式做最小二乘拟合,且平方误差为,现在我们根据给定的节点x0,x1,xm及权函数(x)0，造出带权(x)正交的多项式Pn(x).注意nm，用递推公式表示Pk(x)，即,这里Pk(x)是首项系数为1 的k次多项

38、式，根据Pk(x)的正交性，得,下面用归纳法证明这样给出的Pk(x)是正交的. 首先由(4.10)式第二式及(4.11)式中1的表达式，有,由归纳法假定，当0s k-2时,(Pk, Ps)=0， (Pk-1, Ps)=0.,另外，xPs(x)是首项系数为1的s+1次多项式，它可由P0,P1,Ps+1的线性组合表示，而s+1k-1，故由归纳法假定又有,于是由(4.12)式，当sk-2时，(Pk+1, Ps)=0 .,再看,由假定有 (Pk, Pk-1)=0 ，,利用(4.11)式中k的表达式及以上结果，得,最后,由(4.11)式有,至此已证明了由第一式及第二式确定的多项式Pk(x) (k=0,1,n，nm)组成一个关于点集xi的正交系.,用正交多项式Pk(x)的线性组合作最小二乘曲线拟合只要根据公式第一式及第二式逐步求Pk(x)的同时，相应计算出系数,并逐步把ak*Pk(x)累加到S(x)中去，最后就可得到所求的拟合曲线,这里n可事先给定或在计算过程中根据误差确定.用这种方法编程序不用解方程组，只用递推公式，并且当逼近次数增加一次时，只要把程序中循环数加1，其余不用改变. 这是目前最好的不用解方程组而可以利用递推方法得到多项式拟合的算法.有通用的语言程序供用户使用.,3.5 有理逼近,3.6 有三角多项式逼近 与快速傅里叶变换,自学. 评注见p92.,