计算方法第三章rr

1、第三章第三章 插值法插值法第一节第一节 插值多项式的基本概念插值多项式的基本概念假设已经获得若干点上的函数值假设已经获得若干点上的函数值即提供了一张数据表即提供了一张数据表 如何如何利用这张表求某个给定点上的函数值利用这张表求某个给定点上的函数值呢呢?插值方插值方法所要研究的就是这个课题。法所要研究的就是这个课题。 ,0,1, ,iif xy inx0 x1x2xnx yf x0y1y2yny 通常用多项式来作为近似函数，称为通常用多项式来作为近似函数，称为插值多项式插值多项式。2012( )nnnP xaa xa xa x数据表中的函数值为已知的节点称为数据表中的函数值为已知的节点称为插值节

2、点插值节点，插值节点上所，插值节点上所给的函数值称为给的函数值称为样本值样本值。函数值待求的点称为。函数值待求的点称为插值点插值点。插值节。插值节点所界定的范围称为点所界定的范围称为插值区间插值区间。如果所给插值点位于插值区间。如果所给插值点位于插值区间之内，这种插值过程称为之内，这种插值过程称为内插内插，否则称为，否则称为外插外插。如果插值条件只是给出节点的函数值，称为如果插值条件只是给出节点的函数值，称为拉格朗日插值拉格朗日插值，如，如果既有函数值也有节点处函数的导数值，称为果既有函数值也有节点处函数的导数值，称为埃尔米特插值埃尔米特插值。因式定理：多项式因式定理：多项式P(x)具有具有r

3、 次因式次因式(x-a)r 的充要条件的充要条件是是P(a)=P (a)=P(a)(r-1)=0最一般的插值条件：最一般的插值条件：是是重根，重根，(1)(1)( ),( ),( )iirriiiiiixyxyxy定理：一旦插值条件给定，则插值多项式是唯一的。定理：一旦插值条件给定，则插值多项式是唯一的。irix011mrrrn设函数设函数y =f (x)在闭区间在闭区间a,b 上有上有n +1阶导数，阶导数，满足前面的一般插值条件，且插值节点各不相同，满足前面的一般插值条件，且插值节点各不相同，则插值截断误差为则插值截断误差为01(1)011( )( )( )( )( )(1)!( )()

4、()()mnnnnrrrnmR xf xP xfxnxxxxxxx 01011,mmrrrnx xxx在之间，与 有关证明思路：构造辅助函数，用罗尔定理。证明思路：构造辅助函数，用罗尔定理。33(4)2012( )( )( )1( )() ()()4!R xf xP xfxxxxxx300300311322(),(),( ),()P xy P xy P xy P xy2301223012( )( )( )() ()() ( )( )/() ()()g tf tP txxxxxxf tP txxxxxx值得注意的是在较大区间上进行插值时，误差可能会值得注意的是在较大区间上进行插值时，误差可能会很

5、大！另外，一般情况下，外推不如内插好！很大！另外，一般情况下，外推不如内插好！第二节第二节Lagrange插值公式插值公式插值条件是插值条件是0011(,),( ,),(,)nnxyx yxyLagrange插值实质上是求通过上面插值实质上是求通过上面n+1个点的个点的n次多项式。次多项式。一次插值：一次插值：问题为求一次多项式，即一次函数，过以下问题为求一次多项式，即一次函数，过以下两点：两点：容易求出，该函数为：容易求出，该函数为：0011(,), ( ,)xyx y01010110 xxxxyyyxxxx二次插值：二次插值：问题为求二次多项式，即二次函数，过以下三点：问题为求二次多项式，

6、即二次函数，过以下三点：容易求出，该函数为：容易求出，该函数为：001122(,), ( ,),(,)xyx yxy120010202110120122021()()()()()()()()()()()()xxxxyyxxxxxxxxyxxxxxxxxyxxxx一般插值问题：求过一般插值问题：求过n+1n+1个点个点的不超过的不超过n n次多项式次多项式 。 称为称为LagrangeLagrange插值基函数，满足：插值基函数，满足：0011(,), ( ,),(,)nnxyx yxy( )nL x0( )( )nniiiL xy l x( )il x1,(),0,ijijijijl xij0

