数值分析ppt第3章-函数逼近与曲线拟合

上页下页第3章函数逼近与曲线拟合•3.1函数逼近的基本概念•3.2正交多项式—LagrangeandChebyshev•3.3最佳一致逼近多项式•3.4最佳平方逼近多项式•3.5曲线拟和的最小二乘法•3.6*最佳平方三角逼近与快速傅里叶变换•3.7*有理逼近本章基本内容上页下页曲线拟合也叫函数逼近，就是用简单的函数P(x)近似代替函数f(x)，f(x)称为逼近（被拟合）函数，P(x)称为逼近（拟合）函数.前面所学的插值函数也是函数逼近的一种重要的方法，它虽然在节点处函数值精确相等（甚至导数值也相等），但它的缺陷是在非节点处误差可能很大，即所谓的龙格现象就是一个例子。再一个原因是数据的来源可能也是有误差的，因此就没有必要非在节点处函数值相等。3.1函数逼近的基本概念3.1.1函数逼近与函数空间上页下页本章讨论的函数逼近，是指对函数类A中给定的函数f(x),记作f(x)∈A,要求在另一类简单的便于计算的函数类B中求函数p(x)∈B，使p(x)与f(x)的误差在某种度量意义下最小.函数类A通常是区间[a,b]上的连续函数，记作C[a,b]，称为函数逼近空间;而函数B通常为n次多项式,有理函数或分段低次多项式等.上页下页数学上常把在各种集合中引入某一些不同的确定关系称为赋予集合以某种空间结构，并将这样的集合称为空间。例1所有实n维向量集合，按向量的加法和数乘构成实数域R上的线性空间---Rn,称为n维向量空间.例2、对次数不超过n的（n为正整数）实系数多项式全体，按多项式加法和数乘构成数域R上的多项式线性空间--Hn,称为多项式空间.例3、所有定义在[a,b]集合上的连续函数全体，按函数的加法和数乘构成数域R上的连续函数线性空间–C[a,b],称为连续函数空间.类似地记Cp[a,b]为具有p阶连续导数的函数空间.上页下页1122...0,nnaxaxax则称x1,x2,…,xn线性相关，否则称x1,x2,…,xn线性无关，即只有当a1=a2=…=an=0时等式才成立.定义1设集合S是数域P上的线性空间，元素x1,x2,…,xn∈S，如果存在不全为零的数a1,a2,…,an∈P，使得上页下页则x1,…,xn称为空间S的一组基，记为S=span{x1,…,xn}，并称空间S为n维空间，系数a1,…,an为x在基x1,…,xn下的坐标，记为(a1,…,an)，如果S中有无限多个线性无关元素x1,…,xn,…，则称S为无限维线性空间.若线性空间S是由n个线性无关元素x1,…,xn生成的，即对任意x∈S，都有,11nnxaxax上页下页它由n+1个系数(a0,a1,…,an)唯一确定.1,x,…,xn线性无关，它是Hn的一组基，故集合Hn=span{1,x,…,xn}，且(a0,a1,…,an)是p(x)的坐标向量，Hn是n+1维的.下面考虑次数不超过n实系数多项式集合Hn，其元素p(x)∈Hn表示为,)(10nnxaxaaxp上页下页其中ε为任意给的小正数，即精度要求.这就是下面著名的魏尔斯特拉斯（Weierstrass）定理.对连续函数f(x)∈C[a,b]，它不能用有限个线性无关的函数表示，故C[a,b]是无限维的，但它的任一元素f(x)∈C[a,b]均可用有限维的p(x)∈Hn逼近，使误差)()()()(maxxpxfxpxfbxa上页下页在[a,b]上一致成立.（证明略，书p63有说明.）定理1设f(x)∈C[a,b]，则对任何ε0，总存在一个代数多项式p(x)，使)()(xpxf上页下页函数逼近问题就是对任何f(x)∈C[a,b]，在子空间Ф中找一个元素φ*(x)∈Ф，使f(x)-φ*(x)在某种意义下最小.)()()()(1100xaxaxaxnn更一般地，可用一组在C[a,b]上线性无关的函数集合来逼近f(x)∈C[a,b]，元素niix0)()(,),(),()(10xxxspanxn表示为上页下页3.1.2范数与赋范线性空间为了对线性空间中元素大小进行衡量，需要引进范数定义，它是Rn空间中向量长度概念的直接推广.上页下页定义2设S为线性空间,x∈S,若存在唯一实数满足条件：(1)‖x‖≥0;当且仅当x＝0时,‖x‖＝0;(正定性)(2)‖αx‖＝|α|‖x‖,α∈R;(齐次性)(3)‖x＋y‖≤‖x‖＋‖y‖,x,y∈S.(三角不等式)则称为线性空间S上的范数,S与一起称为赋范线性空间,记为X.||||||||||||上页下页称为－范数或最大范数1称为－范数2称为－范数||x||||,11nxii1n2221||x||iix＝对Rn上的向量x＝(x1,x2,…,xn)T,三种常用范数为：上页下页||||max|()|,axbffx类似的对连续函数空间C[a,b],若f∈C[a,b]可定义以下三种常用函数的范数称为范数1|||||()|,baffxdx1称为范数1222||||(()),baffxdx2称为范数可以验证这样定义的范数均满足定义2中的三个条件.上页下页3.1.3内积与内积空间在线性代数中，Rn上的两个向量x＝(x1,x2,…,xn)T与y＝(y1,y2,…,yn)T的内积定义为(x,y)=x1y1+x2y2+…+xnyn.若将它推广到一般的线性空间X，则有下面的定义.上页下页定义3设X是数域K(R或C)上的线性空间，对任意u,v∈X，有K中一个数与之对应，记为(u,v)，它满足以下条件：.0),(,0,0),()4(;,,),,(),(),()3(;,,),,(),()2(;,,),(),()1(______uuuuuXwvuwvwuwvuXvuKavuavauXvuuvvu时当且仅当则称(u,v)为X上u与v的内积，对应了内积的线性空间称为内积空间.定义中(1)当K为实数域R时为(u,v)＝(v,u).上页下页如果(u,v)=0，则称u与v正交(记为u⊥v)，这是向量相互垂直概念的推广.关于内积空间有以下重要定理.定理2设X为一个内积空间,对任意u,v∈X有如下不等式成立它称为柯西－施瓦茨(Cauchy-Schwarz)不等式.).,)(,(),(2vvuuvu上页下页证明当v=0时,显然成立.设v≠0，则(v,v)0,且对任何数t有(这里设为实空间)).,(),(2),(),(02vvtvutuutvutvu取t=-(u,v)/(v,v),代入上式右端，得.0),(),(),(),(2),(22vvvuvvvuuu即得v≠0时有).,)(,(),(2vvuuvu上页下页),(),(),(),(),(),(),(),(),(212222111211nnnnnnuuuuuuuuuuuuuuuuuuG定理3设X为一个内积空间，u1,u2,…,un∈X，矩阵称为格拉姆(Gram)矩阵,则G非奇异的充分必要条件是u1,u2,…,un线性无关.证明G非奇异等价于detG≠0，其充分必要条件是下面齐次线性方程组只有零解)8(,,1,0),(,11nkauuuuajknjjknjjj上页下页而nkuuaknjjj,,1,0,10,11njjjnjjjuaua)9(022111nnnjjjuauauaua从以上的等价关系可知道，detG≠0等价于从(8)推出a1=a2=…=an=0,而后者等价于从(9)推出a1=a2=…=an=0，即u1,u2,…,un线性无关.证毕上页下页在内积空间X上可以由内积导出一种范数，即对于u∈X，记)10(),(uuu容易验证它满足范数定义的三条性质,其中三角不等式)11(vuvu可由定理2直接得出，即2222),(),(),(2),(2)(vuvuvuvvvuuuvvuuvu两端开方即得(11).上页下页例1Rn的内积，设x,y∈Rn，x＝(x1,x2,…,xn)T，y＝(y1,y2,…,yn)T，则其内积定义为)12(),(1niiiyxyx由此导出的向量2-范数为21122),(niixxxx上页下页若给定实数ωi0(i=1,…,n)，{ωi}称为权函数，则在Rn上可定义加权内积为)13(),(1niiiiyxyx相应的向量2-范数为21122),(niiixxxx不难验证(13)给出的(x,y)满足内积定义的4条.当ωi=1(i=1,…,n)时，(13)就是(12).上页下页)14(),(1niiiiyxyx如果x,y∈Cn，带权内积定义为这里{ωi}仍为正实数序列.在C[a,b]上也可以类是定义带权内积，为此先给出权函数定义.上页下页定义4设[a,b]是有限或无限区间，在[a,b]上的非负函数ρ(x)满足条件：),,1,0()()1(kdxxxbak存在且为有限值.0)(0)()(),(],[)2(xgdxxxgxgbaba则，如果数上的非负连续函对则称ρ(x)为[a,b]上的一个权函数.它的物理意义可以解释为密度函数.上页下页例2C[a,b]上的内积，设f(x),g(x)∈C[a,b]，ρ(x)是上给定的权函数，则可内积定义为容易验证它满足内积定义的4条，由此内积导出的范数)15()()()())(),((badxxgxfxxgxf)16()()())(),(()(2122badxxfxxfxfxf称(15)和(16)为带权ρ(x)的内积和范数，特别常用的是ρ(x)≡1的情形，即badxxgxfxgxf)()())(),((2122)()(badxxfxf上页下页),(),(),(),(),(),(),(),(),(),,,(20111010100010nnnnnnnGG若φ0,φ1,…,φn是C[a,b]中的线性无关函数族，记φ=span{φ0,φ1,…,φn}，它的拉姆(Gram)矩阵为根据定理3可知φ0,φ1,…,φn线性无关的充分必要条件是detG(φ0,φ1,…,φn)≠0.上页下页3.2.1正交函数族与正交多项式3.2正交多项式)(0)(0)()()(),(kjAkjdxxxxkkjbakj则称{φk(x)}是[a,b]上带权ρ(x)的正交函数族.若Ak≡1，则称之为标准正交函数族.定义5如果函数f(x),g(x)在[a,b]上连续,满足badxxgxfxxgxf0)()()())(),((上的连续函数族则称f(x)与g(x)在[a,b]上关于权)(x正交,如果[a,b])(xk满足上页下页例如,三角函数族1,cosx,sinx,cos2x,sin2x,…是在区间[-π,π]上的正交函数系，因为对k=1,2,…有实际上，这就是付里叶(Fourier)逼近的基函数.而对k,j=1,2,…，当k≠j时有)cos,(cos)sin,(sin,2)1,1(kxkxkxkx0sin)sin,1()cos,1()sin,(coskxdxkxkxkxkx0])cos()[cos(21coscos)cos,(cosdxxjkxjkjxdxkxjxkx0)sin,(cos)sin,(sinjxkxjxkx上页下页)(0)(0)()()(),(kjAkjdxxxxkkjbakj则称多项式序列{φn(x)}为在[a,b]上带权ρ(x)的正交，称φn(x)为[a,b]上带权ρ(x)的n次正交多项式.定义6设φn(x)是[a,b]上首项系数an≠0的n次多