计算方法第四章(逼近法)ppt课件.ppt

《计算方法第四章(逼近法)ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算方法第四章(逼近法)ppt课件.ppt（59页珍藏版）》请在三一办公上搜索。

1、第四章 函数最优逼近法一、最优平方逼近二、最优一致逼近,一、最优平方逼近例1：,例2：化学反应 分子扩散,对于例2，设逼近函数形为： ，该函数应该与已知点的某种差距最小。记：,，可求,如果取逼近函数形为：,同样，对于例1，由于已知点几乎分布在一直线上，所以，设拟合函数为,1. 最小二乘拟合 通常情况下，我们会遇到这样的问题：在研究某种客观现象的时候，需要建立所描述对象的量之间的函数关系式。 此时，我们对要研究的函数进行一系列观测，得到若干组观测值，然后利用这些观测值构造函数表达式。 显然，由于观测误差等原因，构造出的函数不可能严格过这些观测值的点。对此，我们要求构造出的函数在观测点上的值与观测

2、值差的平方和达到最小。这称为最小二乘拟合。,线性最小二乘问题的一般提法： 已知函数列 线性无关，对于一组已知点（观测值） ，求函数列的一个组合 ，使之在加权最小二乘的意义下最佳逼近这些点，即求系数 ，使下面的和取最小：这里，求和中加了数 ，代表求和的权重。称 为基于函数列的对已知观测点的一个最小二乘逼近。,注意到 S 实际上是关于 的一个函数，欲取最小值，则如此得到一组方程，从中即可求出系数 。引入记号：则得方程组：称为正规方程组，从中即可求出系数。,类似，可以得到多元函数的线性最小二乘拟合：设多元函数列 线性无关，一组测量数据为求拟合函数使 最小。则拟合系数 同样满足上页蓝色的方程。只不过,

3、例3：观测得到某函数一组数据，求其近似表达式：,设拟合函数为 ，引入变换 ，拟合函数为 ，数据变为：得正规方程组：,最后结果如图,最小二乘拟合多项式：设有变量 x 和 y 的一组数据：对多项式 ，选择适当系数后，使达到最小的多项式, 称为数据的最小二乘(平方)拟合多项式，或称为变量x 和 y 之间的经验公式.,显然，S 达到最小值，则记：得正规方程组(法方程)：,2. 内积定义：设 X 为 R 上的线性空间，对于 X 中的任意两个向量 u，v，定义( u , v )，如果满足下面条件：则称( u , v )为空间X上的一个内积。,例：n维空间中的两个向量定义：证明：这是内积。例：设 i 是一组

4、正实数，定义：证明：这也是内积。例：区间a , b上的所有连续函数全体构成一个线性空间Ca , b, 在这个空间上定义：证明：这是一个内积。,定理：设( u , v )为空间X上的一个内积，对于空间中的一组向量 ，它们线性无关的充分必要条件是下面的所谓Gram（克拉姆）矩阵非奇异。,定义：设 ( u , v )为空间X上的一个内积，对于 X 中的任意两个向量u，v，如果 ( u , v ) 0，则称 u 与 v 正交。记为： u v 。例：3维空间中，证明下面向量两两正交例：区间 -1, 1上的所有连续函数全体构成一个线性空间 C-1 , 1，证明任意一个奇函数与偶函数正交。例： C- , 中

5、，证明下面函数两两正交：1, cosx , sinx , cos2x , sin2x,正交多项式定义：满足 的函数系称为正交函数系，如果该函数系是多项式，称为正交多项式系。1： - , 中， 1, cosx , sinx , cos2x , sin2x， cos3x , sin3x , ，cosnx , sinnx，正交,2：勒让德 (Legendre) 多项式：-1,1上权为1的正交多项式,3. 拉盖尔(Laguerre)多项式：,的正交多项式,区间 0,）上权函数为,4.埃尔米特(Hermite)多项式：,的正交多项式,区间 (-, ) 上权函数为,5.切比雪夫 (Chebyshev) 多

6、项式：,区间 - 1 , 1 上权函数为,的正交多项式,正交多项式的构造,对给定的有限点集X和权i 或区间a,b和权函数，定义了内积后， 可与向量的Schmite正交化类似， 通过函数组1, x, , xn, 可构造由给定内积（离散型或连续型）定义的正交多项式，如下：,设,其中c10是待定常数。,由,设,已构造，两两正交，令,由,正交多项式的性质1. 线性无关.证：假定存在常数 , 使得推论：次数低于 n 次的多项式必与 n 次正交多项式正交.2. n 次正交多项式 在正交区间a, b上有 n 个不同零点.证：,3. 对于最高次项系数为 1 的正交多项式 ，有三项递推公式：,-1,1与a, b