7、11011()()()()( )()()()()iiniiiiiiinxxxxxxxxl xxxxxxxxx问题问题: :过过n+1n+1个点的个点的LagrangeLagrange插值多项插值多项式是否唯一？式是否唯一？满足n+1个插值条件的n次多项式是唯一的；满足n+1个插值条件的多项式不是唯一的；插值公式的误差为：插值公式的误差为：(1)01( )( )( )()()()()(1)!nnnxnR xf xL xfxxxxxxn(1)1 , 101max( )( )()()()(1)!nnxa bnnnMfxMR xxxxxxxn计算程序计算程序框图框图 始 终 输入数据x 及 ,0,1,

8、iix yin 0,0yi 计算权系数i存单元 中 ?iniyyy = 1ii Lagrange 公式的计算流程 第三节第三节 逐次线性插值逐次线性插值函数函数 y =f(x)在节点在节点上的插值多项上的插值多项式记为式记为，则有，则有,ijkx xx, ,( )i jkNx, , , , , , , , , ,( )( )( )( )( )()i jk p qi jk pi jk qi jk ppqpNxL xNxNxNxxxxxAitken（埃特肯）算法埃特肯）算法Neville（列维尔）算法列维尔）算法0,1, ,0,1,0,1,1,0,1,( )( )( )( )( )()k pkkp

9、kkpkNxL xNxNxNxxxxx,1,1,11,2,1,1( )( )( )( )( )()i iki ikiiki ikikiNxL xNxNxNxxxxxAitken（埃特肯）算法埃特肯）算法0 x0N1x1N0,1( )Nx2x2N0,2( )Nx0,1,2( )Nx3x3N0,3( )Nx0,1,3( )Nx0,1,2,3( )NxNeville（列维尔）算法列维尔）算法0 x0N1x1N0,1( )Nx2x2N1,2( )Nx0,1,2( )Nx3x3N2,3( )Nx1,2,3( )Nx0,1,2,3( )Nx例子：求方程例子：求方程在在(2,3)内的根内的根思路，用反函数思

10、路，用反函数3250 xxyx163-122.058823-0.392.058232.0965892.0956590.0121.51E-52.0956592.0945532.0945292.0945542.094553第四节第四节 牛顿插值牛顿插值001122(,),( ,),(,),(,)nnxfxfxfxf010201011( )()()()()()()nnnNxcc xxc xxxxxxxxxxc差商差商设函数设函数 f (x)，定义函数在两个不同点的一阶差商为定义函数在两个不同点的一阶差商为三个不同点的二阶差商为：三个不同点的二阶差商为：在点在点处处K+1 阶差商为：阶差商为：( )(

11、)( ,),(,)ijijijijf xf xf x xxxijxx( ,)(,)( ,)ijjkijkikf x xf xxf x xxxx011,kkx xxx011101101(,)( ,)(,)kkkkkkf x xxf xxxf x xxxxx给定给定 n +1个点的函数值，则牛顿插值公式为：个点的函数值，则牛顿插值公式为：00100120101011101011,( ),0,1,2,( )()(,)()(,)()()(,)()()()( )(,)()()()iiinnnnnnnxff xinNxf xf x xxxf x x xxxxxf x xxxxxxxxNxNf x xxxx

12、xxxx差商的计算简表：差商的计算简表：0011012212012332312301234434234123401234()( ) (,)() ( ,) (,)() (,) ( ,) (,)() (,) (,) ( ,) (,)x f xx f xf x xx f xf x xf x x xx f xf x xf x x xf x x x xx f xf x xf x x xf x x x xf x x x x x例子：例子：用用0、30、45、60、90五个点作出五个点作出sinx牛顿插值多项式。牛顿插值多项式。做差商表做差商表00300.50.016667450.70710.013807-

