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

第四章 函数最优逼近法一、最优平方逼近二、最优一致逼近,一、最优平方逼近例1：,例2：化学反应 分子扩散,对于例2，设逼近函数形为： ，该函数应该与已知点的某种差距最小。记：,，可求,如果取逼近函数形为：,同样，对于例1，由于已知点几乎分布在一直线上，所以，设拟合函数为,1. 最小二乘拟合 通常情况下，我们会遇到这样的问题：在研究某种客观现象的时候，需要建立所描述对象的量之间的函数关系式。 此时，我们对要研究的函数进行一系列观测，得到若干组观测值，然后利用这些观测值构造函数表达式。 显然，由于观测误差等原因，构造出的函数不可能严格过这些观测值的点。对此，我们要求构造出的函数在观测点上的值与观测值差的平方和达到最小。这称为最小二乘拟合。,线性最小二乘问题的一般提法： 已知函数列 线性无关，对于一组已知点（观测值） ，求函数列的一个组合 ，使之在加权最小二乘的意义下最佳逼近这些点，即求系数 ，使下面的和取最小：这里，求和中加了数 ，代表求和的权重。称 为基于函数列的对已知观测点的一个最小二乘逼近。,注意到 S 实际上是关于 的一个函数，欲取最小值，则如此得到一组方程，从中即可求出系数 。引入记号：则得方程组：称为正规方程组，从中即可求出系数。,类似，可以得到多元函数的线性最小二乘拟合：设多元函数列 线性无关，一组测量数据为求拟合函数使 最小。则拟合系数 同样满足上页蓝色的方程。只不过,例3：观测得到某函数一组数据，求其近似表达式：,设拟合函数为 ，引入变换 ，拟合函数为 ，数据变为：得正规方程组：,最后结果如图,最小二乘拟合多项式：设有变量 x 和 y 的一组数据：对多项式 ，选择适当系数后，使达到最小的多项式, 称为数据的最小二乘(平方)拟合多项式，或称为变量x 和 y 之间的经验公式.,显然，S 达到最小值，则记：得正规方程组(法方程)：,2. 内积定义：设 X 为 R 上的线性空间，对于 X 中的任意两个向量 u，v，定义( u , v )，如果满足下面条件：则称( u , v )为空间X上的一个内积。,例：n维空间中的两个向量定义：证明：这是内积。例：设 i 是一组正实数，定义：证明：这也是内积。例：区间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- , 中，证明下面函数两两正交：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) 多项式：,区间 - 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上权函数为,的正交多项式的关系。,所以,是a, b上权为1的正交多项式。,如，0,1上的权为1的正交多项式系为,利用三项递推关系, 可逐步构造正交多项式, 从而求出最优平方逼近多项式。,函数的最优平方逼近 已知一组在区间a,b上线性无关的函数求f ( x )在此区间上基于这一组函数的最佳近似。此问题实际是求已知函数的一个组合 ，使之与f ( x )的距离最小, 即,例4：求 在0,1上的一次最佳平方逼近多项式。解：直接计算,得方程：,用正交函数组作最佳平方逼近已知区间a,b上的连续函数 f ( x ), 以及一组正交函数组 ，易知最佳平方逼近为：,例5：求 exp(x) 在 -1,1 上的三次最佳逼近多项式。,例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 + 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* 上的符号完全由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,则它们的平均函数 也是一个最佳一致 逼近元。,令 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)， 那么上式两个差中至少有一个达不到 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次多项式。 为偶函数， 为奇函数。证：由性质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的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）逼近多项式为低次多项式时关于交错点组的定理,定理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)内至少存在一点 , 使得这与 在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)内的交错点，所以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上的最优一致逼近一次式。,