牛顿均差差值

1、3牛顿插值牛顿插值将将 Pn(x) 改写成改写成.)()(102010 xxxxaxxaa).(10 nnxxxxa的形式，希望每加一个节点时，的形式，希望每加一个节点时，只附加一项只附加一项上去即可。上去即可。?Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函数全部基函数 li(x) 都需重新算过。都需重新算过。 差商差商( (亦称均差亦称均差) )101010)()(,xxxfxfxxf 1阶差商阶差商 202110210,xxxxfxxfxxxf 2阶差商阶差商212121)()(,xxxfxfxxf k阶差商：阶差商：,110kkxxx

2、xf kkkkkxxxxxxfxxxf 1210110,从从0阶差商开始通过简单的差商运算可以逐步提高差商的阶数阶差商开始通过简单的差商运算可以逐步提高差商的阶数阶阶差差商商为为0)(ixf差商具有如下性质：差商具有如下性质：且且的的线线性性组组合合表表示示可可由由函函数数值值阶阶差差商商的的,)(,),(),(,)()2(10110kkkxfxfxfxxxxfkxf ,110kkxxxxf kikiiiiiiixxxxxxxxxf0110)()()()(1) (1) 差商具有对称性差商具有对称性, ,即任意调换节点的次序即任意调换节点的次序, ,差商的值不变差商的值不变,210 xxxf,1

3、20 xxxf ,012xxxf 如如f (x1)f (x2)f (xn 1)f (xn)f x1, x2 f xn 1, xn f xn 2, xn 1, xnx0 x1x2xn 1xn xk 0阶差商阶差商 1阶差商阶差商 2阶差商阶差商 n阶差商阶差商差商的计算方法差商的计算方法(表格法表格法)差商表差商表a10a20an-1,0an,0a11a21 an,1a22 an2annai0=f(xi)jiixxjiajiaaij )1, 1()1,(jx0 x1x2xn 1xniiji,j=0n 牛顿插值牛顿插值,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxx

4、fxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf 12 n 1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ai = f x0, , xi 可验证可验证Nn(x)Nn(x)满足插值条件即牛顿基本插值公式满足插值条件即牛顿基本插值公式nixPin,., 0)( 求求 不超过不超过n 次多项式次多项式 满足满足)(xPn目标：目标：f(xi)注：注：各项系数由差商表容易得到，即对角线上元素各项系数由差商表容易得到，即对角线上元素)(!)1

5、()()(,.,1)1(10 xnfxxxxfnxnnn ),(,!)(,.,maxmin)(0 xxnfxxfnn 相邻次数的多项式相关，即牛顿公式具承袭性相邻次数的多项式相关，即牛顿公式具承袭性 由由唯一性可知唯一性可知 Nn(x) Pn(x)， 只是算法不同，只是算法不同，故其余项也相同，即故其余项也相同，即例例 f(x)的函数表如下，用三次牛顿插值计算的函数表如下，用三次牛顿插值计算f(0.596)的近似值的近似值Xi0.550.650.800.90零阶差商零阶差商0.578150.696750.888111.02652一阶差商一阶差商1.1861.275731.38410二阶差商二阶

6、差商0.358920.43338三阶差商三阶差商0.21303解：解：N3(x)=0.57815+1.186(x-0.55)+0.35892(x-0.55)(x-0.62)+0.21303(x-0.55)(x-0.65)(x-0.80)f(0.596) N3(0.596)=0.63192 差商表实现：存储采用二维数组差商表实现：存储采用二维数组 a(i,0)= f(xa(i,0)= f(xi i) (i=0,1,) (i=0,1,n),n) a(i,j) a(i,j) i=j i,j=0,1i=j i,j=0,1n n 对角线元素对角线元素a a（k,k)k,k)为牛顿插值公式系数为牛顿插值公

7、式系数jiixxjiajia )1, 1()1,( 牛顿插值算法设计牛顿插值算法设计.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxNn).(,.,100 nnxxxxxxfA(i,0) yiA(i,j) j=1,2N;I= j,j+1,Ny y+t*A(k,k)Nk 0 y 0t 1 kNYk k+1jiixxjiAjiA) 1, 1() 1,(1,.,0*)( kjtxxtj牛顿插值算法流程图牛顿插值算法流程图输入输入xi，yi, x,N输出输出y2 Newtons Interpolation 等距节点公式等距节点公式 /* Formulae with Equal

8、 Spacing */牛顿基本插值公式对结点是否等距没有限制牛顿基本插值公式对结点是否等距没有限制. .不过当不过当结点等距时前述牛顿插值公式可进行简化结点等距时前述牛顿插值公式可进行简化. .首先介绍首先介绍差分概念差分概念. .在在x x0 0以以h h为步长的一阶向前差分为步长的一阶向前差分 010y y y当节点当节点等距等距分布时分布时:),.,0(0nihixxi 0nnxxh 步步长长121 y y y在在x x1 1以以h h为步长的一阶向前差分为步长的一阶向前差分 2010 yyy在在x x0 0以以h h为步长的二阶向前差分为步长的二阶向前差分 111 mmmiiiyyy在

9、在x x0 0以以h h为步长的为步长的m m阶向前差分阶向前差分 (1) (1) 差分可表为函数值的线性组合差分可表为函数值的线性组合 ( (证略证略) ) ),( )(0)(0 xxfhynnnn (3)(3)性质性质:hyxxxxnnnnf!,0210 (2) ( (2) (证明用归纳法略证明用归纳法略) )差分表差分表 ( (实用实用) )yyyyxyyyxyyxyxyxii03122330212201100 三阶差分三阶差分二阶差分二阶差分一阶差分一阶差分 等距结点插值公式等距结点插值公式: : 将将NewtonNewton插值公式插值公式 00100120101011( )(),(

10、),()() ,()()()nnnxffxfxxfxxxxx xxx x xxxNx xxxxx 中的差商用性质中的差商用性质(2)(2)换为差分换为差分, ,可整理为如下的可整理为如下的 NewtonNewton向前插值公式向前插值公式yyyxxNNnnnnnttttttfthx002000!)1()1( ! 2)1()()()( 00+ (0n),ixxthtxxih 设设hyxxxxnnnnf!,0210 截断误差可表示为截断误差可表示为)()!1()() 1()()()1(10 fhxnnnntttthRxR 1010()() (1)! max(1)() ?nntnR xRthnt ttnhhMx NewtonNewton向后插值公式向后插值公式例例 f(x)的函数表如下，用四次牛顿插值计算的函数表如下，用四次牛顿插值计算f(0.048)的近似值的近似值f(Xi)1.000000.995000.980070.9553492106xi0.00.10.20.30.4一阶差分一阶差分-0.00500-0.01493-0.02473-0.03428二阶差分二阶差分-0.00993-0.00980-0.00955三阶差分三阶差分0.000130.00025解：解：h=0.1 当当x=0.