13、0.000063556600.8660.010595-0.00010707-0.00000079010.0044658-0.0001362-0.00000049牛顿插值的截断误差：牛顿插值的截断误差：101101( )(,)()()()nnnnNxNf x xxxxxxxx111101110111()()()(,)()()()nnnnnnnnnnf xNxNxf x xxxxxxxx101101( )( )( )(,)()()()nnnnf xNxNxf x xxxxxxxx01101( )( )( )(,)()()()nnnnR xf xNxf x xxxxxxxx例子：例子：用用0、30、

14、45、60、90五个点作出五个点作出sinx牛顿插值多项式。牛顿插值多项式。做差商表做差商表009010.011111800-0.01111 -1.235e-4270-1-0.0111104.572e-736000.011111.235e-44.572e-70差商的计算公式：差商的计算公式：差商的对称性：差商的对称性：差商的线性差商的线性011000()(,)()( )() ,()()kjkkjkjkkkikjjiiiijf xf x xxxxxxxxxx( )()()( )( ,)ijjiijijjif xf xf xf xf x xxxxx( ,)(,)( ,)ijkjikikjf x x

15、xf xx xf x xx010101( )( )( )(,)(,)(,)nnnf xu xv xf x xxu x xxv x xx由于由于n次插值多项式是唯一的，所以牛顿插值公式与次插值多项式是唯一的，所以牛顿插值公式与LagrangeLagrange插值多项式一样，这意味着余项也一样，插值多项式一样，这意味着余项也一样，LagrangeLagrange余项为：余项为：所以牛顿余项也一样，所以牛顿余项也一样，(1)01()( )()()()(1)!nxnnfR xxxxxxxn01101(1)01( )01()()()() ( ,)()()()()(1)!()(,)!nnnnxnkxkxx

16、xxxxxxf x x xxfxxxxxxnff x xxk差商与导数的关系差商与导数的关系重节点差商重节点差商推论：当推论：当n个节点全为同一个点，牛顿插值变成个节点全为同一个点，牛顿插值变成泰勒多项式。泰勒多项式。( )011(,)( )!nnf x xxfn( )00001(,)()!nf x xxfxn差商的导数差商的导数n次多项式的的次多项式的的1阶差商是阶差商是n-1次多项式。次多项式。(1)*011011()(, )(, , )(1)!nnndff x xxxf x xxx xdxn推论：设推论：设p(x)是是n次多项式，次多项式，kn时时k阶差商是阶差商是n-k次次多项式，多项

17、式，kn时时k阶差商为零。阶差商为零。00000000( )( )()()0( )() ( )( )()() ( )( )()( ,)( )g xp xp xg xg xxx q xp xp xxx q xp xp xp x xq xxx差分差分设函数设函数 ，定义，定义 为该函为该函数在数在 i 点的点的一阶差分一阶差分，记为，记为类似地，定义类似地，定义二阶差分为二阶差分为：K 阶差分为阶差分为：此差分称为此差分称为向前差分向前差分。( )iif xxf在的函数值为1iiff, (0,1,2, )ifin21, (0,1,2,)iiifffi 111, (0,1,2,)kkkiiifffi

18、 类似地，类似地，向后差分向后差分定义为：定义为：中心差分中心差分定义为：定义为：1, (0,1,2,)iiifffin111, (0,1,2,)kkkiiifffi 1/21, (0,1,2,)iiifffin1/21/2, (0,1,2,)iiifffin111/21, (0,1,2,)kkkiiifffi差商与差分的关系：等距节点时差商与差分的关系：等距节点时0/201()()()(,)!nnnnnnnnnf xf xf xf x xxn hn hn h0ixxih第五节第五节 带导数的插值带导数的插值问题的提出：如果在已知节点处不仅知道函数值，问题的提出：如果在已知节点处不仅知道函数值

