《第四章多项式插值与数值逼近精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章多项式插值与数值逼近精选PPT.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章多项式插值与数值逼近第1页，此课件共42页哦 实际问题中经常要涉及到实际问题中经常要涉及到函数值的计算函数值的计算问题：问题：（1）如果如果函数表达式函数表达式本身比较复杂，且需要多次本身比较复杂，且需要多次重复计算重复计算时，时，计算量会很大；计算量会很大；（2）有的函数甚至有的函数甚至没有表达式没有表达式，只是一种，只是一种表格函数表格函数，而我们需，而我们需要的函数值可能不在该表格中。要的函数值可能不在该表格中。对于这两种情况，我们都需要寻找一个对于这两种情况，我们都需要寻找一个计算方便且表达简单计算方便且表达简单的函数来的函数来近似代替近似代替，这就是，这就是数值逼近数值逼近问题
2、。问题。问题背景问题背景第2页，此课件共42页哦1 1 插值问题插值问题 /*Interpolation Problem*/（插值的定义（插值的定义）已知定义于区间已知定义于区间 上的实值函数上的实值函数 在在 个个互异互异节点节点 处的函数值处的函数值 ，若函数集合，若函数集合 中的函中的函数数 满足满足则称则称 为为 在函数集合在函数集合 中关于中关于节点节点 的一个的一个插值插值函数函数，并称，并称 为为被插值函数被插值函数,a,b,a,b为为插值区间插值区间，为插值节点，（为插值节点，（*）式为）式为插值条件插值条件。设设外插法外插法：内插法内插法：用用 计算被插值函数计算被插值函数
3、在点在点 处的近似值处的近似值 用用 计算被插值函数计算被插值函数 在点在点 处处的近似值的近似值 第3页，此课件共42页哦插值插值类型类型代数代数插值：集合插值：集合 为多项式函数集为多项式函数集x0 x1x2x3x4xg(x)f(x)几何几何意义：意义：有理有理插值：集合插值：集合 为有理分式函数集为有理分式函数集三角三角插值：集合插值：集合 为三角函数集为三角函数集第4页，此课件共42页哦代数插值的代数插值的存在唯一性存在唯一性设设即即代入插值条件：代入插值条件：第5页，此课件共42页哦方程组的系数矩阵是方程组的系数矩阵是Vandermonde矩阵矩阵 方程组存在唯一解，因此满足插值条件
4、方程组存在唯一解，因此满足插值条件(*)(*)的不超过的不超过n次的插值多项式是次的插值多项式是唯一存在唯一存在的的.第6页，此课件共42页哦截断截断误差误差插值插值余项余项设设 在区间在区间 a,ba,b上连续，上连续，在区间在区间 a,ba,b上存在上存在,是满足插值条件（是满足插值条件（*）的不超过）的不超过n次的插值多项式，则对次的插值多项式，则对 存在存在 ，满足，满足其中其中 。且当且当 在区间在区间 a,ba,b有上有上界界 时，有时，有代数插值的插值余项代数插值的插值余项/*Remainder*/第7页，此课件共42页哦注意这里是对注意这里是对 t 求导求导证明：证明：设设结论
5、结论显然显然成立成立时时构造构造辅助辅助函数函数则则 有有 个互异零点个互异零点 、由罗尔由罗尔(Roll)定理定理在区间在区间（a,b）上至少有上至少有n+1个个互异互异零点零点在区间在区间（a,b）上至少有上至少有n个个互异互异零点零点以此类推，反复利用以此类推，反复利用Roll定理定理在区间在区间（a,b）上至少有上至少有1个零点个零点第8页，此课件共42页哦而而 注注注注：（1 1）插值误差与节点插值误差与节点插值误差与节点插值误差与节点 和和和和 之间的之间的之间的之间的距离距离距离距离有关；有关；有关；有关；（2 2）如果如果如果如果 本身本身本身本身为多项式，其插值函数为本身。为
6、多项式，其插值函数为本身。为多项式，其插值函数为本身。为多项式，其插值函数为本身。（3 3）通常不能确定通常不能确定 ,而是估计而是估计 ,x(a,b)将将 作为误差估计上限。作为误差估计上限。第9页，此课件共42页哦2 2 代数插值多项式的构造方法代数插值多项式的构造方法一、一、拉格朗日多项式拉格朗日多项式 /*Lagrange Polynomial*/niyxPiin,.,0,)(=求求 n 次多项式次多项式 使得使得条件：条件：无重合节点，即无重合节点，即n=1已知已知 x0,x1;y0,y1，求，求使得使得111001)(,)(yxPyxP=可见可见 P1(x)是过是过(x0,y0)和
7、和(x1,y1)两点的两点的直线直线。)()(0010101xxxxyyyxP +=101xxxx 010 xxxx =y0+y1l0(x)l1(x)=10)(iiiyxl称为称为拉氏基函数拉氏基函数 /*Lagrange Basis*/，满足条件满足条件 li(xj)=ij第10页，此课件共42页哦与与 有关，而与有关，而与 无关无关n 1希望找到希望找到li(x)，i=0,n 使得使得 li(xj)=ij；然后令；然后令=niiinyxlxP0)()(，则显然有，则显然有Pn(xi)=yi。li(x)每个每个 li(x)有有 n 个根个根 x0 xi-1、xi+1 xn =j i jiii
8、ixxCxl)(11)(Lagrange Polynomial节点节点f第11页，此课件共42页哦若记若记第12页，此课件共42页哦例如例如 也是一个插值多项式，也是一个插值多项式，其中其中 可以是可以是任意任意多项式。多项式。（2）Lagrange插值多项式结构插值多项式结构对称对称，形式简单，形式简单.（3）误差估计误差估计注注：（1）若不将多项式次数限制为若不将多项式次数限制为 n，则插值多项式，则插值多项式不唯一不唯一。（4）当插值当插值节点增加节点增加时，时，拉氏基函数需要拉氏基函数需要重新重新计算，计算，n较大时，计算量非常大较大时，计算量非常大,故故常用于理论分析。常用于理论分析
9、。第13页，此课件共42页哦Quiz:给定给定 xi=i+1,i=0,1,2,3,4,5.下面哪个是下面哪个是 l2(x)的图像？的图像？y 0-1 0.5 -0.5 1 2 3 4 5 6 x y 0-1 0.5 -0.5 1 2 3 4 5 6 x y 0-1 0.5 -0.5 1 2 3 4 5 6 x ABC 第14页，此课件共42页哦例例1：已知已知分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。解：解：n=1分别利用分别利用x0,x1 以及以及 x1,x2 计算计算利用利用这里这里而而sin 50 =0.
10、7660444)185(50sin10 p pL0.77614利用利用sin 50 0.76008,选择要计算的选择要计算的 x 在区间的内部，在区间的内部，插值效果较好。插值效果较好。第15页，此课件共42页哦高次高次插值通常优于插值通常优于低次低次插值插值n=2)185(50sin20 p pL0.76543sin 50 =0.7660444但绝对不是次数越高就但绝对不是次数越高就越好，越好，嘿嘿嘿嘿第16页，此课件共42页哦 反插值反插值问题问题已知定义于区间已知定义于区间 上的上的单调单调连续函数连续函数 在在 个个互异互异节节点点 处的函数值处的函数值 ，若，若函数值函数值 已已知，
11、如何求知，如何求？即求即求因此可以看作如下插值问题：因此可以看作如下插值问题：已知定义于区间已知定义于区间 上的连续函数上的连续函数 在在 个个互异互异节节点点 处的函数值处的函数值 ，求求函数值函数值第17页，此课件共42页哦 xi 1.0 1.4 1.8 2.0yi=f(xi)-2.0 -0.8 0.4 1.2例例2：已知单调连续函数已知单调连续函数 在如下采样点的函数值：在如下采样点的函数值：求方程求方程 在在1，2内根的近似值内根的近似值 。解：解：第18页，此课件共42页哦二二、牛顿插值牛顿插值 /*Newtons Interpolation*/Lagrange 插值虽然易算，但若要
12、增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函数全部基函数 li(x)都需重新算过。都需重新算过。将将 Ln(x)改写成改写成的形式，希望每加一个节点，的形式，希望每加一个节点，只附加一项只附加一项上去即可。上去即可。?差商差商(亦称亦称均差均差)/*divided difference*/1阶差商阶差商/*the 1st divided difference of f w.r.t.xi and xj*/2阶差商阶差商第19页，此课件共42页哦11101010111010,.,.,.,.,.,+=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)阶差商
13、：阶差商：事实上事实上其中其中差商的值与差商的值与 xi 的的顺序顺序无关！无关！第20页，此课件共42页哦 差商差商性质性质/*Property of divided difference*/性质性质1 1即即其中其中证明：证明：数学归纳法数学归纳法n=1n=2第21页，此课件共42页哦同理归纳，结论成立同理归纳，结论成立性质性质2 2差商具有差商具有对称性对称性，即即 的值与节点的值与节点 的的顺序无关顺序无关。由性质由性质1 1易知易知第22页，此课件共42页哦性质性质3 3如果如果 的的k阶差商阶差商 是是 的的m次多项次多项式，则式，则 的的k+1阶差商阶差商 是是 的的m-1次多项
14、式。次多项式。证明：证明：上式右端的分子是上式右端的分子是 的的m次多项式次多项式 ，记为，记为则则为为m-1次多项式次多项式性质性质4 4第23页，此课件共42页哦 牛顿牛顿插值插值 /*Newtons Interpolation*/已知定义于区间已知定义于区间 上的连续函数上的连续函数 在在 个个互异互异节点节点 处的函数值处的函数值 n次次Lagrange 插值多项式可表示为：插值多项式可表示为：其中其中第24页，此课件共42页哦12 n+11+(x x0)2+(x x0)(x xn 1)n+1Nn(x)Rn(x)ai=f x0,xi 3第25页，此课件共42页哦注：注：由由唯一性唯一性
15、可知可知 Nn(x)Ln(x)，只是只是算法不同算法不同，故，故其其余项也相同余项也相同，即，即 实际计算过程为（实际计算过程为（建立差商表建立差商表）f x0,x1f x1,x2 f xn 1,xnf x0,x1,x2 f xn 2,xn 1,xnf x0,xn xn+1 f(xn+1)f xn,xn+1 f xn 1,xn,xn+1 f x1,xn+1 f x0,xn+1f(x0)f(x1)f(x2)f(xn 1)f(xn)x0 x1x2xn 1xn第26页，此课件共42页哦例例3：已知函数已知函数 的函数表：的函数表：xi 1 2 3 4 5yi=f(xi)1 4 7 8 6写出写出4次
16、次Newton插值多项式插值多项式解：解：构造差商表构造差商表第27页，此课件共42页哦 对(x)=(1+25x2)-1,在区间-1,1上取等距节点xi=-1+ih,i=0,1,10,h=0.2,作(x)关于节点xi(i=0,1,10)的10次插值多项式L10(x),如图所示 看下面的例子补补充充 分段插值多项式分段插值多项式xyo1-10.511.5y=L10(x)这个现象被称为Runge现象现象.表明高次插值的不稳定性.实际上,很少采用高于7次的插值多项式.1 分段分段Lagrange插值插值 取节点ax0 x1xnb,hi=xi-xi-1(i=1,2,n),插值条件yk=(xk),k=0
17、,1,n.第28页，此课件共42页哦 1.分段线性插值分段线性插值 设S1(x)是满足插值条件的分段一次多项式,则有S1(x)是平面上以点(xi,yi)(i=0,1,n)为节点的折线.若(x)C2a,b,则当xxi-1,xi时,有若记 ,对任一xa,b都有可见,当h0时,分段线性插值S1(x)收敛于(x).第29页，此课件共42页哦 2.三次样条插值三次样条插值 给定节点a=x0 x1xn=b,及其上的函数值yk=(xk),k=0,1,n.就是给出平面上n+1个点(xi,yi),i=0,1,n.xyo 定义定义6.1 给定节点a=x0 x1xn=b,及其上的函数值yk=(xk),k=0,1,n
18、.如果函数S(x)满足 (1)S(x)是一个分段的三次多项式且S(xk)=yk;(2)S(x)是连续的二阶可导函数。则称S(x)是区间a,b上的三次样条插值函数三次样条插值函数.第30页，此课件共42页哦 S(x)在区间xi-1,xi上是三次多项式,S(x)=aix3+bix2 +cix+di,有4个待定系数,要确定S(x)共有4n个待定系数.由S(xi)=yi,i=0,1,n,有2n个条件.再由S(xi-0)=S(xi+0),i=1,2,n-1,有n-1个条件 及S(xi-0)=S(xi+0),i=1,2,n-1,有n-1个条件 共有4n-2个条件.第31页，此课件共42页哦为了得到唯一的三
19、次样条函数,通常可在区间a,b的端点x0=a,xn=b上各加一个条件,称为边界条件边界条件.常用的边界条件有 (1)S(x0)=y0,S(xn)=yn;(2)S(x0)=y0,S(xn)=yn;(3)假设(x)是以b-a为周期的周期函数,这时要求 S(x0+0)=S(xn-0)S(x0+0)=S(xn-0)S(x0+0)=S(xn-0)这样确定的S(x)为周期样条函数周期样条函数.第32页，此课件共42页哦 最佳平方逼近最佳平方逼近若存在 ，使 用均方误差最小作为度量标准，研究函数f(x)Ca，b的逼近多项式，就是这一节要讨论的最佳平方逼近问题。就是f(x)在a，b上的最佳平方逼近多项式.我们
20、要研究 是否存在?如何计算?第33页，此课件共42页哦 正交多项式正交多项式 记区间a,b上所有连续函数的全体为Ca,b,可以证明Ca,b是一个线性空间,把所有次数不超过n的多项式全体记为Pn,则Pn是Ca,b的子空间.若(x),g(x)Ca,b,则称 为(x)与g(x)的内积内积,记为(,g),满足 (1)(,g)=(g,);(2)(c,g)=c(,g);(3)(1+2,g)=(1,g)+(2,g);若(,g)=0,称(x)与g(x)正交,记为g.利用内积可以定义函数的平方模第34页，此课件共42页哦 下面介绍几个常用的正交多项式 1.Legendre1.Legendre多项式多项式是区间-
21、1,1上的正交多项式,且满足:(2)有三项递推关系 (n+1)Ln+1(x)=(2n+1)xLn(x)-nLn-1(x),n1 L0(x)=1,L1(x)=x (1)(Lm,Ln)=第35页，此课件共42页哦 2.Chebyshev2.Chebyshev多项式多项式 Tn(x)=cos(narccosx)x-1,1,n=0,1,2,是区间-1,1上权函数(x)=的正交多项式,且满足:(1)(Tm,Tn)=第36页，此课件共42页哦 (2)有三项递推关系 Tn+1(x)=2xTn(x)-Tn-1(x)n=1,2,3,T0(x)=1,T1(x)=x (3)Tn(x)在-1,1上的n个零点为第37页
22、，此课件共42页哦 3.Laguere3.Laguere多项式多项式是区间0,+)上权函数(x)=e-x 的正交多项式,且满足:(1)(Lm,Ln)=Ln+1(x)=(2n+1-x)Ln(x)-n2Ln-1(x),n1 L0(x)=1,L1(x)=1-x第38页，此课件共42页哦 4.Hermite4.Hermite多项式多项式是区间(-,+)上权函数(x)=的正交多项式,且满足:(1)(Hm,Hn)=Hn+1(x)=2xHn(x)-2nHn-1(x),n1 H0(x)=1,H1(x)=2x第39页，此课件共42页哦 数据拟合的最小二乘法数据拟合的最小二乘法 1 数据拟合问题数据拟合问题 经常
23、由观察或测试可得到y(x)的一组离散数据:xix0 x1x2xmyiy0y1y2ym 需要在给定的函数类上根据这组离散数据作出逼近曲线.要求逼近曲线在xi处与离散数据尽可能接近.对函数(x),要求以(x)在离散点的误差 0=(x0)-y0,1=(x1)-y1,m=(xm)-ym为分量的误差向量=(0,1,m)T,按某一向量范数 达到最小.对不同的范数,构造出不同意义下的拟合函数.第40页，此课件共42页哦xyo4-314例例1 给出如下离散数据xi-3-2-101234yi -3.2-2.1-1.20.10.92.13.34试求y(x)的拟合曲线.-3 8a0+4a1=3.9 4a0+44a1
24、=46 解得第41页，此课件共42页哦例例2 对下列数据求形如y=aebx的拟合曲线xi12345678yi15.320.527.436.649.165.687.8 117.6 解 设z=lny,则 z=A+bx,其中A=lna,由zi=lnyi 得zi2.727853.020423.310543.600053.893864.183584.475064.76729 8A+36b=29.97865 36A+204b=147.13503解得 A*=2.43686,b*=0.29122,于是有a*=eA*=11.43707,拟合曲线为:(x)=11.43707e0.29122x第42页，此课件共42页哦