newton插值均差与差分.docx

newton插值均差与差分第五章 函数近似计算(插值问题)的插值方法 5.3 Newton插值/均值与差分 lagrange插值多项式作为一种计算方案，公式简洁，做理论分析也方便其缺点是，当节点改变时，公式需要重建，计算量大；如果还要根据精度要求，选取合适的节点和插值多项式的次数，则只好逐次计算出 L1(x), L2(x) 等，并做误差试算，才可以做到，这当然是不理想的 为次，人们从改进插值多项式的形式入手，给出另一种风格的插值公式，这就是Newton(牛顿)插值公式 Newton插值公式通过均差和差分的记号来表达 1． 均差的概念及其性质 定义 5.3.1 设函数f在互异节点x0,x1,L上的值为 f(x0), f(x1),等，定义 (1) ff在xi,xj上的1阶均差为 f[xi,xj]=f(xi)-f(xj)xi-xj(2) 在xi,xj,xk上的2阶均差为 f[xi,xj,xk]=f[xi,xj]-f[xj,xk]xi-xk递推地，f在x0,x1,L,xk上的k阶均差为 f[x0,x1,L,xk]=f[x0,x1,L,xk-1]-f[x1,x2,L,xk]x0-xkf[x]]=f(xi) 同时规定性质1 f在xi上的零阶均差为 k阶均差可以表示成kk+1个函数值的线性组合，即 f(xj)(5.3.5) f[x0,x1,L,xk]=åj=0(xj-x0)L(xj-xj-1)(xj-xj+1)L(xj-xk)k或记为 f[x0,x1,L,xk]=åj=0f(xj)w'k+1(xj)证明：用数学归纳法。

当k=1时由均差定义有 =f(x0)x0-x1+f(x1)x1-x0f[x0,x1]=f(x0)-f(x1)x0-x1故(5.3.5)式成立现假设k=m-1时(5.3.5)已成立，对k=m由均差定义及归纳假设有 f[x0,x1,L,xm]=m-1f[x0,x1,L,xm-1]-f[x1,x2,L,xm]x0-xmf(xj)1=åj=0m(xj-x0)L(xj-xj-1)(xj-xj+1)(xj-xm-1)x0-xmf(xj)-åj=11(xj-x1)L(xj-xj-1)(xj-xj+1)(xj-xm)x0-xm=f(x0)1xj-x011xj-xm1(x0-x1)(x0-x2)L(x0-xm-1)x0-xmf(xj)(-+)´m-1åj=11x0-xm(xj-x1)(xj-x2)L(xj-xj-1)(xj-xj+1)L(xj-xm-1)f(xm)(xm-x1)(xm-x2)L(xm-xm-1)m+´xm-x0=åj=0f(xj)(xj-x0)(xj-x1)L(xj-xj-1)(xj-xj+1)L(xj-xm)可知(5.3.5)成立 性质2 均差对其节点是对称的，即节点按任意顺序排列，其值不变。

