数值分析4.2 牛顿插值法

将Ln(x)改写成...))(()(102010xxxxaxxaa))...((10nnxxxxa的形式，希望每加一个节点，只附加一项上去即可。Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新计算。4.3Newton(牛顿)插值4.3.1均差及其基本性质定义1称101010)()(],[xxxfxfxxf为f(x)在x0、x1点的一阶均差.一阶均差的均差(差商)202110210],[],[],,[xxxxfxxfxxxf称为函数f(x)在x0、x1、x2点的二阶均差.4.3Newton(牛顿)插值一般地，n-1阶均差的均差nnnnnnxxxxxfxxxfxxxf01112010],,,[],,,[],,,[称为f(x)在x0,x1,…,xn点的n阶均差。差商的计算步骤与结果可列成均差表，如下一般f(xi)称为f(x)在xi点的零阶均差，记作f[xi]。xk函数值一阶均差二阶均差三阶均差...x0x1x2x3...f(x0)f(x1)f(x2)f(x3)...f[x0,x1]f[x1,x2]f[x2,x3]...f[x0,x1,x2]f[x1,x2,x3]...f[x0,x1,x2,x3]......表1（均差表）nknkkkkkkknxxxxxxxxxfxxxf011010)())(()()(],,,[这一性质可以用数学归纳法证明，它表明均差与节点的排列次序无关，即f[x0,x1,x2,...,xn]=f[x1,x0,x2,...,xn]=…=f[x1,x2,...,xn,x0]性质1均差可以表示为函数值的线性组合，即称之为均差的对称性（也称为对称性质）。性质2n次多项式f(x)的k阶差商,当kn时是一个n-k次多项式;当kn时恒等于0.性质3若f(x)在[a,b]上存在n阶导数,且节点x0,x1,…,xn∈[a,b],则至少存在一点[a,b]满足下式!)(],,,[)(10nfxxxfnn例1f(x)=－6x8+7x5－10,求f[1,2,…,9]及f[1,2,…,10].解f(8)(x)=－6·8!,f[1,2,…,9]=-6,f(9)(x)=0,f[1,2,…,10]=0.4.3.2牛顿插值多项式设x是[a，b]上一点，由一阶均差定义得)](,[)()(000xxxxfxfxf同理，由二阶均差定义)](,,[],[],[110100xxxxxfxxfxxf如此继续下去，可得一系列等式000)()(],[xxxfxfxxf110010],[],[],,[xxxxfxxfxxxf得得01010[,,,][,,,][,,,]()nnnnfxxxfxxxfxxxxx)](,[)()(000xxxxfxfxf)](,,[],[],[110100xxxxxfxxfxxf)](,,,[],,[],,[221021010xxxxxxfxxxfxxxf依次把后式代入前式，最后得00000100101001001201012012()()[,]()()[,]()[,,]()()()[,]()[,,]()()[,,,]()()()fxfxfxxxxfxfxxxxfxxxxxxxfxfxxxxfxxxxxxxfxxxxxxxxxx00100101001001201012012()()[,]()[,,]()()()[,]()[,,]()()[,,,]()()()()()nnfxfxfxxxxfxxxxxxxfxfxxxxfxxxxxxxfxxxxxxxxxxNxRx00100120101010011()()[,]()[,,]()()[,,,]()()()[,,,]()nnnnkkkNxfxfxxxxfxxxxxxxfxxxxxxxfxfxxxx其中00101()[,,,]()()()[,,,]()nnnnnRxfxxxxxxxxxfxxxx()()()nnfxNxRx可见,Nn(x)为次数不超过n的多项式,且易知Rn(xi)=0即Nn(xi)=yi,(i=0,1,…,n)满足插值条件,故其为插值问题的解,Nn(x)称为牛顿插值多项式。001001201001()()[,]()[,,]()()[,,]()()nnnNxfxfxxxxfxxxxxxxfxxxxxx001()[,,,]()()()nnnRxfxxxxxxxxxRn(x)称为牛顿型插值余项。由插值多项式的唯一性知，它与拉格朗日插值多项式是等价的,即Ln(x)Nn(x)且有如下递推形式)()](,,[)()(1001nnnnxxxxxxfxNxN和余项公式)()](,,,,[)(010nnnxxxxxxxxfxR)()()!1()(0)1(nnxxxxnf)()](,,,,[)()](,,,,[)(01100101nnnnnnnxxxxxxxxfxxxxxxxxfxRxkf(xk)一阶均差二阶均差三阶均差四阶均差0.400.550.650.800.900.410750.578150.696750.888111.026521.11601.18601.27571.38410.28000.35880.43360.19700.21370.0344例1已知f(x)=shx的数表,求二次牛顿插值多项式,并由此计算f(0.596)的近似值。)55.0)(40.0(2800.0)40.0(1160.141075.0)(2xxxxN解由上表可得过前三点的二次牛顿插值多项式为632010.0)596.0()596.0(2Nf注：过前四点的三次牛顿插值多项式)65.0)(55.0)(40.0(1970.0)()(23xxxxNxN故6319145.0)596.0()596.0(3Nf故)55.0)(40.0(2800.0)40.0(1160.141075.0)(2xxxxN)80.0)(65.0)(55.0)(40.0(0344.0)(3xxxxxR可得N3(x)的截断误差631034.0)596.0(R0344.0],,[40xxf设函数y=f(x)在等距节点xi=x0+ih(i=0,1,…,n)上的函数值为fi=f(xi)(h为步长)定义2fi=fi+1-fi和fi=fi-fi-1分别称为函数f(x)在点xi处的一阶向前差分和一阶向后差分。一般地,f(x)在点xi处的m阶向前差分和m阶向后差分分别为mfi=m-1fi+1-m-1fi和mfi=m-1fi-m-1fi-1*4.3.3差分与等距节点插值4.3.3.1差分及其性质差分有如下基本性质性质1各阶差分均可用函数值表示.即jinjnnjjinnninnininfcfcfcff011)1()1(jijnnjjninnniniinfcfcfcff011)1()1(且有等式nfi=nfi+n.性质3均差与差分的关系式为111[,,,]!1[,,,]!miiimimmimimiimfxxxfmhfxxxfmh性质2函数值均可用各阶差分表示.即injjjninnniniinfcfcfcff01且有差分与微商的关系式为),()()(nkknnnnxxfhf代入牛顿插值公式,可得)1()1(!)1(!2)()(002000ntttnfttftffthxNxNnnn称为牛顿向前插值公式，其余项为),()()!1()()1()()(0)1(10nnnnnxxfhnntttthxRxR插值节点为xi=x0+ih(i=0,1,…,n),如果要计算x0附近点x处的函数值f(x),可令x=x0+th(0tn)4.3.3.2等距节点差值公式类似地,若计算xn附近的函数值f(x),可令x=xn+th(-nt0)，可得牛顿向后插值公式)1()1(!)1(!2)()(2ntttnfttftffthxNxNnnnnnnnn),(,)()!1()()1()()(0)1(1nnnnnnxxfhnntttthxRxR及其余项例2设y=f(x)=ex,xi=1,1.5,2,2.5,3,用三次插值多项式求f(1.2)及f(2.8)的近似值.解相应的函数值及差分表如下:xif(xi)一阶差分二阶差分三阶差分四阶差分11.522.532.718284.481697.2890612.1824920.085541.763412.903474.793437.903051.143961.886063.109620.742101.223560.48146求f(1.2)用牛顿前插公式,且由1.2=1+0.5t,得t=0.431.14396(1.2)(1.2)2.718281.763410.40.4(0.41)2!0.742100.4(0.41)(0.42)3.33386323!fNxif(xi)一阶差分二阶差分三阶差分四阶差分11.522.532.718284.481697.2890612.1824920.085541.763412.903474.793437.903051.143961.886063.109620.742101.223560.48146求f(2.8)用牛顿后插公式,且由2.8=3+0.5t,得t=-0.43(2.8)(2.8)fNxif(xi)一阶差分二阶差分三阶差分四阶差分11.522.532.718284.481697.2890612.1824920.085541.763412.903474.793437.903051.143961.886063.109620.742101.223560.481463.1096220.085547.90305(0.4)(0.4)(0.41)2!1.22356(0.4)(0.41)(0.42)15.76808723!