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

《计算方法第四章逼近法课件.ppt》由会员分享，可在线阅读，更多相关《计算方法第四章逼近法课件.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算方法第四章逼近法第1页，此课件共56页哦一、最优平方逼近一、最优平方逼近例例1：距离距离 0.511.522.533.54水深水深 1.551.982.453.153.214.124.965.32第2页，此课件共56页哦例例2：化学反应：化学反应 分子扩散分子扩散时间时间 0.10.511.52浓度浓度 2.821.61.31.2第3页，此课件共56页哦对于例对于例2 2，设逼近函数形为：，设逼近函数形为：，该函数应该与已知点的某种差距最小。记：该函数应该与已知点的某种差距最小。记：，可求可求第4页，此课件共56页哦如果取逼近函数形为：如果取逼近函数形为：第5页，此课件共56页哦同样，对于

2、同样，对于例例1 1，由于已知点几乎分布在一直线上，所以，设由于已知点几乎分布在一直线上，所以，设拟合函数为拟合函数为第6页，此课件共56页哦1.最小二乘拟合最小二乘拟合 通常情况下，我们会遇到这样的问题：在研究某种客观现象的时候，通常情况下，我们会遇到这样的问题：在研究某种客观现象的时候，需要建立所描述对象的量之间的函数关系式。需要建立所描述对象的量之间的函数关系式。此时，我们对要研究的函数进行一系列观测，得到若干组观测此时，我们对要研究的函数进行一系列观测，得到若干组观测值，然后利用这些观测值构造函数表达式。值，然后利用这些观测值构造函数表达式。显然，由于观测误差等原因，构造出的函数不可能

3、严格过这些显然，由于观测误差等原因，构造出的函数不可能严格过这些观测值的点。对此，我们要求构造出的函数在观测点上的值与观观测值的点。对此，我们要求构造出的函数在观测点上的值与观测值差的平方和达到最小。这称为测值差的平方和达到最小。这称为最小二乘拟合最小二乘拟合。第7页，此课件共56页哦 线性最小二乘问题的一般提法：线性最小二乘问题的一般提法：已知函数列已知函数列 线性无关，对于一组已线性无关，对于一组已知点（观测值）知点（观测值），求函数列的一个，求函数列的一个组合组合 ，使之在加权最小二乘的意义下最佳逼，使之在加权最小二乘的意义下最佳逼近这些点，即求系数近这些点，即求系数 ，使下面的和取最小

4、：，使下面的和取最小：这里，求和中加了数这里，求和中加了数 ，代表求和的权重。，代表求和的权重。称称 为基于函数列的对已知观测点的一个为基于函数列的对已知观测点的一个最小二乘逼近。最小二乘逼近。第8页，此课件共56页哦注意到注意到 S 实际上是关于实际上是关于 的一个函数，欲取最的一个函数，欲取最小值，则小值，则如此得到一组方程，从中即可求出系数如此得到一组方程，从中即可求出系数 。引入记号：引入记号：则得方程组：则得方程组：称为称为正规方程组正规方程组，从中即可求出系数。，从中即可求出系数。第9页，此课件共56页哦类似，可以得到多元函数的线性最小二乘拟合：设多类似，可以得到多元函数的线性最小

5、二乘拟合：设多元元函数列函数列 线线性无关，一组测量数据为性无关，一组测量数据为求拟合函数求拟合函数使使 最小。最小。则拟合系数则拟合系数 同样满足上页蓝色的方程。只不过同样满足上页蓝色的方程。只不过第10页，此课件共56页哦例例3：观测得到某函数一组数据，求其近似表达式：观测得到某函数一组数据，求其近似表达式：1234567891.782.242.743.744.455.316.928.8510.97第11页，此课件共56页哦设拟合函数为设拟合函数为 ，引入变换，引入变换 ，拟合函数，拟合函数为为 ，数据变为：，数据变为：得正规方程组：得正规方程组：1234567890.580.811.01

6、1.321.491.671.932.182.395第12页，此课件共56页哦最后结果如图最后结果如图第13页，此课件共56页哦最小二乘拟合多项式：最小二乘拟合多项式：设有变量设有变量 x 和和 y 的一组数据：的一组数据：对多项式对多项式 ，选择适当系数，选择适当系数后，使后，使达到最小的多项式达到最小的多项式,称为数据的称为数据的最小二乘最小二乘(平方平方)拟合拟合多项式多项式，或称为变量，或称为变量x 和和 y 之间的之间的经验公式经验公式.第14页，此课件共56页哦显然，显然，S 达到最小值，则达到最小值，则记：记：得得正规方程组正规方程组(法方程法方程)：第15页，此课件共56页哦2.

