数值分析--第3章函数逼近与快速傅里叶变换

2020/10/31课件1第3章函数逼近与快速傅里叶变换3.1函数逼近的基本概念3.2正交多项式3.3最佳平方逼近3.4曲线拟合的最小二乘法3.5有理逼近3.6三角多项式与快速傅里叶变换2020/10/31课件23.1函数逼近的基本概念3.1.1函数逼近与函数空间1、数值计算中经常要计算函数值，如计算机中计算基本初等函数及其他特殊函数；2、当函数只在有限点集上给定函数值，要在包含该点集的区间上用公式给出函数的简单表达式.问题这些都涉及到在区间上用简单函数逼近已知复杂],[ba函数的问题，这就是函数逼近问题.2020/10/31课件3插值法就是函数逼近问题的一种.记作，Axf)(),(xf本章讨论的函数逼近，是指“对函数类中给定的函数A中求函数，Bxp)(B使与的误差在某种度量)(xp)(xf要在另一类简单的便于计算的函数类意义下最小”.函数类通常是区间上的连续函数，记作，A],[ba],[baC称为连续函数空间.2020/10/31课件4函数类通常为次多项式，有理函数或分段低次多项式等.Bn数学上常把在各种集合中引入某些不同的确定关系称为赋予集合以某种空间结构，并将这样的集合称为空间.与数的乘法构成实数域上的线性空间，例如将所有实维向量组成的集合，按向量加法及向量n称为维n记作，nR向量空间.2020/10/31课件5类似地,记为具有阶连续导数的函数空间.],[baCpp记作.],[baC所有定义在上的连续函数集合，按函数加法和],[ba数与函数乘法构成数域上的线性空间，R按通常多项式与多项式加法及数与多项式乘法也构成数域称为多项式空间.用表示，nH上一个线性空间，R对次数不超过(为正整数)的实系数多项式全体，nn2020/10/31课件6定义1,,,1Sxxn设集合是数域上的线性空间，元素SP如果存在不全为零的数，Pn,,1,011nnxx（1.1）则称线性相关.nxx,,1否则，若等式(1.1)只对成立，021n则称线性无关.nxx,,1使得2020/10/31课件7},,{1nxxspanS系数称为在基n,,1x并称空间为维空间，nS若线性空间是由个线性无关元素生成的，Snnxx,,1都有Sxnnxxx11则称为空间的一组基，nxx,,1S记为nxx,,1下的坐标，).,,(1n记作如果中有无限个线性无关元素则称,,,,1nxxSS为无限维线性空间.2020/10/31课件8,)(10nnxaxaaxp（1.2）它由个系数唯一确定.1n),,,(10naaa考察次数不超过次的多项式集合，nnH它是的一组基，nH是线性无关的，nxx,,,1},,,,1{nnxxspanH且是的坐标向量，是维的.),,,(10naaa)(xpnH1nnHxp)(表示为其元素故2020/10/31课件9使误差对连续函数，它不能用有限个线性无关的],[)(baCxf函数表示，故是无限维的，但它的任一元素],[baC)(xf均可用有限维的逼近，nHxp)()()(maxxpxfbxa(为任给的小正数)，这就是著名的魏尔斯特拉斯定理.2020/10/31课件10使定理1总存在一设，],[)(baCxf则对任何，0个代数多项式，)(xp)()(xpxf在上一致成立.],[ba伯恩斯坦1912年给出的证明是一种构造性证明.他根据函数整体逼近的特性构造出伯恩斯坦多项式nkknxPnkfxfB0)()(),(（1.3）2020/10/31课件11为二项式展开系数，并证明了!)1()1(kknnnkn)(),(limxfxfBnn在上一致成立；]1,0[若在上阶导数连续，则)(xf]1,0[m其中,)1()(knkkxxknxP).(),(lim)()(xfxfBmmnn这个结果不但证明了定理1，而且由(1.3)给出了的一个逼近多项式，但它收敛太慢，实际中很少使用.)(xfnkknxPnkfxfB0)()(),(（1.3）2020/10/31课件12更一般地，可用一组在上线性无关的函数集合],[baC来逼近，],[)(baCxfniix0)(可表示为],[)}(,),(),({)(10baCxxxspanxn).()()()(1100xaxaxaxnn（1.4）此时元素函数逼近问题就是对任何，],[)(baCxf找一个元素，)(*x使在某种意义下最小.)()(*xxf在子空间Φ2020/10/31课件133.1.2范数与赋范线性空间为了对线性空间中元素大小进行衡量，需要引进范数定义，它是空间中向量长度概念的直接推广.nR2020/10/31课件14定义2设为线性空间，，若存在唯一实数‖·‖，满足条件：（1）当且仅当时，（正定性）,0x0x;0x（2）(齐次性)R;,xx（3）(三角不等式).,,Syxyxyx则称‖·‖为线性空间上的范数，与‖·‖一起称为赋范线性空间，记为SS.XSSx2020/10/31课件15例如，在上的向量三种常用范数为nR,R),,(1nTnxxx称为范数或最大范数，,max1inixx称为1-范数，,11niixx称为2-范数.,)(12122niixx2020/10/31课件16而满足‖·‖1=1的向量则为对角线长度为1的菱形.121xx实际上任何向量的实值函数，只要满足上述三个条件，就可以定义成一种向量范数.在中，满足‖·‖2=1，即的向量为单位圆，2R12221xx满足‖·‖∞=1，即的向量为单位正方形，1},max{21xx2020/10/31课件17所以说，范数是对向量长度的度量，度量方式不同，结果也不一样，但不同范数之间是存在等价关系的.2020/10/31课件18类似地，对连续函数空间，若,],[baC],[)(baCxf称为范数，,)(maxxffbxa称为1-范数，,)(1dxxffba称为2-范数.,))((2122badxxff可以验证这样定义的范数均满足定义2中的三个条件.2020/10/31课件193.1.3内积与内积空间.),(11nnyxyxyx在线性代数中，中两个向量及nRTnxxx),,(1Tnyyy),,(1的内积定义为若将它推广到一般的线性空间，则有下面的定义.X（1.5）2020/10/31课件20定义3;X,,),(),((1)vuuvvu;X,,K),,(),((2)vuvuvu;X,,),,(),(),((3)wvuwvwuwvu.0),(0,0),((4)uuuuu时，当且仅当则称为X上与的内积.),(vuuv,X,vuX是数域K(R或C)上的线性空间，对有K中一个数与之对应，记为，它满足),(vu以下条件：2020/10/31课件21定义中（1）的右端称为的共轭，),(vu),(vu当K为实数域R时.),(),(uvvu如果，则称与正交，这是向量相互垂直概念的推广.0),(vuuv定义了内积的线性空间称为内积空间.2020/10/31课件22定理2对有,,Xvu).,)(,(),(2vvuuvu（1.6）称为柯西-施瓦茨(Cauchy-Schwarz)不等式.证明当时（1.6）式显然成立.0v).,(),(2),(),(02vvvuuuvuvu现设，0v则，0),(vv且对任何数有取，),/(),(vvvu设X为一个内积空间，代入上式右端，得2020/10/31课件23即得时0v).,)(,(),(2vvuuvu0),(),(),(),(2),(22vvvuvvvuuu2020/10/31课件24定理3),(),(),(),(),(),(),(),(),(212222111211nnnnnnuuuuuuuuuuuuuuuuuuG（1.7）称为格拉姆(Gram)则非奇异的充分必要条件是线性无关.nuuu,,,21G,X,,,21nuuu设X为一个内积空间，矩阵2020/10/31课件25证明njjkjknjjjuuuu11),(),(只有零解；022111nnnjjjuuuu0),(01njjjnjjjuunk,,2,1（1.9）,0),(0knjjjuuG非奇异等价于，其充要条件是齐次0detG方程组,0（1.8）nk,,2,1而2020/10/31课件26从以上等价关系知，而后者等价于从（1.9）推出,021n即线性无关.nuuu,,,21,021n在内积空间X,Xu),(uuu（1.10）0detG等价于从（1.8）推出记njjkjknjjjuuuu11),(),(（1.8）nk,,2,1,0nnnjjjuuuu2211102020/10/31课件27两端开方即得三角不等式vuvu（1.11）利用2222)(vvuuvu),(),(2),(vvvuuu2),(vuvuvu2020/10/31课件28例1与的内积.nRnC设,R,nyx,),,(1Tnxxx,),,(1Tnyyyniiiyxyx1),(（1.12）向量2-范数为2112212)(),(niixxxx2020/10/31课件29相应的范数为niiiiyxyx1),(（1.13）若给定实数),,,2,1(0nii称为权系数，}{i当时，),,2,1(1nii.)(21122niiixxnR上的加权内积为（1.13）就是前面定义的内积.2020/10/31课件30如果，nCyx,niiiiyxyx1),(（1.14）这里仍为正实数序列，为的共轭.}{iiyiy在上也可以类似定义带权内积.],[baC带权内积定义为2020/10/31课件31定义4设是有限或无限区间，在上的非负],[ba],[ba函数满足条件：)(x（1）存在且为有限值bakdxxx)(),,1,0(k（2）对上的非负连续函数，如果],[ba)(xgbadxxxg,0)()(则称为上的一个权函数.)(x],[ba.0)(xg2020/10/31课件32例2设],,[)(),(baCxgxf)(x是上给定的权函数,],[babadxxgxfxxgxf.)()()())(),((（1.15）由此内积导出的范数为212))(),(()(xfxfxf称（1.15）和（1.16）为带权的内积和范数.)(x],[baC上的内积.则可定义内积（1.16）212)()(badxxfx2020/10/31课件33常用的是的情形，即1)(xbadxxgxfxgxf.)()())(),((2122)()(badxxfxf2020/10/31课件34若是中的线性无关函数族，n,,,10],[baC},,,,{10nspan),,,(10nGG),(),(),(),(),(),(),(),(),(101110101000nnnnnn（1.17）根据定理3可知线性无关的充要条件是n,,,10.0),,,(det10nG它的格拉姆矩阵为记2020/10/31课件35函数逼近主要讨论给定，求它的最佳逼近多项式的问题.)()(min)()(*xPxfxPxfnHP3.1.4最佳逼近],[baCf若使误差则称是在