计算方法第三章(插值法)

1、第三章第三章 插值法插值法第一节第一节 插值多项式的基本概念插值多项式的基本概念假设已经获得假设已经获得n+1点上的函数值点上的函数值即提供了一张数据表即提供了一张数据表 如何利用这张表求如何利用这张表求 f (x) 在在其他给定点上的合其他给定点上的合理的近似值呢理的近似值呢? ,0,1, ,iif xy inx0 x1x2xnx yf x0y1y2yny 在实验数据的处理、难以计算的函数的逼近、在实验数据的处理、难以计算的函数的逼近、数值微积分等方面需要解决这样的问题，这是数值微积分等方面需要解决这样的问题，这是数值逼近中的一个基本问题。一个自然的想法数值逼近中的一个基本问题。一个自然的想

2、法是找一个简单易计算的函数是找一个简单易计算的函数 x)，使得，使得()(0,1, )iixyin将将(x)作为作为 f (x) 在一定范围内的近似函数，对于在一定范围内的近似函数，对于这个范围内的某个给定点这个范围内的某个给定点a，取，取 f (a) (a)。这种。这种近似方法称为近似方法称为插值法插值法。(x)称为称为 f (x)的以的以xi (i=0,1,n)为插值节点的为插值节点的插值函数插值函数。插值节点上。插值节点上所给的函数值称为所给的函数值称为样本值样本值。(xi)=yi 称为称为插值条件插值条件。函数值待求的点称为函数值待求的点称为插值插值点点。插值节点所界定的范围称为。插值

3、节点所界定的范围称为插值区间插值区间。如。如果所给插值点位于插值区间之内，这种插值过程果所给插值点位于插值区间之内，这种插值过程称为称为内插内插，否则称为，否则称为外插外插。 若用多项式来作为插值函数，则称其为若用多项式来作为插值函数，则称其为插值插值多项式。多项式。通常用通常用 n 次多项式作为次多项式作为n+1个插值条件个插值条件的插值多项式。如果插值条件只是给出节点的函的插值多项式。如果插值条件只是给出节点的函数值，称为数值，称为拉格朗日插值拉格朗日插值，如果既有函数值也有，如果既有函数值也有节点处函数的导数值，称为节点处函数的导数值，称为埃尔米特插值埃尔米特插值。因式定理：多项式因式定

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

5、差为则插值截断误差为01(1)011( )( )( )( )( )(1)!( )() ()()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 ttxtxtxf tP txxxxxx值得注意

6、的是在较大区间上进行插值时，误差可能会值得注意的是在较大区间上进行插值时，误差可能会很大！另外，一般情况下，外推不如内插好！很大！另外，一般情况下，外推不如内插好！第二节第二节 Lagrange插值公式插值公式插值条件是插值条件是0011(,),( ,),(,)nnxyx yxyLagrange插值实质上是求通过上面插值实质上是求通过上面n+1 个点的个点的 n 次多项式。次多项式。一次插值：一次插值：问题为求一次多项式，即一次函数，过以下问题为求一次多项式，即一次函数，过以下两点：两点：容易求出，该函数为：容易求出，该函数为：0011(,), ( ,)xyx y01010110 xxxxyy

7、yxxxx一般插值问题：求过一般插值问题：求过n+1n+1个点个点的不超过的不超过n n次多项式次多项式 。 称为称为LagrangeLagrange插值基函数，满足：插值基函数，满足：0011(,), ( ,),(,)nnxyx yxy( )nL x0( )( )nniiiL xy l x( )il x1,(),0,ijijijijl xij011011()()()()( )()()()()iiniiiiiiinxxxxxxxxl xxxxxxxxx求过求过n+1n+1个点的不超过个点的不超过n n次多项式的插值多项次多项式的插值多项式是唯一的。式是唯一的。插值公式的误差为：插值公式的误差为

8、：(1)01()( )( )( )()()()(1)!nxnnnfR xf xL xxxxxxxn(1)1 , 101max( )( )()()()(1)!nnxa bnnnMfxMR xxxxxxxn计算程序计算程序框图框图 始 终 输入数据x 及 ,0,1,iix yin 0,0yi 计算权系数i存单元 中 ?iniyyy = 1ii Lagrange 公式的计算流程 第三节第三节 逐次线性插值逐次线性插值函数函数 y = f (x)在节点在节点 上的插值多项上的插值多项式记为式记为 ，则有，则有,ijkx xx, ,( )i jkNx, , , , , , , , , ,( )( )(

9、)( )( )()i jk p qi jk pi jk qi jk ppqpNxL xNxNxNxxxxxAitken（埃特肯）算法埃特肯）算法Neville（列维尔）算法列维尔）算法0,1, ,0,1,0,1,1,0,1,( )( )( )( )( )()k pkkpkkpkNxL 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