19、，同时还知道导数同时还知道导数值，这样，插值多项式就要求在值，这样，插值多项式就要求在已知节点处与已知节点处与函数值和导数值都相等函数值和导数值都相等。这就是所。这就是所谓谓埃尔米特插值埃尔米特插值，记为，记为H(x)1、牛顿插值、牛顿插值如果已知如果已知某个点某个点i 的的，则，则插值节点应视为插值节点应视为个相同节点个相同节点，并注意到，并注意到k+1重节点的差商重节点的差商(1),iriiiiy y yyirix( )1( )( ,)!kiiiiikfxf x x xxk 例子：例子：已知关于函数已知关于函数y =f(x)的函数值、导数值的函数值、导数值0011112211,00,4,0

20、,61,2,5xyxyyyxyy -100-4-40-4040-403-11-222-101-253121(0,0)(0)0(0,0,0)(0)/2!3(1,1)(1)5fyfyfy已知函数在已知函数在n个不同的节点处的函数值和导数值：个不同的节点处的函数值和导数值：求次数不超过求次数不超过2n-1次的多项式次的多项式设想该多项式具有形式设想该多项式具有形式：,(1,2, )iiixyyin2121( ),( ),(1,2, )niiniiHxyHxyin2111( )( )( )nnnjjjjjjHxy h xy h x( ),( )0,1,2,( )0 ,( ),1,2,jiijjijij

21、iijh xh xj inh xhxj in由条件可得：由条件可得：此外，由此外，由 得：得：2( )()( )jjh xAxB Wx111111()()()()( )()()()()jjnjjjjjjjnxxxxxxxxW xxxxxxxxx()1 ,()0jjjjh xh x12()2()()012()jjjjjjjjjAxBAWxAAxB WxBx Wx 2( )12()()( )jjjjjh xWxxxWx同理：同理：由由 ，可得：，可得：最后，得到埃尔米特插值公式：最后，得到埃尔米特插值公式：2( )()( )jjjh xC xx Wx()1jjh x22()11( )()( )jj

22、jjjCWxCh xxx Wx21112211( )( )( )1 2()()( )()( )nnnjjjjjjnnjjjjjjjjjjHxy h xy h xWxxxWx yxx Wx y特别，当特别，当 n=2 时，三阶埃尔米特多项式为：时，三阶埃尔米特多项式为：311322311322(),(),(),()HxyHxyHxyHxy21231121222122121222111221221( )(1 2)()(1 2)()()()()()xxxxHxyxxxxxxxxyxxxxxxxxxxyxxyxxxx埃尔米特插值公式唯一。埃尔米特插值公式唯一。误差估计，设被插值函数在插值区间上误差估计

23、，设被插值函数在插值区间上2n次连续可导，次连续可导，则在则在n个节点上的个节点上的2n-1次插值多项式的余项为：次插值多项式的余项为：特别，对于特别，对于2个节点个节点3次插值，余项为：次插值，余项为：2121(2 )212( )( )( )()()()()(2 )!nnnxnRxf xHxfxxxxxxn(4)223312()( )( )( )() ()4!xfR xf xHxxxxx例子：例子：3333(0)0,( )0,(0)1 ,( )1HHHH sin x223( )()()()xxHxxx如用距离较小的两个点插值，效果会好得多如用距离较小的两个点插值，效果会好得多3333(0)0

24、,(/2)1,(0)1 ,(/2)0HHHH223/2/2( )(12)()()/2/2/2xxxHxx第六节第六节 样条函数样条函数由于被插值函数高阶导数未知，因此，如果高阶导数随阶数由于被插值函数高阶导数未知，因此，如果高阶导数随阶数增长出现无限增长，则由误差公式可知，高阶插值公式就不增长出现无限增长，则由误差公式可知，高阶插值公式就不一定无限接近被插值函数。这称为一定无限接近被插值函数。这称为龙格现象龙格现象。所以，在进行多项式插值时，不宜进行高次多项式插值。所以，在进行多项式插值时，不宜进行高次多项式插值。一个解决的途径是一个解决的途径是分段低次插值分段低次插值。样条函数插值：给定区间

