第3节 差商及Newton插值多项式

§3差商及Newton插值多项式一、差商及其性质Lagrange插值多项式的优点是格式整齐规范，但其缺点是：当需要增加节点时，其基函数都要发生变化，需要重新计算，这在实际计算中会影响效率。下面介绍的Newton插值法会弥补这一不足。1.差商的定义设y=f(x)在n+1个互异点x0,x1,…,xn处的函数值为：)(,),(),(10nxfxfxf则称jijijixxxfxfxxf)()(],[为f(x)关于点xi,xj的一阶差商。称kikjjikjixxxxfxxfxxxf],[],[],,[为f(x)关于点xi,xj,xk的二阶差商。一般地，称k-1阶差商的一阶差商kkkkkxxxxxfxxxfxxxxf021110110],,,[],,,[],,,,[为f(x)关于点的k阶差商。kxxx,,,10例如，已知f(x)在5.0,3.0,1.0210xxx的函数值为：4)(,2.3)(,2)(210xfxfxf可以求得62.02.13.01.02.32],[10xxf42.08.05.03.042.3],[21xxf54.025.01.046],[],[],,[202110210xxxxfxxfxxxf2.差商的性质],,,,[110kkxxxxf性质1：k阶差商)(,),(),(10kxfxfxf是由函数值的线性组合而成，即kjjkjkkxxfxxxxf01110)()(],,,,[)())(()(101kkxxxxxxx其中以k=2进行证明。由101010)()(],[xxxfxfxxf212121)()(],[xxxfxfxxf得到202110210],[],[],,[xxxxfxxfxxxf))(()())(()())(()(120222101120100xxxxxfxxxxxfxxxxxf))()(()(2103xxxxxxx由得到))(())(())(()(1020213xxxxxxxxxxxxx))(()(201003xxxxx311012()()()xxxxx))(()(120223xxxxx从而],,[210xxxf))(()())(()())(()(120222101120100xxxxxfxxxxxfxxxxxf203)()(jjjxxf)()()()()()(232131030xxfxxfxxf由性质1立刻可得。性质2:差商具有对称性,即k阶差商f[x0,x1,…,xk-1,xk]中，任意调换xi,xj的次序，其值不变。kjjkjkkxxfxxxxf01110)()(],,,,[再由数学归纳法可证得：00000)()()()(],[xxxpxpxxxfxfxxfnn性质3：若f(x)为n次多项式，则f[x,x0]为关于x的n-1次多项式。证明：已知故)()()()()(],[100000xqxxxpxpxxxfxfxxfnnn类似的可以得到：)(],,[210xqxxxfn也就是说，对多项式求一次差商，次数降低一次。)()()()(100xqxxxpxpnnn由于是的根，所以0x0()()0nnpxpx3.差商的计算为构造Newton插值多项式方便起见，计算差商时，采用列表的方式进行。0x1x2x3x0y1y2y3y],[10xxf],[21xxf],[32xxfixiy],[1iixxf],,[21iiixxxf],,,[321iiiixxxxf],,[210xxxf],,[321xxxf],,,[3210xxxxf例2.2已知函数y=f(x)的如下离散数据(1,0)、(2,2)、(4,12)、(5,20)、(6,70)，试求其各阶差商.解：列差商表计算xy一阶差商二阶差商三阶差商四阶差商1022412520670258501121051二、Newton插值多项式对于区间[a,b]内的离散点及相应的函数值，计算如下差商：nxxxx,,,,10)(,),(),(),(10nxfxfxfxf000)()(],[xxxfxfxxf110010],[],[],,[xxxxfxxfxxxf221010210],,[],,[],,,[xxxxxfxxxfxxxxfnnnnxxxxxfxxxfxxxxf],,,[],,,[],,,,[101010可以求得：000)()(],[xxxfxfxxf],[)()()(000xxfxxxfxf110010],[],[],,[xxxxfxxfxxxf],,[)(],[],[101100xxxfxxxxfxxf221010210],,[],,[],,,[xxxxxfxxxfxxxxf],,,[)(],,[],,[210221010xxxxfxxxxxfxxxf00010101()()()[,]()()[,,]fxfxxxfxxxxxxfxxx000101012012012()()()[,]()()[,,]()()()[,,,]fxfxxxfxxxxxxfxxxxxxxxxfxxxx依次类推得到：],,,,[)())((],,,[)())((],,[))((],[)()()(101010110210101000nnnnxxxxfxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxf令：],,,[)())((],,[))((],[)()()(10110210101000nnnxxxfxxxxxxxxxfxxxxxxfxxxfxN],,,,[)())(()(1010nnnxxxxfxxxxxxxR()()()nnfxNxRx则可以将函数f(x)表示成：由如上构造，容易验证nixfxNiin,,1,0),()(因此Nn(x)满足插值条件，是一个n次插值多项式。并称],,,[)())((],,[))((],[)()()(10110210101000nnnxxxfxxxxxxxxxfxxxxxxfxxxfxN为n次Newton插值多项式。如果f(x)≈Nn(x),则误差为：],,,,[)())(()(1010nnnxxxxfxxxxxxxR☆关于Newton插值多项式，有以下几个特点：1Newton插值多项式与同次Lagrange插值多项式相同，因而误差相同因为Newton插值多项式与Lagrange插值多项式满足相同的插值条件，由插值多项式的存在唯一性知因此，Newton插值多项式与Lagrange插值多项式的误差相同。这样，由],,,,[)())(()(1010nnnxxxxfxxxxxxxRNn(x)=Ln(x))())(()!1()()(10)1(nnnxxxxxxnfxR得到)!1()(],,,,[)1(10nfxxxxfnn这个表达式给出了n+1阶差商与n+1阶导数之间的关系式。例3已知，试求其如下差商1)(5xxxf]2,2,2,2,2,2[543210f]2,2,2,2,2,2,2[6543210f解：由差商与导数的关系式)!1()(],,,,[)1(10nfxxxxfnn得到!5)(]2,2,2,2,2,2[)5(543210ff1!5!5!6)(]2,2,2,2,2,2,2[)6(6543210ff0练习：32(),[0,1,]1,[1,2,]?pxxqxrxsptpt若那么[0,1,][1,,2]()3![0,1,,2]1023!3!ptptppt提示：2.Newton插值多项式具有递推式],,,[)())((],,[))((],[)()()(10110210101000nnnxxxfxxxxxxxxxfxxxxxxfxxxfxN由],,,,[)())(()()(110101nnnnnxxxxfxxxxxxxNxN可知],[)()()(10001xxfxxxfxN],,[))((],[)()()(2101010002xxxfxxxxxxfxxxfxN],,[))(()(210101xxxfxxxxxN所以，具有递推公式：],,,,[)())(()()(110101nnnnnxxxxfxxxxxxxNxN所以，具有递推公式：由此可知：当求出n次插值多项式后，再增加一个节点时，只需要增加一项的计算即可。由Newton插值多项式的结构可以看出，在构造Newton插值多项式时，必须首先计算各阶差商。3.Newton插值多项式的计算例4已知f(x)的五组数据(1,0)、(2,2)、(3,12)、(4,42)、(5,116),求N4(x)。如果再增加一个节点(6,282),求出N5(x)，并计算N4(1.5)、N5(1.5).解：先由前五组数据列差商表10223124425116210307441022240.5得到：)4)(3)(2)(1(5.0)3)(2)(1(2)2)(1(4)1(20)(4xxxxxxxxxxxN28125.0329)5.1()5.1(4Nf如果，再增加一点(6,282),就在上表中增加一行计算差商。628216646810.1)5)(4)(3)(2)(1(1.0)()(45xxxxxxNxN由Newton公式的递推式得到：)5.1()5.1(5Nf得到：)55.1)(45.1)(35.1)(25.1)(15.1(1.0)5.1(4N328125.028125.0609375.0练习题：已知离散数据(1,0)、(2,2)、(4，12）、(5,20)求三次Newton插值多项式，增加一点(6,70)后，再求出四次Newton插值多项式。本节(§3)要点1.掌握差商及其性质，导数与差商的关系2.掌握Newton插值多项式的构造方法及具体结构3.掌握Newton插值多项式的误差结果4.编写Newton插值多项式计算程序进行实际计算思考题：如何实现差商表和Newton插值多项式的程序设计。作业：2-4；2-5；2-7关于离散数据：构造了lagrange插值多项式：),(),()!1()()(1)1(baxnfxRnnnnjjijinjiinyxxxxxL00)(Newton插值多项式：],,,[)())((],,[))((],[)()()(10110210101000nnnxxxfxxxxxxxxxfxxxxxxfxxxfxN根据问题需要，有时还需要构造分段插值多项式，下面加以介绍ixiy0x1x0y1ynxny