1.2牛顿(Newton)插值多项式 .27 2.差商的计算 按照差商定义用两个k一1阶差商计算k阶差商，通常用差商表的形式存放和 计算（表1.1）. 表1.1差商表 工if(x) 一阶差商 二阶差商 三阶差商 n阶差商 0x0f(x0) 1x1f(x1) f[zo.z1l 2x2 f(x2 fro,1,2] f(3 f2,23] fz1,2,x3 f0,x1,x2,3 n In f(rn)f儿zn-1,xn】fzn-2,xn-1,xn】frn-3,xn】fr0,x1,.,xn】 由于差商对节点具有对称性，可以任意选择两个k-1阶差商的值计算k阶差 商.例如： fo,1,l=f1为]-fo,到=fo,-f,到-f,2-fo 2一E0 2-1 工1一C0 等多种形式. 例1.5计算(-2,17)，(0,1)，(1,2，(2,19)的一至三阶差商。 f4-,f[4-2,4-1,xf4-3,x-2,-1,x 0 f-2,0=-8 2 f0,1=1 f[-2.0.11=3 2 19 f1,2到=17 f10,1,2=8 f-2,0,1,2=1.25 解f-2,0=(1-17)/0-(-2)=-8 f0,1=(2-1)/1-0)=1,f1,2=(19-2)/(2-1)=17 f-2,0,1刂=(f[0,1刂-f-2,0)/1-(-2)=3 f10,1,2=(f1,2-f10,1)/(2-0)=8 f-2,0,1,2=(f0,1,2-f-2,0,1)/2-(-2)=1.25 1.2.2 Newton插值 1.线性插值 问题1.4给定两个插值点(o,f(o),(1,f(x1),xo≠x1,怎样构造线性插 值函数的Newton形式？ 用点斜式构造线性插值函数，设N1(e)=a0+a1(红-o),将x=o,x=x1代 入N()得
.28 第1章插值 Ni(xo)=ao=f(ro),Ni(1)=f(zo)+ai(z1-ro)=f(r1) a1=f）@=f,l t1-t0 得到线性插值的Newton形式： Ni(x)=f(xo)+(z-to)f[co,1] (1.12) 由插值唯一性，线性插值的Newton形式N1(x)与Lagrange形式L(r)为同 一个多项式，仅是表达形式不同而已. 2.二次插值多项式 问题1.5给定{(c,f(x),i=0,l,2x,互不相同，怎样构造二次Newton 插值多项式？ 分析Newton插值基函数{L,x-xo,(e-xo)(x一x1)} N2(x)=a0+a1(x-x0)+a2(x-x0)(e-x1) 由 N2(xo)=f(xo),N2(z1)=f(r1) ao+a1(x-zo)就是f(z)关于xo,x1的线性Newton插值M1(x,即 N2(x)=N1(x)+a2(e-xo)(e-) 在构造（回）过程中己经计算出o,a4,将r=2代入上式得 N2(x2)=f(ro)+f(ro,z1](r2-zo)+a2(22-ro)(x2-1)=f(2) 整理得 2=o,-fo到=fo,1,l x2-x1 得到二次插值的Newton形式： N2()=f(ro)+(-ro)flro,1]+(z-Fo)(x-1)f[zo,1,2] (1.13) 3.n次Newton插值函数 问题1.6给定{(r,fc》,i=0,1,.,n:其中互不相同，怎样构造n次 Newton插值多项式？ 用数学归纳法给出构造过程.由一阶差商的定义f化，可=回-儿四】，有 -To f(x)=f(ro)+(x-xo)f[r,zo] (1)
1.2牛顿(Newton)插值多项式 ·29 注(1)式是f(e)的零次插值，f(x)=No(c)+Ro(x). 为了进一步展开f,0,由，0，=区，0-儿o,到得 f[,zo]f[o,1]+(-1)f[,xo,z1] (2) 将(2)代入(1)得到Newton线性插值多项式 f(x)=f(xo)+f[ro,x1](r-ro)+f(r,ro,1](x-zo)(x-1) f(x)=N1(a)+B(x) 设k=n-1时，有 f (r)=f(xo)+(z-z0)f[ro,z1]+(x-xo)(x-z1)f[ro,z1;x2]+. +(x-o)(x-1).(r-xn-2)fr0,x1,.,xn-]+n-1(x) f(x)=Nn-1()+(-o)(x-.(e-xn-i)fx,x0,x1,.,xn-](3) f,0,.,小=f,0,.n-f0, T-Tn 有 fz,x0,.,n-i]=fo,1,.,xn+(-xn)fz,x0,.,xnl () 将(4)式代入（③）得到 f(x)=Nn(x)+Rn(x) 其中 Nn (z)=f(xo)+(x-zo)f[o,1]+. +(x-o)(x-x1).(x-xn-1)f0,1,·,xn Rn(a)=(x-zo)(e-x1).(e-xn)fz,0,x1,·,xn Nn(c)至多为n次多项式，可以验证N(x)=f(c),i=1,2,·,n:称N()是 过n+1个插值点的（至多）n次Newton插值多项式.也记 N(e）=fxol+fo,x1,.,xk](e-xo)(z-x1).(e-Ek-1) k=1 其中 R()=f,0,.,nlΠe-)
·30 第1章插值 为插值多项式的误差 由插值多项式的唯一性得到Lagrange插值多项式L(c)与Newton插值多项 式N(x)是完全相同的，它们是同一插值多项式在不同基下的不同表达形式，因 此Lagrange插值多项式的余项与Newton插值多项式的余项也完全相等.故当 f∈Cm+1[a,时，有 Rg)=w但ie-动=压o.,ie- (n+1)！ =0 故有 fn+1)() (n+1)！ =f,x0,E1,.,n (1.14) (1.14)给出函数差商和导数之间的关系式. 记Nn(e)=t(x)fzo,.,xl,其中 i=0 to(x)三1，t(a)=(x-1)-1(x)= He-a).i-1.2. 也有 t(r)=0,j<i t()≠0，j=i 可以看到Lagrange插值多项式是基函数{l(r),i=0,l,.,nm}的线性组合， Newton插值多项式是基函数{(c),i=0,1,·,n}的线性组合. Newton插值多项式的承袭性质表现在 N()=NK-1()+tk()f[o,1,.,] 对于k-1阶Newton插值多项式Nk-1(z),只需增加一项tk(z)f[xo,x1,·,x, 即可得到k阶Newton插值多项式Nk(x), 例1.6设f(x)=10x3-100x+1,计算f0,x1,2,xl,fz0,E1,x2,x3,x4 其中{x,i=0,1,.,4}任取. 解f0,1,2,x3= 8_60 =10 o4,2,ao国0o 例1.7给定如表1.2所列插值节点的值，构造Newton形式插值函数，计算 N2(0.9),N3(0.9) 表1.2 -2 0 2 f(i) 17 19
l.2牛顿(Newton)插值多项式 31 N2()=f(ro)+(-zo),1]+(-zo)(x-z1)f[ro,1,2] 取x0=-2,x1=0,x2=1;用例1.5中算出的差商代入上式，得到二阶Newton 插值多项式 N2(x)=17-8(x+2)+3(x+2) N2(0.9)=17.0-8(0.9+2)+3(0.9+2)·0.9=1.63 N3(x)=N2(x)+fro,x1,E2,x3](r-xo)(r-E1)(e-x2) 取x0=-2,x1=0,x2=1,3=2:得到三阶Newton插值多项式： N3(x)=17-8(x+2)+3x(x+2)+1.25z(x+2)(x-1) N3(0.9)=N2(0.9)+1.25.0.9.(x+0.9)(0.9-1.0)=1.30375 构造N3(x)的嵌套乘法形式，计算N3()只需3次乘法。 N3(x)=f(zo)+(-xo)[f[o,1]+(-1)[f[o,1,2]+(-x2)f[zo,1,2,x3] N3(x)=17+(x+2)[-8+3x+1.25(x-1)川 一般地，记90=fo,9张=fro,t1,.,k,Nn()=90+(r-o)g1+(e 1)儿g2+.+(-xn-1)儿gn-1+(-xn)9nll. 计算Nn(x)的计算量为n次乘法. 4.Newton插值的算法 st@p1输入插值节点数n,插值点序列{(x(),f(),i=1,2,·,n} 要计算的插值点u step2形成差商表{gk,k=0,1,·,nm}Ig张表示fo,1,.,Ek] step3置初始值t=1;newton=90 step4 for k=1 to n t=t(u-Ik-1) newton newton +t.g step5输出f(u)的近似数值Nn(u)=newton 从表1.1的差商计算中可以看到，在给定的n+1个插值点，似乎存放所有差商 值需要n2个存储单元，而在Newton插值表达式中只用到f[xo,fo,x1,x2,· f[x0,x1,.,n】对角线上的差商值，在计算中可用一维数组g间，i=0,1,2,.,n 存放这些差商值 下面对step2算法形成差商表{g(k),k=1,2,·,n}作进一步展开