25、一个样条函数插值：给定区间一个划分划分如函数如函数 S(x)满足下面条件：满足下面条件：（1）在每个小区间）在每个小区间上为上为m次多项式；次多项式；（2）S(x)及及m1阶导数在整个区间上连续。阶导数在整个区间上连续。则称则称S(x)是关于该划分的是关于该划分的m次次样条函数样条函数，划分点称，划分点称为节点，为节点，m3时，就是最常用的时，就是最常用的3次样条函数。次样条函数。01 , ,:Na baxxxb1,(1,2,)jjxxjN3次样条函数的基本思想：次样条函数的基本思想：将样条函数在每一个子区间端点的二阶导数值当作参将样条函数在每一个子区间端点的二阶导数值当作参数，则用这两个二阶

26、导数值可以将样条函数表示出数，则用这两个二阶导数值可以将样条函数表示出来，再利用衔接条件，即每一段样条函数在相邻两来，再利用衔接条件，即每一段样条函数在相邻两个子区间端点处的二阶导数相等，建立求解二阶导个子区间端点处的二阶导数相等，建立求解二阶导数的方程组。数的方程组。设设S(x)在每个小区间在每个小区间端点的二阶导端点的二阶导数为：数为：则：则：记记，将上式积分两次，并利用端点函数值已知，将上式积分两次，并利用端点函数值已知，有：有：1,(1,2,)jjxxjN11(),()jjjjSxMSxM1111( )jjjjjjjjxxxxSxMMxxxx3311221111()()( )66()(

27、)66,1,2,jjjjjjjjjjjjjjjjjjxxxxS xMMhhMhxxM hxxyyhhxxxjN1jjjhxx我们注意到，在相邻的两个子区间我们注意到，在相邻的两个子区间 和和 的共同端点处，样条函数一阶导数相等，的共同端点处，样条函数一阶导数相等，经过化简，最后得到：经过化简，最后得到：11jjjxxx1,jjxx1,jjxx111111112,1,1,2,1()/()/6jjjjjjjjjjjjjjjjjjjjjMMMdhjNhhyyhyyhdhh 注意到上面的方程组总共只有注意到上面的方程组总共只有 N1个方程，而未知数却共有个方程，而未知数却共有 N 个，因此，要求解方程

28、，还需要两个条件（即两个方个，因此，要求解方程，还需要两个条件（即两个方程），通常有以下几种方案程），通常有以下几种方案:1、给出端点一阶导数值、给出端点一阶导数值 ，这相当于增加两个方程；，这相当于增加两个方程；2、给定端点二阶导数值，得方程：、给定端点二阶导数值，得方程：特别，令二阶导数在端点为零，得特别，令二阶导数在端点为零，得10010111162()62()NNNNNNNyyMMyhhyyMMyhh0,Nyy00,NNMyMy00 ,0NMM3、样条件函数在第一后最后一个区间上为二次多项样条件函数在第一后最后一个区间上为二次多项式，即样条函数在第一和最后一个区间上的二阶式，即样条函数

29、在第一和最后一个区间上的二阶导数为常数，得两个方程：导数为常数，得两个方程：总之，可以将方程组统一写为：总之，可以将方程组统一写为：011,NNMMMM0001111120202NNNNMdMdMd 4、周期性条件（这只有在给的初值满足、周期性条件（这只有在给的初值满足 时才能用），时才能用），此时，由周期性，此时，由周期性， ，就得到两个，就得到两个方程；第一个方程为方程；第一个方程为 ，第二个方程为，第二个方程为最后一个方程为：最后一个方程为：最后，方程组为：最后，方程组为：0Nyy1111,NNyyMM1011211121122NMMMdMMMd0NMM111122NNNNNNNNNNNMMMdMMMd111122221222NNNNNMdMdMd 小结小结插值法，其目的是利用节点上的值，构造通过这些节点的多插值法，其目的是利用节点上的值，构造通过这些节点的多项式，从原则上说，利用项式，从原则上说，利用n+1个节点的值，可以构造个节点的值，可以构造n次多次多项式，而且这种构造是项式，而且这种构造是唯一的唯一的！利用待定系数法，将节点