第四章插值与拟合

1、插值法n插值法是一种古老的数学方法，早在一千多年前的隋唐时期定制历法时就广泛应用了二次插值。刘焯将等距节点的二次插值应用于天文计算。n插值理论却是在17世纪微积分产生后才逐步发展起来的，Newton插值公式理论是当时的重要成果。n由于计算机的使用以及航空、造船、精密仪器的加工，插值法在理论和实践上都得到进一步发展，获得了广泛的应用。4.1 引言引言 问题的提出问题的提出函数解析式未知函数解析式未知,通过实验观测得到的一组数据通过实验观测得到的一组数据, 即在即在某个区间某个区间a, b上给出一系列点的函数值上给出一系列点的函数值 yi= f(xi)或者给出函数表或者给出函数表y=f(x)y=p

2、(x)xx0 x1x2xnyy0y1y2yn插值法的基本原理插值法的基本原理设函数设函数 y=f(x) 定义在区间定义在区间 a, b 上上, , 是是 a, b 上取定的上取定的n+1个互异节点个互异节点, ,且在这些点处的函数值且在这些点处的函数值 为已知为已知 , ,即即 若存在一个若存在一个f(x)的近似函数的近似函数 , ,满足满足则称则称 为为f( (x) )的一个的一个插值函数插值函数, f( (x) )为为被插函数被插函数, 点点xi为为插值节点插值节点, 称称( (4.1)4.1)式为式为插值条件插值条件, 而误差函数而误差函数R(x)= 称为称为插值余项插值余项, 区间区间