7、上权函数为,的正交多项式的关系。,所以,是a, b上权为1的正交多项式。,如，0,1上的权为1的正交多项式系为,利用三项递推关系, 可逐步构造正交多项式, 从而求出最优平方逼近多项式。,函数的最优平方逼近 已知一组在区间a,b上线性无关的函数求f ( x )在此区间上基于这一组函数的最佳近似。此问题实际是求已知函数的一个组合 ，使之与f ( x )的距离最小, 即,例4：求 在0,1上的一次最佳平方逼近多项式。解：直接计算,得方程：,用正交函数组作最佳平方逼近已知区间a,b上的连续函数 f ( x ), 以及一组正交函数组 ，易知最佳平方逼近为：,例5：求 exp(x) 在 -1,1 上的三次

8、最佳逼近多项式。,例6：求函数 f (x)=xexp(-x) 在区间0,10上的三次最佳平方逼近多项式,二、最优一致逼近 已知区间a,b上的连续函数 f ( x )，如果有n次多项式，使得所有n次多项式中，该多项式与函数f ( x )在区间上的 距离达到最小，则称该多项式为函数f ( x )在区间a,b上的n次最优一致逼近多项式。 数学提法是：选取多项式 使得偏差,定理1(切比雪夫): n次多项式 P( x )为区间a,b上的连续函数 f ( x )的最优一致逼近多项式的充要条件是：f ( x ) - P( x )在该区间上以正负相间的符号依次取值为 的点(称为交错点组)的个数不少于 n +

