Chapter5_1Newton插值

牛顿插值（Newton’sInterpolation）Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需要重新计算。能否重新在Pn中寻找新的基函数？希望每加一个节点时，只附加一项上去即可。本讲主要内容:●Newton插值多项式的构造●差商的定义及性质●差分的定义及性质●等距节点Newton插值公式｛1,x-x0,(x-x0)(x-x1)，…，(x-x0)(x-x1)…(x-xn-1)｝是否构成Pn的一组基函数？01020101()()()()...()...()nnnNxAAxxAxxxxAxxxx利用插值条件Nn(xj)=f(xj),j=0,1，…，n代入上式，得关于Ak(k=0,1，…，n)的线性代数方程组基函数0010111000100()10()1()()nninniAfxxxAfxxxxxAfx当xj互异时，系数矩阵非奇异，且容易求解10110()()fxfxAxx10212202110()()()()()/()fxfxfxfxAxxxxxxHowcomplextheexpressionsare!Itisnotadifficultthingforamathematician.Wecanusenotation00()Afx1．差商的定义定义1：设有函数f(x)以及自变量的一系列互不相等的x0,x1,…,xn（即在ij时，xixj）的值f(xi),称),()()(],[jijijijixxjixxxfxfxxf为f(x)在点xi,xj处的一阶差商，并记作f[xi,xj]，f[xi,xj]的几何意义为过(xi,f(xi))和(xj,f(xj))两点处割线的斜率。)(],[],[],,[kixxxxfxxfxxxfkikjjikji称为f(x)在点xi,xj,xk处的二阶差商。nnnnxxxxxfxxxfxxxf02111010],,[],,,[],,[称为f(x)在点x0,x1,…,xn处的n阶差商。特别地，规定f(x)在点xi,处的零阶差商为f[xi]=f(xi)。利用插值条件和差商,可求出Nn(x)的系数Ai:00100011()()[,]()[,,]()()()nnnNxfxfxxxxfxxxxxxxx00010101()[][,][,,,]nnAfxfxAfxxAfxxx0010010001010101()()()()[,]()()[,]()()()[,,]()()()kkkkNxfxNxfxfxxxxNxfxxxxNxNxfxxxxxxxx因此，每增加一个结点，Newton插值多项式只增加一项，克服了Lagrange插值的缺点。.xkf(xk)一阶差商二阶差商三阶差商……n阶差商差商表123onxxxxx0123[][][][][]nfxfxfxfxfx0112231[,][,][,][,]nnfxxfxxfxxfxx01212321[,,][,,][,,]nnnfxxxfxxxfxxx0123321[,,,][,,,]nnnnfxxxxfxxxx01[,,,]nfxxx例1：气温函数y=f(x)的一组观测数据如下时间xi(时)10111213气温yi(℃)20222826求气温函数的近似函数N3(x)，并求N3(12.5)根据已知数据求出差商表由此表得:N3(x)=20+2(x-10)+2(x-10)(x-11)-2(x-10)(x-11)(x-12)=-2x3+68x2-764x+2860N3(12.5)=28.75xiyi一阶差商二阶差商三阶差商1020112221228621326-2-4-2解：例2:给定f(x)=lnx的数据表xi2.202.402.602.803.00f(xi)0.788460.875470.955511.029621.098611.构造差商表2.分别写出二次、四次Newton插值多项式解:差商表[]2.200.788462.400.875470.435052.600.955510.400100.0873752.801.029620.370550.0738750.022503.001.098610.344950.064000.016460.00755iixfx一阶差商二阶差商三阶差商四阶差商N2(x)=0.78846+0.43505(x-2.20)-0.087375(x-2.20)(x-2.40）N4(x)=0.78846+0.43505(x-2.20）-0.087375(x-2.20)(x-2.40)+0.0225(x-2.20)(x-2.40)(x-2.60)-0.00755(x-2.20)(x-2.40)(x-2.60)(x-2.80)11101010111010],,...,[],,...,[],,...,[],...,,[],...,[kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)阶差商：kiikikxxfxxf010)()(],...,[事实上其中,)()(01kiikxxxkijjjiikxxx01)()(差商的性质性质1（差商与函数值的关系)0101()[,,,]()kikinifxfxxxx证：当k=1时，等式成立。当k=2时，有：011201202[,][,][,,]fxxfxxfxxxxx0112020112()()()()1fxfxfxfxxxxxxx011201202[,][,][,,]fxxfxxfxxxxx012010201120212()()()()()()()()()fxfxfxxxxxxxxxxxxx012010210122021()()()()()()()()()fxfxfxxxxxxxxxxxxx性质2(差商的对称性)差商与节点的顺序无关。如:[,,][,,][,,]ijkikjjikfxxxfxxxfxxx证:由性质1可得。性质3(差商与导数的关系)若f(x)在包含k+1个互异节点的区间[a,b]上k阶可导,则：()01()[,,](a,b)!kkffxxxk此性质在后面证明。性质4(多项式的差商)若f(x)是n阶多项式，则f[x,xj]是n-1阶多项式。因为f(x)是n次多项式，所以g(x)=f(x)-f(xi)也是n次多项式。由于g(xi)=0，所以可设g(x)=(x-xi)Pn-1(x)，故有1()()[]()iin-ifx-fxfx,x==pxx-x即f[x,xj]是n-1阶多项式。证：牛顿插值/*Newton’sInterpolation*/],[)()()(000xxfxxxfxf],,[)(],[],[101100xxxfxxxxfxxf],...,,[)(],...,[],...,,[0010nnnnxxxfxxxxfxxxf))...((...))(()()(10102010nnnxxxxaxxxxaxxaaxN12…………n11+(xx0)2+……+(xx0)…(xxn1)n1...))(](,,[)](,[)()(102100100xxxxxxxfxxxxfxfxf))...(](,...,[100nnxxxxxxf))()...(](,...,,[100nnnxxxxxxxxxfNn(x)Rn(x)ai=f[x0,…,xi]注：由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即)(!)1()()(],...,,[1)1(10xnfxxxxfkxnkn),(,!)(],...,[maxmin)(0xxkfxxfkk实际计算过程为f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]差分，等距节点插值如果xi是等距节点，则xi-xi-1=h(i=1,2,…,n)，称h0为步长。则xi=x0+ih(i=1,2,…,n)。由于这是一种特殊情况，所以牛顿插值公式仍然成立。不过，通过引入差分的概念，可以把牛顿插值公式表示得更加方便。一阶向前差分一阶向后差分当节点等距分布时:),...,0(0nihixxi1.差分及其性质1iiiyyy21121()()2iiiiiiiiiyyyyyyyyy1iiiyyy1112))2iiiiiiiiiyyyyyyyyy二阶向前差分二阶向后差分向前差分表向后差分表的计算与此类似.xiyiyi2yi3yinyix0y0x1y1y0x2y2y12y0x3y3y22y13y0xnynyn-12yn-23yn-3ny0性质2:(前差与后差的关系)性质1:(差分与函数值各阶差分均可表示为函数值的线性组合的关系)00(1)(1)mmjjimijmjmmmjjimijmjyCyyCymmiimyy性质3:(差分与差商的关系)1111[,,,]!11[,,,]!miiimimmiiimimfxxxymhfxxxymh性质4:(差分与导数的关系)设f(x)有m阶导数，则有关系式()![,,,]()()1mmmmymhfxxxhfxxiiiimiim给定等距节点xi=x0+ih(i=1,2,…,n)。令x=x0+th,0xxn,0tn,则i+1(x)=(x-x0)(x-x1)…(x-xi)=t(t-1)(t-2)…(t-i)hi+1。2.等距节点的牛顿插值牛顿公式))...(](,...,[...)](,[)()(1000100nnnxxxxxxfxxxxfxfxN牛顿前插公式020000()(1)(1)(1)2!!nnn(x)=Nx+thtt-tt-t-n+=y+ty+y++ynNDDDLL（1）牛顿后插公式将节点顺序倒置：))...(](,...,[...)](,[)()(101xxxxxxfxxxxfxfxNnnnnnnn注：一般当x靠近x0时用前插，靠近xn时用后插，计算时分别用向前差分表和向后差分表.22()()(1)(1)(1)(1)(1)2!!nnnnnnnnnxNxthtttttnytyyynN=----+=-?-?+-?LL实际中，插值点x有的靠近,有的靠近，用两个差分表会很麻烦。由差分的性质2得这个公式只用到向前差分表.用其最后一行的叫表后公式（2）,用其对角线上的值的公式叫表前公式（1）.12220()()(1)(1)(1)(1)(1)2!!nnnnnnnnNxNxthytytttttnyyn--=-=-+---+-++-VLVLV（2）0xnx向前插值公式和向后插值公式的余项分别为:例3:已知y=f(x)的函数值表如下:(1)100(1)1100()()(1)(),(1)!()()(1)(1)(),(1)!nnnnnnnnnfRxthhtttnxxnfRxthhtttnxxnxxxx++++++=--+-=---+LLxi0.40.60.81.0yi1.51.82.22.8求y=f(0.5)和y=f(0.9).这是一个等距节点的插值问题,构造向前差分表由于所以由表