3、 a, b 称为称为插值插值区间区间, 插值点在插值区间内的称为插值点在插值区间内的称为内插内插, 否则称否则称外插外插 nxxx,10)(,),(),(10nxfxfxf)(iixfy )(x), 2 , 1()()(nixfxii)(x( (4.1)4.1)()(xxf插值函数插值函数 在在n+1 个互异插值节点个互异插值节点 ( (i=0,1,n )处与处与 相等相等, ,在其它点在其它点x就用就用 的值作为的值作为f( (x) ) 的近似值。这一过程称为的近似值。这一过程称为插值插值，点，点x称为插值点。称为插值点。换句话说换句话说, , 插值就是根据被插函数给出的函数表插值就是根据被

4、插函数给出的函数表“插出插出”所要点的函数值。用所要点的函数值。用 的值作为的值作为f( (x) )的近似值的近似值, ,不仅不仅希希望望 能较好地逼近能较好地逼近 f( (x) ), ,而且还希望它计算简单而且还希望它计算简单 。由于代数多项式具有数值计算和理论分析方便的优点。由于代数多项式具有数值计算和理论分析方便的优点。所以本章主要介绍代数插值。即求一个次数不超过所以本章主要介绍代数插值。即求一个次数不超过n n次的次的多项式。多项式。 )(xix)(ixf)(x)(x)(x0111)(axaxaxaxPnnnn0111)(axaxaxaxPnnnn满足满足 ), 2 , 1 , 0()

5、()(nixfxPii则称则称P(x)P(x)为为f(x)f(x)的的n n次插值多项式。这种插值法通常称次插值多项式。这种插值法通常称为代数插值法。其几何意义如下图所示为代数插值法。其几何意义如下图所示 y y=P(x) y=f(x) y1 yn x0 x1 xn x 定理定理1 n1 n次代数插值问题的解是存在且惟一的次代数插值问题的解是存在且惟一的 证明证明: : 设设n n次多项式次多项式 0111)(axaxaxaxPnnnn是函数是函数 在区间在区间 a, ba, b上的上的n+1n+1个互异的节点个互异的节点 ( (i=0,1,2,n )i=0,1,2,n )上的插值多项式上的插

6、值多项式, ,则求插值多项式则求插值多项式P(x)P(x)的问题就归结为求它的系数的问题就归结为求它的系数 ( (i=0,1,2,n )i=0,1,2,n )。 )(xfy ixia由插值条件由插值条件: (: (i=0,1,2,n),i=0,1,2,n),可得可得 )()(iixfxp)()()(01111011111100011010nnnnnnnnnnnnnnnnxfaxaxaxaxfaxaxaxaxfaxaxaxa 这是一个关于待定参数这是一个关于待定参数 的的n+1阶线性方阶线性方程组程组, ,其系数矩阵行列式为其系数矩阵行列式为 naaa,10niijjinnnnnnxxxxxxx

7、xxxxV110212110200)(111为为VandermondeVandermonde（范德蒙）行列式，因范德蒙）行列式，因x xi ixxj j（当当ijij），），故故V0V0。根据解线性方程组的克莱姆根据解线性方程组的克莱姆（GramerGramer）法则，方程组的解法则，方程组的解 存在惟一，从而存在惟一，从而P(x)P(x)被惟一确定。被惟一确定。 naaa,10惟一性说明，不论用何种方法来构造，也不论用何种惟一性说明，不论用何种方法来构造，也不论用何种形式来表示插值多项式形式来表示插值多项式, ,只要满足插值条件只要满足插值条件( (4.1)4.1)其结其结果都是相互恒等的。

8、果都是相互恒等的。 4.2 拉格朗日（拉格朗日（Lagrange）插值插值 为了构造满足插值条件为了构造满足插值条件 (i=0,1,2,n )的便于使用的插值多项式的便于使用的插值多项式 L(x),先考察几种简单情形先考察几种简单情形,然后再推广到一般形式。（然后再推广到一般形式。（ 线性插值与抛物插值）线性插值与抛物插值）（1）线性插值）线性插值线性插值是代数插值的最简单形式。假设给定了函数线性插值是代数插值的最简单形式。假设给定了函数f(x)在两个互异的点的值，在两个互异的点的值，现要求用线性函数现要求用线性函数 近似地代替近似地代替 f(x)。选选择参数择参数a和和b, 使使 。称这样的

9、线性函。称这样的线性函数数L1(x) 为为 f(x) 的线性插值函数的线性插值函数 。( )( )iiL xf x0 x1x)(),(1100 xfyxfy1( )L xax b1( )( )(0,1)iiL xf xi线性插值的几何意义线性插值的几何意义: :用用通过点通过点 和和 的直线近似地代替曲线的直线近似地代替曲线 y=f(x)y=f(x)由解析几何知道由解析几何知道, ,这条直线用点斜式表示为这条直线用点斜式表示为 )(,(00 xfxA)(,(11xfxB1010010( )()yyL xyxxxx011010110( )xxxxL xyyxxxx01011010)(,)(xxx

10、xxlxxxxxl0)(, 1)(1000 xlxl1)(,0)(1101xlxl1)()(10 xlxl为了便于推广，记为了便于推广，记 这是一次函这是一次函数数, ,且有性质且有性质 y=f(x) L1(x)=ax+b A(x.0,f(x.0) B(x.1,f(x.1) )(0)(1)(kikixlkiik 与与 称为线性插值基函数。且有称为线性插值基函数。且有 )(0 xl)(1xl1 , 0,)(10kxxxxxlkjjjkjk于是线性插值函数可以表示为与基函数的线性组合于是线性插值函数可以表示为与基函数的线性组合 10011( )( )( )L xl x yl x y例例4.1 已知

11、已知 求求 10100 11121 115y解解: 这里这里x0=100，y0=10，x1=121，y1=11, 利用线性插值利用线性插值 1121100( )1011100121121100 xxL x1115(115)10.714yL（2）抛物插值）抛物插值 抛物插值又称二次插值，它也是常用的代数插值之一。抛物插值又称二次插值，它也是常用的代数插值之一。设已知设已知f(x)在三个互异点在三个互异点x0，x1，x2的函数值的函数值y0，y1，y2，要构造次数不超过二次的多项式要构造次数不超过二次的多项式使满足二次插值条件：使满足二次插值条件：这就是二次插值问题。其几何意义是用经过这就是二次插

12、值问题。其几何意义是用经过3个点个点 的抛物线的抛物线 近似代替曲线近似代替曲线 , 如下图所示。因此也称之为抛物插值。如下图所示。因此也称之为抛物插值。 22210( )Lxa xa xa2( )(0,1,2)iiL xyi),(),(),(221100yxyxyx2( )yL x)(xfy y y=L2(x) y0 y1 y1 y=f(x) O x0 x1 x2 x L L2 2(x)(x)的参数的参数直接由插值条件决定，直接由插值条件决定，即即 满足下面满足下面的代数方程组：的代数方程组： 210,aaa210,aaa222221012121100202010yxaxaayxaxaayx

13、axaa222211200111xxxxxx该三元一该三元一次方程组次方程组的系数矩阵的系数矩阵 的行列式是范德蒙行列式，当的行列式是范德蒙行列式，当 时，时，方程组的解唯一。方程组的解唯一。 210 xxx为了与下一节的为了与下一节的LagrangeLagrange插值公式比较插值公式比较, ,仿线性插值仿线性插值, ,用用基函数的方法求解方程组。先考察一个特殊的二次插值基函数的方法求解方程组。先考察一个特殊的二次插值问题：问题： 求二次式求二次式 , ,使其满足条件：使其满足条件： )(0 xl0)(,0)(, 1)(201000 xlxlxl这个问题容易求解。由上式的后两个条件知这个问题

14、容易求解。由上式的后两个条件知: : 是是 的两个零点。于是的两个零点。于是 21,xx)(0 xl)()(210 xxxxcxl再由另一条件再由另一条件 确定系数确定系数 1)(00 xl)(12010 xxxxc)()()(2010210 xxxxxxxxxl从而导出从而导出 类似地可以构造出满足条件：类似地可以构造出满足条件：的插值多项式的插值多项式 0)(, 0)(, 1)(210111xlxlxl)()()(2101201xxxxxxxxxl及满足条件：及满足条件： 的插值多项式的插值多项式 0)(,0)(, 1)(120222xlxlxl)()()(1202102xxxxxxxxx

15、l这样构造出来的这样构造出来的 称为抛物插值的基函数称为抛物插值的基函数 )(),(),(210 xlxlxl取已知数据取已知数据 作为线性组合系数作为线性组合系数, ,将基函数将基函数 线性组合可得线性组合可得 210,yyy)(),(),(210 xlxlxl0201122012010210122021()()()()()()( )()()()()()()x xx xx xx xx xx xL xyyyxxxxxxxxxxxx容易看出容易看出, ,P(x)P(x)满足条件满足条件 2()(0,1,2)iiLxyi4.2.1 拉格朗日插值多项式拉格朗日插值多项式 两个插值点可求出一次插值多项

16、式两个插值点可求出一次插值多项式, ,而三个插值点可而三个插值点可求出二次插值多项式。插值点增加到求出二次插值多项式。插值点增加到n+1n+1个时个时, ,也就是通也就是通过过n+1n+1个不同的已知点个不同的已知点 , ,来构造一个次数来构造一个次数为为n n的代数多项式的代数多项式L Ln n(x)(x)。与推导抛物插值的基函数类似与推导抛物插值的基函数类似, ,先构造一个特殊先构造一个特殊n n次多项式次多项式 的插值问题的插值问题, ,使其在各节点使其在各节点 上满足上满足 ), 1 , 0)(,(niyxii)(xliix0)(, 0)(, 1)(, 0)(, 0)(110nkkkk

17、kkkkxlxlxlxlxl)(0)(1)(kikixlkiik即即 由条件由条件 ( ) ( )知知, , 都是都是n n次次 的零点的零点, ,故可设故可设 0)(ikxlki nkkxxxxx,1110)(xlk)()()()(110niiixxxxxxxxAxl 设设.为为待待定定常常数数其其中中 A可可得得由由1)( iixl)()()(1110niiiiiixxxxxxxxA 0110110()()()()( )()()()()()(0,1,)(*)()iiniiiiiiinnjjijjixxxxxxxxlxxxxxxxxxxxinxx所以称之为称之为Lagrange插值基函数插值

18、基函数.利用拉格朗日基函数利用拉格朗日基函数,可以构造多项式可以构造多项式0 01 10( )( )( )( )( ) (4.2)nnn ni iiLxy lxy lxy lxy lx( ),(),.( )Lagrange.nniinLxnLxyLx为次数不超过 的多项式 且满足插值条件故其为拉格朗日问题的解 称为插值多项式插值多项式为：插值多项式为：线性插值多项式：线性插值多项式：n=1010110101xxxxyxxxxyxL)(),(,)(101iyxLii满满足足y=f (x)xyx0 x1y=L1(x).),(),()(的的直直线线为为过过点点11001yxyxxLy 几何意义：几何

19、意义：抛物插值多项式：抛物插值多项式：n=2插值多项式为：插值多项式为：)()()()()()()(1202102210120120102102xxxxxxxxyxxxxxxxxyxxxxxxxxyxL),(,)(2102iyxLii满满足足xyy=L2 (x)x0y=f(x)x1x2.),(),(),()(的的一一条条抛抛物物线线和和为为过过点点2211002yxyxyxxLy 几何意义：几何意义：101 ( )()()() (4.3)nnxxxxxxx引入记号)()()()( 1101nkkkkkkknxxxxxxxxx 则则得得101( ) ( ) (4.4)()()nnnkkknkxL

20、xyxxx于是例例4.2处处的的近近似似值值。在在公公式式求求，利利用用插插值值，的的值值分分别别为为：，在在设设2007408180778801086070809048370300250150100. . . . ,. ,. .)(xxexexf解解： )()()()()()()()()()()()()()()()()(23130321033212023102312101320130201032103xxxxxxxxxxxxyxxxxxxxxxxxxyxxxxxxxxxxxxyxxxxxxxxxxxxyxL代代入入分分别别将将 .,.,.,.,. 3002501501002003210 xx

21、xxx81873002003.).( L可可得得. . .52001081873080相相比比，误误差差与与准准确确结结果果e定理定理4.14.1nnnxaxaxaaxP2210)(niyxPiin,2 ,1 ,0)(),(jixxji若插值节点则满足插值条件则满足插值条件的插值多项式的插值多项式存在且唯一存在且唯一.反证：若不唯一，则除了反证：若不唯一，则除了Pn(x) 外还有另一外还有另一 n 阶多项式阶多项式 Ln(x) 满足满足 Ln(xi) = yi 。考察考察 则则 Qn 的阶数的阶数, )()()(xLxPxQnnn n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注

22、：注：若不将多项式次数限制若不将多项式次数限制为为 n ，则插值多项式，则插值多项式不唯一不唯一。例如例如 也是一个插值多项也是一个插值多项式，其中式，其中 可以是任意多项式。可以是任意多项式。 niinxxxpxLxP0)()()()()(xp例例4.3 4.3 已知已知y=f(x)y=f(x)的函数表的函数表 求线性插值多项式求线性插值多项式, , 并计算并计算x=1.5 x=1.5 的值的值X 1 3 y 1 225.1)5.1()5.1()1(2121311313)(10100101pfxxxyxxxxyxxxxxp解解: : 由线性插值多项式公式得由线性插值多项式公式得例例4.4 4

23、.4 已知已知x=1, 4, 9 x=1, 4, 9 的平方根值的平方根值, , 用抛物插值用抛物插值公式公式, , 求求 (x0 x1)(x0 x2)(xx1)(xx2)y0+(x1x0)(x1x2)(xx0)(xx2)y1+(x2x0)(x2x1)(xx0)(xx1)y2L2(7) =x0=1, x1=4, x2=9y0=1, y1=2, y2=3 (14)(19)(74)(79)* 1 +(41)(49)(71)(79)* 2+(91)(94)(71)(74)* 3= 2.7L2(x) =7解解:例例4.5 求过点求过点(0,1)、(1,2)、(2,3)的三点插值多项式的三点插值多项式1

24、3) 12)(02 () 1)(0(2) 21)(01 () 2)(0(1) 20)(10 () 2)(1()(xxxxxxxxp解解:由由Lagrange 插值公式插值公式（给定的三个点在一条直线上）（给定的三个点在一条直线上）212021012101200201021)()()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxP例例4.6 已知已知f (x)的观测数据的观测数据 x 0 1 2 4 f (x) 1 9 23 3 构造构造Lagrange插值多项式插值多项式解解 四个点可构造三次四个点可构造三次Lagrange插值多项式插值多项式: :基函数为基函数为

25、 1478781)40)(20)(10()4)(2)(1()(230 xxxxxxxlxxxxxxxl38231)41)(21)(01 ()4)(2)(0()(231xxxxxxxl2324541)42)(12)(02()4)(1)(0()(xxxxxxxl12181241)24)(14)(04()2)(1)(0()(233Lagrange插值多项式为插值多项式为 )()(303xlyxLkkk)(3)(23)(9)(3210 xlxlxlxl12144541123xxx为便于上机计算为便于上机计算, ,常将拉格朗日插值多项式常将拉格朗日插值多项式( (4.2)改写成改写成 nknkiiiki

26、knxxxxyxL00)(Lagrange插值法的流程图插值法的流程图x0 x1 xixi+1 xn-1 xny=f(x)y=Ln(x)ab在插值区间在插值区间 a, b 上用上用插值多项式插值多项式Ln(x)近似代替近似代替f(x), 除了除了在插值节点在插值节点xi上没有误差外，在其它点上一般是存在误上没有误差外，在其它点上一般是存在误差的。差的。若记若记 R (x) = f(x) - Ln(x) 则则 R(x) 就是用就是用 Ln(x) 近似代替近似代替 f(x) 时的截断误差时的截断误差, 或称或称插值余项我们可根据后面的定理来估计它的大小。插值余项我们可根据后面的定理来估计它的大小。

27、4.2.2 插值多项式的误差插值多项式的误差 定理定理4.2 设设f(x)在在 a, b 有有n+1阶导数，阶导数， x0, x1, xn 为为 a, b 上上n+1个互异的节点个互异的节点, Ln(x)为满足为满足 Ln(xi) = f(xi) (i=1,2, , n) 的的n 次插值多项式，那么对于任何次插值多项式，那么对于任何x a, b 有有 插值余项插值余项其中其中a b 且依赖于且依赖于x1010( )()()()(),nnniixx xx xx xx xa b(1)1( )( )( )( )( )(1)!nnnnfR xf xL xxn 插值余项插值余项 /* Remainder

28、 */设节点设节点)1( nf在在a , b内存在内存在, 考察截断误差考察截断误差)()()(xLxfxRnn ,baCfn bxxxan 10，且，且 f 满足条件满足条件 , Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。)(x 0)()(10 xx ),(10 xx 0)( 推广：推广：若若0)()()(210 xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(0 nxx 存在存在),(ba 使得使得0)()( nRn(x) 至少有至少有 个根个根n+1 niinxxxKxR0)()()

29、(任意固定任意固定 x xi (i = 0, , n), 考察考察 niixtxKtRnt0)()()()( (t)有有 n+2 个不同的根个不同的根 x0 xn x),(,0)()1(baxxn !)1()()()1(nxKRxnn 注意这里是对注意这里是对 t 求导求导 !)1)()()()1()1(nxKLfxnnxn !)1()()()1( nfxKxn niixnnxxnfxR0)1()(!)1()()( 注：注： 若记若记 ，则插值余项为，则插值余项为 当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可可知知 ，即插值多项式对于次数，即插值多项式对于次数

30、 n 的的多项式是多项式是精精确确的。的。(若是代数插值若是代数插值,其插值函数就是其插值函数就是f(x) )0)()1( xfn0)( xRn定义定义：00min,max.iii ni nxx 称插值节点所界定的范围为基本插值区间当点当点x位于基本插值区间内时位于基本插值区间内时,插值过程称为插值过程称为内插内插,否则称为否则称为外推外推.1)1()( nnMxf)()!(xnMnn111 通常不能确定通常不能确定 , 而是估计而是估计 , x (a,b) 于是将于是将 作为误差估计上限。作为误差估计上限。 niinxxx01)()( . )()!()()()(xnfxRnnn111 外推比

31、内插效果差。外推比内插效果差。 对于线性插值，其误差为对于线性插值，其误差为对于抛物插值（二次插值），其误差为对于抛物插值（二次插值），其误差为011( )( )( )( )()(),2R xf xP xfx xx xa bbaxxxxxxfxPxfxR,)( )()(61)()()(210 (1)11n 1max |( )|, |( )|( )|, (1)!nna x bnnfxMMR xxn 若则例例4.7 已知已知 =100, =121, 用线性插值估计用线性插值估计 在在x=115时的时的截断误差截断误差xxf)(0 x1x解解: 由插值余项公式知由插值余项公式知 )()(21)(1x

32、fxR 2341)( xxf)(81)(10231xxxxxR因为因为 )121115)(100115(81)115(231R23121,100max)121115)(100115(81)121115)(100115(1081301125. 010615813例例4.8 已知已知x0=100, x1=121, x2=144,当用抛物插值求当用抛物插值求 在在x=115时的近似值，估计其的截断误差时的近似值，估计其的截断误差 ( )f xx解解0201122012010210122021()()()()()()( )()()()()()()115(115) 10.772756x x x xx x

33、 x xx x x xp xyyyxx xxxx xxxx xxp=0017. 010)144115)(121115)(100115(161)115()144)(121)(100(161)()()()(61)(52252210) 3(2RxxxxxRxxxxxxfxR2583)( xxf例例4.9 设设f(x)=x4, 用余项定理写出节点用余项定理写出节点 -1, 0, 1, 2的三次插值多项式的三次插值多项式 解解: 根据余项定理根据余项定理(4)0123432( )( )( )()()()()4!( )( 1 )( 1 )( 2)( ) 22ff x pxx x x x x x x xx

34、px xxxxpxx xx 例4.10 已知 sin0.32=0.314567，sin0.34=0.333487，sin0.36=0.352274，分别用一、二次Lagrange插值计算 sin0.3367的值，并估计截断误差。（1）解3403203403203203403203401.sin.sin.)( xxxL3403203403203367032034032034033670336701.sin.sin.).( L3303650. 得).)(.(sin)(34032021 xxxR 510920 .)()!()()()()()(xnfxLxfxRnnnn111 由于是|.|.|sin|

35、 ).(|34033670320336702336701 R3400000918920003300167023334870. （2）3603403603403403603403601.sin.sin.)( xxxL3603403603403367034036034036033670336701.sin.sin.).( L3303870. 得).)(.(sin)(36034021 xxxR )()!()()()()()(xnfxLxfxRnnnn111 由于是|.|.|sin| ).(|36033670340336702336701 R700001354310023300033023522740

36、. 700001354310023300033023522740. 510351 .由此可知 稍好于 ).(336701L).(336701L（3）3603403603203603403203403603403203403603203203603203403203603402.sin).)(.().)(.(.sin).)(.().)(.(.sin).)(.().)(.()( xxxxxxxL3303740336702.).( L因为).)(.)(.(!)()()(360340320332 xxxfxR )(xL1)(xL1则|.|.|.|!|cos| ).(|3603403203336702

37、xxxR 0233000330016703320.!.cos 7101780 .oxyxsin)(xL2例例4.11：已知：已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用21646214641/)( xxxL这里这里),(,sin)(,sin)()(462 fxxf而而)(!)()(,sin)(462222121 xxfxR00762.

38、0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 的实际误差的实际误差 0.01010.01013,421 xx利用利用00660.018500538.01 R内插内插 的实际误差的实际误差 0.005960.00596内插通常优于外推。选择要内插通常优于外推。选择要计算的计算的 x 所在的区间的端点，所在的区间的端点，插值效果较好。插值效果较好。sin 50 = 0.76008, )(1851 Ln = 22321214363463464363646342)()()()()()()( xxxxxxxL)185(50sin

39、20 L0.76543232134632 cos;)()(!cos)(xxxxR00077.018500044.02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越高但绝对不是次数越高就越好，嘿嘿就越好，嘿嘿4.3 均差与均差与牛顿插值多项式牛顿插值多项式 拉格朗日插值多项式拉格朗日插值多项式结构对称结构对称，使用方便。，使用方便。但由于是用基函数构成的插值，这样要但由于是用基函数构成的插值，这样要增加一个增加一个节点节点时，所有的基函数必须全部时，所有的基函数必须全部重新计

40、算重新计算，不具，不具备备承袭性承袭性，还造成计算量的浪费。这就启发我们，还造成计算量的浪费。这就启发我们去构造一种具有去构造一种具有承袭性承袭性的插值多项式来克服这个的插值多项式来克服这个缺点缺点，也就是说，每增加一个节点时，只需增加，也就是说，每增加一个节点时，只需增加相应的一项即可。这就是相应的一项即可。这就是牛顿插值多项式牛顿插值多项式。 由线性代数知由线性代数知,任何一个不高于任何一个不高于n次的多项式次的多项式, 都可以都可以表示成函数表示成函数)()( ,),)( , 1110100nxxxxxxxxxxxx的线性组合的线性组合, 也就是说也就是说, 可以把满足插值条件可以把满足

41、插值条件p(xi)=yi (i=0,1,n)的的n次插值多项式次插值多项式, 写成如下形式写成如下形式)()()()(110102010nnxxxxxxaxxxxaxxaa其中其中ak (k=0,1,2,n)为待定系数为待定系数,这种形式的插值多项这种形式的插值多项式称为式称为Newton插值多项式。我们把它记为插值多项式。我们把它记为Nn(x)即即)()()()()(110102010nnnxxxxxxaxxxxaxxaaxN（4.5） 可见，牛顿插值多项式可见，牛顿插值多项式Nn(x)是是插值多项式插值多项式Pn(x)的另一种表示形式的另一种表示形式, 与与Lagrange多项式多项式相比

42、它不仅克相比它不仅克服了服了“增加一个节点时整个计算工作重新开始增加一个节点时整个计算工作重新开始”的缺的缺点点, 且可以节省乘除法运算次数且可以节省乘除法运算次数, 同时在同时在Newton插值多插值多项式中用到差分与差商等概念，又与数值计算的其他项式中用到差分与差商等概念，又与数值计算的其他方面有密切的关系方面有密切的关系.它满足它满足其中其中ak (k=0,1,2,n)为待定系数，形如（为待定系数，形如（4.5）的）的插值多项式称为插值多项式称为牛顿牛顿(Newton)插值多项式插值多项式。 )()()()(1101nnnnxxxxxxaxNxN1 1、差商的定义、差商的定义称000 x

43、xxfxfxxfkkk )()(,为 关于点 的一阶差商一阶差商。)(xfkxx ,0称110010 xxxxfxxfxxxfkkk ,为 关于点 的二阶差商二阶差商。)(xfkxxx,104.3.1 差商及其性质差商及其性质一般，称111021010 kkkkkkxxxxxfxxxxfxxxf,为 于点 的 k 阶差商阶差商。)(xfkxxx,102 2、差商的计算、差商的计算010110 xxxfxfxxf )()(,232332xxxfxfxxf )()(,021021210 xxxxfxxfxxxf ,243243432xxxxfxxfxxxf ,143214324321xxxxxfx

44、xxfxxxxf ,043210432143210 xxxxxxfxxxxfxxxxxf ,xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+2 ,xi+200283275125621640208 1923827 493527125 9156125216 503419 10251949 14364991 105510 1261014 例例4.12 求求 f(xi)= x3在节点在节点 x=0, 2, 3, 5, 6上的各阶差商值上的各阶差商值解解: 计算得如下表计算得如下表nknkkkkkkkknkiiikknkkknxxxxxxxxxxxfxxxxxfxxxf011

45、100010)()()()()()()()(,其中这个性质可用数学归纳法证明（用这个性质可用数学归纳法证明（用Lagrange插值插值多项式比较最高项系数来得到）多项式比较最高项系数来得到）性质性质1 函数函数 f(x) 的的 n 阶差商阶差商 f x0, x1 , , xn 可由可由 函数值函数值 f (x0), f (x1 ), , f (xn ) 的线性组的线性组 合表示合表示, 且且差商的性质差商的性质mmjjmjjjjjjjmmmjmjjjjjjjmxxxxxxxxxfxxxfxxxxxxxxxfxxfmk10 1102010111010 )()()()(, )()()()(, ,

46、,1和即命题成立时设1102001, mmmmmmxxxxfxxxfxxfm知阶差商定义和上面两式由. , ,1 . :011100010110命题成立时当数学归纳法证明xxxfxxxfxxxfxfxxfk121011120201211011)()()( 1)()()( 1)()()(11)( mmmmmmmmmmmmmjmmmjjjjjjmjmjjxxxxxxxfxxxxxxxfxxxxxxxxxxxxxxxf. . )()()()(0110归纳法完成时命题成立于是，当mkxxxxxxxxxfmjmjjjjjjjfx0 , x1=fx1 , x0f(x1)- f(x0)x1 x0f(x0)-

47、 f(x1)x0 x1=性质性质2 2 差商具有对称性差商具有对称性, ,即在即在k k阶差商中阶差商中 任意交换两个节点任意交换两个节点 和和 的次序的次序, ,其值不变。其值不变。 例如例如kxxxf,10ixjx0110,xxfxxf120021210,xxxfxxxfxxxf性质性质3 k阶差商阶差商 和和k阶导数之间有下阶导数之间有下 列关系列关系 这个性质可直接用罗尔（这个性质可直接用罗尔（Rolle）定理证明（或以定理证明（或以下方法即余项方法）下方法即余项方法）kxxxf,10)max,min(!)(,00)(10iniinikkxxkfxxxf性质性质4 若若fx, x0,

48、x1 , , xk 是是 x 的的 m 次多项式次多项式, 则则 fx, x0, x1 , xk , xk+1是是 x 的的 m-1 次多项式次多项式证：由差商定义证：由差商定义 右端分子为右端分子为 m 次多项式次多项式, 且当且当 x = xk+1 时时, 分子为分子为0 ,故分子含有因子故分子含有因子 xk+1 x，与分母相消后，右端与分母相消后，右端为为m-1 次多项式。次多项式。xxxxxxfxxxxfxxxxxfkkkkkk110110110,性质性质5 若若 f(x)是是n次多项式次多项式, 则则f x, x0, x1 , , xn 恒为恒为0 证：证： f (x)是是n次多项式

49、，则次多项式，则f x, x0 是是 n-1次多次多 项式项式, f x, x0, x1 是是 n-2 次多项式次多项式, 依次递推依次递推 ， f x, x0, x1 , , xn-1 是零次多项式，所以是零次多项式，所以 fx,x0,x1 ,xn 04.3.2 牛顿牛顿(Newton)插值多项式插值多项式 )()()()()(110102010nnnxxxxxxaxxxxaxxaaxN 的系数的系数 可根据插值条件推出可根据插值条件推出, 即由即由 有有 naaa,10nixfxNiin, 1 , 0)()()()(000 xfaxNn)()()(101101xfxxaaxNn)()()(

50、)(21202201102xfxxxxaxxaaxNn )()()()()(1100110nnnnnnnnxfxxxxxxaxxaaxN这是关于这是关于 的下三角方程组的下三角方程组, ,可以求得可以求得 naaa,10)(00 xfa 10010101011,)()()()()(xxfxxxfxfxxaxfa2101210201202021022,)(,)()()()(xxxfxxxxfxxfxxxxxxaxfxfa一般，用数学归纳法可证明一般，用数学归纳法可证明 ), 1 , 0(,10nkxxxfakk所以所以n n次牛顿次牛顿( (Newton)Newton)插值公式为插值公式为 )(

51、)(,)(,)()(110100100nnnxxxxxxxxxfxxxxfxfxN其余项其余项 0101( ),()()()nnnRxf xxxxxxxxxx为牛顿插值多项式的误差。由插值多项式的存在为牛顿插值多项式的误差。由插值多项式的存在惟一性定理知，满足同一组插值条件的拉格朗日惟一性定理知，满足同一组插值条件的拉格朗日插值多项式插值多项式P(x)与牛顿插值多项式与牛顿插值多项式Nn(x)实际上是实际上是同一个多项式，仅是同一插值多项式的不同表达同一个多项式，仅是同一插值多项式的不同表达形式而已，因此得到牛顿插值多项式的误差与拉形式而已，因此得到牛顿插值多项式的误差与拉格朗日插值多项式的误

52、差也完全相等。故有格朗日插值多项式的误差也完全相等。故有(1)0100( )( ),()()(1)!nnnnniiiifR xf x xx xxxxxn)!1()(,) 1(10nfxxxxfnn0101( ),()()()nnnR xf xxxxxxxxxx)!()(,.,)(10nfxxxfnn由由（性质（性质3）建起了差商和）建起了差商和导数的关系用导数代替牛顿插值多项式中的差商，有导数的关系用导数代替牛顿插值多项式中的差商，有勒公式时，上式就是常用的泰都趋于当010110)(102010,)()(!)()(! 2)()()()(xxxxxxxxxxnfxxxxfxxfxfxpnnnn

53、差商和导数的关系也可用罗尔定理证出，余项差商和导数的关系也可用罗尔定理证出，余项R(x) =f(x)- P(x)R(xi) =f(xi)- P(xi)=0 i=0,1, ,n Rn(n)(x) =f (n)(x)- Pn(n)(x)=f (n)(x)- f(x0)+(x-x0) fx0, x1+(x-x0)(x-x1) fx0, x1 , x2+(x-x0)(x-x1)(x-xn-1)fx0,x1,xn(n)=f (n)(x)- n! fx0,x1,xnRn(xi)=0 (i=0,1,.,n)Rn( i)=0 (i=0,1,.,n-1)Rn(n)( )=0 (x0,x1,xn)Rn(n)( )

54、=0=f (n)( )- n! fx0,x1,xn)!()(,.,)(10nfxxxfnn 即即R(x)R(x)在在xx0 0, x, xn n 有有n+1n+1个零点，根据罗尔定理个零点，根据罗尔定理R R(n)(n)(x)(x)在在xx0 0, x, xn n 有有1 1个零点，设为个零点，设为 ，即有即有 Rn(n)( )=0)!()(,.,)(10nfxxxfnn 增加新节点增加新节点x，并且并且f(x)为为(n+1)阶可导时，有阶可导时，有(x0,x1,xn)!1()(,.,)1(10 nfxxxxfnn (x0,x1,xn,x),.,).()()(1010 xxxxfxxxxxxx

55、Rnnn ).()()!1()(10)1(nnxxxxxxnf (1)0( )()(1)!nniifxxn|f(x)(n+1)| Mn+110|( )|()|(1)!nnniiMR xxxn 可以看出，牛顿插值公式计算方便，增加可以看出，牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而一个插值点，只要多计算一项，而Nn(x)的的各项系数恰好是各阶差商值，很有规律各项系数恰好是各阶差商值，很有规律. . )()()()(1101nnnnxxxxxxaxNxN000,xxxfxfxxf fx0,x(x- x0) = f(x) - f(x0)f(x)+ fx0,x(x- x0)=f(x0)1

56、01001,xxxxfxxfxxxf fx1,x0,x(x-x1)=fx0,x-fx1,x0fx0,x+ fx1,x0,x(x-x1)= fx1,x0f(x)+ (x- x0) fx1,x0=f(x0)+ (x- x0) (x-x1) fx1,x0,x牛顿插值公式牛顿插值公式(另一种推导方法）另一种推导方法）f(x)=f(x0)+(x- x0)fx1,x0+(x- x0)(x-x1)fx1,x0,x201201012,xxxxxfxxxfxxxxf fx1,x0,x = (x-x2) fx2,x1,x0,x +fx2,x1,x0f(x)=f(x0)+(x- x0)fx1,x0 + (x- x0

57、)(x-x1)fx2,x1,x0 + (x- x0)(x-x1)(x-x2) fx2,x1,x0,x,.,).()(,.,).()(.,)(,)()()(011001110012100100 xxxxfxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxfnnnnnn Nn(x)Rn(x)如当如当n=1时，时，f(x) = f(x0) + (x- x0)fx1,x0 + (x- x0)(x-x1) fx1,x0,xNn(x)= f(x0) + (x- x0)fx1,x0()010001yyyxxxx 其中其中Nn(x)称为称为牛顿插值多项式牛顿插值多项式 Rn(x)称为称为牛顿插值

58、余项牛顿插值余项xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+2x0f(x0)x1f(x1)fx0,x1x2f(x2)fx1,x2fx0,x1,x2x3f(x3)fx2,x3fx1,x2,x3fx0,x1,x2 ,x3,.,).()(.,)(,)()()(01110012100100 xxxfxxxxxxxxxfxxxxxxfxxxfxNnnnn 例例4.13 已知已知 x=0, 2, 3, 5 对应的函数值为对应的函数值为 y=1, 3, 2, 5 , 作三次作三次Newton插值多项式。插值多项式。 xi f(xi) 一阶差商一阶差商 二阶差商二阶差商 三阶差

59、商三阶差商 0 1 2 3 1 3 2 -1 -2/3 5 5 3/2 5/6 3/10 所求的三次所求的三次Newton插值多项式为插值多项式为3001001201(),(),()()231(2)(2)(3)310Nf xf x xxxf x x xxxxxxx xx xx例例4.14 已知已知 f(x) = x7+ x4+ 3x+ 1 求求 f 20, 21, 27 及及 f 20, 21, 27, 28 分析：本题分析：本题 f(x)是一个多项式是一个多项式, 故应利用差商的性质故应利用差商的性质解解: 由差商与导数之间的关系由差商与导数之间的关系 ()01(7 )(8 )(7 )017

60、(8 )01781,()!( )7 !,( )0()7 !2 , 2 , 217 !7 !()02 , 2 , 2 , 208!8!nnfxxxfnfxfxffff 及知例例4.15 求求 ，并估计其误差，并估计其误差的的值值7解：作函数解：作函数 f(x) =x取取 x0=4, x1=9, x2=6.25 , 建立差商表建立差商表N2(7)= 2+ (7-4)*0.2+ (7-4)*(7-9)*(-0.00808)= 2.648482.56.253924 fxi,xi+1,xi+2 f xi,xi+1, f(x) x2 . 04923 18182. 0925. 635 . 2 00808.