9、2个.,证明:只证充分性,用反证法. 设f(x)-pn*(x)在a,b上存在一个至少由n+2个点组成的交错点组，但pn*(x)不是最佳一致逼近元. 不妨设Pna,b中的元素qn(x)为最佳一致逼近元，即 f(x)-qn(x)f(x)-pn*(x) (1) 令 Q(x)=pn*(x)-qn(x) =f(x)-qn(x)-(f(x)-pn*(x) 记x1*,x2*,xn+2*为误差曲线函数f(x)-pn*(x)在a,b上的交错点组。,由于 Q(xi*)=f(xi*)-qn(xi*)-f(xi*)-pn*(xi*) 由(1)式可知, n次多项式Q(x)在点集x1*,x2*,xn+2* 上的符号完全由

10、f(x)-pn*(x)在这些点上的符号所决定。 又x1*,x2*,xn+2*为f(x)-pn*(x)的交错点组，即f(x)-pn*(x) 在这n+2个点上正负(或负正)相间至少n+1次，因此至少n+1次改变符号，故Q(x)也至少n+1次改变符号。这说明 n次多项式Q(x)至少在a,b上有n+1个根，矛盾，所以 f(x)- pn*(x)f(x)-qn(x). 证毕.必要性证明，见王德人著数值逼近引论，1990,定理2（最佳一致逼近元的惟一性）在Pna,b中，若存在对函数f(x)Ca,b的最佳一致逼近元，则唯一.,证明: 反证，设有2个最佳一致逼近元，分别是pn*和qn,则它们的平均函数 也是一个

11、最佳一致 逼近元。,令 En=f(x)- pn*(x)=f(x)-qn(x). 由于 Enf(x)-（pn*(x)+qn(x)/2 1/2(f(x) - pn*(x)+f(x) - qn(x) 1/2(En+En)=En, 这说明 也是对函数f(x)Ca,b的最 佳一致逼近元.,现设误差曲线函数f(x)-pn(x)在区间a,b上的一个交错 点组为x1,x2,xn+2，则 En=|f(xk) -pn(xk)| = 1/2 |(f(xk)-pn*(xk)+(f(xk)-qn(xk)|,若对某一个k, 1kn+2，f(xk)-pn*(xk)f(xk)-qn(xk)， 那么上式两个差中至少有一个达不到

12、 En或-En，从而 En|f(xk)-pn(xk)| 1/2(| f(xk)-pn*(xk)|)+|f(xk)-qn(xk)|) 1/2(f(x)- pn*(x)+f(x)-qn(x) 1/2(En+En)=En. 矛盾！ 所以 f(xk)-pn*(xk)=f(xk)-qn(xk), 即 pn*(xk)=qn(xk), k=1,2,，n+2. 而 pn*(x), qn(x)Pna,b，故必有 Pn*(x)=qn(x) . 证毕.,切比雪夫多项式的性质性质1：切比雪夫多项式为区间-1,1上关于权 的正交多项式。性质2：三项递推关系,性质3： 是最高次项系数为 的n次多项式。 为偶函数， 为奇函

13、数。证：由性质2，用归纳法即知结论成立。性质4： 在-1,1上有n个零点证：,性质5：在-1,1上 ,且在 交错的取得最大值1和最小值 1。这些点称为偏差点。证: 性质6：设Pn(x)为最高次项系数为 1 的n次多项式，则 这个性质称为Chebyshev多项式的最小模性质.证: 取f ( x )=0 , 由Chebyshev定理可知结论成立.,利用性质2可以得到,关于最佳一致逼近多项式的求解问题,（1）当f(x)为-,上的n+1次多项式时，求f(x)在Pn-,中的最佳一致逼近多项式。不妨记 f(x)=b0+b1x+ bn+1xn+1, |x|1,设pn(x)为最佳一致逼近元，由于首项系数为1的

14、n+1次Chebyshev多项式T*n+1(x)的无穷模最小（性质6），所以,考虑两种特殊情形:,例7 设f(x)=4x4+2x-x+ 8x - 5/2， |x|1. 求f(x)在P3-1,1 中的最佳一致逼近元p3(x).,解:由f(x)的表达式可知b,首项系数为1的4次Chebyshev 多项式T4(x)xx1/8. 由(1)得 p3(x) = f(x)-4T4(x) = 2x- x+ 8x - 3.,对区间为a,b的情形，作变换 x=(b-a)t/2+(b+a)/2 (*) 后,对变量为t的多项式用(1)求得Pn(t)，然后再作(*)式的反 变换得到a,b上的最佳一致逼近多项式。,（2）

15、逼近多项式为低次多项式时关于交错点组的定理,定理3 设pn*(x)Pna,b为对 f(x)Ca,b的最佳一致逼近 元.若f(n+1)(x)在区间a,b上不变号，则x=a和b为误差曲线 函数f(x)-pn(x)在区间a,b上交错点组中的点。 证明：（用反证法） 若点a(点b类似)不属于交错点组，那么在区间(a,b)内至少存在n+1个点属于交错点组. 若f(x)足够光滑，由交错点组的定义，可以证得(a,b)内的交错点必为误差曲线函数 f(x)-Pn*(x) 的驻点，即区间 (a,b)内n+1个交错点上, f(x)-Pn*(x) 的一阶导数等于零. 这样，由 Rolle 定理便可推得，在(a,b)内

16、至少存在一点 , 使得这与 在a,b上不变号，即 无零点矛盾，故点 x=a 属于交错点组。 证毕。,推论1 设pn*(x)Pna,b为对f(x)Ca,b的最佳一致逼近元. 若f(n+1)(x)在区间(a,b)上不变号，但在x=a(或b)处不存在(但为无穷)而符号与(a,b)内f(n+1)(x)的符号相同，则x=a (或b)属于f(x)-pn*(x)的交错点组.,例8. 设f(x)= x, 求在P10,1中对f(x)的最佳一致逼近元.,解: 由定理3和推论1可知, x=0,1为f(x)-p1*(x)交错点组的点.,由定理3，交错点还差一个，,记这个点为 x1(,), x,x.,x为区间(0，1)

17、内的交错点，所以x就是误差曲线函数f(x)-p1*(x)的驻点 .,Chebyshev 多项式应用1-近似最优一致逼近多项式设函数 f ( x )在区间-1,1上连续，正交函数取为切比雪夫多项式， f ( x )可以展为：,记：则由于 有n+2个偏差点，所以 近似的也有n+2个偏差点，由切比雪夫定理， 为 的近似最优一致逼近多项式。,Chebyshev 多项式的应用2 多项式降次,因降次而增的误差,设 f (x) Pn(x)。在降低 Pn(x) 次数的同时，使因此增加的误差尽可能小。,从 Pn中去掉一个含有其最高次项的 Fn , 结果降次为Pn-1, 则：,若简单取 ，则误差,注：对一般区间a, b，先将 x 换为 t ，考虑 f (t)在1, 1上的逼近Pn(t)，再将 t 换回x，最后得到Pn(x)。,练习：求arctgx在-1,1上的最优一致逼近一次式。,