数值分析牛顿插值法

1、.1 ii i j jiji i l xlb x 1 1 nnnn n n aaa aaa aaa A 21 22221 11211 bAx ni, 3 ,2 2.2.2 Newton插值法插值法 2.2.3 等距节点插值公式等距节点插值公式 .2 )(xl j n ji iij i xx xx 0 )( )( nj,2 , 1 ,0 我们知道,Lagrange插值多项式的插值基函数为 形式上太复杂,计算量很大,并且重复计算也很多 由线性代数的知识可知,任何一个n次多项式都可以表示成 , 1, 0 xx ),)( 10 xxxx)()( 110 n xxxxxx, 共n+1个多项式的线性组合

2、那么，是否可以将这n+1个多项式作为插值基函数呢？ .3 , 1, 0 xx ),)( 10 xxxx)()( 110 n xxxxxx, 显然，多项式组 线性无关， 因此，可以作为插值基函数 , i x设插值节点为( ) ,0,1, ii ff xin函数值为 1,2 , 1 ,0, 1 nixxh iii i i hhmax nifxP ii , 1 , 0,)(插值条件为 )()( )()()( 110 102010 nn xxxxxxa xxxxaxxaaxP 具有如下形式设插值多项式)(xP .4 nifxPxP ii , 1 , 0,)()(应满足插值条件 000) (afxP 有

3、 )()( 011011 xxaafxP 00 fa 01 01 1 xx ff a )()()( 12022021022 xxxxaxxaafxP 12 01 01 02 02 2 xx xx ff xx ff a 再继续下去待定系数的形式将更复杂 为此引入差商和差分的概念 .5 一、差商(均差) 定义1.nifxxf ii , 1 , 0,)(处的函数值为在互异的节点设 称 )(,ji xx ff xxf ji ji ji )(,)(均差一阶差商关于节点为 ji xxxf )( , ,kji xx xxfxxf xxxf jk jiki kji 的二阶差商关于为 kji xxxxf,)(

4、依此类推 .6 , 110kk iiii xxxxf 阶差商的关于节点为kxxxxxf kk iiii ,)( 110 , 110kk xxxxf 差商具有如下性质(请同学们自证)： 且的线性组合表示 可由函数值阶差商的 ,)(,),(),( ,)()1( 10 110 k kk xfxfxf xxxxfkxf 显然 kk kkk ii iiiiiii xx xxxxfxxxf 1 210110 , kk kkk xx xxxxfxxxf 1 210110 , .7 , 110kk xxxxf k i kiiiiii i xxxxxxxx xf 0 110 )()()( )( (2) 差商具有

5、对称性,即任意调换节点的次序,差商的值不变 , 210 xxxf, 120 xxxf, 012 xxxf 如 ,)()3( 10 ) 的区间存在时在包含节点当 （ k k xxxxf 使得之间必存在一点在, 10 k xxx , 10k xxxf 用余项的 相同证明 ! )( )( k f k .8 )( )( )( )( )( )( 44 33 22 11 00 xfx xfx xfx xfx xfx xfx kk 四阶差商三阶差商二阶差商一阶差商 差商的计算方法(表格法): , 10 xxf , 21 xxf , 32 xxf , 43 xxf , 210 xxxf , 321 xxxf

6、, 432 xxxf , 3210 xxxxf , 4321 xxxxf , 410 xxxf 规定函数值为零阶差商 差商表 Chashang.m .9 xifxi fxi,xi+1fxi,xi+1,xi+2 fxi,xi+1,xi+2 ,xi+2 00 28 327 5125 6216 4 02 08 19 23 827 49 35 27125 91 56 125216 5 03 419 10 25 1949 14 36 4991 1 05 510 1 26 1014 例1 求 f(xi)= x3在节点 x=0, 2, 3, 5, 6上的各阶差商 值 解: 计算得如下表 .10 二、Newt

7、on基本插值公式 )()( )()()( 110 102010 nn xxxxxxa xxxxaxxaaxP 设插值多项式 满足插值条件nifxP ii , 1 , 0,)( 则待定系数为 00 fa , 101 xxfa , 2102 xxxfa , 10nn xxxfa .11 )()( )()()( 110 102010 nn n xxxxxxa xxxxaxxaaxN n k k j jk xxxxxff 1 1 0 100 )(, 称 基本插值多项式次的关于节点为Newtonnxxf i )( 定义3. )()()(xNxfxR nn )( )!1( )( 1 )1( x n f n

8、 n 由插值多项式的唯一性,Newton基本插值公式的余项为 n k kk xxxxff 1 100 )(, 1 0 )( k j j xx)(x k 为k次多项式 .12 , 10 xxxxf k , 110 xxxxf k 则视为一个节点若将,), 1 , 0( ,nixx i 因此可得)(,)( 000 xxxxffxf )(,( 0110100 xxxxxxxfxxff )(,)(, 10100100 xxxxxxxfxxxxff n j jn n k k j jk xxxxxxfxxxxxff 0 10 1 1 0 100 )(,)(, xx xxxxfxxxf k kk , 110

9、10 )(, 1010kkk xxxxxxfxxxf 下面推导余项的另外一种形式 .13 )(xRn )( )!1( )( 1 )1( x n f n n )(, 110 xxxxxf nn n j jnn xxxxxxfxN 0 10 )(,)( )()(xRxN nn 因此 )!1( )( )1( n f n , 10n xxxxf ! )( )( k f k , 10k xxxf )(xRk)(, 1110 xxxxf kk nk 一般 Newton插值 估计误差的 重要公式 另外 .14 . . 6 , 8 , 7 , 4 , 1)(,5 , 4 , 3 , 2 , 1 插值多项式 求

10、四次牛顿时设当 ii xfx练练习习 kxkf(xk) 一阶差商 二阶差商 三阶差商 四阶差商 0 1 2 3 4 1 2 3 4 5 1 4 7 8 6 3 3 0 1 -1 -1/3 -2 -3/2 -1/6 1/24 )()4)(3)(2)(1()()3)(2)(1( 0)2)(1(3) 1(1)( 24 1 3 1 4 xxxxxxx xxxxN 1 12 33 2 24 83 3 12 9 4 24 1 xxxx .15 2.2.3 等距节点插值公式 定义. 称 处的函数值为在等距节点设 , 1 , 0 ,)( 0 nk fkhxxxf kk kkk fff 1 处的一阶向前差分在为

11、 k xxf)( 1, 1 ,0nk 1 kkk fff 处的一阶向后差分在为 k xxf)( nk,2 , 1 kkk fff 1 2 处的二阶向前差分在为 k xxf)( 1 2 kkk fff处的二阶向后差分在为 k xxf)( .16 k m k m k m fff 1 1 1 阶向前差分处的在为mxxf k )( 阶向后差分处的在为mxxf k )( 依此类推 1 11 k m k m k m fff 可以证明 mk m k m ff 1 kk ff 2 22 kk ff 3 33 kk ff 如 .17 44 33 22 11 00 fx fx fx fx fx fx kk 四阶差

12、分三阶差分二阶差分一阶差分 0 f 1 f 2 f 3 f 0 2 f 1 2 f 2 2 f 0 3 f 1 3 f 0 4 f 差分表 4 f 3 f 2 f 1 f 4 2 f 3 2 f 2 2 f 4 3 f 3 3 f 4 4 f .18 在等距节点的前提下,差商与差分有如下关系 , 1ii xxf h fi , 21iii xxxf 2 1 2h ff ii 2 2 2h fi h fi 1 12 2 2 ii ff h 2 2 2 2h fi , 321iiii xxxxf 3 1 22 23h ff ii 3 3 ! 3 h fi ii ii xx ff 1 1 2 211

13、, ii iiii xx xxfxxf 3 32121 , ii iiiiii xx xxxfxxxf .19 3 3 2 2 2 23h fxf ii 3 3 3 ! 3 h fi , 1miii xxxf 依此类推 m i m hm f ! m mi m hm f ! , 10k xxxf k k hk f ! 0 k k k hk f ! .20 即是等距节点如果节点, 10n xxx n ab hnkkhxxk , 1 , 0, 0 , 10k xxxf k k hk f ! 0 由差商与向前差分的关系 )(xNn n k kk xxxxff 1 100 )(, Newton插值基本公

14、式为 如果假设 thxx 0 1.Newton向前(差分)插值公式 .21 1 0 )( k j j xx)(x k 1 0 00 )( k j jhxthx 1 0 )( k j hjt k k hk f ! 0 n k f 1 0 )( 1 0 k j hjt ! 0 k f k n k f 1 0 )( 1 0 k j jt )(xNn n k kk xxxxff 1 100 )(, )( 0 thxNn )(xRn )( )!1( )( 1 )1( x n f n n 则插值公式 化为 其余项 )( 0 thxRn )!1( )( )1( n f n n j n jth 0 1 )(

15、化为 .22 )( 0 thxRn )!1( )( )1( n f n n j n jth 0 1 )( ! 0 k f k n k f 1 0 )( 1 0 k j jt )( 0 thxNn 称 为Newton向前插值公式（又称为表初公式） 插值余项为 .23 ! k fn k n k n f 1 )( 1 0 k j jt )(thxN nn )(thxR nn )!1( )( )1( n f n n j n jth 0 1 )( 插值余项为 根据向前差分和向后差分的关系 mk m k m ff 如果假设thxx n )0( t 可得Newton向后插值公式 2.Newton向后(差分)

16、插值公式 .24 例例 4 设设x0=1.0,h=0.05,给出给出 在在 处的函数值如表处的函数值如表2-5的第的第3列，试用三次等距节点插值公式求列，试用三次等距节点插值公式求f(1.01)和和 f(1.28)的近似值。的近似值。 xxf )()6 , 1 , 0( 0 kkhxxk 32 0 1.00 1.00000 0.02470 1 1.05 1.02470 0.02411 -0.00059 2 1.10 1.04881 0.02357 -0.00054 -0.00005 3 1.15 1.07238 4 1.20 1.09544 0.02307 -0.00048 -0.00003

17、5 1.25 1.11803 0.02259 -0.00045 6 1.30 1.14017 0.02214 32 kk fxk 表表2-5 .25 解解 用用Newton向前插值公式来计算向前插值公式来计算f(1.01)的近似值。先构造与均的近似值。先构造与均 差表相似的差分表，见表差表相似的差分表，见表2-5得上半部分。由得上半部分。由t=(x-x0)/h=0.2的得的得 .00499. 1)01. 1()01. 1( 3 Nf 用用Newton向后插值公式计算向后插值公式计算f(1.28)的近似值，可利用表的近似值，可利用表2-5中的下半部中的下半部 分。由分。由t=(x-x6)/h=-

18、0.4，得，得 .13137. 1)28. 1()28. 1( 3 Nf 事实上，事实上，f(1.01)和和f(1.28)的真值分别为的真值分别为1.00498756和和1.13137085。由。由 此看出，计算结果是相当精确的。此看出，计算结果是相当精确的。 例例 2.5 已知已知f(x)=sinx的数值如表的数值如表2-6的第的第2列，分别用列，分别用Newton 向前、向后插值公式求向前、向后插值公式求sin0.57891的近似值。的近似值。 .26 0.4 0.38942 0.5 0.47943 0.09001 0.6 0.56464 0.08521 0.00480 0.7 0.6442