数值分析第3章 (1)

1、1第三章第三章 函数逼近与函数逼近与快速傅立叶变换快速傅立叶变换23.1 函数逼近的基本知识函数逼近的基本知识n函数逼近函数逼近:用比较简单的函数代替复杂的函数用比较简单的函数代替复杂的函数n误差为最小，即距离为最小（不同的度量意义）误差为最小，即距离为最小（不同的度量意义）n对同一个被逼近函数，不同度量意义下的逼近，对同一个被逼近函数，不同度量意义下的逼近，逼近函数是不同的逼近函数是不同的. .3通常叫做数量乘法通常叫做数量乘法。451，向量空间，向量空间nR几种线性空间几种线性空间2，多项式空间，多项式空间nH3，连续函数空间，连续函数空间,baC4，,baCp5 5nnR 6范数范数例如

2、例如向向量量范范数数、上上的的 xxxRn21矩矩阵阵范范数数、上上的的 AAARnn217赋范线性空间赋范线性空间8内积内积内积空间内积空间Cauchy-Schwarz不等式不等式9例如例如 niiiyxyx1, niiiiyxyx1, 12103内积导出的范数内积导出的范数11定义定义1 1：设：设)(x 定义在有限或无限区间定义在有限或无限区间a,b上上, ,如果满足如果满足:(1):(1)对任取对任取; 0)(, xbax ( (2) )( )(0,1,);bnaxx dx n 存在且有限值( )0bag xx dx）， 则称其为区间则称其为区间a,b上的权函数上的权函数. .( (3

3、)a,b)a,b非负连续函数非负连续函数g( ) x 若g( )0 x 则12定义定义2 如果函数如果函数f(x), g(x) 在在 a a, ,b b 上连续上连续, ,满满足足 badxxgxfx0)()()( )(x 则称则称f(x)与与g(x)在在a,b上关于权上关于权 正交正交, ,如果如果a,b上的连续函数系上的连续函数系 )(xk 满足满足定义定义1：设：设为为称称dxxgxfxbacxgxfba) )( () )( () )( (, , ,) )( (),),( ( )(x f(x),g(x)关于权关于权的的内积内积，记为，记为(f, g).3.2 正交多项式正交多项式13 )

4、(0)(0)()()(kjAkjdxxxxkkjbakj ），（称其是称其是a,b上关于权上关于权 的的正交函数系正交函数系.)(x 上述是正交化过程上述是正交化过程14(1)它们是次数不超过它们是次数不超过n的多项式。的多项式。152 常见的正交多项式系常见的正交多项式系（1 1）勒让德多项式）勒让德多项式), 1 , 0()1(!21)(2 nxdxdnxPnnnnn 性质性质：正交性正交性. .Pn(x) 在在 -1,1 上是正交多上是正交多项项式系式系, ,且且 nmnnmdxxPxPnm122,0)()(11161718 三项递推关系三项递推关系), 2 , 1()()()12(11

5、)()(1)(1110 nxnTPxxPnnxPxxPxPnnn8/ )33035()(2/ )35()(2/ )13()(2443322 xxxPxxxPxxP19对零的平方误差最小对零的平方误差最小 1122112)()()!2() !(2dxxfdxxPnnnn)(次多项式次多项式为任意首一为任意首一nxf零点零点n次的在次的在(-1,1)内有内有n个互异实零点个互异实零点.20定义定义1 ChebyshevChebyshev多项式多项式称称Tn(x)=cos(n arccosx),|x|1为为n次次Chebyshev多项式多项式Chebyshev多项式及其性质多项式及其性质21Cheb

6、yshevChebyshev多项式的性质多项式的性质n性质性质1n1n次次ChebyshevChebyshev多项式相邻三项有递推关系多项式相邻三项有递推关系 ：T T0 0(x)=1,T(x)=1,T1 1(x)=x,(x)=x,T Tn+1n+1(x)=2xT(x)=2xTn n(x)-T(x)-Tn-1n-1(x),n=1,2,(x),n=1,2,. .22性质性质2n次次Chebyshev多项式多项式Tn(x)的首项系的首项系数为数为12n23性质性质3 3 正交性。正交性。 T Tn n( (x x)在在-1,1-1,1上是关于权上是关于权(1-(1-x x2 2) )-1/2-1/

7、2正交多项式系正交多项式系, ,且且 0,2/0,0)()(11112nmnmnmdxxTxTxnm 24性质性质4 4性质性质5 5当当 时，时， 交错取到极大值交错取到极大值 1 和极小值和极小值 1，即，即),., 1, 0(cosnknktk )(kntT |)(|) 1()(xTtTnkkn零点：零点：T Tn n( (x x) )在在-1,1-1,1内有内有n n个互异实零点个互异实零点: :), 2 , 1()212cos(nknkxk 25显然显然 是首项系数为是首项系数为1 1的的n n次次ChebyshevChebyshev多项式多项式. . 又若记又若记 为一切定义在，上

8、为一切定义在，上首项系数为首项系数为1 1的的n n次多项式的集合次多项式的集合*()nTx*1( )( )2nnnTxTx26函数逼近问题函数逼近问题举例举例n对被逼近函数对被逼近函数f(x)=sqrt(xf(x)=sqrt(x）, ,在区间在区间 ，上按如下三种不同的逼近方式求其形如上按如下三种不同的逼近方式求其形如 p p1 1(x)=ax+b (x)=ax+b 的逼近函数的逼近函数. .27n解解 （1)1)按插值法，以按插值法，以x x0 00, x0, x1 1为插值节为插值节点对点对f(x) f(x) 作一次插值所得形如作一次插值所得形如(1)(1)式的式的p p1 1(x)(x

9、)是是p p1 1(x)=x.(x)=x. 按下列的距离定义按下列的距离定义dis(f(x),pdis(f(x),p1 1(x)=f(x)-p(x)=f(x)-p1 1(x)(x)=max|f(x)-p=max|f(x)-p1 1(x)|(x)|的意义下，在的意义下，在P P ，中求得与，中求得与f(x)f(x)的距离最小的的距离最小的形如形如(1)(1)式的式的p p1 1(x)(x)是是p p(x)=x+1/8.(x)=x+1/8.按距离按距离dis (f(x),pdis (f(x),p(x) =f(x)-p(x) =f(x)-p1 1(x)(x)=(=(0 01 1f(x)-pf(x)-

10、p(x)(x)dx) dx) 1/21/2的意义下，在的意义下，在P P ，中求得与，中求得与f(x)f(x)的距离最小的的距离最小的形如形如(1)(1)式的式的p p(x)(x)是是p p(x)=4/5x+4/15(x)=4/5x+4/1528n可见，对同一个被逼近函数，不同距离意义下可见，对同一个被逼近函数，不同距离意义下的逼近，逼近函数是不同的的逼近，逼近函数是不同的. .29最佳一致逼近最佳一致逼近 多项式多项式| )(|max|,xffbax 在在 意义下，使得意义下，使得 最小。最小。|fP偏差偏差在在P Pn na,ba,b中，是否存在一个元素中，是否存在一个元素p pn n(x

11、)(x)，使不等式使不等式f(x)-pf(x)-p* *n n(x)(x)f(x)-pf(x)-pn n(x)(x) (1) (1)对任意的对任意的p pn n(x)P(x)Pn na,ba,b成立成立? ?30一、一、 最佳逼近最佳逼近多项式多项式的存在性的存在性n定理定理对任意的对任意的f(x)Cf(x)Ca,ba,b，在，在P Pn na,ba,b中中都存在对都存在对f(x)f(x)的最佳一致逼近元，记为的最佳一致逼近元，记为p p* *n n(x)(x)，即，即成立成立. .最小偏差最小偏差。*( )( )min max( )( )nnnnpHa x bf xpxf xpx 31定义定

12、义( (交错点组交错点组) ) 若函数若函数f(x)f(x)在其定义域的某一区间在其定义域的某一区间a,ba,b上上存在存在n n个点个点xxk k n n k=1k=1，使得，使得|f(x|f(xk k)|=max|f(x)|=f(x)|=max|f(x)|=f(x)，k=1k=1，2 2，n;n;-f(x-f(xk k)=f(x)=f(xk+1k+1) )，k=1,2,k=1,2,，n-1,n-1,则称点集则称点集xxk k n n k=1k=1为函数为函数f(x)f(x)在区间在区间a,ba,b上的一个交错点组，上的一个交错点组，点点x xk k称为交错点组的点称为交错点组的点. .二二

13、 最佳一致逼近多项式的充要条件最佳一致逼近多项式的充要条件32n定理定理 ( (ChebyshevChebyshev定理）定理）p pn n* *(x)P(x)Pn na,ba,b为对为对f(x)Cf(x)Ca,ba,b的最佳一致逼近的最佳一致逼近多项式多项式的充要条的充要条件是误差曲线函数件是误差曲线函数f(x)- pf(x)- pn n* *(x) (x) 在区间在区间a,ba,b上存在一个至少由上存在一个至少由n+2n+2个点组成的个点组成的交错点组交错点组. . 即存在点集即存在点集 a x1 xn+2 b 使得使得 1)()()1()()(* xfxPxpxfkknk33证明充分性n

14、用反证法用反证法. . 设设f(x)- f(x)- p pn n(x)(x)在在a,ba,b上存在一个至少上存在一个至少由由n+2n+2个点组成的交错点组，但个点组成的交错点组，但p pn n(x)(x)不是最佳一致逼不是最佳一致逼近近多项式多项式. .不妨设不妨设H Hn na,b a,b 中的多项式中的多项式q qn n(x)(x)为最佳一致逼近为最佳一致逼近多项多项式式，即，即f(x)-qf(x)-qn n(x)(x)f(x)-f(x)-p pn n(x)(x). (4). (4)令令Q(x) = Q(x) = p pn n(x)(x) -q -qn n(x)(x) = =f(x)-qf

15、(x)-qn n(x)(x)- -f(x)- f(x)- p pn n(x)(x)记记xx1 1* *, , x x2 2* *, , , x xn+2n+2* * 为误差曲线函数为误差曲线函数f(x)- f(x)- p pn n(x)(x)在在a,ba,b上的交错点组，上的交错点组，34由由(4)(4)式可知式可知n n次多项式次多项式Q(x)Q(x)在点集在点集xx1 1* *, , x x2 2* *, , , x xn+2n+2* * 上的符号完全由上的符号完全由f(x)- f(x)- p pn n(x)(x)在这些点上的在这些点上的符号所决定，符号所决定， xx1 1* *, , x

16、 x2 2* *, , , x xn+2n+2* * 为为f(x)-f(x)-p pn n(x)(x)的交错点组，即的交错点组，即f(x)- f(x)- p pn n(x)(x) 在这在这n+2n+2个点上正负个点上正负( (或负或负 正正) )相间相间至少至少n+1n+1次，从而至少次，从而至少n+1n+1次改变符号，故次改变符号，故Q(x)Q(x)也也至少至少n+1n+1次改变符号，次改变符号， 说明说明n n次多项式次多项式Q(x)Q(x)至少在至少在a,ba,b上有上有n+1n+1个根，个根，矛盾矛盾. . 即必有即必有f(x)- f(x)- p pn n(x)(x)f(x)-qf(x

17、)-qn n(x)(x). .35), 2 , 1()(max21)(21max111111 nxfxTxnnnx三、关于最佳一致逼近三、关于最佳一致逼近多项式多项式的求解的求解 1 , 1 xTxnnn121)(121n定理 在区间上所有最高次项系数为上所有最高次项系数为1的的n次多项式中，次多项式中，与零的偏差最小，其最小偏差为与零的偏差最小，其最小偏差为3637（1 1） 当当f(x)f(x)为，上的为，上的n+1n+1次多项式时，求次多项式时，求f(x)f(x)在在P Pn n, ,中的最佳一致逼近多项式中的最佳一致逼近多项式. .不妨记不妨记f(x)=bf(x)=b0 0+b+b1

18、1x+x+ b+ bn+1n+1x xn+1n+1,|x|1,|x|1,且设且设b bn+1n+10 0 ，p pn n(x)(x)为最佳一致逼近元为最佳一致逼近元. . 由于首项系数为由于首项系数为1 1的的n+1n+1次次ChebyshevChebyshev多项式多项式T Tn+1n+1(x)(x)无无穷模最小，穷模最小，*11()()()nnnfxpxTxb考虑两种特殊情形考虑两种特殊情形38例例1 1 设设f(x)=4xf(x)=4x4 42x2xx x8x-5/28x-5/2， |x|1. |x|1. 求求f(x)f(x)在在P P3 3-1,1-1,1中的最佳一致逼近中的最佳一致逼

19、近多项式多项式p p3 3(x).(x). )()(*3xpxf与零的偏差最小。与零的偏差最小。81)(212)()(244142*3xxXTxpxfmin)()(max*311xpxfx解解 所求的最佳逼近多项式所求的最佳逼近多项式 应该满足：应该满足：)(*3xp382)(23*3xxxxp所以所以39对区间为对区间为a,ba,b的情形的情形，作变换作变换x=(b-a)t/2+(b+a)/2 (6)x=(b-a)t/2+(b+a)/2 (6)后，对变量为后，对变量为t t的多项式用的多项式用(5)(5)式求得式求得pn(t)(t)，然后再作，然后再作(6)(6)式的反变换得到式的反变换得到

20、a,ba,b上的最佳一致逼近多项式上的最佳一致逼近多项式. .40（2）逼近多项式为低次多项式时关于交错点组的定理关于交错点组的定理定理定理 设设p pn n* *(x)P(x)Pn na,ba,b为对为对 f(x)Cf(x)Ca,ba,b的最佳一致逼近多项式的最佳一致逼近多项式. . 若若f f(n+1)(n+1)(x)(x)在区间在区间a,ba,b上不变号，则上不变号，则x=ax=a和和b b为为误差曲线函数误差曲线函数f(x)-pf(x)-pn n(x)(x)在区间在区间a,ba,b上交上交错点组中的点错点组中的点. .41证证 用反证法用反证法. . 若点若点a (a (点点b b类似

21、类似) )不属于交错点不属于交错点组，那么在区间组，那么在区间(a,b)(a,b)内至少存在内至少存在n+1n+1个点属于个点属于交错点组交错点组. . 若若f(x)f(x)足够光滑，由交错点组的定足够光滑，由交错点组的定义，可以证得义，可以证得(a,b)(a,b)内的交错点必为误差曲线函内的交错点必为误差曲线函数数f(x)-f(x)-p pn n* *(x)(x)的驻点，的驻点，即区间即区间(a,b)(a,b)内内n+1n+1个交错点上，个交错点上， f(x)-f(x)-p pn n* *(x) (x) 的一阶导数等于零的一阶导数等于零. . 这样，由这样，由RolleRolle定理便可定理

22、便可推得在推得在(a,b)(a,b)内至少存在一点内至少存在一点 ，使得，使得f f (n+1)(n+1) ( ( ) ) =0.这与这与f f(n+1)(n+1)(x)(x)在在a,ba,b上不变号上不变号则则f f(n+1)(n+1)(x)(x)无零点矛盾，故点无零点矛盾，故点x=ax=a属于交错点组属于交错点组. .42推论推论1 1设设p pn n* *(x)P(x)Pn na,ba,b为对为对f(x)Cf(x)Ca,ba,b的最佳一的最佳一致逼近元致逼近元. . 若若f f(n+1)(n+1)(x)(x)在区间在区间(a,b)(a,b)上不变号，但上不变号，但在在x=a (x=a (

23、或或b)b)处不存在处不存在( (但为无穷但为无穷) )而符号与而符号与(a,b)(a,b)内内f f(n+1)(n+1)(x)(x)的符号相同，则的符号相同，则x=a(x=a(或或b)b)属于属于f(x)-f(x)-p pn n* *(x)(x)的交错点组的交错点组. .43例例2 2设设f(x)= f(x)= x x. . 求在求在P P1 10,10,1中对中对f(x)f(x)的最的最 佳一致逼近元佳一致逼近元. .解解 由定理和推论由定理和推论1 1可知可知x=0,1x=0,1为为f(x)-pf(x)-p1 1* *(x)(x)交错点组的点交错点组的点. .由定理，交错点还差一个，由定

24、理，交错点还差一个，记这个点为记这个点为x x1 1（，）（，）. .x x ，x x. .x x为区间为区间(0(0，1)1)内的交错点，所以内的交错点，所以x x就是误差曲线函数就是误差曲线函数f(x)- f(x)- p p1 1* *(x)(x)的驻点的驻点 . .记记 p p1 1* *(x)(x)=a=aa ax x，由由x-(ax-(a0 0+a+a1 1x)x)x x，可得，可得44 x x1/(2a1/(2a) ). . p p1 1(x)(x)x+1/8x+1/8为所求在为所求在P P1 10,10,1中对中对f(x)= f(x)= x x 的最佳一致逼近多项式的最佳一致逼近

25、多项式. .因为因为x=0,1x=0,1为交错点，由为交错点，由x-(ax-(a0 0+a+a1 1x)x)x=0 x=0 x-(ax-(a0 0+a+a1 1x)x)x=1x=1得得 a a1 1=1=1将将a a代入代入x x1/(2a1/(2a) )得得x x1/4. 1/4. 再由再由x-(ax-(a0 0+a+a1 1x)x)x1=1/4x1=1/4- -x-(ax-(a0 0+a+a1 1x)x)x2=1x2=1得得a a1/81/8，故，故453.3 最佳平方逼近多项式最佳平方逼近多项式称满足上式的称满足上式的 为为 f(x) 在区间在区间a,b 上的上的最佳最佳平方逼近多项式。

26、平方逼近多项式。)(*xS460011( , )( , )( , )nnafafaf 0, 00101, 011101() ( , )( , )() ( , )( , )( , ) ( , )( , )nnnnnn 称为称为正规方程组正规方程组或或法方程法方程。474849则则 0( ,) ( , )njkjkka x xx f(j=0,1,(j=0,1,n)(14),n)(14)式式(14)(14)是关于是关于 的线形方程组用矩阵表示为的线形方程组用矩阵表示为 01,.,na aa5001(1, )(1,1)(1, )(1,)( , )( ,1)( , )( ,)(, )(,1) (, )(

27、,)nnnnnnnnafxxax fxx xx xaxfxx xx x（15）方程组方程组(15)的系数矩阵是一个对称正定矩阵，故存的系数矩阵是一个对称正定矩阵，故存在唯一解。在唯一解。51从式从式(14)中解出中解出 (k=0,1,2,n)，从而可得最佳平，从而可得最佳平方逼近多项式方逼近多项式ka( )nknkk oSxa x若若 a,b=0,1， 则则 ( ) 1x11001( ,),( , )( ),1jkj kjjjx xx dxx fx f x dx dj k 52111211112321111221nHnnnn 方程组方程组(15)的系数矩阵为的系数矩阵为( )1x称为希尔伯特（

28、称为希尔伯特（Hierbert）矩阵。以后，不特别声明，）矩阵。以后，不特别声明，均取均取 53例例1 1 求求f(x)= f(x)= 在区间在区间00，11上的二次最佳平方上的二次最佳平方逼近多项式逼近多项式xe解解：1001 1.7138xde dxe 1101,xdxe dx122020.7183xdx e dxe 54得正规方程组得正规方程组012111231.718311112340.7183111345aaa 解得解得 所以所以0121.013,0.851,0.839,aaa22( )1.0130.8510.839.Sxxx55用用 作基，求最佳平方逼近多项式，当作基，求最佳平方逼

29、近多项式，当n 较大时，系数矩阵可能是病态矩阵，较大时，系数矩阵可能是病态矩阵，1,.,nxx求正规方程组的解，舍入误差会很大求正规方程组的解，舍入误差会很大, ,这时选正交这时选正交多项式为基，就可避免这种情况。多项式为基，就可避免这种情况。56若取若取 , ,( )(0,1,., )jjxx jn若取若取 为区间为区间a,ba,b上的正交多项式，系上的正交多项式，系数矩阵为对角矩阵，解为数矩阵为对角矩阵，解为 0( )njx( ) ( )( )( )bjabjjax f x dxxx dx(, )(,)jjjjfa 5758例例2 求求 在区间在区间-1,1-1,1上的三次最佳平方上的三次

30、最佳平方逼近多项式逼近多项式( )xf xe 解解 取勒让德多项式系中取勒让德多项式系中 为基，则为基，则 0123( ),( ),( ),( )p x p x p x p x112(,)( )( )21iiiip pp x p x dxi0,1,2,3i59 101(,)2.3504xxp ee dx111( ,)0.7358xxp exe dx0.143112211(,)(31)2xxp exe dx13311(,)(53 )0.020132xxp exx e dx60得得02.35041.7522a 130.73581.10362a 251.14310.35782a 370.020130

31、.070462a 所以所以3013( )1.1752( )1.1036( )0.0746( )s xp xp xp x230.99630.99790.53670.1761xxx61 623.4曲线拟合最小二乘法曲线拟合最小二乘法n一、一、 线性最小二乘拟合线性最小二乘拟合设设)0)(nixi 为为n+1个线性无关的函数个线性无关的函数,) )( (),),( (),),( (xxxSpann 10 对其中任一对其中任一S(x),有有定义定义:S(x)关于参数关于参数ai是线性的是线性的.63二、最小二乘法的基本原理二、最小二乘法的基本原理具体的做法是求具体的做法是求 S(x) 使使 几何意义几

32、何意义: 求在给定点求在给定点 x0, x1, xm 处与点处与点(x0,y0), (x1,y1), ,(xm, ym) 的距离的距离平方和最小的曲线平方和最小的曲线y =S(x),这就是最小二乘曲线拟合问题这就是最小二乘曲线拟合问题. 20*)(20*02)(min)( miiixsmiiimiiyxSyxSr 641.定义定义 对给定的一组数据对给定的一组数据(xi,yi)(i=0,1,m),在上述在上述集合集合 中求中求S(x),使其满足使其满足这就是一般的线性最小二乘拟合问题这就是一般的线性最小二乘拟合问题.652.2.求法求法由多元函数求极值的必要条件由多元函数求极值的必要条件, ,

33、 可得可得002()()0mnkkiijiikjIaxyxa (0,1,., )jn 000()()()nmmjikikjiikiixxaxy 即：即：(0,1,., )jn 称为称为正规方程组正规方程组或或法方程组法方程组. .66记记miikijkjnkjxx010 ,.,., , ,),),( () )( () ), ,( ( 000()()()nmmjikikjiikiixxaxy (0,1,., )jn mjiijjnjyxy010 ,.,., , ,) )( () ), ,( ( 则则67可用矩阵表示为：可用矩阵表示为：0001000101111101(,) (,)(,)(, )(

34、,)(,)(,)(, )(,) (,)(,)(, )nnnnnnnnayayay 68), 1 , 0()(000njyxaxmiijiknkmikji nxxxSpan,12，如如果果 69矩阵形式为矩阵形式为000021100001200001mmmniiiiiimmmmniiiiiiiiimmmmnnnniiiiiniiiiamxxyxxxx yaxxxx ya 称之为法方程组或正规方程组称之为法方程组或正规方程组.70例例1 测得铜导线在温度测得铜导线在温度 时的电阻时的电阻 如表如表1，求电阻，求电阻R与温度与温度T的近似函数关系的近似函数关系R=a0+a1T。)( iR)( CTi表表185.1083.908