第四章插值与拟合1(1)

1、4.1 引言引言 问题的提出问题的提出 函数解析式未知函数解析式未知,通过实验观测得到的一组数据通过实验观测得到的一组数据, 即在即在某个区间某个区间a, b上给出一系列点的函数值上给出一系列点的函数值 yi= f(xi) 或者给出函数表或者给出函数表y=f(x)y=p(x)xx0 x1x2xnyy0y1y2yn插值法的基本原理插值法的基本原理设函数设函数y=y=f( (x) )定义在区间定义在区间 a, b 上上, , 是是 a, b 上取定的上取定的n+1个互异节点个互异节点, ,且在这些点处的函数值且在这些点处的函数值 为已知为已知 , ,即即 若存在一个若存在一个f(x)的近似函数的近

2、似函数 , ,满足满足则称则称 为为f( (x) )的一个的一个插值函数插值函数, f( (x) )为为被插函数被插函数, 点点xi为为插值节点插值节点, 称称( (2.1)2.1)式为式为插值条件插值条件, 而误差函数而误差函数R(x)= 称为称为插值余项插值余项, 区间区间 a, b 称为称为插值插值区间区间, 插值点在插值区间内的称为插值点在插值区间内的称为内插内插, 否则称否则称外插外插 nxxx,10)(,),(),(10nxfxfxf)(iixfy )(x), 2 , 1()()(nixfxii)(x( (4.1)4.1)()(xxf插值函数插值函数 在在n+1个互异插值节点个互异

3、插值节点 ( (i=0,1,n )处与处与 相等相等, ,在其它点在其它点x就用就用 的值作为的值作为f( (x) ) 的近似值。这一过程称为的近似值。这一过程称为插值插值，点，点x称为插值点。换称为插值点。换句话说句话说, , 插值就是根据被插函数给出的函数表插值就是根据被插函数给出的函数表“插出插出”所要点的函数值。用所要点的函数值。用 的值作为的值作为f( (x) )的近似值的近似值, ,不仅希不仅希望望 能较好地逼近能较好地逼近f( (x) ), ,而且还希望它计算简单而且还希望它计算简单 。由由于代数多项式具有数值计算和理论分析方便的优点。所于代数多项式具有数值计算和理论分析方便的优

4、点。所以本章主要介绍代数插值。即求一个次数不超过以本章主要介绍代数插值。即求一个次数不超过n n次的多次的多项式。项式。 )(xix)(ixf)(x)(x)(x0111)(axaxaxaxPnnnn0111)(axaxaxaxPnnnn满足满足 ), 2 , 1 , 0()()(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 n次代数插值问题的解是存在且惟一的次代数插

5、值问题的解是存在且惟一的 证明证明: : 设设n n次多项式次多项式 0111)(axaxaxaxPnnnn是函数是函数 在区间在区间 a, ba, b上的上的n+1n+1个互异的节点个互异的节点 ( (i=0,1,2,i=0,1,2,n ),n )上的插值多项式上的插值多项式, ,则求插值多项式则求插值多项式P(x)P(x)的问题就归结为求它的系数的问题就归结为求它的系数 ( (i=0,1,2,i=0,1,2,n ),n )。 )(xfy ixia由插值条件由插值条件: (: (i=0,1,2,i=0,1,2,n),n),可得可得 )()(iixfxp)()()(01111011111100

6、011010nnnnnnnnnnnnnnnnxfaxaxaxaxfaxaxaxaxfaxaxaxa 这是一个关于待定参数这是一个关于待定参数 的的n+1阶线性方阶线性方程组程组, ,其系数矩阵行列式为其系数矩阵行列式为 naaa,10niijjinnnnnnxxxxxxxxxxxV110212110200)(111 称为称为Vandermonde（范德蒙）行列式，因范德蒙）行列式，因xixj（当当ij），），故故V0。根据解线性方程组的克莱姆根据解线性方程组的克莱姆（Gramer）法则，方程组的解法则，方程组的解 存在惟一，从而存在惟一，从而P(x)P(x)被惟一确定。被惟一确定。 naaa,

7、10惟一性说明，不论用何种方法来构造，也不论用何种惟一性说明，不论用何种方法来构造，也不论用何种形式来表示插值多项式形式来表示插值多项式, ,只要满足插值条件只要满足插值条件( (4.1)4.1)其结其结果都是相互恒等的。果都是相互恒等的。 4.2 拉格朗日（拉格朗日（Lagrange）插值插值 为了构造满足插值条件为了构造满足插值条件 (i=0,1,2,n )的便于使用的插值多项式的便于使用的插值多项式P(x),P(x),先考察几种简单情形先考察几种简单情形, ,然后再推广到一般形式。（然后再推广到一般形式。（ 线性插值与抛物插值）线性插值与抛物插值）（1）线性插值）线性插值线性插值是代数插

8、值的最简单形式。假设给定了函数线性插值是代数插值的最简单形式。假设给定了函数f(x)f(x)在两个互异的点的值，在两个互异的点的值，, ,现要求用线性函数现要求用线性函数 近似地代替近似地代替f(x)f(x)。选选择参数择参数a和和b, 使使 。称这样的线性函数。称这样的线性函数P(x)P(x)为为f(x)f(x)的线性插值函数的线性插值函数 。)()(iixfxp0 x1x)(),(1100 xfyxfybaxxp)() 1 , 0)()(ixfxpii线性插值的几何意义线性插值的几何意义: :用用通过点通过点 和和 的直线近似地代替曲线的直线近似地代替曲线 y=f(x)=f(x)由解析几何

9、知道由解析几何知道, ,这条直线用点斜式表示为这条直线用点斜式表示为 )(,(00 xfxA)(,(11xfxB)()(001010 xxxxyyyxp10100101)(yxxxxyxxxxxp01011010)(,)(xxxxxlxxxxxl0)(, 1)(1000 xlxl1)(,0)(1101xlxl1)()(10 xlxl为了便于推广，记为了便于推广，记 这是一次函这是一次函数数, ,且有性质且有性质 y=f(x) p(x)=ax+b A(x.0,f(x.0) B(x.1,f(x.1) )(0)(1)(kikixlkiik 与与 称为线性插值基函数。且有称为线性插值基函数。且有 )(

10、0 xl)(1xl1 , 0,)(10kxxxxxlkjjjkjk于是线性插值函数可以表示为与基函数的线性组合于是线性插值函数可以表示为与基函数的线性组合 1100)()()(yxlyxlxp例例4.1 4.1 已知已知 , , , , 求求 10100 11121 115y解解: : 这里这里x0=100，y0=10，x1=121，y1=11, 利用线性插值利用线性插值 1110012110010121100121)(xxxp714.10)115(115py（2 2）抛物插值）抛物插值 抛物插值又称二次插值，它也是常用的代数插值之一。抛物插值又称二次插值，它也是常用的代数插值之一。设已知设已

11、知f(x)f(x)在三个互异点在三个互异点x0，x1，x2的函数值的函数值y0，y1，y2，要构造次数不超过二次的多项式要构造次数不超过二次的多项式使满足二次插值条件：使满足二次插值条件：这就是二次插值问题。其几何意义是用经过这就是二次插值问题。其几何意义是用经过3个点个点 的抛物线的抛物线 近似代替曲线近似代替曲线 , ,如下图所示。因此也称之为抛物插值。如下图所示。因此也称之为抛物插值。 0122)(axaxaxP)2 , 1 , 0()(iyxPii),(),(),(221100yxyxyx)(xPy )(xfy y y=L2(x) y0 y1 y1 y=f(x) O x0 x1 x2

12、x P(x)的参数的参数直接由插值条件决定，直接由插值条件决定，即即 满足下面满足下面的代数方程组：的代数方程组： 210,aaa210,aaa222221012121100202010yxaxaayxaxaayxaxaa222211200111xxxxxx该三元一该三元一次方程组次方程组的系数矩阵的系数矩阵 的行列式是范德蒙行列式，当的行列式是范德蒙行列式，当 时，时，方程组的解唯一。方程组的解唯一。 210 xxx为了与下一节的为了与下一节的Lagrange插值公式比较插值公式比较, ,仿线性插值仿线性插值, ,用用基函数的方法求解方程组。先考察一个特殊的二次插值基函数的方法求解方程组。先

13、考察一个特殊的二次插值问题：问题： 求二次式求二次式 , ,使其满足条件：使其满足条件： )(0 xl0)(,0)(, 1)(201000 xlxlxl这个问题容易求解。由上式的后两个条件知这个问题容易求解。由上式的后两个条件知: : 是是 的两个零点。于是的两个零点。于是 21,xx)(0 xl)()(210 xxxxcxl再由另一条件再由另一条件 确定系数确定系数 1)(00 xl)(12010 xxxxc)()()(2010210 xxxxxxxxxl从而导出从而导出 类似地可以构造出满足条件：类似地可以构造出满足条件：的插值多项式的插值多项式 0)(, 0)(, 1)(210111xl

14、xlxl)()()(2101201xxxxxxxxxl及满足条件：及满足条件： 的插值多项式的插值多项式 0)(,0)(, 1)(120222xlxlxl)()()(1202102xxxxxxxxxl这样构造出来的这样构造出来的 称为抛物插值的基函数称为抛物插值的基函数 )(),(),(210 xlxlxl取已知数据取已知数据 作为线性组合系数作为线性组合系数, ,将基函数将基函数 线性组合可得线性组合可得 210,yyy)(),(),(210 xlxlxl212021012101200201021)()()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxP容易看出容

15、易看出, ,P(x)P(x)满足条件满足条件 )2 , 1 , 0()(iyxPii拉格朗日插值多项式拉格朗日插值多项式 两个插值点可求出一次插值多项式两个插值点可求出一次插值多项式, ,而三而三个插值点可求出二次插值多项式。插值点增加到个插值点可求出二次插值多项式。插值点增加到n+1个时个时, ,也就是通过也就是通过n+1个不同的已知点个不同的已知点, ,来构造一个次数为来构造一个次数为n的代数多项式的代数多项式P(x)。与推导抛物插与推导抛物插值的基函数类似值的基函数类似, ,先构造一个特殊先构造一个特殊n次多项式次多项式 的插的插值问题值问题, ,使其在各节点使其在各节点 上满足上满足

16、), 1 , 0)(,(niyxii)(xliix0)(, 0)(, 1)(, 0)(, 0)(110nkkkkkkkkxlxlxlxlxl)(0)(1)(kikixlkiik即即 由条件由条件 ( ) ( )知知, , 都是都是n n次次 的零点的零点, ,故可设故可设 0)(ikxlki nkkxxxxx,1110)(xlk)()()()(1110nkkkkxxxxxxxxxxAxl其中其中 为待定常数。由条件为待定常数。由条件 , ,可求得可求得 kA1)(kkxlkA1)(0nkjjjkkxxA于是于是 nkjjjkkxxA0)(1代入上式代入上式, ,得得nkjjjkjnkjjjkn

17、kjjjkxxxxxxxxxl000)()()(称称 为关于基点为关于基点 的的n n次次插值基函数插值基函数( (i=0,1,i=0,1,n),n) )(xlkix)()()()(110niiixxxxxxxxAxl 设设.为为待待定定常常数数其其中中 A可可得得由由1)( iixl)()()(1110niiiiiixxxxxxxxA (*),1 ,0()()()()()()()()()(0110110nixxxxxxxxxxxxxxxxxxxxxlnijjjijniiiiiiniii 所所以以称之为称之为Lagrange插值基函数插值基函数.以以n+1个个n次基本插值多项式次基本插值多项式

18、为基础为基础, ,就能直接写出满足插值条件就能直接写出满足插值条件的的n次代数插值多项式。次代数插值多项式。事实上，由于每个插值基函数事实上，由于每个插值基函数都是都是n次值多项式次值多项式, ,所以他们的线性组合所以他们的线性组合), 1 ,0)(nkxlk), 2 , 1 , 0()()(nixfxPiinnyxlyxlyxlxP)()()()(1100), 1 ,0)(nkxlknkkkyxlxP0)()(是次数不超过是次数不超过n n次的多项式次的多项式 , 称形如（称形如（4.2）式的插）式的插值多项式为值多项式为n次拉格朗日插值多项式。并记为次拉格朗日插值多项式。并记为 （4.2）

19、)(xLn101 ( )()()() (4.3)nnxxxxxxx引入记号)()()()( 1101nkkkkkkknxxxxxxxxx 则则得得101( ) ( ) (4.4)()()nnnkkknkxLxyxxx于是定理定理4.14.1nnnxaxaxaaxP2210)(niyxPiin,2 ,1 ,0)(),(jixxji若插值节点则满足插值条件则满足插值条件的插值多项式的插值多项式存在且唯一存在且唯一.反证：若不唯一，则除了反证：若不唯一，则除了Pn(x) 外还有另一外还有另一 n 阶多项式阶多项式 Ln(x) 满足满足 Ln(xi) = yi 。考察考察 则则 Qn 的阶数的阶数,

20、)()()(xLxPxQnnn n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注：注：若不将多项式次数限制若不将多项式次数限制为为 n ，则插值多项式，则插值多项式不唯一不唯一。例如例如 也是一个插值多项也是一个插值多项式，其中式，其中 可以是任意多项式。可以是任意多项式。 niinxxxpxLxP0)()()()()(xp例例4.2 已知已知y=f(x)的函数表的函数表 求线性插值多项式求线性插值多项式, 并计算并计算x=1.5 的值的值X 1 3 y 1 225.1)5.1()5.1()1(2121311313)(10100101pfxxxyxxxxyxxxxxp解解: 由线

21、性插值多项式公式得由线性插值多项式公式得例例4.3 已知已知x=1, 4, 9 的平方根值的平方根值, 用抛物插值公式用抛物插值公式, 求求 (x0 x1)(x0 x2)(xx1)(xx2)y0+(x1x0)(x1x2)(xx0)(xx2)y1+(x2x0)(x2x1)(xx0)(xx1)y2p2(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.7p2(x) =7例例4.4 已知函数已知函数y=f(x)在节点上满足在节点上满足 x x0 x1

22、 x2 y y0 y1 y2 求二次多项式求二次多项式 p(x) = a0 + a1x + a2x2 使之满足使之满足 p(xi) = yi i=0, 1, 2解解: 用待定系数法用待定系数法, 将各节点值依次代入所求多项式将各节点值依次代入所求多项式, 得得解上述方程解上述方程, 将求出的将求出的a0, a1, a2 代入代入p(x) = a0 + a1x + a2x2 即得所求二次多项式即得所求二次多项式 201202012120122aa x a xyaa x a xyaa x a xy例例4.5 求过点求过点(0,1)、(1,2)、(2,3)的三点插值多项式的三点插值多项式13) 12

23、)(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插值多项式插值多项式: :基函数为基函数为 1478

24、781)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为便于上机计算为便于上机计算, ,常将拉格朗日插值多项式常将拉格朗日插值多项式( (5.8)改写成改写成 nknkiiikiknxxx

25、xyxL00)(34)()()()()(2333221100 xxyxlyxlyxlyxlxp 例例4.7 已知已知f(x)的观测数据的观测数据 x 1 2 3 4f(x) 0 -5 -6 3构造插值多项式构造插值多项式 解解: 四个点可以构造三次插值多项式四个点可以构造三次插值多项式, 将数据将数据 代入插值公式，有代入插值公式，有 这个例子说明这个例子说明p(x)的项数不超过的项数不超过n+1项，但可以有项，但可以有 缺项。缺项。 ttxxxxjkj j = 0 , ,k -1 ,k + 1 , ,n 输 入 (xi,yi), n i= 0 ,1 , ,n 0 y 0 t 1 = t k

26、= n ? 输 出y y + t yk y k + 1 k n y 拉格朗日插值算法实现拉格朗日插值算法实现 x0 x1 xixi+1 xn-1 xny=f(x)y=p(x)ab在插值区间在插值区间 a, b 上用上用插值多项式插值多项式p(x)近似代替近似代替f(x), 除了除了在插值节点在插值节点xi上没有误差外，在其它点上一般是存在误上没有误差外，在其它点上一般是存在误差的。差的。若记若记 R (x) = f(x) - p(x) 则则 R(x) 就是用就是用 p(x) 近似代替近似代替 f(x) 时的截断误差时的截断误差, 或称或称插值余项我们可根据后面的定理来估计它的大小。插值余项我们

27、可根据后面的定理来估计它的大小。4.2.24.2.2插值多项式的误差插值多项式的误差 定理定理2 设设f(x)在在 a, b 有有n+1阶导数，阶导数， x0, x1, xn 为为 a, b 上上n+1个互异的节点个互异的节点, p(x)为满足为满足 p(xi) = f(xi) (i=1,2, , n) 的的n 次插值多项式，那么对于任何次插值多项式，那么对于任何x a, b 有有 插值余项插值余项)()!1()()()()()1(xnfxpxfxRn其中其中a b 且依赖于且依赖于xbaxxxxxxxxxniin,),()()()(010证明证明 ( 略略 ) 对于线性插值，其误差为对于线性

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

29、因为因为 )121115)(100115(81)115(231R23121,100max)121115)(100115(81)121115)(100115(1081301125. 010615813例例4.9 已知已知x0=100, x1=121, x2=144,当用抛物插值求当用抛物插值求 在在x=115时的近似值，估计其的截断误差时的近似值，估计其的截断误差 0017. 010)144115)(121115)(100115(161)115()144)(121)(100(161)()()()(61)(52252210) 3(2RxxxxxRxxxxxxfxR解解( )f xx02011220

30、12010210122021()()()()()()( )()()()()()()115(115) 10.772756x x x xx x x xx x x xp xyyyxx xxxx xxxx xxp=2583)( xxf例例4.10 设设f(x)=x4, 用余项定理写出节点用余项定理写出节点 -1, 0, 1, 2的三次插值多项式的三次插值多项式 解解: 根据余项定理根据余项定理(4)0123432( )( )( )()()()()4!( )( 1 )( 1 )( 2)( ) 22ff x pxx x x x x x x xx px xxxxpxx xx 4.3 均差与均差与牛顿插值多项

31、式牛顿插值多项式 拉格朗日插值多项式结构对称，使用方便。拉格朗日插值多项式结构对称，使用方便。但由于是用基函数构成的插值，这样要增加一个但由于是用基函数构成的插值，这样要增加一个节点时，所有的基函数必须全部重新计算，不具节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。这就启发我们备承袭性，还造成计算量的浪费。这就启发我们去构造一种具有去构造一种具有承袭性承袭性的插值多项式来克服这个的插值多项式来克服这个缺点，也就是说，每增加一个节点时，只需增加缺点，也就是说，每增加一个节点时，只需增加相应的一项即可。这就是牛顿插值多项式。相应的一项即可。这就是牛顿插值多项式。 由线性代

32、数知由线性代数知,任何一个不高于任何一个不高于n次的多项式次的多项式, 都可以都可以表示成函数表示成函数)()( ,),)( , 1110100nxxxxxxxxxxxx的线性组合的线性组合, 也就是说也就是说, 可以把满足插值条件可以把满足插值条件p(xi)=yi (i=0,1,n)的的n次插值多项式次插值多项式, 写成如下形式写成如下形式)()()()(110102010nnxxxxxxaxxxxaxxaa其中其中ak (k=0,1,2,n)为待定系数为待定系数,这种形式的插值多项这种形式的插值多项式称为式称为Newton插值多项式。我们把它记为插值多项式。我们把它记为Nn(x)即即)()

33、()()()(110102010nnnxxxxxxaxxxxaxxaaxN（4.5） 可见，牛顿插值多项式可见，牛顿插值多项式Nn(x)是是插值多项式插值多项式p(x)的另的另一种表示形式一种表示形式, 与与Lagrange多项式相比它不仅克服了多项式相比它不仅克服了“增加一个节点时整个计算工作重新开始增加一个节点时整个计算工作重新开始”的缺点的缺点, 且可且可以节省乘除法运算次数以节省乘除法运算次数, 同时在同时在Newton插值多项式中用插值多项式中用到差分与差商等概念，又与数值计算的其他方面有密切到差分与差商等概念，又与数值计算的其他方面有密切的关系的关系.它满足它满足其中其中ak (k

34、=0,1,2,n)为待定系数，形如（为待定系数，形如（4.5）的）的插值多项式称为插值多项式称为牛顿牛顿(Newton)插值多项式插值多项式。 )()()()(1101nnnnxxxxxxaxNxN定义定义 函数函数y= f(x)在区间在区间xi ,xi+1上的平均变化率上的平均变化率iiiiiixxxfxfxxf111)()(,自变量之差和因变量之差之比叫自变量之差和因变量之差之比叫差商差商 （均差）（均差） 称为称为f(x)关于关于xi , xi+1 的一阶差商的一阶差商,并记为并记为fxi ,xi+1 二阶差商二阶差商iiiiiiiiixxxxfxxfxxxf212121,0110211

35、0,xxxxxfxxxfxxxfmmmmm阶差商阶差商fxi,xj,xk是指是指fxi , xj , xk=fxj , xk- fxi , xj xk- xi一般的一般的,可定义区间可定义区间xi, xi+1 , xi+n上的上的n阶差商为阶差商为ininiiiniiiniiixxxxxfxxxfxxxf ,.,.,.,11211021021210,xxxxfxxfxxxf 例例如如：差商及其性质差商及其性质差商表差商表xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+2x0f(x0)x1f(x1)fx0,x1x2f(x2)fx1,x2fx0,x1,x2x3f(x3)

36、fx2,x3 fx1,x2,x3fx0,x1,x2 ,x3fx1,x2- fx0,x1x2 x0 xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+2 ,xi+300283275125621640208 1923827 493527125 9156125216 503419 10251949 14364991 105510 1261014 例例4.11 求求 f(xi)= x3在节点在节点 x=0, 2, 3, 5, 6上的各阶差商值上的各阶差商值解解: 计算得如下表计算得如下表00101121201223 ( ) , : f x x f(x) f , f , f ,

37、 , yxyxxxyxx xxx xx如果的函数值称为零阶差商则计算如下表231233121 nn-nn-n-n f , f , , f , f, yxxx xxyxxxxx01 ,nn, f xx xx在在n+1n+1个节点处各阶差商的计算方法个节点处各阶差商的计算方法差商及其性质差商及其性质nknkkkkkkkknkiiikknkkknxxxxxxxxxxxfxxxxxfxxxf011100010)()()()()()()()(,其中这个性质可用数学归纳法证明（用这个性质可用数学归纳法证明（用Lagrange插值多项式比较最高项系数来得到插值多项式比较最高项系数来得到）性质性质1 函数函数

38、 f(x) 的的 n 阶差商阶差商 f x0, x1 , , xn 可由可由 函数值函数值 f (x0), f (x1 ), , f (xn ) 的线性组的线性组 合表示合表示, 且且差商及其性质差商及其性质mmjjmjjjjjjjmmmjmjjjjjjjmxxxxxxxxxfxxxfxxxxxxxxxfxxfmk10 1102010111010 )()()()(, )()()()(, , ,1和即命题成立时设1102001, mmmmmmxxxxfxxxfxxfm知阶差商定义和上面两式由. , ,1 . :011100010110命题成立时当数学归纳法证明xxxfxxxfxxxfxfxxfk

39、121011120201211011)()()( 1)()()( 1)()()(11)( mmmmmmmmmmmmmjmmmjjjjjjmjmjjxxxxxxxfxxxxxxxfxxxxxxxxxxxxxxxf. . )()()()(0110归纳法完成时命题成立于是，当mkxxxxxxxxxfmjmjjjjjjjfx0 , x1=fx1 , x0f(x1)- f(x0)x1 x0f(x0)- f(x1)x0 x1=性质性质2 2 差商具有对称性差商具有对称性, ,即在即在k k阶差商中阶差商中 任意交换两个节点任意交换两个节点 和和 的次序的次序, ,其值不变。其值不变。 例如例如kxxxf,

40、10ixjx0110,xxfxxf120021210,xxxfxxxfxxxf性质性质3 k3 k阶差商阶差商 和和k k阶导数之间有下阶导数之间有下 列关系列关系 这个性质可直接用罗尔（这个性质可直接用罗尔（RolleRolle）定理证明（或定理证明（或以下方法即余项方法）以下方法即余项方法）kxxxf,10)max,min(!)(,00)(10iniinikkxxkfxxxf性质性质4 若若fx, x0, x1 , , xk 是是 x 的的 m 次多项式次多项式, 则则 fx, x0, x1 , xk , xk+1是是 x 的的 m-1 次多项式次多项式证：由差商定义证：由差商定义 右端分

41、子为右端分子为 m 次多项式次多项式, 且当且当 x = xk+1 时时, 分子为分子为0 ,故分子含有因子故分子含有因子 xk+1 x，与分母相消后，右端与分母相消后，右端为为m-1 次多项式。次多项式。xxxxxxfxxxxfxxxxxfkkkkkk110110110,性质性质5 若若 f(x)是是n次多项式次多项式, 则则f x, x0, x1 , , xn 恒为恒为0 证：证： f (x)是是n次多项式，则次多项式，则f x, x0 是是 n-1次多次多 项式项式, f x, x0, x1 是是 n-2 次多项式次多项式, 依次递推依次递推 ， f x, x0, x1 , , xn-1

42、 是零次多项式，所以是零次多项式，所以 fx,x0,x1 ,xn 04.3.2 牛顿牛顿(Newton)插值多项式插值多项式 )()()()()(110102010nnnxxxxxxaxxxxaxxaaxN 的系数的系数 可根据插值条件推出可根据插值条件推出, 即由即由 有有 naaa,10nixfxNiin, 1 , 0)()()()(000 xfaxNn)()()(101101xfxxaaxNn)()()()(21202201102xfxxxxaxxaaxNn )()()()()(1100110nnnnnnnnxfxxxxxxaxxaaxN这是关于这是关于 的下三角方程组的下三角方程组,

43、,可以求得可以求得 naaa,10)(00 xfa 10010101011,)()()()()(xxfxxxfxfxxaxfa2101210201202021022,)(,)()()()(xxxfxxxxfxxfxxxxxxaxfxfa一般，用数学归纳法可证明一般，用数学归纳法可证明 ), 1 , 0(,10nkxxxfakk所以所以n n次牛顿次牛顿( (Newton)Newton)插值公式为插值公式为 )()(,)(,)()(110100100nnnxxxxxxxxxfxxxxfxfxN其余项其余项 0101( ),()()()nnnRxf xxxxxxxxxx为牛顿插值多项式的误差。由插

44、值多项式的存在为牛顿插值多项式的误差。由插值多项式的存在惟一性定理知，满足同一组插值条件的拉格朗日惟一性定理知，满足同一组插值条件的拉格朗日插值多项式插值多项式P(x)P(x)与牛顿插值多项式与牛顿插值多项式N Nn n(x)(x)实际上是实际上是同一个多项式，仅是同一插值多项式的不同表达同一个多项式，仅是同一插值多项式的不同表达形式而已，因此得到牛顿插值多项式的误差与拉形式而已，因此得到牛顿插值多项式的误差与拉格朗日插值多项式的误差也完全相等。故有格朗日插值多项式的误差也完全相等。故有(1)0100( )( ),()()(1)!nnnnniiiifR xf x xx xxxxxn)!1()(

45、,) 1(10nfxxxxfnn 可以看出，牛顿插值公式计算方便，增加可以看出，牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而一个插值点，只要多计算一项，而Nn(x)的的各项系数恰好是各阶差商值，很有规律各项系数恰好是各阶差商值，很有规律. . 000,xxxfxfxxf fx0,x(x- x0) = f(x) - f(x0)f(x)+ fx0,x(x- x0)=f(x0)101001,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-

46、 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)(x-x1)fx2,x1,x0 + (x- x0)(x-x1)(x-x2) fx2,x1,x0,x,.,).()(,.,).()(.,)(,)()()(011001110012100100 xxxxfxxxxx

47、xxxxfxxxxxxxxxfxxxxxxfxxxfxfnnnnnn 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)称为称为牛顿插值余项牛顿插值余项xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+2x0f(x0)x1f(x1)fx0,x1x2f(x2)fx1,x2fx0,x1,x2x3f(x3)fx2,x3fx1,

48、x2,x3fx0,x1,x2 ,x3,.,).()(.,)(,)()()(01110012100100 xxxfxxxxxxxxxfxxxxxxfxxxfxNnnnnxifxifxi,xi+1fxi,xi+1,xi+2114293N2(7)=1+(7-1)*0.33333+ (7-1)*(7-4)*(-0.01667)= 2.6999233333. 01412 2 . 04923 01667. 01933333. 02 . 0 + (x- x0) (x-x1) fx1,x0,x2+ (x- x0) fx1,x0=f(x0)N(x)例例 4.12 已知已知 x = 1, 4, 9 的平方根值，求

49、的平方根值，求解：解：7)!()(,.,)(10nfxxxfnn由由建起了差商和导数的关建起了差商和导数的关系系用导数代替牛顿插值多项式中的差商，有用导数代替牛顿插值多项式中的差商，有勒公式时，上式就是常用的泰都趋于当010110)(102010,)()(!)()(! 2)()()()(xxxxxxxxxxnfxxxxfxxfxfxpnnnn 差商和导数的关系也可用罗尔定理证出，余项差商和导数的关系也可用罗尔定理证出，余项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)-