10、,2,3( )NxNeville（列维尔）算法列维尔）算法0 x0N1x1N0,1( )Nx2x2N1,2( )Nx0,1,2( )Nx3x3N2,3( )Nx1,2,3( )Nx0,1,2,3( )Nx例子：求方程例子：求方程 x3-2x-5=0 在在(2 , 3)内的根内的根思路思路: 设设 y = f(x) =x3-2x-5 ，其反函数为，其反函数为 x=f -1(y)，则，则根为根为x* =f -1(0) 。先用。先用3= f -1(16)， 2= f -1(-1)插值，得插值，得N0,1 (y) f -1(y), 计算计算N0,1 (0)= 2.058823, f(2.058823)

11、 =-0.39 ，以，以-0.39为新的节点，继续为新的节点，继续yixiNi,i+1 (0)Ni,i+1,i+2 (0) Ni,i+1,i+2,i+3 (0)163-122.058823-0.392.058232.0965892.0956590.0122.0956592.0945292.0945542.0945531.51E-52.094553第四节第四节 牛顿插值牛顿插值设插值点为设插值点为插值多项式形如插值多项式形如称为称为Newton形式的插值多项式。形式的插值多项式。001122(,),( ,),(,),(,)nnxfxfxfxf010201011( )()()()()()()nnn

12、Nxcc xxcxxxxcxxxxxx差商概念：差商概念：设函数设函数 f (x) ，定义函数在两个不同点的一阶差商为定义函数在两个不同点的一阶差商为三个不同点的二阶差商为：三个不同点的二阶差商为：在点在点 处处 K+1 阶差商为：阶差商为：( )()( ,),(,)ijijijijf xf xf x xxxijxx( ,)(,)( ,)ijjkijkikf x xf xxf x xxxx011,kkx xxx011101101(,)( ,)(,)kkkkkkf x xxf xxxf x xxxxx给定给定 n +1个点的函数值个点的函数值00100120101011101011( )()(,

13、)()(,)()()(,)()()()( )( )(,)()()()nnnnnnnNxf xf x xxxf x x xxxxxf x xxxxxxxxNxNxf x xxxxxxxx(),0,1,2,iif xfin（）则牛顿插值公式为：则牛顿插值公式为：差商的计算简表：差商的计算简表：0011012212012332312301234434234123401234( )( )( , )( )( , )( , , )( )( , )( , , )( , , , )( )( , )( , , )( , , , )( , , , , )x f xx f xf x xx f xf x xf x x

14、 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-0.000063556600.8660.010595-0.00010707-0.00000079010.0044658-0.0001362-0.00000049牛顿插值的截断误差：牛顿插值的截断误差：101101( )( )(,)()()()nnnnNxNxf x xxxxxxxx111

15、101110111()()()(,)()()()nnnnnnnnnnf xNxNxf x xxxxxxxx10101( )( )( )(, )()()()nnnnf xNxNxf x xxxxxxxxx0101( )( )( )(, )()()()nnnnRxf xNxf x xxxxxxxxx例子：例子：用用0、90、180、270、360五个点作出五个点作出sinx牛顿插值多项式。牛顿插值多项式。做差商表做差商表009010.011111800-0.01111 -1.235e-4270-1-0.0111104.572e-736000.011111.235e-44.572e-70差商的性质差

16、商的计算公式：差商的计算公式：01000()(,)()( )() ,()()kjkjkjkkkikjjiiiijf xf x xxxxxxxxx通过比较插值多项式的Lagrange形式和Newton形式即可得。()()()()( ,)(,)ijjiijjiijjif xf xf xf xf x xf xxxxxx( ,)(,)( ,)ijkjikikjf x xxf xx xf x xx010101( )( )( ),(,)(,)(,)nnnf xu xv xf x xxu x xxv x xx若则差商的对称性：差商的对称性：差商的线性性：差商的线性性：由于由于n次插值多项式是唯一的，所以牛顿

17、插值公式与次插值多项式是唯一的，所以牛顿插值公式与LagrangeLagrange插值多项式一样，这意味着余项也一样，插值多项式一样，这意味着余项也一样，LagrangeLagrange余项为：余项为：所以牛顿余项也一样，所以牛顿余项也一样，(1)01()( )()()()(1)!nxnnfR xxxxxxxn01101(1)01( )01()()()() ( ,)()()()()(1)!( )(,)!nnnnxnkkxxxxxxxxf x x xxfxxxxxxnff x xxk差商与导数的关系差商与导数的关系重节点差商重节点差商推论：推论：当当n个节点全为同一个点，牛顿插值变成个节点全为同

