第1节课 第一章 插值法拉格朗日插值 分段插值

1、第一章 插值方法李书杰合肥工业大学 计算机学院 提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值插值的基本概念插值的基本概念例例. 某地区某年夏季时节间隔某地区某年夏季时节间隔 30 天的日出日落时天的日出日落时间为间为 5月月1日日 5月月31日日 6月月30日日日出日出 5：51 5：17 5：10日落日落 19：04 19：38 19：50任意一天的日照时间？任意一天的日照时间？日照时间的变化设为日照时间的变化设为 y(x)=a0+ a1x + a2x2,6614616135143131211322102210210.)(.)(.aaaaaaaaa什么是插值什么是插值? 插值法是函

2、数逼近的一种简单但又十分重要的方法，实际中，f(x)是复杂多样的，通常只能观测到一些离散数据；或者f(x)过于复杂而难以运算。这时我们要用近似函数 (x)来逼近f(x)。 自然地，希望(x)通过所有的离散点x3x4x(x) f(x)x0 x1x2定义定义1:函数函数y=f(x)给出一组函数值给出一组函数值 nixfyii, 1 , 0),( x: x0 x1 x2 xny: y0 y1 y2 yn其中其中x0 ,x1,x2 ,xn是区间是区间a,b上的互异点上的互异点,要在函数类要在函数类中中求一个简单的函数求一个简单的函数(x)作为作为f(x)的近似表达式。的近似表达式。使满足使满足 niy

3、xii, 1 , 0,)( (插值原则、插值条件插值原则、插值条件 ) 这类问题称为这类问题称为插值问题插值问题。 )(x -f(x)的的插值函数插值函数; f(x) -被插值函数被插值函数;x0 ,x1,x2 ,xn -插值节点插值节点; 求插值函数的方法称为求插值函数的方法称为插值法插值法。 若若xa,b,需要计算需要计算f(x) 的近似值的近似值(x),则称则称x为为插值点插值点。 函数类函数类 -插值函数类插值函数类;一、定义：一、定义：当选择代数多项式作为插值函数类时，称为代数多项当选择代数多项式作为插值函数类时，称为代数多项式插值问题式插值问题: 代数多项式插值问题代数多项式插值问

4、题: 设函数设函数y=f(x)在在a,ba,b有定义有定义, , 且已知在且已知在n+1n+1个点个点ax0 x1xnb上的函数值上的函数值y0, y1,yn.,要求一要求一个次数不高于个次数不高于n n的多项式的多项式 nnnxaxaxaaxP 2210)(使满足插值原则使满足插值原则 niyxPiin, 1 , 0,)( 称称Pn(x)为为f(x)的的n次插值多项式次插值多项式。 这样的插值多项式是否存在、唯一？这样的插值多项式是否存在、唯一？ 设设 Pn (x)=a0 + a1x + a2x2 + + anxn是是y=f(x)在在a,b上的上的n+1个互异节点个互异节点x0,x1,xn的

5、插值多的插值多项式，则求项式，则求Pn (x)问题归结为求系数问题归结为求系数a0,a1,an。nnnnnnnnnyxaxaayxaxaayxaxaa101111000010故故Pn (x)存在且唯一。存在且唯一。njinjinnnnnnnxxxxxxxxxxxxxxV121211020010)(111),()(jixxji提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值拉格朗日插值线性插值抛物插值一般情形给定插值节点给定插值节点 x0, x1， y0=f(x0)，y1=f(x1).求线性插值多项式求线性插值多项式L1 (x)=a0+ a1x，使满足，使满足: L1(x0)=y0 , L

6、1(x1)=y1.)()(0010101xxxxyyyxL001110101yxxxxyxxxxxL)(可以看到，可以看到， L1 (x)是由两个线性函数是由两个线性函数01010110 xxxxxlxxxxxl)(,)(11001)()()(yxlyxlxL的线性组合得到，其系数分别为的线性组合得到，其系数分别为y0， y1。即。即kjkjxljk01)(l0 (x)及及l1 (x) 在节点在节点x0,x1上满足条件：上满足条件：l0(x0)=1 , l0(x1)=0.l1(x0)=0 , l1(x1)=1.称称l0 (x)及及l1 (x)为线性插值为线性插值基函数基函数。(j,k=0,1)

7、即即 n=1时的时的一次基函数一次基函数为为: 0 x1xy1 O x)(0 xl y 10 x1x)(1xlO x.)(,)(01011010 xxxxxlxxxxxl l0(x0)=1 , l0(x1)=0 , l0(x2)=0.l1(x0)=0 , l1(x1)=1 , l1(x2)=0.l2(x0)=0 , l2(x1)=0 , l2(x2)=1.满足上式的插值基函数很容易求出。满足上式的插值基函数很容易求出。kjkjxljk01)()(12010 xxxxC)()()(2010210 xxxxxxxxxl故故如求如求l0(x): 因因x1, x2 为其零点，故可表为为其零点，故可表为

8、)()(210 xxxxCxl)()()(2101201xxxxxxxxxl同理同理显然显然 L2(x)=l0(x)y0+l1(x)y1+l2(x)y2 满足条件满足条件L2(xj)=yj (j=0,1,2)()()(1202102xxxxxxxxxl2120210121012002010212yxxxxxxxxyxxxxxxxxyxxxxxxxxxL)()()()()()()(1200102()()( ),()()xxxxlxxxxx n=2时的时的二次基函数二次基函数为为 : 0211012()()( ),()()xxxxlxxxxx 0122021()()( ).()()xxxxlxxx

9、xx 设有设有n+1个互异节点个互异节点x0 x1xn，且，且yi = f(xi)(i=0,1,2,n)构造构造Ln (x)，使，使 Ln (xj)= yj (j = 0,1,2,n)kjkjxljk01)(一般情形一般情形(xj)=0(j k)知知=(x-)(x-)(x-)(x-) (x-) 其中其中为待定系数。为待定系数。 再由再由 (xk)=1有有=(-) (-)(-)(-)(-) 由由0111()()()()kkkkkkknAxxxxxxxx 从而得从而得Lxlx ylx ylx ynnn( )( )( )( )0011nkiiikikxxxxxl0)()()()()()()()()(

10、)(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxlx0 ,x1,xn上的值分别为上的值分别为y0 ,y1,ynLxlx ylx ylx ynnn( )( )( )( )0011)()()()()()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxln=1时时,线性插值线性插值n=2时时,二次插值二次插值或或抛物插值抛物插值11001)()()(yxlyxlxL2001122( )( )( )( )Lxlx yl x ylx y取取x0=4, y0=2，x1=9, y1=3 ，x2=16, y2=4.416, 39, 24734942949)(1

11、xxxL6251347537952771.)()()(L4) 916)(416() 97)(47(3)169)(49()167)(47(2)164)(94()167)(97()7(72L6286. 2)6458. 27( 取取x0=4, x1=9, x2=16（2）抛物插值：抛物插值：4, 3, 1, 13210 xxxx)4)(3)(1(401)41)(31)(11()4)(3)(1()(0 xxxxxxxl)4)(3)(1(121)41)(31)(11()4)(3)(1()(1 xxxxxxxl)4)(1)(1(81)43)(13)(13()4)(1)(1()(2 xxxxxxxl)3)(

12、1)(1(151)34)(14)(14()3)(1)(1()(3 xxxxxxxl例例2 求过点求过点(- -1,- -2), (1,0), (3,- -6), (4,3)的三次插值多项式的三次插值多项式解解 以以以为节点的基函数以为节点的基函数分别为分别为:)()()()()(332211003xlyxlyxlyxlyxL ) 3)(1)(1(1513)4)(1)(1(81)6()4)(3)(1(1210)4)(3)(1(401) 2( xxxxxxxxxxxx)3)(1)(1(51)4)(1)(1(43)4)(3)(1(201 xxxxxxxxx3423 xx()则拉格朗日则拉格朗日的三次

13、插值多项式为的三次插值多项式为0 01 10( )( )( )( )( )nnn ni iiL xy lxy l xy lxy l x 使其满足使其满足利用拉格朗日基函数利用拉格朗日基函数l i(x), 构造次数构造次数不超过不超过n的多项式的多项式njyxLjjn, 1 , 0)( )()(xLxPnn 称为称为拉格朗日插值多项式拉格朗日插值多项式。由插值多项式的唯一性由插值多项式的唯一性,得得 特别地特别地, 当当 n =1时又叫时又叫线性插值线性插值,其几何意义为其几何意义为过两点的直线过两点的直线. 当当 n =2时又叫时又叫抛物（线）插值抛物（线）插值, 其几其几何意义为过三点的抛物

14、线何意义为过三点的抛物线.注意注意 :(1)对于插值节点对于插值节点,只要求它们互异只要求它们互异,与大小次序无关与大小次序无关;(2) 插值基函数插值基函数l i(x) 仅由插值节点仅由插值节点xi (i=0,1, ,n)确定确定, 与被插函数与被插函数 f(x)无关无关;(3) 插值基函数插值基函数l i(x) 的顺序与的顺序与插值节点插值节点xi (i=0,1, ,n) 的顺序一致的顺序一致.提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值逐步插值逐步插值 拉格朗日插值公式拉格朗日插值公式 计算函数的近似值计算函数的近似值 若对原先选定的若对原先选定的n+1个节点所得结果精度不够，

15、个节点所得结果精度不够， 需要需要增加节点增加节点 怎么办怎么办？ 给定区间给定区间a, ,b上上一组插值节点一组插值节点 (r =0,1, ,k)0ix1 ixikx 0 1i iikxP0 1i iikiriryxP 1 20 1(1)00 10i iiki ii kiiki iikikixxxxxxxPPPxxNeville算法算法 算法步骤如下表算法步骤如下表 K=0 1 2 3= 23121312331xxxxxxxPPPxxAitken算法算法 算法步骤如下表算法步骤如下表= 01(1)(1)0101(1)(1)1rrktktrttkrxxxxxPPxxxxP提纲插值的基本概念拉格

16、朗日插值逐步插值插值余项分段插值定理定理 设设 f(x)在在a,b上具有上具有n阶连续导数阶连续导数, 且且 f (n+1)(x) 存在存在,节点节点a x0 x1xnb， Ln (x)是满足条件是满足条件Ln (xj)= yj (j = 0,1,2,n)的插值的插值多项式，则对任何多项式，则对任何x a,b，插值余项，插值余项)()!1()()()()(1)1(xnfxLxfxRnnnn,ba)()()(101nnxxxxxxx插值余项插值余项证明：证明： 因为因为)()()(xLxfxRnn上显然在插值节点为), 1 , 0(nixi)()()(iniinxLxfxRni, 1 , 0,0

17、.1,)(个零点个零点上至少有上至少有在在因此因此 nbaxRn设设其中其中)()()(1xxKxRnn),()()(101nnxxxxxxx 为待定函数)(xK)()()()()(1xxKxLxfxRnnn)()()()(1xxKxLxfnn0)()()()()(1txKtLtftnn若引入辅助函数)(x则有0的区别的区别与与注意注意xt)(ix且)()()(1ininxxKxR0即个零点上至少有在区间若令因此,2,)(,nbatxxi,0)(xni, 1 , 0nixi, 2 , 1 , 0,0)(.)(,)(,)()(1也可微也可微则则可微可微因此若因此若为多项式为多项式和和由于由于tx

18、fxxLnn )()()()(1xxKxLxfnn)()()()(1ininixxKxLxf根据Rolle定理,;1),()(个零点个零点上有至少上有至少在区间在区间 nbat 再由Rolle定理,;),()(个零点个零点上有至少上有至少在区间在区间nbat 依此类推，.1)(,),(导数为零导数为零阶阶的的使得使得内至少有一个点内至少有一个点在区间在区间 ntba 0)()1(n)()1(tn)()()()()(1txKtLtftnn)()()()()1(1)1()1(txKtLtfnnnnn由于)()()()()()1(1)1()1()1(nnnnnnxKLf因此)!1()()()1(nx

19、Kfn0)!1()()()1(nfxKn)()()(1xxKxRnn)()!1()(1)1(xnfnn所以1)1()(maxnnbxaMxf)()!1()(11xnMxRnnn 当当 f(x) 是是n次的多项式时次的多项式时, Ln(x)= f(x)。即。即n次次多项式的多项式的n次插值函数即为该次插值函数即为该n次多项式本身。次多项式本身。)()(21)()(21)(1021xxxxfxfxR ),(10 xx)()()(61)(2102xxxxxxfxR ),(20 xx例例:225,169,144,)(三个节点为若xxf线性插值的余项为设LagrangexR)(1插值的余项为二次Lagr

20、angexR)(2解解:.)175(值的截断误差值的截断误差近似近似线性和二次插值做线性和二次插值做试估计用试估计用fLagrangexxf21)(2341)( xxf2583)( xxf|)(|max2251692xfMx |)169(| f 41014. 1|)(|max2251443xfMx |)144(| f 61051. 1|)(|22xN|)225175)(169175(|300|)(|33xN|)225175)(169175)(144175(|9300|)(|1xR22! 21NM3001014. 121421071. 1|)(|2xR33! 31NM93001051. 1616

21、31035. 2误差更小。二次插值比线性插值的用时在求从以上分析可知Lagrange,175,25. 0)4(, 4 . 0)5 . 2(, 5 . 0)2(210 fyfyfy)45 . 2)(25 . 2()4)(2(4 . 0)42)(5 . 22()4)(5 . 2(5 . 0)(2 xxxxxL)5 . 24)(24()5 . 2)(2(25. 0 xx15. 1425. 005. 02 xx,1)(xxf ，节点节点4, 5 . 2, 2210 xxx)(xf求求的抛物插值多项式的抛物插值多项式,且计算且计算f (3)的近似值并估计误差。的近似值并估计误差。例例2 设设解解 插值多

22、项式为插值多项式为,6)(4xxf 83| )2(| )(|max4, 23 fxfMx21 3|(3)| |(3)(3)|(32)(32.5)(34)|6 80.03125RfL 因为因为故故| )4)(5 . 2)(2( |8361| )4)(5 . 2)(2( |!3| )(|33 xxxxxxMxR325. 0)3()3(2 Lf于是于是用二次插值计算用二次插值计算ln11.25ln11.25的近似值的近似值, ,并估计误差并估计误差. .例例3 给定函数表给定函数表x10111213lnx 2.302585 2.3978952.484907 2.564949解解 取节点取节点x x0

23、 0=10,x=10,x1 1=11,x=11,x2 2=12,=12,作二次插值有作二次插值有302585. 2)1210)(1110()1225.11)(1125.11( 397895. 2)1211)(1011()1225.11)(1025.11( 484907. 2)1112)(1012()1125.11)(1025.11( 420426. 2 ln11.25ln11.25 L L2 2(11.25)(11.25)在区间在区间10,1210,12上上lnx lnx 的三阶导数的上限的三阶导数的上限M M3 3=0.002,=0.002,可得误差估计式可得误差估计式00007. 0| )

24、1225.11)(1125.11)(1025.11( |! 3)25.11(32 MR实际上实际上,ln11.25=2.420368,ln11.25=2.420368, |R |R2 2(11.25)|=0.000058.(11.25)|=0.000058.事后误差估计 一般直接应用余项公式来估计误差是困难的，常采用一种事后估计法。 设x0 xx1x2,且f(xi)(i=0,1,2)已知，若将用x0,x1两点作线性插值所求得y的近似值记为y1，将用x0,x2两点作线性插值所求得y的近似值记为y2，则由余项公式知：()()()!()()()!fyyxxxxfyyxxxx 1101220222 得

25、：假设()()ff 12 ()()yyxxyyxxxxyyyyxxxxyyyyxx 1122112121112121即 这表明可以通过两个结果的偏差y2-y1来估计插值误差y-y1。这种直接利用计算结果来估计误差的方法，称为事后事后估计法。估计法。00847.0)71428.1068182.10(1211441211151151 y事后估计法算例分析事后估计法算例分析为节点为节点,求得近似值为求得近似值为:121,10010 xx71428.101y用用 为节点为节点,求得近似值为求得近似值为:02100,144xx68182.102y按照估计式有按照估计式有用用115121,10010 xx

26、用用121,10010 xx用用例：求例：求的近似值。的近似值。提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值高次插值的病态性质：高次插值的病态性质：对于一个确定的区间，如果插值节点之间的距对于一个确定的区间，如果插值节点之间的距离较小，自然插值节点就增多，如果用一个多离较小，自然插值节点就增多，如果用一个多项式插值，自然次数就会升高，也就是说要用项式插值，自然次数就会升高，也就是说要用高次多项式插值。高次多项式插值。但是否次数越高，插值多项式的逼近效果越但是否次数越高，插值多项式的逼近效果越好呢？好呢？20世纪初，世纪初，Runge就给出了一个等距节点插值就给出了一个等距节点插值多项

27、式不收敛的例子。多项式不收敛的例子。211)(xxf5 10(0,1, )kkxknn 1201( )1( )1()()nnnjjjnjxL xxxxxn20.1379310.759615-0.6216844 0.066390-0.3568260.42321660.0544630.607879-0.55341680.049651-0.8310170.880668100.0470591.578721-1.531662120.045440-2.7550002.800440140.0443345.332743-5.288409160.043530-10.17386710.217397180.0429

28、2020.123671-20.080751200.042440-39.95244939.994889下表列出了下表列出了n=2,4,20的的Ln(xn-1/2)和和R(xn-1/2)的值：的值：1/2()nf x1/2()nnL x1/2()nR x取取xk=-5+k 计算计算: f(xk) (k=0,1,10) 构造构造L10(x).取取:tk=-5+0.05k (k=0,1,200),计算计算: L10(tk)-5-4-3-2-1012345-0.500.511.52L10(t) f(t) f(x)()()(11)(1xlyxlyxLkkkkk11kkkkxxxxykkkkxxxxy11)

29、(1xLnnnxxxxLxxxxLxxxxL1)1(121)1(110)0(1)()()(iiyxL)(1为插值点设*xx 1*kkxxx若*)(*1xLy 则*)()(1xLk11*kkkkxxxxykkkkxxxxy11*0*xx 若*)(*1xLy 取*)()0(1xL1010*xxxxy0101*xxxxynxx *若*)(*1xLy 取*)()1(1xLnnnnnxxxxy11*11*nnnnxxxxy内插外插外插-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.6

30、0.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81的图象分段线性插值)(1xLy 的一条折线实际上是连接点niyxkk, 1 , 0,),( )()(lim10 xfxLh上连续在若,)(baxf)()!1()(1)1(xnfnn)()()(xLxfxRnn)()()(11xLxfxR)()()(1xLxfk)(2)(1 kkxxxxf有关与且xxxxkk,1| )(

31、|max| )(|max21)(11 kkkbxabxaxxxxxfxR224121hM 2281hM)()()()(1111)(2xlyxlyxlyxLkkkkkkk)()(11111kkkkkkkxxxxxxxxy1,2 , 1nk)()(2xLk)()(1111kkkkkkkxxxxxxxxy)()(11111kkkkkkkxxxxxxxxy)()!1()(1)1(xnfnn)()()(xLxfxRnn)()()(22xLxfxR)()()(2xLxfk)()(6)(11 kkkxxxxxxf有关与且xxxxkk,11|)(|2xR| )()( |max| )(|max611111 kkkkxxxbxaxxxxxxxfkk3393261hM 33273hM由于由于那么分段二次插值那么分段二次插值L2(x)的余项为：的余项为：)(.1 . 1 ,98. 0 ,75. 0 ,42. 0 ,36. 0)(用分段线性、二次插值用分段线性、二次插值处的近似值处的近似值在在求求 xxf18885. 187335. 069675. 057815. 041075. 030163. 005. 180. 065. 055. 040. 030.