50、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)( )=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,

51、 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 xxxxfxxxxxxxRnnn ).()()!1()(10)1(nnxxxxxxnf (1)0( )()(1)!nniifxxn|f(x)(n+1)| Mn+110|( )|()|(1)!nnniiMR xxxn 例例4.13 已知已知 x=0, 2, 3, 5 对应的函数值

52、为对应的函数值为 y=1, 3, 2, 5 , 作三次作三次Newton插值多项式。插值多项式。 xi f(xi) 一阶差商一阶差商 二阶差商二阶差商 三阶差商三阶差商 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

53、)是一个多项式是一个多项式, 故应利用差商的性质故应利用差商的性质解解: 由差商与导数之间的关系由差商与导数之间的关系 ()01(7 )(8 )(7 )017(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 , 建立差商表建立差商表xf(x)f xi,xi+1,fxi,xi+1,xi+242936.25 2.5N2(7)= 2+ (7-4)*

54、0.2+ (7-4)*(7-9)*(-0.00808)= 2.648482 . 04923 18182. 0925. 635 . 2 00808. 0425. 62 . 018182. 0 f 3(x) =5)1(83x011719. 0)41(835 Rn (x)00879. 0| )25. 67)(97)(47( |! 3011719. 0 在区间在区间 4 , 9 上，上，余式近似余式近似 0.5 *10 -2, N2(7) = 2.64848 可舍入为可舍入为2.65.645751. 27 10|( )|()|(1)!nnniiMR xxxn| f(x)(n+1) | Mn+1由由已知

55、等距节点nxxhnkkhxxnk00210 ,4.4 Newton4.4 Newton等距插值等距插值1 1、差分、差分定义)()()(kkkxfxfxf 1简记为kkkfff 11 kkkfff)()()(1 kkkxfxfxf简记为 22hxfhxfxfkkk)( 22hkhkkfff 简记为向前差分向前差分 向后差分向后差分 中心差分中心差分 前差算子前差算子后差算子后差算子kmkmkmfff111 高阶向前差分高阶向前差分 111 kmkmkmfff高阶向后差分高阶向后差分 如)()(kkkkkkkfffffff 11212kkkfff 122)()(21112 kkkkkkkffff

56、fff212 kkkfff2、高阶差分、高阶差分 )()()()(kkkkkkkkffffffff 1121223kkkkffff 12333)()(kkkkkkkfffffff 1122123又如又如 3、前差与后差的关系、前差与后差的关系 11 kkkkffff)()(kkkkkkkfffffff 112122212 kkkfffmkmkmff 一般有一般有再定义再定义1 kkfEf前移算子前移算子kkffI 不变算子不变算子11 kkffE后移算子后移算子则有则有kkkkkkfIEIfEffff)( 1因此因此knknfIEf)( inkniinikniiininifCfIEC 0011

57、)()(knknknfIEfEIf)()( 11nikniininkniniininfCfEC 0011)()( knnniniininnnfICIECEC0011)()( knnnniinininnnnfICIECIECEC)()(11110 4、差商与差分的关系、差商与差分的关系hfxxxfxfxxfkkkkkkk 111)()(,hhfhfxxxxfxxfxxxfkkkkkkkkkkk21211221 ,kfh2221 kmmmkkkfhmxxxf 111!,m阶向前差商与阶向前差商与m阶向前差分的关系阶向前差分的关系m阶向后差商与阶向后差商与m阶向后差分的关系阶向后差分的关系kmmmk

58、kkfhmxxxf 111!,又又!)(,)(mfxxxfmmkkk 1所以所以)(,!)( mmmkkkmkmfhxxxfmhf 15、差分的计算、差分的计算6、等距节点的、等距节点的Newton插值插值已知等距节点nxxhnkkhxxnk00210 ,)(,)()(0100 xxxxfxfxNn )()(,1010 nnxxxxxxxf)(,10210 xxxxxxxf 得得)()(000001xthxfhfthxNn )(!hxthxxthxfh 000002221)()(!hnxthxxthxfhnnn1100000 令令 由由Newton插值公式插值公式thxx 0其中其中)(00

59、xff kmmmkkkfhmxxxf 111!,参参照照)()(000001xthxfhfthxNn )(!hxthxxthxfh 000002221)()(!hnxthxxthxfhnnn1100000 即即htthfhthfhfthxNn)(!)(1211022000 hntthfhnnn)(! 110002001121fnntttfttftfn !)()(!)(前插公式前插公式同理可得后插公式同理可得后插公式)(thxNnn 0021121fnntttfttftfnnn !)()(!)(其中其中 , ,公式公式 称之为牛顿向后插值公式余项。称之为牛顿向后插值公式余项。 hxxtn/ )(

60、 nhxxfhnntttxRnn,),()!1()() 1()(0)1(1例例4.16 计算计算 f (x) = x3在等距节点在等距节点0，1，2，3, 4上的各上的各 阶差分值阶差分值xy y 2y 3y001128327464 4y17193761218660 x-1 012y-11311解：解：建立差分表建立差分表xy y 2y 3y-1-10121320211 866hxxt0 5 .01)1()5 .0( 2*! 15 . 01 0*!2)15.0(5.0 6*!3)25 .0)(15 .0(5 .0 = -1+1+0+0.375 = 0.375例例4.17 按下列数值表用按下列数