18、一个点，牛顿插值变成泰勒多项式。泰勒多项式。( )011(,)( )!nnf x xxfn( )00001(,)()!nf x xxfxn差商的导数差商的导数n 次多项式的的次多项式的的 1 阶差商是阶差商是 n-1 次多项式。次多项式。(1)*011011()(, )(, , )(1)!nnndff x xxxf x xxx xdxn推论：设推论：设 p(x) 是是 n 次多项式，次多项式，k n 时时 k 阶差商阶差商是是 n - k 次多项式，次多项式，k n 时时 k 阶差商为零。阶差商为零。00000000( )( )()()0( )() ( )( )()() ( )( )()( ,

19、)( )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,)ifi21, (0,1,2,)iiifffi 111, (0,1,2,)kkkiiifffi 类似地，类似地，向后差分向后差分定义为：定义为：中心差分中心差分定义为：定义为：1, (0,1,2,)iiifffin

20、111, (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第五节第五节 带导数的插值带导数的插值问题的提出：如果在已知节点处不仅知道函数值，问题的提出：如果在已知节点处不仅知道函数值，同时还知道导数同时还知道导数值，这样，插值多项式就要求在值，这样，插值多项式就要求在已知节点处与已知节点处与函数值和导

21、数值都相等函数值和导数值都相等。这就是所。这就是所谓谓埃尔米特（埃尔米特（Hermite）插值）插值。 1、推广牛顿插值法、推广牛顿插值法如果已知如果已知某个点某个点 i 的的 ，则，则插值节点应视为插值节点应视为 个相同节点个相同节点 ，并注意到，并注意到k+1重节点的差商重节点的差商(1),iriiiiy y yyirix( )1( )( ,)!kiiiiikfxf x x xxk 例子：例子：已知关于函数已知关于函数 y = f (x)的函数值、导数值的函数值、导数值0011112211:00:4,0,61:2,5xyxyyyxyy xif(xi) f(xi, xi+1) f(xi, x

22、i+1 ,xi+2)3阶差商阶差商4阶差商阶差商5阶差商阶差商-100-4-40-4040-403-11-222-101-253121(0,0)(0)0(0,0,0)(0)/2!3(1,1)(1)5fyfyfy2、构造基函数法构造基函数法已知函数在已知函数在n个不同的节点处的函数值和导数值：个不同的节点处的函数值和导数值：求次数不超过求次数不超过2n-1次的多项式次的多项式设想其具有形式设想其具有形式：要求：要求：,(1,2, )iiixyyin2121( ),( ),(1,2, )niiniiHxyHxyin2111( )( )( )nnnjjjjjjHxy h xy h x( ),( )0

23、,1,2,( )0 ,( ),1,2,jiijjijijiijh 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 x

24、x Wx()1jjh x22()11( )()( )jjjjjCWxCh xxx Wx21112211( )( )( )1 2()()( )()( )nnnjjjjjjnnjjjjjjjjjjHxy h xy h xWxxxWx yxx Wx y特别，当特别，当 n=2 时，三阶埃尔米特多项式为：时，三阶埃尔米特多项式为：311322311322(),(),(),()HxyHxyHxyHxy21231121222122121222111221221( )(1 2)()(1 2)()()()()()xxxxHxyxxxxxxxxyxxxxxxxxxxyxxyxxxx埃尔米特插值公式唯一。埃尔米特

25、插值公式唯一。误差估计：设被插值函数在插值区间上误差估计：设被插值函数在插值区间上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 sinyx223( )()()()xxHxxx如用距离较小的两个点插值，效果会好得

26、多如用距离较小的两个点插值，效果会好得多3333(0)0,(/2)1,(0)1 ,(/2)0HHHH223/2/2( )(12)()()/2/2/2xxxHxx第六节第六节 样条函数样条函数由于被插值函数高阶导数未知，因此，如果高由于被插值函数高阶导数未知，因此，如果高阶导数随阶数增长出现无限增长，则由误差公阶导数随阶数增长出现无限增长，则由误差公式可知，高阶插值公式就不一定无限接近被插式可知，高阶插值公式就不一定无限接近被插值函数。这称为值函数。这称为龙格（龙格（Runge)现象现象。所以，在进行多项式插值时，不宜进行高次多所以，在进行多项式插值时，不宜进行高次多项式插值。项式插值。 一个解