7、内积内积定义定义：设：设 X 为为 R 上的线性空间，对于上的线性空间，对于 X 中的任意两中的任意两个向量个向量 u，v，定义定义(u,v)，如果满足下面条件：如果满足下面条件：则称则称(u,v)为空间为空间X上的一个上的一个内积内积。第16页，此课件共56页哦例：例：n维空间中的两个向量维空间中的两个向量定义：定义：证明：这是内积。证明：这是内积。例：设例：设 i 是一组正实数，是一组正实数，定义：定义：证明：这也是内积。证明：这也是内积。例：区间例：区间a,b上的所有连续函数全体构成一个线性空间上的所有连续函数全体构成一个线性空间Ca,b,在这在这个空间上定义：个空间上定义：证明：这是一

8、个内积。证明：这是一个内积。第17页，此课件共56页哦定理定理：设：设(u,v)为空间为空间X上的一个内积，对于空间中上的一个内积，对于空间中的一组向量的一组向量 ，它们线性无关的充，它们线性无关的充分必要条件是下面的所谓分必要条件是下面的所谓Gram（克拉姆）矩阵非奇克拉姆）矩阵非奇异。异。第18页，此课件共56页哦定义定义：设：设(u,v)为空间为空间X上的一个内积，对于上的一个内积，对于 X 中的任意两中的任意两个向量个向量u，v，如果如果(u,v)0，则称则称 u 与与 v 正交正交。记为：。记为：u v。例例：3维空间中，证明下面向量两两正交维空间中，证明下面向量两两正交例例：区间区

9、间-1,1上的所有连续函数全体构成一个线性空间上的所有连续函数全体构成一个线性空间 C-1,1，证明任意一个奇函数与偶函数正交。证明任意一个奇函数与偶函数正交。例例：C-,中，证明下面函数两两正交：中，证明下面函数两两正交：1,cosx,sinx,cos2x,sin2x第19页，此课件共56页哦3.正交多项式正交多项式定义定义：满足：满足 的函数系称为的函数系称为正交函数系正交函数系，如果该函数系是，如果该函数系是多项式，称为多项式，称为正交多项式系正交多项式系。1：-,中，中，1,cosx,sinx,cos2x,sin2x，cos3x,sin3x,，cosnx,sinnx，正交正交第20页，

10、此课件共56页哦2：勒让德：勒让德(Legendre)多项式：多项式：-1,1上权为上权为1的正交多项式的正交多项式第21页，此课件共56页哦3.拉盖尔拉盖尔(Laguerre)(Laguerre)多项式：多项式：的正交多项式的正交多项式区间区间 0,）上权函数）上权函数为为第22页，此课件共56页哦4.埃尔米特埃尔米特(Hermite)(Hermite)多项式：多项式：的正交多项式的正交多项式区间区间(-,)上权函数上权函数为为第23页，此课件共56页哦5.切比雪夫切比雪夫(Chebyshev)多项式：多项式：区间区间-1,1 上权上权函数为函数为的正交多项式的正交多项式第24页，此课件共5

11、6页哦正交多项式的构造正交多项式的构造 对给定的有限点集对给定的有限点集X和权和权i 或区间或区间a,b和权函数，定义了内积后，和权函数，定义了内积后，可与向量可与向量的的Schmite正交化类似，正交化类似，通过函数组通过函数组1,x,xn,可构造由可构造由给给定内定内积积（离散型或离散型或连续连续型型）定）定义义的正交多的正交多项项式，如下：式，如下：设设其中其中c10是待定常数。是待定常数。由由设设已构造，两两正交，令已构造，两两正交，令由由第25页，此课件共56页哦 正交多项式的性质正交多项式的性质1.线性无关线性无关.证：证：假定存在常数假定存在常数 ,使得使得推论推论：次数低于：次

