讲稿 第四章插值及拟合(1～3节)

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

2、称 为为f( (x) )的一个的一个插值函数插值函数, f( (x) )为为被插函数被插函数, 点点xi为为插值节点插值节点, 称称( (4 4. .2 2) )式为式为插值条件插值条件, 而误差函数而误差函数R(x)= 称为称为插值余项插值余项, 区间区间 a, b 称为称为插值插值区间区间, 插值点在插值区间内的称为插值点在插值区间内的称为内插内插, 否则称否则称外插外插 nxxx,10)(,),(),(10nxfxfxf)(iixfy )(x), 2 , 1()()(nixfxii)(x( (4 4. .2 2) )()(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 2 n次代数插值问题的解存在且唯一次代数插值问题的解存在且唯一 定

5、理定理1 1证明证明: : 设设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)()()(01111011111100011010n

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

7、论用何种方法来构造，也不论用何种唯一性说明，不论用何种方法来构造，也不论用何种形式来表示插值多项式形式来表示插值多项式, ,只要满足插值条件只要满足插值条件( (4.24.2) )其结其结果都是相互恒等的。果都是相互恒等的。 2 插值多项式的求法插值多项式的求法 为了构造满足插值条件为了构造满足插值条件 (i=0,1,2,n )的便于使用的插值多项式的便于使用的插值多项式P(x),P(x),先考察几种简单情形先考察几种简单情形, ,然后再推广到一般形式。然后再推广到一般形式。1 拉格朗日插值多项式拉格朗日插值多项式（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 与与 称为线性插值基函数。且有称为线性插值基函数。且有 )(0 xl)(1xl1 , 0,)(

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

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

12、直接由插值条件决定，即即 满足下面满足下面的代数方程组：的代数方程组： 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)(210111xlxlxl)()()(2101201xxxxxxx

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

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

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

17、xxxxxxl000)()()(称称 为关于基点为关于基点 的的n n次插值基函数次插值基函数( (i=0,1,i=0,1,n),n) )(xlkix以以n+1个个n次基本插值多项式次基本插值多项式为基础为基础, ,就能直接写出满足插值条件就能直接写出满足插值条件的的n次代数插值多项式。次代数插值多项式。事实上，由于每个插值基函数事实上，由于每个插值基函数都是都是n次值多项式次值多项式, ,所以它们的线性组合所以它们的线性组合), 1 ,0)(nkxlk), 2 , 1 , 0()()(nixfxPiinnyxlyxlyxlxP)()()()(1100), 1 ,0)(nkxlknkkkyxl

18、xP0)()(是次数不超过是次数不超过n n次的多项式次的多项式 , 称形如（称形如（ 4 4.13 ）式的插）式的插值多项式为值多项式为n次拉格朗日插值多项式，记为次拉格朗日插值多项式，记为 。（4 4.11）)(xLn例例2 已知已知y=f(x)的函数表的函数表 求线性插值多项式求线性插值多项式, 并计算并计算x=1.5 的值的值X 1 3 y 1 225.1)5.1()5.1()1(2121311313)(10100101pfxxxyxxxxyxxxxxp解解: 由线性插值多项式公式得由线性插值多项式公式得例例3 已知已知x=1, 4, 9 的平方根值的平方根值, 用抛物插值公式用抛物插

19、值公式, 求求 (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 已知函数已知函数y=f(x)在节点上满足在节点上满足 x x0 x1 x2 y y0 y1 y2 求二次多项式求二次多项式 p(x) = a0 + a1x + a2x2 使之满足使之满足 p(xi)

20、 = yi i=0, 1, 2解解: 用待定系数法用待定系数法, 将各节点值依次代入所求多项式将各节点值依次代入所求多项式, 得得解上述方程解上述方程, 将求出的将求出的a0, a1, a2 代入代入p(x) = a0 + a1x + a2x2 即得所求二次多项式即得所求二次多项式 201202012120122aa x a xyaa x a xyaa x a xy例例5 求过点求过点(0,1)、(1,2)、(2,3)的三点插值多项式的三点插值多项式13) 12)(02 () 1)(0(2) 21)(01 () 2)(0(1) 20)(10 () 2)(1()(xxxxxxxxp解解:由由La

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

22、)(0()(231xxxxxxxl2324541)42)(12)(02()4)(1)(0()(xxxxxxxl12181241)24)(14)(04()2)(1)(0()(233Lagrange插值多项式为插值多项式为 )()(303xlyxLkkk)(3)(23)(9)(3210 xlxlxlxl12144541123xxx为便于上机计算为便于上机计算, ,常将拉格朗日插值多项式常将拉格朗日插值多项式( (4.11)改写成改写成 nknkiiikiknxxxxyxL00)(4.13)34)()()()()(2333221100 xxyxlyxlyxlyxlxp 例例7 已知已知f(x)的观测

23、数据的观测数据 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 k 1=t k = n ? 输 出y y+t yk y k +1k n y 拉格朗日插值算法实现拉格朗日插值算法实现 x0 x1 xixi+1 xn-1 xny=f(x)y=

24、p(x)ab在插值区间在插值区间 a, b 上用上用插值多项式插值多项式p(x)近似代替近似代替f(x), 除了除了在插值节点在插值节点xi上没有误差外，在其它点上一般是存在误上没有误差外，在其它点上一般是存在误差的。差的。若记若记 R (x) = f(x) - p(x) 则则 R(x) 就是用就是用 p(x) 近似代替近似代替 f(x) 时的时的截断误差截断误差, 或称或称插值余项，插值余项，我们可根据后面的定理来估计它的大小。我们可根据后面的定理来估计它的大小。(4) (4) 插值多项式的误差插值多项式的误差 定理定理2 设设f(x)在在 a, b 有有n+1阶导数，阶导数， x0, x1

25、, 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证明证明 ( 略略 ) 对于线性插值，其误差为对于线性插值，其误差为对于抛物插值（二次插值），其误差为对于抛物插值（二次插值），其误差为baxxxxfxPxfxR,)()(21)()()(10 baxxxxxxfxPxf

26、xR,)( )()(61)()()(210 例例 8 已知已知 =100, =121, 用线性插值估计用线性插值估计 在在x=115时的截断误差时的截断误差xxf)(0 x1x解解: 由插值余项公式知由插值余项公式知 )()(21)(1xfxR 2341)( xxf)(81)(10231xxxxxR因为因为 )121115)(100115(81)115(231R23121,100max)121115)(100115(81)121115)(100115(1081301125. 010615813例例9 已知已知x0=100, x1=121, x2=144,当用抛物插值求当用抛物插值求 在在x=1

27、15时的近似值，估计其截断误差时的近似值，估计其截断误差 0017. 010)144115)(121115)(100115(161)115()144)(121)(100(161)()()()(61)(52252210) 3(2RxxxxxRxxxxxxfxR解解( )f xx0201122012010210122021()()()()()()( )()()()()()()115(115) 10.772756x x x xx x x xx x x xp xyyyxx xxxx xxxx xxp=2583)( xxfx=100(1)111max( )( )( )( )( )(1)!nna x bn

28、nfxMp xf xMR xxn 通常，在做误差估计时，若能求出那么近似代替的截断误差限是：2 2 差商与牛顿基本插值多项式差商与牛顿基本插值多项式 拉格朗日插值多项式结构对称，使用方便。拉格朗日插值多项式结构对称，使用方便。但由于是用基函数构成的插值，这样要增加一个但由于是用基函数构成的插值，这样要增加一个节点时，所有的基函数必须全部重新计算，不具节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。这就启发我们备承袭性，还造成计算量的浪费。这就启发我们去构造一种具有承袭性的插值多项式来克服这个去构造一种具有承袭性的插值多项式来克服这个缺点，也就是说，每增加一个节点时，只需

29、增加缺点，也就是说，每增加一个节点时，只需增加相应的一项即可。这就是牛顿插值多项式。相应的一项即可。这就是牛顿插值多项式。 由线性代数知由线性代数知,任何一个不高于任何一个不高于n次的多项式次的多项式, 都可以都可以表示成函数表示成函数)()( ,),)( , 1110100nxxxxxxxxxxxx的线性组合的线性组合, 也就是说也就是说, 可以把满足插值条件可以把满足插值条件p(xi)=yi (i=0,1,n)的的n次插值多项式次插值多项式, 写成如下形式写成如下形式)()()()(110102010nnxxxxxxaxxxxaxxaa其中其中ak (k=0,1,2,n)为待定系数为待定系

30、数,这种形式的插值多项这种形式的插值多项式称为式称为n次次Newton插值多项式插值多项式。记为。记为Nn(x)，即，即)()()()()(110102010nnnxxxxxxaxxxxaxxaaxN（4.174.17） 可见，牛顿插值多项式可见，牛顿插值多项式Nn(x)是插值多项式是插值多项式p(x)的另的另一种表示形式一种表示形式, 与与Lagrange多项式相比它不仅克服了多项式相比它不仅克服了“增加一个节点时整个计算工作重新开始增加一个节点时整个计算工作重新开始”的缺点的缺点, 且可且可以节省乘除法运算次数以节省乘除法运算次数, 同时在同时在Newton插值多项式中用插值多项式中用到差

31、分与差商等概念，又与数值计算的其他方面有密切到差分与差商等概念，又与数值计算的其他方面有密切的关系。的关系。它满足它满足其中其中ak (k=0,1,2,n)为待定系数为待定系数。 )()()()(1101nnnnxxxxxxaxNxN差商及其性质差商及其性质定义定义1 函数函数y= f(x)在区间在区间xi ,xi+1上的平均变化率上的平均变化率iiiiiixxxfxfxxf111)()(, 自变量之差和因变量之差之比叫自变量之差和因变量之差之比叫差商差商 称为称为f(x)关于关于xi , xi+1 的的一阶差商一阶差商, 并记为并记为fxi ,xi+1 二阶差商二阶差商iiiiiiiiixx

32、xxfxxfxxxf212121,01102110,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,

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

34、xxxxxfxxxf011100010)()()()()()()()(,其中这个性质可用数学归纳法证明这个性质可用数学归纳法证明性质性质1 函数函数 f(x) 的的 n 阶差商阶差商 f x0, x1 , , xn 可由可由 函数值函数值 f (x0), f (x1 ), , f (xn ) 的线性组的线性组 合表示合表示, 且且fx0 , x1=fx1 , x0f(x1)- f(x0)x1 x0f(x0)- f(x1)x0 x1=性质性质2 2 差商具有对称性差商具有对称性, ,即在即在k k阶差商中阶差商中 任意交换两个节点任意交换两个节点 和和 的次序的次序, ,其值不变。其值不变。 例

35、如例如kxxxf,10ixjx0110,xxfxxf120021210,xxxfxxxfxxxf牛顿插值公式牛顿插值公式牛顿牛顿(Newton)插值多项式插值多项式 )()()()()(110102010nnnxxxxxxaxxxxaxxaaxN 的系数的系数 可根据插值条件推出可根据插值条件推出, 即由即由 有有 naaa,10nixfxNiin, 1 , 0)()()()(000 xfaxNn)()()(101101xfxxaaxNn)()()()(21202201102xfxxxxaxxaaxNn )()()()()(1100110nnnnnnnnxfxxxxxxaxxaaxN这是关于这

36、是关于 的下三角方程组的下三角方程组, ,可以求得可以求得 naaa,10)(00 xfa 10010101011,)()()()()(xxfxxxfxfxxaxfa2101210201202021022,)(,)()()()(xxxfxxxxfxxfxxxxxxaxfxfa一般，用数学归纳法可证明一般，用数学归纳法可证明 ), 1 , 0(,10nkxxxfakk所以所以n n次牛顿插值公式为次牛顿插值公式为 )()(,)(,)()(110100100nnnxxxxxxxxxfxxxxfxfxN其其 余项余项 )()(,)(1010nnnxxxxxxxxxxfxR（4.19）（4.20）为牛

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

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

39、fx1,x0=f(x0)N(x)例例 12 已知已知 x = 1, 4, 9 的平方根值，求的平方根值，求解：解：7 例例13 已知已知 x=0, 2, 3, 5 对应的函数值为对应的函数值为 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

40、xx xx3 等距节点插值等距节点插值等距节点等距节点 xi+1 - xi = h ，函数在等距节点上的值为函数在等距节点上的值为y0 , y1, , yn ，称，称 yi-1= yi - yi-1为函数为函数f(x) 在在xi-1, xi上的上的一阶（向前）差分一阶（向前）差分。称称 2yi-1= yi - yi-1= yi+1 - 2yi + yi-1为函数为函数f(x) 在在xi-1, xi+1上的上的二阶差分二阶差分。称称 kyi-1= k-1yi - k-1yi-1为函数为函数f(x) 在在xi-1, xi+k-1上的上的 k 阶差分阶差分。 当插值节点等距分布时当插值节点等距分布时

41、, 被插值函数的变化率就可用差被插值函数的变化率就可用差分来表示分来表示, 这时牛顿插值公式的形式更简单这时牛顿插值公式的形式更简单, 计算量更小计算量更小xy y 2y 3y 4yx0y0 x1y1x2y2x3y3x4y4 y0 = y1 y0 y1 = y2 y1 y2 = y3 y2 y3 = y4 y3 2y0 = y1 - y0 2y1= y2 - y1 2y2= y3 - y2 3y0= 2y1 - 2y0 3y1= 2y2 - 2y1 4y0 y0= y1 y0 y1= y2 y1 y2= y3 y2= y2 2y1 +y0 2y0= y1 - y0 3y0= 2y1 - 2y0

42、= y3 2y2 +y1 (y2 2y1 +y0)= y3 3y2 +3y1 y0 2y1= y2 - y1= y3 2y2 +y1(a-b)3=a3-3a2b+3ab2-b3(a-b)2=a2-2ab+b2 4y0= 3y1 - 3y0= y4 3y3 +3y2 y1 -(y3 3y2 +3y1 y0 )= y4 4y3 +6y2 4 y1 +y0 (a-b)4=a4-4a3b+6a2b2-4ab3+b3结论：各阶差分中函数值的系数正好等于结论：各阶差分中函数值的系数正好等于 ( (a-b)a-b)r r展开式中的系数展开式中的系数等距节点情况下等距节点情况下xi= x0+ih ，用差分表示

43、差商：用差分表示差商：010110,xxxfxfxxf =y1 y0h= y01!hfx1 , x2=y2 y1h= y11!hfx0,x1,x2=fx1,x2- fx0,x1x2 x0= y11!h y01!h2h= y1- y02h2= 2y02!h2fx1,x2,x3=fx3,x2- fx2,x1x3 x1= y21!h y11!h2h= y2- y12!h2= 2y12!h2fx0,x1,x2 ,x3= 2y12!h2 2y02!h23h= 2y1 - 2y02*3h3= 3y03!h3001,.,!nnnyf x xxn h例例14 计算计算 f (x) = x3在等距节点在等距节点

44、0，1，2，3, 4上的各上的各 阶差分值阶差分值xy y 2y 3y001128327464 4y17193761218660牛顿向前插值公式牛顿向前插值公式取间距为取间距为h, 等距节点等距节点 x0 x1 xn 顺序建立牛顿差商公式顺序建立牛顿差商公式,.,).()(,.,).()(.,)(,)()()(01100111001210000 xxxxfxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxfnnnnnn fx0 , x1= y01!hfx0,x1,x2= 2y02!h2fx0,x1,x2 ,x3= 3y03!h3Nn(x)=y0+(x-x0) y01!h+(x-x

45、0)(x-x1) 2y02!h2+ (x-x0)(x-x1) (x-xn-1) ny0n!hn前插公式前插公式,.,).()(,.,).()(.,)(,)()()(011001110012100100 xxxxfxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxfnnnnnn Nn(x)Rn(x)2300000(1)(1)(2)( )1!2!3!(1).(1).!nntt tt ttP xyyyyt ttnynhxxt0 因因 设设 , ,则则 ihxxi0thxx0), 1 , 0()(nihitxxixy y 2y 3y 4yx0y0 x1y1 y0 x2y2 y1 2y0

46、x3y3 y2 2y1 3y0 x4y4 y3 2y2 3y1 4y00030200!)1).(1(.!3)2)(1(!2)1(!1)(ynntttytttyttytyxPnn 向后差分（略）向后差分（略）函数函数y=f(x), 若记若记y-1=f(x0-h), y-2=f(x0-2h),则各阶向后差分则各阶向后差分一阶一阶 y0= y0- y-1， y1= y1- y0， y2= y2- y1， 二阶二阶 2y0= y0- y-1= y0- y-1- (y-1- y-2 )= y0- 2y-1+ y-2 2y1= y1- y0 = y1- y0- (y0- y-1 ) = y1- 2y0+

47、y-1 K阶阶 ky0= k-1y0- k-1y-1 ky1= k-1y1- k-1y0 同样利用向后差分可以得到牛顿向后插值公式同样利用向后差分可以得到牛顿向后插值公式其中其中 , ,公式公式 称之为牛顿向后插值公式余项。称之为牛顿向后插值公式余项。 nnnnnnnnfnntttfttftfthxNxN!) 1() 1(! 2) 1()()(2hxxtn/ )( nhxxfhnntttxRnn,),()!1()() 1()(0)1(1x-1 012y-11311解：解：建立差分表建立差分表xy y 2y 3y-1-10121320211 866hxxt0 5 .01)1()5 .0( 2*!

48、 15 . 01 0*!2)15.0(5.0 6*!3)25 .0)(15 .0(5 .0 = -1+1+0+0.375 = 0.375例例15 按下列数值表用按下列数值表用牛顿前插公式求牛顿前插公式求y(-0.5) 的近似值的近似值N3(x)002000!) 1() 1(! 2) 1()(fnntttfttftfthxNnn例例16 估计用拉格朗日线性插值法计算估计用拉格朗日线性插值法计算lg47时的误差限时的误差限10100101yxxxxyxxxxy 取取x0=45, x1=48,104548454748454847yyy 106666667. 03333333. 0yy =1.6718

49、98401解：应用拉格朗日线性插值公式解：应用拉格朗日线性插值公式x424548lgx1.62324931.65321261.6812413(1)101( )|( ) | | ()() |(1)!nfRxxxxxn)(lg2110 xxxx ( 45, 48 )1(lg )gexx221lg0.43(lg )()geexxxx 3121 0.43( )|(4745)(4748) |0.22 102 45R x误差限误差限3 3 分段低次插值分段低次插值高次插值的龙格现象高次插值的龙格现象 插值多项式余项公式说明插值节点越多，一般说插值多项式余项公式说明插值节点越多，一般说来误差越小，函数逼近越

50、好，但这也不是绝对的，来误差越小，函数逼近越好，但这也不是绝对的，因为余项的大小既与插值节点的个数有关，也与函因为余项的大小既与插值节点的个数有关，也与函数数f( (x) )的高阶导数有关。换句话说，适当地提高插的高阶导数有关。换句话说，适当地提高插值多项式的次数，有可能提高计算结果的准确程度值多项式的次数，有可能提高计算结果的准确程度，但并非插值多项式的次数越高越好。当插值节点，但并非插值多项式的次数越高越好。当插值节点增多时，不能保证非节点处的插值精度得到改善，增多时，不能保证非节点处的插值精度得到改善，有时反而误差更大。考察函数有时反而误差更大。考察函数 考察函数考察函数 55,11)(

51、2xxxf右图给出了右图给出了和和 的图像的图像, ,当当n增大时增大时, , 在两端在两端会发出激烈的振荡会发出激烈的振荡, ,这就是所谓龙格现这就是所谓龙格现象。该现象表明象。该现象表明, ,在在大范围内使用高次大范围内使用高次插值插值, ,逼近的效果往逼近的效果往往是不理想的往是不理想的 y P10(x) f(x) P5(x) -5 0 5 x )(5xP)(10 xP)(xPn 另外，从舍入误差来看，高次插值误差的传播另外，从舍入误差来看，高次插值误差的传播也较为严重，在一个节点上产生的舍入误差会在计也较为严重，在一个节点上产生的舍入误差会在计算中不断扩大，并传播到其它节点上。因此，次

52、数算中不断扩大，并传播到其它节点上。因此，次数太高的高次插值多项式并不实用，因为节点数增加太高的高次插值多项式并不实用，因为节点数增加时，计算量增大了，但插值函数的精度并未提高。时，计算量增大了，但插值函数的精度并未提高。为克服在区间上进行高次插值所造成的龙格现象，为克服在区间上进行高次插值所造成的龙格现象，采用分段插值的方法采用分段插值的方法，将插值区间分成若干个小的，将插值区间分成若干个小的区间，在每个小区间进行线性插值，然后相互连接区间，在每个小区间进行线性插值，然后相互连接，用连接相邻节点的折线逼近被插函数，这种把插，用连接相邻节点的折线逼近被插函数，这种把插值区间分段的方法就是分段线

53、性插值法。值区间分段的方法就是分段线性插值法。 1 1 分段线性插值分段线性插值 分段线性插值就是通过插值节点用折线段连接起分段线性插值就是通过插值节点用折线段连接起来逼近来逼近f( (x) )。 设设f(x)f(x)在在n+1n+1个节点个节点 上的函数值为上的函数值为 , ,在每个小区间在每个小区间 ( (k=0,1,k=0,1,，n n）上作线性插值，得上作线性插值，得 bxxxan10)(,),(),(10nxfxfxf1,kkxx111111( )( )()()kkkkkkkkkkxxxxL xf xf xxxxxxxx 0101010110211212122111111( )( )

54、 ()( )( ) ()( )()( ) ()nnnnnnnnnnx xx xf xf xxxxxxxxx xx xf xf xxxxxxxxS xx xx xf xf xxxxxxxx y y=f(x) 0 x0 x1 x2 xn x 在几何上就是用折线在几何上就是用折线替代曲线替代曲线, ,如右图所示。如右图所示。 若用插值基函数表示若用插值基函数表示, ,则在则在 a, ,b 上上 )()()()(0bxaxfxlxSinii11111111,0,)(iiiiiiiiiiiiixxxbaxxxxxxxxxxxxxxxxl其中其中显然，显然， 是分段线性连续函数，且是分段线性连续函数，且

55、称称S S( (x x) )为为f f( (x x) )的的分段线性插值函数。分段线性插值函数。由线性插值的余项估计式知由线性插值的余项估计式知, ,f f( (x x) )在每个子段在每个子段上有误差估计式上有误差估计式其中其中 )(xlikikixlki, 0, 1)(1,iixx)(max8)()(12xfhxSxfiixxxi iiixxh1例例17 17 已知已知f(x)f(x)在四个节点上的函数值如下表所示在四个节点上的函数值如下表所示 ix)(ixf 30 45 60 902122231求求f(x)f(x)在区间在区间 30,9030,90 上的上的分段连续线性插值函数分段连续线

56、性插值函数S(x)S(x) 解解 将将插值区间插值区间 30,9030,90 分成连续的三个小区间分成连续的三个小区间 30,4530,45 , , 45,6045,60 , , 60,9060,90 则则S(x)在区间在区间 30,4530,45 上的上的线性插值为线性插值为 2233012)()()(10100101xxfxxxxxfxxxxxSS(x)在区间在区间 45,6045,60 上的上的线性插值为线性插值为 323223023)()()(21211212xxfxxxxxfxxxxxSS(x)S(x)在区间在区间 60,9060,90 上的线性插值为上的线性插值为 22336032

57、)()()(32322323xxfxxxxxfxxxxxS将各小区间的将各小区间的线性插值函数连接在一起，得线性插值函数连接在一起，得 906022336032604532322302345302233012)(xxxxxxxS2 2 三次样条插值三次样条插值 高次插值不仅计算复杂高次插值不仅计算复杂, ,而且可能出现而且可能出现RungeRunge现象现象. . 采用分段插值虽然计算简单、也有一致收敛性采用分段插值虽然计算简单、也有一致收敛性, ,但不能保但不能保证整条曲线在连接点处的光滑性证整条曲线在连接点处的光滑性: : 如分段线性插值如分段线性插值, ,其图形是锯齿形的折线其图形是锯齿

58、形的折线, ,虽然连续虽然连续, ,但插但插值节点处都是值节点处都是“尖点尖点”, ,因而一阶导数都不存在因而一阶导数都不存在, ,这在实用上这在实用上, ,往往不能满足某些工程技术的高精度要求。往往不能满足某些工程技术的高精度要求。 生产中生产中如船体、飞机等外形曲线的设计中如船体、飞机等外形曲线的设计中不仅要求不仅要求曲线连续曲线连续, ,而且要有二阶光滑度而且要有二阶光滑度, ,即有连续的二阶导数。这就即有连续的二阶导数。这就要求分段插值函数在整个区间上具有连续的二阶导数要求分段插值函数在整个区间上具有连续的二阶导数。 定义定义5 5 .设函数定义在区间设函数定义在区间 a a, b b

59、 上，给定上，给定n+1n+1个个 节点和一组与之对应的函数值，若函数节点和一组与之对应的函数值，若函数 满足满足: : （1 1）在每个节点上满足）在每个节点上满足 S( S(xi i)=)=f( (xi i)(i=0,1,)(i=0,1,n),n) （2 2）在）在 a a, b b 上有连续的二阶导数上有连续的二阶导数 （3 3）在每个小区间）在每个小区间 xi i, ,xi+1i+1 (i=0,1,(i=0,1,n-1),n-1) 上是一个三次多项式。上是一个三次多项式。 则称则称S(S(x) )为为三次样条插值函数三次样条插值函数。 其中四个待定系数为其中四个待定系数为 ；子区间共有

60、；子区间共有n个，个，所以要确定所以要确定S(S(x) )需要需要4n个待定系数。个待定系数。 另一方面另一方面, ,要求分段三次多项式要求分段三次多项式S(S(x) )及其导数及其导数 和和 在整个插值区间在整个插值区间 a,ba,b 上连续上连续, ,则要求它们在各个子则要求它们在各个子区间的连接点区间的连接点 上连续，即满足条上连续，即满足条件件 由样条函数的定义可知由样条函数的定义可知, ,三次样条插值函数三次样条插值函数S(S(x) )是一是一个分段三次多项式个分段三次多项式, ,要求出要求出S(S(x),),在每个小区间在每个小区间 xi i, ,xi+1i+1 上上要确定要确定4