数值计算方法-插值法.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013/11/20,#,1,引言 问题的提出,函数解析式未知,通过实验观测得到的一组数据,即在某个区间,a,b,上给出一系列点的函数值,y,i,=f(x,i,),或者给出函数表,y=f,(,x,),y,=,p,(,x,),x,x,0,x,1,x,2,x,n,y,y,0,y,1,y,2,y,n,第二章 插值法,满足,则称,P(x),为,f(x),的,n,次插值多项式。这种插值法通常称为代数插值法。其几何意义如下图所示,原理：,定理,1 n,次代数插值问题的解是存在且惟一的,证明:设,n,次多项式,是函数 在区间a,b,上的,n+1,个互异的节点(,i=0,1,2,n),上的插值多项式,则求插值多项式,P(x),的问题就归结为求它的系数 (,i=0,1,2,n)。,由插值条件:(,i=0,1,2,n),可得,这是一个关于待定参数 的,n+1,阶线性方,程组,其系数矩阵行列式为,称为,Vandermonde,（,范德蒙）行列式，因,x,i,x,j,（,当,i,j,），,故,V,0,。,根据解线性方程组的克莱姆,（,Gramer,）,法则，方程组的解,存在惟一，从而,P(x),被惟一确定。,惟一性说明，不论用何种方法来构造，也不论用何种形式来表示插值多项式,只要满足插值条件(,2.1),其结果都是相互恒等的。,x,0,x,1,x,i,x,i+1,x,n-1,x,n,y=f(x),y=p(x),a,b,在插值区间,a,b,上用,插值多项式,p(x),近似代替,f(x),除了在插值节点,x,i,上没有误差外，在其它点上一般是存在误差的。,若记,R(x)=f(x)-p(x),则,R(x),就是用,p(x),近似代替,f(x),时的截断误差,或称,插值余项我们可根据后面的定理来估计它的大小。,插值多项式的误差,定理2 设,f,(,x,),在,a,b,有,n,+1,阶导数，,x,0,x,1,x,n,为,a,b,上,n,+1,个互异的节点,p,(,x,),为满足,p,(,x,i,)=,f,(,x,i,)i,=1,2,n,),的,n,次插值多项式，那么对于任何,x,a,b,有,插值余项,其中,a,b,且依赖于,x,证明 (略),拉格朗日插值多项式,两个插值点可求出一次插值多项式,而三,个插值点可求出二次插值多项式。插值点增加到,n+1,个时,也就是通过,n+1,个不同的已知点,来构造一个次数为,n,的代数多项式,P(x),。,与推导抛物插值的基函数类似,先构造一个特殊,n,次多项式 的插值问题,使其在各节点 上满足,即,由条件 ()知,都是,n,次 的零点,故可设,其中 为待定常数。由条件 ,可求得,于是,代入上式,得,称 为关于基点 的,n,次插值基函数(,i=0,1,n),以,n+1,个,n,次基本插值多项式,为基础,就能直接写出满足插值条件,的,n,次代数插值多项式。,事实上，由于每个插值基函数,都是,n,次值多项式,所以他们的线性组合,是次数不超过,n,次的多项式,称形如（,2.8,）式的插,值多项式为,n,次拉格朗日插值多项式。并记为,（,2.8,）,3,均差与,牛顿插值多项式,拉格朗日插值多项式结构对称，使用方便。但由于是用基函数构成的插值，这样要增加一个节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。这就启发我们去构造一种具有,承袭性,的插值多项式来克服这个缺点，也就是说，每增加一个节点时，只需增加相应的一项即可。这就是牛顿插值多项式。,由线性代数知,任何一个不高于,n,次的多项式,都可以表示成函数,的线性组合,也就是说,可以把满足插值条件,p(x,i,)=y,i,(i=0,1,n),的,n,次插值多项式,写成如下形式,其中,a,k,(,k,=0,1,2,n,),为待定系数,这种形式的插值多项式称为,Newton,插值多项式。我们把它记为,N,n,(,x,),即,（,3.12,）,可见，牛顿插值多项式,N,n,(x),是,插值多项式,p(x),的另一种表示形式,与,Lagrange,多项式相比它不仅克服了“增加一个节点时整个计算工作重新开始”的缺点,且可以节省乘除法运算次数,同时在,Newton,插值多项式中用到差分与差商等概念又与数值计算的其他方面有密切的关系.,它满足,其中,a,k,(,k,=0,1,2,n,),为待定系数，形如（,3.12,）的,插值多项式称为,牛顿(,Newton),插值多项式,。,3.1,差商及其性质,定义 函数,y,=,f,(,x,),在区间,x,i,x,i+1,上的平均变化率,自变量之差和因变量之差之比叫,差商,称为,f,(,x,),关于,x,i,x,i+1,的一阶差商,并记为,f,x,i,x,i+1,二阶差商,m,阶差商,f,x,i,x,j,x,k,是指,f,x,i,x,j,x,k,=,f,x,j,x,k,-,f,x,i,x,j,x,k,-,x,i,一般的,可定义区间,x,i,x,i1,x,i+n,上的,n,阶差商为,差商及其性质,差商表,x,i,f,x,i,f,x,i,x,i+1,f,x,i,x,i+1,x,i+2,f,x,i,x,i+1,x,i+2,x,0,f(x,0,),x,1,f(x,1,),f,x,0,x,1,x,2,f(x,2,),f,x,1,x,2,f,x,0,x,1,x,2,x,3,f(x,3,),f,x,2,x,3,f,x,1,x,2,x,3,f,x,0,x,1,x,2,x,3,f,x,1,x,2,-,f,x,0,x,1,x,2,x,0,x,i,fx,i,fx,i,x,i+1,fx,i,x,i+1,x,i+2,fx,i,x,i+1,x,i+2,x,i+2,0,0,2,8,3,27,5,125,6,216,例,2.11,求,f,(,x,i,)=,x,3,在节点,x,=0,2,3,5,6上的各阶差商值,解:计算得如下表,在,n+1,个节点处各阶差商的计算方法,差商及其性质,这个性质可用数学归纳法证明（用,Lagrange,插值多项式比较最高项系数来得到,）,性质1,函数,f,(,x,),的,n,阶差商,f,x,0,x,1,x,n,可由,函数值,f,(,x,0,),f,(,x,1,),f,(,x,n,),的线性组,合表示,且,差商及其性质,f,x,0,x,1,=,f,x,1,x,0,f,(,x,1,)-,f,(,x,0,),x,1,x,0,f,(x,0,)-,f,(,x,1,),x,0,x,1,=,性质,2,差商具有对称性,即在,k,阶差商中,任意交换两个节点 和 的次序,其值不变。,例如,性质,3,若,f,x,x,0,x,1,x,k,是,x,的,m,次多项式,则,f,x,x,0,x,1,x,k,x,k+1,是,x,的,m,-1,次多项式,证：由差商定义,右端分子为,m,次多项式,且当,x,=,x,k+1,时,分子为0,故分子含有因子,x,k+1,x,，,与分母相消后，右端为,m,-1,次多项式。,4.4.1 差商及其性质,性质,4,若,f,(,x,),是,n,次多项式,则,f,x,x,0,x,1,x,n,恒为0,证：,f,(,x,),是,n,次多项式，则,f,x,x,0,是,n,-1,次多,项式,f,x,x,0,x,1,是,n,-2,次多项式,依次递推,，,f,x,x,0,x,1,x,n-1,是零次多项式，所以,f,x,x,0,x,1,x,n,0,性质5,k,阶差商 和,k,阶导数之间有下,列关系,这个性质可直接用罗尔（,Rolle）,定理证明（或以下方法即余项方法）,牛顿(,Newton),插值多项式,的系数 可根据插值条件推出,即由,有,这是关于 的下三角方程组,可以求得,一般，用数学归纳法可证明,所以,n,次牛顿(,Newton),插值公式为,其余项,为牛顿插值多项式的误差。由插值多项式的存在惟一性定理知，满足同一组插值条件的拉格朗日插值多项式,P(x),与牛顿插值多项式,N,n,(x),实际上是同一个多项式，仅是同一插值多项式的不同表达形式而已，因此得到牛顿插值多项式的误差与拉格朗日插值多项式的误差也完全相等。故有,可以看出，牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而,N,n,(x),的各项系数恰好是各阶差商值，很有规律,f,x,0,x,(,x,-,x,0,),=f,(,x,)-,f,(,x,0,),f,(,x,),+f,x,0,x,(,x,-,x,0,),=f,(,x,0,),f,x,1,x,0,x,(,x,-,x,1,),=f,x,0,x,-,f,x,1,x,0,f,x,0,x,+f,x,1,x,0,x,(,x,-,x,1,),=f,x,1,x,0,f,(,x,),+,(,x,-,x,0,),f,x,1,x,0,=f,(,x,0,),+,(,x,-,x,0,)(,x,-,x,1,),f,x,1,x,0,x,牛顿插值公式(另一种推导方法）,f,(,x,),=f,(,x,0,),+,(,x,-,x,0,),f,x,1,x,0,+,(,x,-,x,0,)(,x,-,x,1,),f,x,1,x,0,x,f,x,1,x,0,x,=,(,x,-,x,2,),f,x,2,x,1,x,0,x,+,f,x,2,x,1,x,0,f,(,x,),=f,(,x,0,),+,(,x,-,x,0,),f,x,1,x,0,+(,x,-,x,0,)(,x,-,x,1,),f,x,2,x,1,x,0,+,(,x,-,x,0,)(,x,-,x,1,)(,x,-,x,2,),f,x,2,x,1,x,0,x,N,n,(x),R,n,(x),如当,n=1,时，,f,(,x,),=f,(,x,0,),+,(,x,-,x,0,),f,x,1,x,0,+,(,x,-,x,0,)(,x,-,x,1,),f,x,1,x,0,x,N,n,(x)=,f,(,x,0,),+,(,x,-,x,0,),f,x,1,x,0,其中,N,n,(x),称为,牛顿插值多项式,R,n,(x),称为,牛顿插值余项,x,i,f,x,if,x,i,x,i+1,f,x,i,x,i+1,x,i+2,f,x,i,x,i+1,x,i+2,x,0,f(x,0,),x,1,f(x,1,),f,x,0,x,1,x,2,f(x,2,),f,x,1,x,2,f,x,0,x,1,x,2,x,3,f(x,3,),f,x,2,x,3,f,x,1,x,2,x,3,f,x,0,x,1,x,2,x,3,4.4.2 牛顿插值公式,x,i,f,x,i,f,x,i,x,i+1,f,x,i,x,i+1,x,i+2,1,1,4,2,9,3,N,2,(7)=1+(7-1)*0.33333+(7-1)*(7-4)*(-0.01667)=2.69992,+,(,x,-x,0,)(,x,-,x,1,),f,x,1,x,0,x,2,+,(,x,-,x,0,),f,x,1,x,0,=f,(,x,0,),N,(,x,),例,2.12,已知,x=1,4,9,的平方根值，求,解：,牛顿插值余项,由,建起了差商和导数的关系,用导数代替牛顿插值多项式中的差商，有,差商和导数的关系也可用罗尔定理证出，余项,R(x),=,f,(,x,)-P(,x,),R(x,i,),=,f,(,x,i,)-P(,x,i,)=0 i=0,1,n,R,n,(n),(x),=,f,(n),(,x,)-P,n,(n),(,x,),=,f,(n),(,x,)-,f,(,x,0,)+(,x,-,x,0),f,x,0,x,1,+(,x,-,x,0,)(,x,-,x,1,),f,x,0,x,1,x,2,+(,x,-,x,0,)(,x,-,x,1,)(,x,-,x,n-1,),f,x,0,x,1,x,n,(n),=,f,(n),(,x,)-n!,f,x,0,x,1,x,n,R,n,(,x,i,)=0 (i=0,1,.,n),R,n,(,i,)=0 (i=0,1,.,n-1),R,n,(n),(,)=0 (,x,0,x,1,x,n,),R,n,(n),(,)=0=,f,(n),(,)-n!,f,x,0,x,1,x,n,即,R(x),在,x,0,x,n,有,n+1,个零点，根据罗尔定理,R,(n)x),在,x,0,x,n,有,1,个零点，设为,，,即有,R,n,(n),(,)=0,增加新节点,x,，,并且,f,(,x,),为(,n,+1),阶可导时，有,(,x,0,x,1,x,n,),(,x,0,x,1,x,n,x),|f,(,x,),(n+1)|,M,n+1,4.4.1 差商及其性质,例,2.13,已知,x,=0,2,3,5,对应的函数值为,y,=1,3,2,5,作三次,Newton,插值多项式。,x,i,f,(,x,i,),一阶差商 二阶差商 三阶差商,0 1,2 3 1,3 2 -1 -2/3,5 5 3/2 5/6 3/10,所求的三次,Newton,插值多项式为,4.4.1 差商及其性质,例,2.14,已知,f,(,x,)=,x,7,+,x,4,+3,x,+1,求,f,2,0,2,1,2,7,及,f,2,0,2,1,2,7,2,8,分析：本题,f,(,x,),是一个多项式,故应利用差商的性质,解:由差商与导数之间的关系,例,2.15,求 并估计其误差,解：作函数,f,(,x,)=,取,x,0,=4,x,1,=9,x,2,=6.25,建立差商表,x,f(x),f,x,i,x,i+1,f,x,i,x,i+1,x,i+2,4,2,9,3,6.25,2.5,N,2,(7)=2,+(7-4)*0.2,+(7-4)*(7-9)*(-0.00808),=2.64848,f,3,(x)=,R,n,(,x,),在区间 4,9 上，,余式近似 0.5*10,-2,N,2,(7)=2.64848,可舍入为2.65,|f,(,x,),(n+1),|,M,n+1,由,差分与等距节点插值,等距节点,x,i+1,-,x,i,=,h,，,函数在等距节点上的值为,y,0,y,1,y,n,，称,y,i-1,=,y,i,-,y,i-1,为函数,f,(,x,),在,x,i-1,x,i,上的,一阶差分,。,称,2,y,i-1,=,y,i,-,y,i-1,=,y,i+1,-,2,y,i,+,y,i-1,为函数,f,(,x,),在,x,i-1,x,i+1,上的,二阶差分,。,称,k,y,i-1k-1,y,i,-,k-1,y,i-1,为函数,f,(,x,),在,x,i-1,x,i+k-1,上的,k,阶差分,。,当插值节点等距分布时,被插值函数的变化率就可用差分来表示,这时牛顿插值公式的形式更简单,计算量更小,x,y,y,2,y,3,y,4,y,x,0,y,0,x,1,y,1,x,2,y,2,x,3,y,3,x,4,y,4,y,0,=,y,1,y,0,y,1,=,y,2,y,1,y,2,=,y,3,y,2,y,3,=,y,4,y,3,2,y,0,=,y,1,-,y,0,2,y,1,=,y,2,-,y,1,2,y,2,=,y,3,-,y,2,3,y,0,=,2,y,1,-,2,y,0,3,y,1,=,2,y,2,-,2,y,1,4,y,0,等距节点插值,y,0,=,y,1,y,0,y,1,=,y,2,y,1,y,2,=,y,3,y,2,=,y,2,2,y,1,+,y,0,2,y,0,=,y,1,-,y,0,3,y,0,=,2,y,1,-,2,y,0,=,y,3,2,y,2,+,y,1,(,y,2,2,y,1,+,y,0,),=,y,3,3,y,2,+,3,y,1,y,0,2,y,1,=,y,2,-,y,1,=,y,3,2,y,2,+,y,1,(,a,-,b,),3,=a,3,-3,a,2,b,+3,ab,2,-,b,3,(,a,-,b,),2,=a,2,-2,ab,+,b,2,4,y,0,=,3,y,1,-,3,y,0,=,y,4,3,y,3,+3,y,2,y,1,-(,y,3,3,y,2,+3,y,1,y,0,),=,y,4,4,y,3,+,6,y,2,4,y,1,+,y,0,(,a,-,b,),4,=a,4,-4,a,3,b,+6,a,2,b,2,-4,ab,3,+b,3,结论：各阶差分中函数值的系数正好等于,(,a-b),r,展开式中的系数,等距节点情况下,x,i,=,x,0,+,ih,，,用差分表示差商：,=,y,1,y,0,h,=,y,0,1!,h,f,x,1,x,2,=,y,2,y,1,h,=,y,1,1!,h,f,x,0,x,1,x,2,=,fx,1,x,2,-,f,x,0,x,1,x,2,x,0,=,y,1,1!,h,y,0,1!,h,2,h,=,y,1,-,y,0,2,h,2,=,2,y,0,2!,h,2,f,x,1,x,2,x,3,=,f,x,3,x,2,-,f,x,2,x,1,x,3,x,1,=,y,2,1!,h,y,1,1!,h,2,h,=,y,2,-,y,1,2!,h,2,=,2,y,1,2!,h,2,f,x,0,x,1,x,2,x,3,=,2,y,1,2!,h,2,2,y,0,2!,h,2,3,h,=,2,y,1,-,2,y,0,2*3,h,3,=,3,y,0,3!,h,3,n,y,0,n!,h,n,例,2.16,计算,f,(,x,),=,x,3,在等距节点0，1，2，3,4上的各,阶差分值,x,y,y,2,y,3,y,0,0,1,1,2,8,3,27,4,64,4,y,1,7,19,37,6,12,18,6,6,0,牛顿前插公式,取间距为,h,等距节点,x,0,x,1,x,n,顺序建立牛顿差商公式,f,x,0,x,1,=,y,0,1!,h,f,x,0,x,1,x,2,=,2,y,0,2!,h,2,f,x,0,x,1,x,2,x,3,=,3,y,0,3!,h,3,N,n,(,x,),=y,0,+,(,x,-,x,0,),y,0,1!,h,+,(,x,-,x,0,)(,x,-,x,1,),2,y,0,2!,h,2,+,(,x,-,x,0,)(,x,-,x,1,)(,x,-,x,n-1,),n,y,0,n!,h,n,牛顿前插公式,N,n,(x),R,n,(x),因 ,设 ,则,x,y,y,2,y,3,y,4,y,x,0,y,0,x,1,y,1,y,0,x,2,y,2,y,1,2,y,0,x,3,y,3,y,2,2,y,1,3,y,0,x,4,y,4,y,3,2,y,2,3,y,1,4,y,0,向后差分,函数,y=f(x),若记,y,-1,=f(x,0,-h),y,-2,=f(x,0,-2h),则各阶向后差分,一阶,y,0,=y,0,-y,-1,，,y,1,=y,1,-y,0,，,y,2,=y,2,-y,1,，,二阶,2,y,0,=,y,0,-,y,-1,=y,0,-y,-1,-(y,-1,-y,-2,)=y,0,-2y,-1,+y,-2,2,y,1,=,y,1,-,y,0,=y,1,-y,0,-(y,0,-y,-1,)=y,1,-2y,0,+y,-1,K,阶,k,y,0,=,k-1,y,0,-,k-1,y,-1,k,y,1,=,k-1,y,1,-,k-1,y,0,同样利用向后差分可以得到牛顿向后插值公式,其中 ,公式,称之为牛顿向后插值公式余项。,