1、数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS3.1 函数逼近的基本概念函数逼近的基本概念3.2 正交多项式正交多项式3.3 最佳平方逼近最佳平方逼近3.4 曲线拟合的最小二乘法曲线拟合的最小二乘法3.6 最佳平方三角逼近与快速傅里最佳平方三角逼近与快速傅里叶变换叶变换第三章第三章 函数逼近与曲线拟合函数逼近与曲线拟合3.函数逼近的基本概念函数逼近的基本概念一、函数逼近与函数空间一、函数逼近与函数空间1、函数逼近、函数逼近 在数值计算中经常遇到求函数值的问题，手算时常常通过函在数值计算中经常遇到求函数值的问题，手算时常常通过函数表求得用计算机计算时若把函数表
2、存入内存进行查表，则占数表求得用计算机计算时若把函数表存入内存进行查表，则占用单元太多，不如直接用公式计算方便因此，我们希望求出便用单元太多，不如直接用公式计算方便因此，我们希望求出便于计算且计算量省的公式近似已知函数于计算且计算量省的公式近似已知函数f(x)例如，泰勒展开式例如，泰勒展开式的部分和的部分和nnnxxnxfxxxfxfxP)(!)()(!1)()()(00)(000 就是的一种近似公式用它求就是的一种近似公式用它求 x0 附近的函数值误差较小，当附近的函数值误差较小，当|x-x0|较较大时误差就很大例如在大时误差就很大例如在-1，1上用上用近似近似 ，其误差，其误差 ，于是，于
3、是432424161211)(xxxxxP xe)1,1(,120)()(544 exxPexRx.0226.0120)(max,120)(41154 exRxexRx它在整个区间上误差较大若在计算机上用这种方法计算，如精度它在整个区间上误差较大若在计算机上用这种方法计算，如精度要求较高，则需取很多项，这样既费时又多占存储单元，因此，我要求较高，则需取很多项，这样既费时又多占存储单元，因此，我们要求在给定精度下求计算次数最少的近似公式，这就是函数逼近们要求在给定精度下求计算次数最少的近似公式，这就是函数逼近与计算要解决的问题与计算要解决的问题.这问题可叙述为：这问题可叙述为：“对函数类对函数类
4、A中给定的函数中给定的函数 f(x),要求在另要求在另一类较简单的便于计算的函数类一类较简单的便于计算的函数类B中，求函数中，求函数 ,使使P(x)与与f(x)之差在某种度量意义下最小之差在某种度量意义下最小”.函数类函数类A通常是区间通常是区间a，b上的上的连续函数，记作连续函数，记作Ca，b；函数类；函数类B通常是代数多项式，分式有理函通常是代数多项式，分式有理函数或三角多项式数或三角多项式BxP)(2、函数空间、函数空间 数学上常把在各种集合中引入数学上常把在各种集合中引入某些某些不同的不同的确定关系确定关系称为赋予称为赋予集合以某种集合以某种空间结构空间结构，并将这样的集合称为空间，并
5、将这样的集合称为空间.；阶连续导数的函数空间阶连续导数的函数空间具有具有上的线性空间；上的线性空间；数域数域多项式空间；多项式空间；维向量空间；维向量空间；例如例如pbaCbaCnpnn:,R:,:H:R定义定义1 设集合设集合S是数域是数域 P 上的线性空间，元素上的线性空间，元素 ，如，如果存在不全为零的数果存在不全为零的数 ，使得，使得 ，则，则称称 线性相关线性相关.否则，则称否则，则称 线性无关线性无关.Sxxn,1，P,1 naa，011 nnxaxanxx,1，nxx,1，若线性空间若线性空间S是由是由 n 个线性无关元素个线性无关元素 生成的，即对生成的，即对nxx,1，.),
6、(,span,1111111nnnnnnnaaxxxaanSxxSSxxxaxaxSx下的坐标，记作在基称为维空间，系数为，称空间记为的一组基，称为空间，则都有：下面考察次数不超过下面考察次数不超过n次的多项式集合次的多项式集合Hn,其元素其元素p(x)Hn,表示为表示为nnxaxaxaaxp2210)(它由它由n+1个系数个系数),(210naaaa唯一确定唯一确定,nxx,1线性无关线性无关,它是它是Hn的一组基的一组基.故故Hn=spannxx,1且且),(210naaaa是是p(x)的坐标向量的坐标向量,Hn是是n+1维的维的.更一般地更一般地,可用一组在可用一组在Ca,b上线性无关的
7、函数集合上线性无关的函数集合niix0)(来逼近来逼近,)(baCxf元素元素,)(,),(),()(10baCxxxspanxn表示为表示为);()()()(1000 xaxaxaxnn逼近问题就是对任何逼近问题就是对任何,)(baCxf在子空间在子空间中找一个元素中找一个元素)(*x使使)()(*xxf在某种意义下在某种意义下最小最小.设设S为线性空间为线性空间,xS,若存在唯一实数若存在唯一实数 满足条件：满足条件：(1)x0;当且仅当当且仅当x0时时,x0;(正定性正定性)(2)x|x,R;(齐次性齐次性)(3)xyxy,x,yS.(三角不等式三角不等式)则称则称 为线性空间为线性空间
8、S上的范数上的范数,S与与 一起称为赋范线性空间一起称为赋范线性空间,记为记为X.|3、范数的定义范数的定义 在Rn上的向量 x(x1,x2,xn)TRn,三种常用范数为称为：称为范数或最大范数 1称为 范数 2称为 范数几种常用范数几种常用范数|,|max|1inixx,|11niixx,)(|2/1122niixx|max|()|,ax bff x 类似的对连续函数空间Ca,b,若fCa,b可定义以下三种常用函数的范数函数的范数 称为范数1|()|,baff xdx1称为范数1222|(),baffx dx2称为范数设X为一个内积空间,对 u,vX有 2.|(,)|(,)(,)u vu u
9、v v称为柯西施瓦次不等式.柯西施瓦次不等式柯西施瓦次不等式 魏尔斯特拉斯定理魏尔斯特拉斯定理 设设f(x)Ca,b,则对任何则对任何0,总存在一个代数多总存在一个代数多项式项式p(x),使使|)()(|xpxf在在a,b上一致成立上一致成立。),(),(),(),(),(),(),(),(),(212222111211nnnnnnuuuuuuuuuuuuuuuuuuG定理定理：设X为一个内积空间,u1,u2,unX,矩阵称为格拉姆矩阵,则G非奇异的充分必要条件是u1,u2,un线性无关线性无关。记区间记区间a,ba,b上所有连续函数的全体为上所有连续函数的全体为Ca,b,Ca,b,可以证明可
10、以证明Ca,bCa,b是一个线性空间是一个线性空间,把所有次数不超把所有次数不超过过n n的多项式全体记为的多项式全体记为P Pn n,则则 P Pn n是是Ca,bCa,b的子空间的子空间.若若(x),g(x)(x),g(x)Ca,b,Ca,b,则称()()baf x g x dx为(x)与g(x)的内积内积,记为(,g),4、函数的内积函数的内积满足(1)(1)(,g)=(g,g)=(g,);若若(,g)=0,g)=0,称称(x)(x)与与g(x)g(x)正交正交 ,记为记为g.g.22(,)()baff ffx dx(2)(2)(c(c,g)=c(,g)=c(,g);,g);(3)(3)
11、(1 1+2 2,g)=(,g)=(1 1,g)+(,g)+(2 2,g);,g);利用内积可以定义函数的平方模利用内积可以定义函数的平方模(1)(1)2 2 0,0,而且而且2 2=0=0(x)=0;(x)=0;(2)(2)c c2 2=|c|=|c|2 2;(3)(3)+g+g 2 22 2+g g 2 2 考虑到考虑到(x)(x)在区间在区间a,ba,b上各点的函数值比重不同上各点的函数值比重不同,常引进加权形式的定义常引进加权形式的定义 (,)()()()baf gx f x g x dx22()()bafx fx dx这里函数这里函数(x)(x)是非负连续函数是非负连续函数,称为称为
12、a,ba,b上的上的权函数权函数.它的物理意义可以解释为它的物理意义可以解释为密度函数密度函数.权函数权函数一、正交函数族与正交多项式一、正交函数族与正交多项式 正交多项式是函数逼近的重要工具，在数值积分中也有重要作用正交多项式是函数逼近的重要工具，在数值积分中也有重要作用.3.正交多项式正交多项式 定义定义5 若若 为为a,b上的权函数且满足上的权函数且满足 f(x),g(x)Ca,b,(x)(f(x),g(x)=ba(x)f(x)g(x)dx=0 则称则称 f(x)与与g(x)在在a,b上带权上带权(x)正交正交.若函数族若函数族 0(x),1(x),n(x),满足关系满足关系则称则称 k
13、(x)是是a,b上带权上带权(x)的的正交函数族正交函数族;若若Ak=1,则称之为则称之为标准正交函数族标准正交函数族.(j,k)=ba(x)j(x)k(x)dx=0,j kAk0,j=k(2.2)(2.1)例如例如,三角函数族三角函数族,2sin,2cos,sin,cos,1xxxx就是区间就是区间,上的正交函数族上的正交函数族.因为对因为对,2,1k有有)cos,(cos)sin,(sin,2)1,1(kxkxkxkx而对而对0)sin,(cos)sin,(sin)cos,(cos;0)sin,1()cos,1()sin,(cos,2,1,jxkxjxkxjxkxkxkxkxkxjkjk时
14、有当2)如何构造正交多项式如何构造正交多项式 只要给定区间只要给定区间a,b及权函数及权函数,均可由一组线性无关的均可由一组线性无关的幂函数幂函数1,x,xn,利用逐个正交化手续构造出正交利用逐个正交化手续构造出正交多项式序列多项式序列 如此得到的正交多项式有如下性质：(1)是具有最高次项系数为1的n次：0)(xn,.).2,1()()(),()(,()(,1)(10n0nxxxxxxxxjnjjjjnn)(xn(2)任何任何n次多项式次多项式Pn(x)Hn均可表示为均可表示为 的线性组合的线性组合.(3)当当kj时时,与任一次数小于与任一次数小于k的多项式正交的多项式正交.)(),.,(),
15、(10 xxxn)(,0)(),(xxxkkj且(4)成立递推关系成立递推关系,.)1,0()()()()(11nxxaxxnnnnn0)(xn)(xn(5)设 是在a,b上带权(x)的正交多项式序列,则 (n1)的n个根都是在区间(a,b)内的单重实根.,.)2,1()(),(/()(),(),(),(/()(),(0,x)(,1)(11n10nxxxxxxxxxxnnnnnnnnn其中bannndxxxxxxx.)()()(),(2并且41ln),(100 xdxxx1010001ln1ln),(xdxdxx)()()()()()(111120000222xxxxx00001)()()(x
16、xx1)(0 xxxxln1ln)(例题：利用 Gram-schmidt 方法构造 0,1 上带权 的前3个正交多项式 xx1ln)(210,解：利用正交化公式来求 2521775)41(7591)(222xxxxx1445)41()ln(),(10212dxxxxx101022111447)16121)(ln)41)(ln(),(dxxxxdxxx41)(1 xx91ln),(10202xdxxx于是于是3）几种常用的正交多项式）几种常用的正交多项式 勒让德多项式勒让德多项式当区间当区间-1,1,权函数权函数(x)1时时,由由1,x,xn,正交化得到的多项式就称为勒让德多项式正交化得到的多项
17、式就称为勒让德多项式,并并用用P0(x),P1(x),Pn(x),表示表示.其简单的表达其简单的表达式为式为),2,1()1(!21)(,1)(20nxdxdnxPxpnnnnn.)1()!2(!)(2nnnnxdxdnnxP最高项系数为最高项系数为1的勒让德多项式为的勒让德多项式为.11)(5.11)(14)()()12()()1(3)()1()(2.,122;,0)(d)()(11111个个不不同同的的实实零零点点内内有有，在在区区间间：性性质质上上与与零零的的平平方方误误差差最最小小，在在项项式式次次多多项项式式中中，勒勒让让德德多多的的在在所所有有最最高高项项系系数数为为：性性质质：递
18、递推推关关系系性性质质：奇奇偶偶性性性性质质：正正交交性性性性质质个个重重要要性性质质：勒勒让让德德多多项项式式有有以以下下几几nxPxPnxnPxxPnxPnxPxPnmnnmxxPxPnnnnnnnnmn ,16/)5105315231()(8/)157063()(8/)33035()(2/)35()(2/)13()(24663552443322xxxxPxxxxPxxxPxxxPxxPP0(x)P1(x)P2(x)P3(x)时时,由序列由序列1,x,xn,正交化得到的多项式就是正交化得到的多项式就是切比雪夫多项式切比雪夫多项式,它可表示为它可表示为 Tn(x)=cos(narccosx)
19、,|x|1若令xcos，则Tn(x)=cosn，0.,11)(2xx切比雪夫多项式切比雪夫多项式区间为区间为-1,1当权函数当权函数(1)递推关系递推关系切比雪夫多项式的性质切比雪夫多项式的性质1184832)(52016)(188)(34)(12)()(1)()()(2)(246635524433221011xxxxTxxxxTxxxTxxxTxxTxxTxTxTxxTxTnnnT0(x)T1(x)T2(x)T3(x)(2)切比雪夫多项式Tk(x)在区间-1,1上带权 正交且(3)T2k(x)只含x的偶次幂偶次幂,T2k+1(x)只含x的奇次幂奇次幂.0 ,;0n ,2m;n ,01)()(
20、112mnmxdxxTxTmn21/1)(xx,2,1,212cosknkxk(4)Tn(x)在区间-1,1上有n个零点).(22201xTknxknnknn若将xn用T0(x),T1(x),Tn(x)的线性组合表示,则其公式为)()(6)(15)(10(321)()(5)(10(161)()(4)(3(81)()(3(41)()(21)()(1642065315420431320210 xTxTxTxTxxTxTxTxxTxTxTxxTxTxxTxTxxTxxT 最佳最佳平方平方逼近：在逼近：在 意义意义 下，使得下，使得 最最小。小。),(|2fff 2|yP 最佳最佳一致一致逼近逼近/*
21、uniform approximation*/|)(|max|,xffbax 在在 意义下，使得意义下，使得 最小。也称最小。也称为为minimax problem。|yP偏差偏差/*deviation*/3.3 最佳平方逼近最佳平方逼近一、最佳平方逼近及其计算一、最佳平方逼近及其计算 对对 f(x)Ca,b及及Ca,b中的一个子集中的一个子集 =span 0(x),1(x),n(x),若存在若存在S*(x),使使 则称则称S*(x)是是 f(x)在子集在子集 Ca,b中的中的最佳平方逼近函数最佳平方逼近函数.的的最小值最小值.|f(x)-S*(x)|22=|f(x)-S(x)|22 )(mi
22、nxS=(x)f(x)-S(x)2dx,)(minxS baI(a0,a1,an)=(x)aj j(x)-f(x)2dx ba j=0nakI(k=0,1,n)=2 (x)aj j(x)-f(x)k(x)dx=0 ba j=0n求求S*(x)：等价于等价于求多元函数求多元函数 I(a0,a1,an)是关于是关于a0,a1,an的二次函数的二次函数,取极值必要取极值必要:(3.1)(3.2)于是有于是有这是关于这是关于a0,a1,an的线性方程组的线性方程组,称为称为法方程法方程.0(x),1(x),n(x)线性无关线性无关,则系数则系数detG(0,1,n)0,于是上述方程组有唯一解于是上述方
23、程组有唯一解ak=ak*(k=0,1,n),可得可得S*(x)=a0*0(x)+a1*1(x)+an*n(x).j=0n(j(x),k(x)aj=(f(x),k(x)(k=0,1,n),下面证明下面证明S*满足（满足（3.）(3.3)即对任何)(xS有dxxSxfxdxxSxfxbaba22*)()()()()()(3.4)即考虑:dxxSxfxSxSxdxxSxSxdxxSxfxdxxSxfxDbabababa2*2*2*2)()()()()(2)()()()()()()()()(若令若令(x)=f(x)-S*(x),则则平方平方误差误差为为|(x)|=(f(x)-S*(x),f(x)-S*
24、(x)=(f(x),f(x)-(S*(x),f(x)22=|f(x)|-ak*(k(x),f(x).k=0n22由于由于)(*xS的系数是方程的系数是方程(3.3)的解的解,故有故有),1,0(0)()()()(*nkdxxxSxfxkba从而上式第二个积分为从而上式第二个积分为0,于是于是0)()()(2*dxxSxSxDba故故(3.4)成立成立,这就证明了这就证明了)(*xS是是f(x)在在中的最佳平方逼近函数中的最佳平方逼近函数(3.5)若取若取 k(x)=xk,(x)1,f(x)C0,1,在在Hn中求中求n次最佳次最佳平方逼近多项式平方逼近多项式:S*(x)=a0*+a1*x+a2*
25、x2+an*xn.(j(x),k(x)=(f(x),k(x)=此时此时xk+jdx=10k+j+11f(x)xkdxdk 10若用若用H表示表示Gn=G(1,x,x2,xn)对应的矩阵，即对应的矩阵，即称为称为希尔伯特希尔伯特(Hilbert)矩阵矩阵.记记a=(a0,a1,an)T,d=(d0,d1,dn)T,则则Ha=d的解的解ak=ak*(k=0,1,n)即为所求即为所求.H=1 1/2 1/(n+1)1/2 1/3 1/(n+2)1/(n+1)1/(n+2)1/(2n+1)(3.6)(3.7).,1span)1.00(sin)(8 2并并给给出出平平方方误误差差式式上上的的最最佳佳平平
26、方方逼逼近近多多项项在在空空间间，求求例例xxxxxf .)(.dsin)(),(,d)(),(2210*1.001.00dHaxaxaaxSxxxxxfdxxxxkkkjkkj 方方程程组组，则则系系数数满满足足设设欲欲求求多多项项式式定定义义解解 二、用正交函数族作最佳平方逼近二、用正交函数族作最佳平方逼近.6.3,1交多项式做基交多项式做基困难的，通常是采用正困难的，通常是采用正直接求解方程是相当直接求解方程是相当）是高度病态的，因此）是高度病态的，因此系数矩阵（系数矩阵（较大时，较大时，多项式，当多项式，当做基，求最佳平方逼近做基，求最佳平方逼近，用用nxxn）的的解解为为且且方方程程
27、（为为非非奇奇异异对对角角阵阵，的的系系数数矩矩阵阵）故故法法方方程程（而而（）的的正正交交函函数数族族，则则是是满满足足条条件件（若若设设3.3)(,),(),(3.3,0)(),(,0)(),(2.2)(,),(),(),(,),(),(,)(101010 xxxGGxxjixxxxxxxxspanbaCxfnnjjjinn )8.3(),1,0()(),(/()(),(*nkxxxxfakkkk )9.3().(|)(|)(),(),)(022*xxxxfxSbaCxfknkkk （为为中的最佳平方逼近函数中的最佳平方逼近函数在在于是于是21022222*2)|)(|)(),(|)(|)
28、()(|)(|3.5 nkkknnxxxfxfxSxfx 差为差为）式可得平方逼近的误）式可得平方逼近的误由（由（(3.10)22220*|)(|)|)(|xfxaknkk （由此可得贝塞尔不等式由此可得贝塞尔不等式.)()(8.3),1,0()(,)(*0*称为广义傅立叶系数称为广义傅立叶系数数数的广义傅立叶级数，系的广义傅立叶级数，系称为称为）计算，得级数）计算，得级数按（按（展开，系数展开，系数按正交函数族按正交函数族若若kkkkkkaxfxakaxbaCxf (3.11)(3.12).0|)()(|lim,1,0),()(9.3)(,)(82*xSxfnkxxfxSbaCxfnnk是正
29、交多项式，则有是正交多项式，则有平方逼近多项式，其中平方逼近多项式，其中的最佳的最佳）给出的）给出的是由（是由（设设定理定理 11*1*10*0*10)()(212)(),()(),(),()()()(9.38.3)(,),(),(,1,1)(dxxPxfkxPxPxPxfaxPaxPaxPaxSxPxPxPCxfkkkkknnnn其中其中）式可得）式可得）和（）和（展开，由（展开，由（按勒让德多项式按勒让德多项式下面考虑函数下面考虑函数2*110222122)(|)(|10.3knkkakdxxfx ），平方误差为），平方误差为根据（根据（(3.13)(3.14)(3.15)的结论。的结论。
30、一致收敛于一致收敛于满足光滑条件还可得到满足光滑条件还可得到如果如果可得可得由定理由定理)()()(.0|)()(|lim8*2*xfxSxfxSxfnnn .|)()(|,0 1,113.3)(,1,1)(9*2nxSxfnxxSCxfnn 充分大时有充分大时有当当和和）式给出，则对任意）式给出，则对任意由（由（设设定理定理小小与零的平方逼近误差最与零的平方逼近误差最上上，在在项式项式次多项式中，勒让德多次多项式中，勒让德多的的在所有最高项系数为在所有最高项系数为定理定理）给出）有以下性质）给出）有以下性质（由公式（由公式（的勒让德多项式的勒让德多项式对于首项系数为对于首项系数为 11110
31、.6.21 nnPnPnnxaxaaxS 10*)(.11)(9多项式多项式上的三次最佳平方逼近上的三次最佳平方逼近，在在求求例例 xexf.10)(01多多项项式式上上的的一一次次最最佳佳平平方方逼逼近近，在在求求例例xxf 仍然是已知仍然是已知 x1 xm;y1 ym,求一个简单易求一个简单易算的近似函数算的近似函数 P(x)f(x)。但是但是 m 很大；很大；yi 本身是测量值，不准确，即本身是测量值，不准确，即 yi f(xi)这时没必要取这时没必要取 P(xi)=yi,而要使而要使 P(xi)yi 总体上总体上尽可能小。尽可能小。常见做法：常见做法：使使 最小最小|)(|max1ii
32、miyxP 太复杂太复杂 使使 最小最小 miiiyxP1|)(|不可导，求解困难不可导，求解困难 使使 最小最小 miiiyxP12|)(|3.5 曲线拟合的曲线拟合的最小二乘法最小二乘法一、一、最小二乘拟合最小二乘拟合多项式多项式 确定多项式确定多项式 ，对于一组数据，对于一组数据(xi,yi)(i=1,2,n)使得使得 达到达到极小极小，这里，这里 n m。nnxaxaaxP .)(10 miiiyxP12)(实际上是实际上是 a0,a1,an 的多元函数，即的多元函数，即 miinininyxaxaaaaa121010.),.,(在在 的极值点应有的极值点应有nkak,.,0,0 ki
33、miiikaxPyxPa )()(201 kiminjijijxyxa 102 njmikiimikjijxyxa0112记记 mikiikmikikxycxb11,nnnnnnccaabbbb.000000法方程组法方程组(或或正规方程组正规方程组)回归系数回归系数定理定理最小二乘拟合多项式最小二乘拟合多项式存在唯一存在唯一(n 0,b 0)线性化：线性化：由由 可做变换可做变换xbay lnlnbBaAxXyY ,ln,1,lnBXAY 就是个就是个线性问题线性问题将将 化为化为 后易解后易解 A 和和B),(iiYX),(iiyxxbAeaxPBbea/)(,二、二、一般的一般的最小二乘
34、法最小二乘法 mii0222 miiiyxS*02)()(minxS miiiyxS02)(4.1)其中其中)()()()()(1100mnxaxaxaxSnn (4.2)为了更具一般性为了更具一般性,通常考虑为加权平方和通常考虑为加权平方和22 miiiixfxSx0222)()()(0)(x 是是a,b上的权函数上的权函数,它表示不同点它表示不同点(xi,f(xi)的数据比的数据比重不同重不同.minjiijjinxfxaxaaaI00210)()()(),(4.3)用用最小二乘法最小二乘法求拟合曲线的问题求拟合曲线的问题,就是在就是在形如形如(4.2)的的S(x)中求一函数中求一函数 y
35、=S*(x),使使(4.3)取得最小取得最小.它转化它转化求多元函数求多元函数(4.4),(*1*0naaa的极小值的极小值 问题问题.=2 (xi)aj j(xi)-f(xi)k(xi)=0 j=0n i=0makI(k=0,1,n)(j,k)=(xi)j(xi)k(xi),i=0m(f,k)=(xi)f(xi)k(xi)dk i=0m(k=0,1,n)j=0n(j,k)aj=dk(k=0,1,n)Ga=d这方程称为这方程称为法方程法方程，可写成矩阵形式，可写成矩阵形式:上式可改写为上式可改写为若记若记(4.5)(4.6)由求多元函数的极值的必要条件，有由求多元函数的极值的必要条件，有),(
36、10naaa其中其中a=T,d=(d0,d1,dn)T,G=(0,0)(0,n)(0,1)(1,0)(1,n)(1,1)(n,0)(n,n)(n,1)(4.7)要使法方程要使法方程(4.6)有唯一解有唯一解a0,a1,an,就要求矩阵就要求矩阵G非非奇异奇异.必须指出必须指出,0(x),1(x),n(x)在在a,b上线性无关不能上线性无关不能推出矩阵推出矩阵G非奇异非奇异.例如例如,令令 0(x)=sinx,1(x)=sin2x,x 0,2,显然显然 0(x),1(x)在在0,2 上线性无关上线性无关,但若取点但若取点xk=k,k=0,1,2(n=1,m=2),那么有那么有 0(xk)=1(x
37、k)=0,k=0,1,2,由此得出由此得出G=0(0,0)(0,1)(1,0)(1,1)为保证为保证(4.6)的系数矩阵的系数矩阵G非奇异，必须加上另外的条件非奇异，必须加上另外的条件.定义定义7 设设 0(x),1(x),n(x)Ca,b的任意线性组合的任意线性组合在点集在点集xi,i=0,l,.,m(m n)上至多只有上至多只有n个不同的零点个不同的零点,则称则称 0(x),1(x),n(x)在点集在点集xi,i=0,l,.,m上满足哈尔上满足哈尔(Haar)条件条件.可以证明可以证明,如果如果 0(x),1(x),n(x)Ca,b在在xi0m上满上满足哈尔足哈尔(Haar)条件条件,则法
38、方程则法方程(4.6)的系数矩阵的系数矩阵G非奇异非奇异.于是方程于是方程(4.6)(4.6)存在唯一的解存在唯一的解nkaakk,1,0,*从而得到函数从而得到函数f(x)的最小二乘解为的最小二乘解为:)()()()(*1*10*0*xaxaxaxSnn 可以证明这样得到的可以证明这样得到的)(*xS对任何形如对任何形如(4.2)(4.2)的的S(x),),都有都有miiiimiiiixfxSxxfxSx0202*)()()()()()()(*xS的确是所求最小二乘解的确是所求最小二乘解.故故给定给定f(x)的离散数据的离散数据 miyxii,1,0),(要确定要确定是困难的是困难的.一般可
39、取一般可取nxxspan,1但这样做当但这样做当n大于等于大于等于3 3时时,G G为病态问题为病态问题.通常对通常对n=1=1的简单情形可以通过求法方程的简单情形可以通过求法方程(.6).6)得到得到)(*xS有时根据给定数据图形有时根据给定数据图形,其拟合函数表面上不是其拟合函数表面上不是(.2).2)的形式的形式但通过变化可化为线性模型但通过变化可化为线性模型,例如例如,bxaexS)(若两边取对数得若两边取对数得bxaxS ln)(ln例已知一组实验数据如下例已知一组实验数据如下,求它的拟合曲线求它的拟合曲线xi12345yi44.5688.5wi21311解:选择线性函数做拟合曲线,
40、令xaaxs101)(function f=polifitw(x,y,w,n)%带权最小二乘拟合m=length(x);A=zeros(n+1,n+1);b=zeros(n+1,1);for i=1:n+1 for j=1:n+1 for t=1:m A(i,j)=A(i,j)+w(t)*x(t)(i+j-2)end endendfor i=1:n+1 for t=1:m b(i)=b(i)+w(t)*y(t)*x(t)(i-1);endendf=Ab;x=1 2 3 4 5;y=4 4.5 6 8 8.5;w=2 1 3 1 1;P=polifitw(x,y,w,1)例例10 10 设数据设
41、数据)4,3,2,1,0)(,(iyxii由表给出，表中第由表给出，表中第4 4行为行为iiyy ln可以看出数学模型为可以看出数学模型为bxaey 用最小二乘法确定用最小二乘法确定a a及及b.b.i012341.005.101.255.791.506.531.757.452.008.461.629 1.756 1.876 2.0082.135ixiyiy解:两边取对数得:bxay lnln若令xbxAyaAyy,1,ln,ln有先将),(),(iiiiyxyx转化为 用最小二乘法得到的法方程组用最小二乘法得到的法方程组(4.6)，其系数矩阵，其系数矩阵G是病态的是病态的,但如果但如果 0(
42、x),1(x),n(x)是关于点集是关于点集 xi(i=0,l,.,m)带权带权(xi)(i=0,l,.,m)正交正交的函数族，即的函数族，即则方程（则方程（4.6）的解为）的解为(j,k)=(xi)j(xi)k(xi)=i=0m0,jk,Ak j=k.=ak*=(k,k)(f,k)(xi)f(xi)k(xi)i=0m(xi)k2(xi)i=0m(k=0,l,.,n)3.5.2 用正交多项式做最小二乘拟合用正交多项式做最小二乘拟合(5.8)且平方误差为且平方误差为2*02222)(|knkkaAf )()()()(*1*10*0*xaxaxaxSnn从而从而:离散点集上正交多项式的构造方法离散
43、点集上正交多项式的构造方法:给定点集给定点集 miix0和权数和权数 miiw0并且点集并且点集 miix0中至少中至少有有n+1个互异个互异,则由下列三项递推公式则由下列三项递推公式1,2,1),()()()()(,1)(11010nkxPbxPaxxPaxxPxPkkkkk给出的多项式序列给出的多项式序列)()(0mnxPnkk是正交多项式序列是正交多项式序列,其中其中),(),(,),(),(11kkkkkkkkkkPPPPbPPPxPa例:已知点集 1,75.0,5.0,25.0,040iix和权数 1,1,1,1,140iiw试用三项递推公式求关于该点集的正交多项式)(),(),(2
44、10 xPxPxP解:,5.2)()P,P(,5)()P,P(1)P4020004020000iiiiiiixPxwxxPwx（5.0)(5.0),/(),(0100000 xaxxPPPPxPa3125.0)(),(625.0)(),(214011214011iiiiiiixPxwPxPxPwPP125.0),(),(,5.0),(),(0011111111PPPPbPPPxPa125.0)5.0()()()()(201112xxPbxPaxxP例:已知点集 1,75.0,5.0,25.0,040iix和权数 1,1,1,1,140iiw 96.1,09.1,81.0,35.0,1.040i
45、iy用正交多项式做最小二乘拟合解:125.0)5.0()(,5.0)(,1)(2210 xxxxx0546875.0),(,625.0),(,5),(22110006625.0),(,115.1),(,31.4),(210yyy211428571.1,784.1,862.0210aaa2221100*2114.15726.01214.0)()()()(xxxaxaxaxs做一般的二乘拟合.3.6.1 最佳平方三角逼近与三角插值最佳平方三角逼近与三角插值3.6 最佳平方三角逼近与快速傅里叶变换最佳平方三角逼近与快速傅里叶变换当当f(x)是周期函数时是周期函数时,显然用三角多项式逼近显然用三角多项
46、式逼近f(x)比用代数多项式更合适比用代数多项式更合适,本节主要讨论用三角多项式做最小平方逼近及本节主要讨论用三角多项式做最小平方逼近及快速傅里叶变换快速傅里叶变换(Fast Fourier Transform)简称简称FFT 算法算法.设设f(x)是以是以2为周期的平方可积函数为周期的平方可积函数,用三角多项式用三角多项式做最佳平方逼近函数做最佳平方逼近函数.由于三角函数族由于三角函数族在在0,2上是正交函数族上是正交函数族,于是于是f(x)在在 0,2 上的最小平上的最小平方三角逼近多项式方三角逼近多项式Sn(x)的系数是的系数是:)sin()cos()sin()cos(21)(110nx
47、bnxaxbxaaxSnnn)sin(),cos(,),sin(),cos(,1kxkxxxak,bk 称为傅里叶系数称为傅里叶系数,函数函数f(x)按傅里叶系数展开得到的级数按傅里叶系数展开得到的级数就称为傅里叶级数就称为傅里叶级数,只要只要f(x)在在 0,2 上分段连续上分段连续,则级数则级数(6.3)一致一致收敛到收敛到f(x).频谱分析频谱分析),.1,0(,)sin()(1)cos()(12020nkdxkxxfbdxkxxfakk00)sin()cos(21kkkkxbkxaa2.离散型离散型当)(xf只是在给定的离散点集1,1,0,2NjjNxj上已知时，则可以类似地得到离散点集正交性与相应的Fourier级数，一下只给出奇数个点的情形。令在给定点集上是正交的，成立函数组，可以证明对任意sin,cos,sin,cos102,1,0,122kxkxxxmlkmjmjxj)2,1,0(),(mjxffjj若令则)(xf的最小二乘三角逼近为：于是有时可以证明当其中)2,1,0(,)(),1(,122sin122),1,0(,122cos122),(),sin()cos(21)(202010mjfxSmnmkmjkfmbmkmjkfmamnkxbkxaaxSjjmmjjkmjjknkkknmkkknkxbkxaaxS10)sin()cos(21)(