27、决的途径是一个解决的途径是分段低次插值分段低次插值。样条函数：给定区间一个样条函数：给定区间一个划分划分如函数如函数 S(x) 满足下面条件：满足下面条件：（1）在每个小区间）在每个小区间 上为上为m次多项式；次多项式；（2） S(x) 直至直至m1 阶导数在整个区间上连续。阶导数在整个区间上连续。 则称则称 S(x) 是关于该划分的是关于该划分的 m 次次样条函数样条函数，划分点，划分点 称为节点，称为节点，m3 时，就是最常用的时，就是最常用的 3 次样条函数。次样条函数。01 , ,:Na baxxxb1,(1,2,)jjxxjN样条函数插值：样条函数插值：对给定的插值条件，寻找合适的样

28、条对给定的插值条件，寻找合适的样条函数作为插值函数，使其满足插值条件。函数作为插值函数，使其满足插值条件。3次样条插值三弯矩方法的基本思想：次样条插值三弯矩方法的基本思想：将样条函数在每一个子区间端点的二阶导数值当作参将样条函数在每一个子区间端点的二阶导数值当作参数，则用这两个二阶导数值可以将样条函数表示出来，数，则用这两个二阶导数值可以将样条函数表示出来，再利用衔接条件，即每一段样条函数在相邻两个子区间再利用衔接条件，即每一段样条函数在相邻两个子区间端点处的二阶导数相等，建立求解二阶导数的方程组。端点处的二阶导数相等，建立求解二阶导数的方程组。设设S(x)在每个小区间在每个小区间 端点的二阶

29、导端点的二阶导数为：数为：则：则：记记 ， 将上式积分两次，并利用端点函数值已将上式积分两次，并利用端点函数值已知，有：知，有：1,(1,2,)jjxxjN11(),()jjjjSxMSxM1111( )jjjjjjjjxxxxSxMMxxxx3311221111()()( )66()()66,1,2,jjjjjjjjjjjjjjjjjjxxxxS xMMhhMhxxM hxxyyhhxxxjN1jjjhxx我们注意到，在相邻的两个子区间我们注意到，在相邻的两个子区间 和和 的共同端点处，样条函数一阶导数相等，的共同端点处，样条函数一阶导数相等，经过化简，最后得到：经过化简，最后得到：11jj

30、jxxx1,jjxx1,jjxx111111112,1,1,2,1()/()/6jjjjjjjjjjjjjjjjjjjjjMMMdhjNhhyyhyyhdhh 注意到上面的方程组总共只有注意到上面的方程组总共只有 N1个方程，而未知数却共有个方程，而未知数却共有 N +1 个，因此，要求解方程，还需要补充两个条件（即两个个，因此，要求解方程，还需要补充两个条件（即两个方程），通常有以下几种方案之一方程），通常有以下几种方案之一:1、给出端点一阶导数值、给出端点一阶导数值 ，这相当于增加两个方程；，这相当于增加两个方程；2、给定端点二阶导数值，得方程：、给定端点二阶导数值，得方程：特别，令二阶导

31、数在端点为零，得特别，令二阶导数在端点为零，得10010111162()62()NNNNNNNyyMMyhhyyMMyhh0,Nyy00,NNMyMy00 ,0NMM3、样条件函数在第一个和最后一个区间上为二次多项样条件函数在第一个和最后一个区间上为二次多项式，即样条函数在第一和最后一个区间上的二阶导式，即样条函数在第一和最后一个区间上的二阶导数为常数，得两个方程：数为常数，得两个方程： 总之，以上三种补充条件下，可将方程组统一写为：总之，以上三种补充条件下，可将方程组统一写为：011,NNMMMM0001111120202NNNNMdMdMd 4、周期性条件（这只有在给的初值满足、周期性条件（这只有在给的初值满足 时才能用），时才能用），此时，由周期性，此时，由周期性， ，就得到两个，就得到两个方程；第一个方程为方程；第一个方程为 ，第二个方程为，第二个方程为 最后一个方程为：最后一个方程为： 最后，方程组为：最后，方程组为：0Nyy1111,NNyyMM1011211121122NMMMdMMMd0NMM111122NNNNNNNNNNNMMMdMMMd111122221222NNNNNMdMdMd 小结小结多项式插值法，其目的是利用节点上的值，构造通过这些节点多项式插值法，其目的是利用节点上的值，构造通过这些节点的多项式，从原则上说，利用的多项式