如 f[xi,xj,xm]=f[xj,xi,xk]=f[xk,xj,xi]=L 这个性质称为对称性 性质3 如果f[x,x0,x1,L,xk]是x的m次多项式，则其1阶均差f[x,x0,x1,L,xk,xk+1]是x的m-1次多项式，且由此递推可得n阶均差为零阶均差，n+1阶均差为零 f[x,x0,x1,L,xk]的1阶均差为 证明：按均差定义，f[x,x0,x1,L,xk+1]=f[x,x0,L,xk]-f[x0,x1,L,xk+1]x-xk+1由假设，上式等号右端分子为x的m次多项式，且当x=xk+1时为零，可知分子会有因子(x-xk+1),它与分母(x-xk+1)同时约去，则得等号右端为m-1次多项式 xj f(xj) 零阶均差 1阶均差 2阶均差 3阶均差 x0 f(x0) f[x0] x1 f(x1) f[x1] f[x0,x1] x2 f(x2) f[x2] f[x1,x2] f[x0,x1,x2] x3 f(x3) f[x3] f[x2,x3] f[x1,x2,x3] f[x0,x1,x2,x3] 2．Newton插值公式及其余项 由均差的定义可知 f(x)=f(x0)+f[x,x0](x-x0) f[x,x0]=f[x0,x1]+f[x,x0,x1](x-x1) f[x,x0,x1]=f[x0,x1,x2]+f[x,x0,x1,x2](x-x2) f[x,x0,L,xn-1]=f[x0,x1,L,xn]+f[x,x0,L,xn](x-xn) 对上述第二式两端乘以(x以(x-x0)，第三式两端乘以(x-x0)(x-x1), 最后一式两端乘-x0)(x-x1)L(x-xn-1)，然后由后一式的左端代入前一式的右端(第二项)，即可得 f(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+L+f[x0,x1,L,xn](x-x0)(x-x1)L(x-xn-1)+f[x,x0,x1,L,xn](x-x0)(x-x1)L(x-xn)=Nn(x)+Rn(x)Nn(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+L+f[x0,x1,L,xn](x-x0)(x-x1)L(x-xn)(5.3.6)Rn(x)=f[x,x0,x1,L,xn](x-x0)(x-x1)L(x-xn) (5.3.7) 显然，Nn(x)是n次多项式，又Rn(x)有Rn(xi)=0，故有f(xi)=Nn(xi)+0(i=0,1,L,n)，从而满足条件Nn(xi)=f(xi)，这就说明Nn(x)是f(x)关于x0,x1,L,xn的n次插值多项式，通常称它为Newton插值公式，Rn(x)为插值余项。

根据插值多项式的惟一性，可知Newton插值与Lagrange插值之间有 Nn(x)=Ln(x) Rn(x)=Rn(x) 于是就有 f[x,x0,x1,L,xn]wn+1(x)=f(n+1)(x)(n+1)!wn+1(x) xÎ(a,b) 从而可得均差与导数之间存在关系 f[x,x0,x1,L,xn]=f(n+1)(x)(n+1)!xÎ(a,b) Nn+1(xn+1)=f(xn+1) 现在如果再 增加节点xn+1，即相当于增加插值条件 这时，只要在Nn(x)中增加一项 f[x0,x1,L,xn,xn+1](x-x0)(x-x1)L(x-xn) 即可满足条件，从而可得新的Newton插值公式 Nn+1(x)=Nn(x)+f[x0,x1,L,xn,xn+1](x-x0)(x-x1)L(x-xn) Newton插值余项称为均差型余项，Lagrange插值余项称为微分型余项 3． 差分的概念及其性质 定义 5.3.2 设函数f在等距节点 xi=x0+ih(i=0,±1,±2,L,)12处的值fi=f(xi)，在xi±(1) (2) (3) 12h处 的值记为fi±=f(xi±12h),定义 fff在xi的1阶向前差分 在xi的1阶向后差分 Dfi=fi+1-fi Ñfi=fi-fi-1 在xi的1阶中心差分 dfi=fi+12-fi-12由此递推得定义f在xi的 nn-1n阶向前差分 Dfi=Dnfi+1-Dn-1n-1fi fi-1 n阶向后差分 Ñfi=Ñn阶中心差分 dfi=d以及规定零阶差分 nfi-Ñ12n-1n-1fi+-dn-1fi-12Dfi=Ñfi=dfi=fi 上述定义中的符号，实际上起着算子的作用。

此外，进一步还使用另外两个差分算子符号： (1) 位移算子 000E Efi=fi+1 Efi=fi-1 Ifi=fi (2) 单位(或称不变)算子 于是由 Dfi=fi+1-fi=(E-I)fi，可得 -1D=E-I Ñ=I-E1d=E-E2-12性质1 差分与函数值可互相表示例如 fi+n=Efi=(I+D)fi=å(j)Dfi (5.3.12 ) j=0nnnnjDfi=(E-I)fi=å(-1)(j)fn+i-jj=0nnnjn (5.3.13 ) Ñfi=(I-E)fi=å(-1)j=0n-1nnn-j(j)fi+j-nn其中 (j)=nn(n-1)L(n-j+1)j!性质 2 差分与均差可互相表示 f[xk,xk+1]=fk+1-fkxk+1-xk=Dfkhf[xk,xk+1,xk+2]=f[xk,xk+1]-f[xk+1,xk+2]xk-xk+2=Dfk2h22f[x0,x1,L,xk]=1k!hkDf0 k性质3 差分与导数值也可互相表示例如 设 fÎC[x0,x0+kh]，则有 kDf0=hfkk(k)(x) xÎ(x0,xk) 4． 等距离节点的Newton插值公式 (1) Newton前插公式 设节点xk=x0+kh(k=0,1,L,n)，要计算x0附近点x的函数值f(x),可令 x=x0+kh(0£t£1)，于是 wn+1(x)=Õ(x-xj)=t(t-1)(t-2)L(t-k)hj=0kk+1并注意到 f[x0,x1,L,xk]=1k!h12!kDf0， 代入(5.3.6 )Nn(x)得 2kNn(x0+th)=f0+tDf0+t(t-1)Df0+L+1n!t(t-1)L(t-n+1)Df0n它称为Newton前插公式，其余项公式为 Rn(x)=(2) Newton后插公式 如果要求的是t(t-1)L(t-n)(n+1)!hn+1f(n+1)(x) xÎ(x0,xn) f在xn附近的值，把插值节点按xn,xn-1,L,x1,x0次序排列，再取变换 x=xn+th(-1£t£0)，即得Newton后插公式 Nn(xn+th)=fn+tÑfn+余项为 12!t(t+1)Ñfn+L+21n!t(t+1)L(t+n+1)ÑfnnRn(x)=t(t+1)L(t+n)(n+1)!hn+1f(n+1)(x) xÎ(xn,x0) 。