12、数低于 n 次的多项式必与次的多项式必与 n 次正交多项式正交次正交多项式正交.2.n 次正交多项式次正交多项式 在正交区间在正交区间a,b上有上有 n 个不同零点个不同零点.证：证：第26页，此课件共56页哦3.对于最高次项系数为对于最高次项系数为 1 的正交多项式的正交多项式 ，有，有三项递推公式三项递推公式：第27页，此课件共56页哦第28页，此课件共56页哦-1,1与与a,b上权函数为上权函数为的正交多项式的关系。的正交多项式的关系。所以所以是是a,b上权为上权为1的正交多项式的正交多项式。如，如，0,1上的权为上的权为1的正交多项式系为的正交多项式系为利用三项递推关系利用三项递推关系

13、,可逐步构造正交多项式可逐步构造正交多项式,从而求出最优平方从而求出最优平方逼近多项式。逼近多项式。第29页，此课件共56页哦4.函数的最优平方逼近函数的最优平方逼近 已知一组在区间已知一组在区间a,b上线性无关的函数上线性无关的函数求求f(x)在此区间上基于这一组函数的最佳近似。此问题实际在此区间上基于这一组函数的最佳近似。此问题实际是求已知函数的一个组合是求已知函数的一个组合 ，使之与，使之与f(x)的距的距离最小离最小,即即第30页，此课件共56页哦例例4：求：求 在在0,1上的一次最佳平方逼近多项式。上的一次最佳平方逼近多项式。解：解：直接计算直接计算,得方程得方程：第31页，此课件共

14、56页哦用正交函数组作最佳平方逼近用正交函数组作最佳平方逼近已知区间已知区间a,b上的连续函数上的连续函数 f(x),以及一组正交函以及一组正交函数组数组 ，易知最佳平方逼近为：，易知最佳平方逼近为：第32页，此课件共56页哦例例5：求：求 exp(x)在在-1,1 上上的三次最佳逼近多项式。的三次最佳逼近多项式。第33页，此课件共56页哦例例6：求函数：求函数 f(x)=xexp(-x)在区间在区间0,10上的上的三次三次最佳平方逼最佳平方逼近多项式近多项式第34页，此课件共56页哦第35页，此课件共56页哦第36页，此课件共56页哦第37页，此课件共56页哦二、最优一致逼近二、最优一致逼近

15、 已知区间已知区间a,b上的连续函数上的连续函数 f(x)，如果有如果有n次多项式，使次多项式，使得所有得所有n次多项式中，该多项式与函数次多项式中，该多项式与函数f(x)在区间上的在区间上的 距距离达到最小，则称该多项式为函数离达到最小，则称该多项式为函数f(x)在区间在区间a,b上的上的n次次最优一致逼近多项式最优一致逼近多项式。数学提法是：选取多项式数学提法是：选取多项式 使得使得偏差偏差第38页，此课件共56页哦定理定理1(1(切比雪夫切比雪夫):n次多项式次多项式 P(x)为区间为区间a,b上上的连续函数的连续函数 f(x)的的最优一致逼近多项式最优一致逼近多项式的充要条的充要条件是

16、：件是：f(x)-P(x)在该区间上以正负相间的符号在该区间上以正负相间的符号依次取值为依次取值为 的点的点(称为称为交错点组交错点组)的的个数不少于个数不少于 n+2个个.第39页，此课件共56页哦证明证明:只证充分性只证充分性,用反证法用反证法.设设f(x)-f(x)-p pn n*(x)(x)在在a,ba,b上存在一个上存在一个至少由至少由n+2n+2个点组成的交错点组，但个点组成的交错点组，但p pn n*(x)(x)不是最佳一致逼近不是最佳一致逼近元元.不妨设不妨设Pna,b 中的元素中的元素q qn n(x)(x)为最佳一致逼近元，即为最佳一致逼近元，即 f(x)-q f(x)-q

17、n n(x)(x)f(x)-f(x)-p pn n*(x)(x)(1)(1)令令 Q(x)=Q(x)=p pn n*(x)(x)-q-qn n(x)(x)=f(x)-q =f(x)-qn n(x)-(f(x)-(x)-(f(x)-p pn n*(x)(x)记记 x x1 1*,x x2 2*,x xn+2n+2*为误差曲线函数为误差曲线函数f(x)-f(x)-p pn n*(x)(x)在在a,ba,b上的交错上的交错点组。点组。第40页，此课件共56页哦 由于由于 Q(xQ(xi i*)=f(x)=f(xi i*)-q)-qn n(x(xi i*)-f(x)-f(xi i*)-)-p pn n

18、*(x xi i*)由由(1)(1)式可知式可知,n,n次多项式次多项式Q(x)Q(x)在点集在点集 x x1 1*,x x2 2*,x xn+2n+2*上的符号完全由上的符号完全由f(x)-f(x)-p pn n*(x)(x)在这些点上的符号所决定。在这些点上的符号所决定。又又 x x1 1*,x 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次改变次改变符号，故符

19、号，故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)-qn n(x)(x).证毕证毕.必要性证明，见王德人著必要性证明，见王德人著数值逼近引论数值逼近引论，1990第41页，此课件共56页哦 定理定理2 2（最佳一致逼近元的惟一性）最佳一致逼近元的惟一性）在在Pna,b中，若存在对函数中，若存在对函数f(x)Ca,bf(x)Ca,b的最佳一致逼近元，则唯一的最佳一致逼近元，则唯一.证

20、明证明:反证，设有反证，设有2 2个最佳一致逼近元个最佳一致逼近元，分别是分别是pn*和和qn 则它们的平均函数则它们的平均函数 也是一个最佳一致也是一个最佳一致 逼近元逼近元。第42页，此课件共56页哦 令令 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,bf(x)Ca,b的最的最 佳一致逼近元佳一致逼近元.现设误差曲线函数现设误差曲线函数f(x)-pn(x)在区间在区间a,ba,b上的一个交错上的一个交

21、错 点组为点组为x1,x2,xn+2，则，则 En=|f(xk)-pn(xk)|=1/2|(f(xk)-pn*(xk)+(f(xk)-qn(xk)|第43页，此课件共56页哦 若对某一个若对某一个k,1kn+2k,1kn+2，f(xf(xk k)-)-p pn n*(x(xk k)f(x)f(xk k)-q)-qn n(x(xk k)，那么上式两个差中至少有一个达不到那么上式两个差中至少有一个达不到 E En n或或-E En n，从而从而 E En n|f(x|f(xk k)-)-p pn n(x(xk k)|)|1/2(|f(x 1/2(|f(xk k)-)-p pn n*(x(xk k)

22、|)+|f(x)|)+|f(xk k)-q)-qn n(x(xk k)|)|)1/2(f(x)-1/2(f(x)-p pn n*(x)(x)+f(x)-q+f(x)-qn n(x)(x)1/2(E 1/2(En n+E+En n)=E)=En n.矛盾！矛盾！所以所以 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).证毕证毕.第44页，此课件共56页哦切比雪夫多项式的性质切比雪夫多项式的性质性质性质1：切比雪夫多项式为区间：切比雪夫多项式为区间-1,

23、1上关于权上关于权 的正交多项式。的正交多项式。性质性质2：三项递推关系：三项递推关系第45页，此课件共56页哦性质性质3：是最高次项系数为是最高次项系数为 的的n次多项式。次多项式。为偶函数，为偶函数，为奇函数。为奇函数。证：由性质证：由性质2，用归纳法即知结论成立。，用归纳法即知结论成立。性质性质4：在在-1,1上有上有n个零点个零点证：证：第46页，此课件共56页哦性质性质5：在在-1,1上上 ,且在且在 交错的取得最大值交错的取得最大值1和最小值和最小值 1。这些点称为。这些点称为偏差点偏差点。证证:性质性质6：设设Pn(Pn(x x)为最高次项系数为为最高次项系数为 1 的的n次多项

24、式，则次多项式，则 这个性质称为这个性质称为Chebyshev多项式的最小模性质多项式的最小模性质.证证:取取f(x)=0,由由Chebyshev定理可知结论成立定理可知结论成立.第47页，此课件共56页哦利用性质利用性质2可以得到可以得到第48页，此课件共56页哦关于最佳一致逼近多项式的求解问题关于最佳一致逼近多项式的求解问题（1）当当f(x)为为-,上的上的n+1次多项式时，求次多项式时，求f(x)在在Pn-,中的中的最佳一致逼近多项式。不妨记最佳一致逼近多项式。不妨记 f(x)=b0+b1x+bn+1xn+1,|x|1,设设pn(x)为最佳一致逼近元，由于首项系数为为最佳一致逼近元，由于

25、首项系数为1的的n+1次次Chebyshev多多项式项式T*n+1(x)的无穷模最小（性质的无穷模最小（性质6），所以），所以考虑两种特殊情形考虑两种特殊情形:第49页，此课件共56页哦 例例7 7 设设f(x)=4x4+2x-x+8x-5/2，|x|1.求求f(x)在在P3-1,1 中的最佳一致逼近元中的最佳一致逼近元p3(x).解解:由由f(x)f(x)的表达式可知的表达式可知b b,首项系数为首项系数为1 1的的4 4次次ChebyshevChebyshev 多项式多项式T T4 4(x)(x)x xx x1/8.1/8.由由(1)1)得得 p3(x)=f(x)-4T4(x)=2x-x+

26、8x-3.对区间为对区间为a,ba,b的情形，作变换的情形，作变换 x=(b-a)t/2+(b+a)/2 (*)x=(b-a)t/2+(b+a)/2 (*)后后,对变量为对变量为t t的多项式用的多项式用(1)1)求得求得Pn(t)Pn(t)，然后再作然后再作(*(*)式的反式的反 变换得到变换得到a,ba,b上的最佳一致逼近多项式。上的最佳一致逼近多项式。第50页，此课件共56页哦（2）逼近多项式为低次多项式时关于交错点组的定理逼近多项式为低次多项式时关于交错点组的定理 定理定理3 3 设设pn*(x)Pna,b为对为对 f(x)Ca,bf(x)Ca,b的最佳一致逼近的最佳一致逼近 元元.若

27、若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上交错点组中的点。上交错点组中的点。证明证明：（用反证法）：（用反证法）若点若点a(点点b类似类似)不属于交错点组，那么在区间不属于交错点组，那么在区间(a,b)内至少存在内至少存在n+1个点属于交错点组个点属于交错点组.若若f(x)足够光滑，由交错点组的足够光滑，由交错点组的定义，可以证得定义，可以证得(a,b)内的交错点必为误差曲线函数内的交错点必为误差曲线函数 f(x)-Pn*(x)的

28、驻点，的驻点，即区间即区间(a,b)内内n+1个交错点上个交错点上,f(x)-Pn*(x)的一阶导数等于零的一阶导数等于零.这样，这样，由由 Rolle 定理便可推得，在定理便可推得，在(a,b)内至少存在一点内至少存在一点,使得使得这与这与 在在a,b上不变号，即上不变号，即 无零点矛盾，故点无零点矛盾，故点 x=a 属属于交错点组。于交错点组。证毕。证毕。第51页，此课件共56页哦推论推论1 1 设设p pn n*(x)P(x)Pn na,ba,b为对为对f(x)Ca,bf(x)Ca,b的最佳一致逼近的最佳一致逼近元元.若若f f(n+1)(n+1)(x)(x)在区间在区间(a,b)a,b

29、)上不变号，但在上不变号，但在x=a(x=a(或或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)的交错点组的交错点组.第52页，此课件共56页哦例例8.设设f(x)=x,求在求在P10,1中对中对f(x)的最佳一致逼近元的最佳一致逼近元.解解:由定理由定理3 3和推论和推论1 1可知可知,x=0,1,x=0,1为为f(x)-pf(x)-p1 1*(x)(x)交错点组的点交错点组的点.由定理由定理3 3，交错点还差

30、一个，交错点还差一个，记这个点为记这个点为 x x1 1(,),x),x,x,x.x x为区间为区间(0(0，1)1)内的交错点，所以内的交错点，所以x x就是误差曲线函数就是误差曲线函数f(x)-pf(x)-p1 1*(x)(x)的驻点的驻点.第53页，此课件共56页哦第54页，此课件共56页哦Chebyshev 多项式应用多项式应用1-近似最优一致逼近多项式近似最优一致逼近多项式设函数设函数 f(x)在区间在区间-1,1上连续，正交函数取为切比雪夫多项上连续，正交函数取为切比雪夫多项式，式，f(x)可以展为：可以展为：第55页，此课件共56页哦记：记：则则由于由于 有有n+2个偏差点，所以个偏差点，所以 近似的也有近似的也有n+2个偏差点，由切比雪夫定理，个偏差点，由切比雪夫定理，为为 的近似最优的近似最优一致逼近多项式。一致逼近多项式。第56页，此课件共56页哦