第三章 插值法和最小二乘法 3.4 Newton插值法§ 3.4 Newton插值法§ )(xl j ∏ ≠ = ? ?= n ji i ij i xx xx 0 )( )( nj ,,2,1,0 L= 我们知道 ,Lagrange插值多项式的插值基函数为 形式上太复杂 ,计算量很大 ,并且重复计算也很多 由线性代数的知识可知 ,任何一个 n次多项式都可以表示成 ,1 ,0xx ? ),)(( 10 xxxx ?? )())(( 110 ???? nxxxxxx L,L 共 n+1个多项式的线性组合 那么 ， 是否可以将这 n+1个多项式作为插值基函数呢 ？ ,1 ,0xx ? ),)(( 10 xxxx ?? )())(( 110 ???? nxxxxxx L,L 显然 ， 多项式组 线性无关 ， 因此 ， 可以作为插值基函数 ,ix设插值节点为 nifi ,,1,0, L=函数值为 1,,2,1,0,1 ?=?= + nixxh iii L i i hh max= nifxP ii ,,1,0,)( L==插值条件为 )())(( ))(()()( 110 102010 ????+ +??+?+= nn xxxxxxa xxxxaxxaaxP L L 具有如下形式设插值多项式 )(xP nifxPxP ii ,,1,0,)()( L==应满足插值条件 000 )( afxP ==有 )()( 011011 xxaafxP ?+== 00 fa = 01 01 1 xx ffa ? ?= ))(()()( 12022021022 xxxxaxxaafxP ??+?+== 12 01 01 02 02 2 xx xx ff xx ff a ? ? ?? ? ? = 再继续下去待定系数的形式将更复杂 为此引入差商和差分的概念 一 、 差商 (均差 ) 定义 1. nifxxf ii ,,1,0,)( L=处的函数值为在互异的节点设 称 )(],[ jixx ffxxf ji ji ji ≠? ?= )(,)( 均差一阶差商关于节点为 ji xxxf )(],[],[],,[ kjixx xxfxxfxxxf jk jiki kji ≠≠? ?= 的二阶差商关于为 kji xxxxf ,,)( 依此类推 ],,,,[ 110 kk iiii xxxxf ? L 阶差商的关于节点为 kxxxxxf kk iiii ,,,,)( 110 ? L ],,,,[ 110 kk xxxxf ?L 差商具有如下性质 且的线性组合表示 可由函数值阶差商的 ,)(,),(),( ],,,,[)()1( 10 110 k kk xfxfxf xxxxfkxf L L ? 显然 kk kkk ii iiiiiii xx xxxxfxxxf ? ?= ? ?? 1 210110 ],,,,[],,,[ LL kk kkk xx xxxxfxxxf ? ?= ? ?? 1 210110 ],,,,[],,,[ LL ],,,,[ 110 kk xxxxf ?L ∑ = +? ???? = k i kiiiiii i xxxxxxxx xf 0 110 )())(()( )( LL (2) 差商具有对称性 ,即任意调换节点的次序 ,差商的值不变 ],,[ 210 xxxf ],,[ 120 xxxf= ],,[ 012 xxxf=如 ,,,,)()3( 10) 的区间存在时在包含节点当 （ kk xxxxf L 使得之间必存在一点在 ,,,, 10 xkxxx L ],,,[ 10 kxxxf L ! )( )( k f k x= )( )( )( )( )( )( 44 33 22 11 00 xfx xfx xfx xfx xfx xfx kk 四阶差商三阶差商二阶差商一阶差商 差商的计算方法 (表格法 ): ],[ 10 xxf ],[ 21 xxf ],[ 32 xxf ],[ 43 xxf ],,[ 210 xxxf ],,[ 321 xxxf ],,[ 432 xxxf ],,,[ 3210 xxxxf ],,,[ 4321 xxxxf ],,,[ 410 xxxf L 规定函数值为 零阶差商 差商表 Chashang.m 二 、 差分 定义 2. 称 处的函数值为在等距节点设 ,,,1,0 ,)( 0 nk fkhxxxf kk L= += kkk fff ?=? +1 处的一阶向前差分在为 kxxf )( 1,,1,0 ?= nk L 1??=? kkk fff 处的一阶向后差分在为 kxxf )( nk ,,2,1 L= kkk fff ???=? +1 2 处的二阶向前差分在为 kxxf )( 1 2 ????=? kkk fff 处的二阶向后差分在为 kxxf )( k m k m k m fff 1 1 1 ? + ? ???=? 阶向前差分处的在为 mxxf k)( 阶向后差分处的在为 mxxf k)( 依此类推 1 11 ? ?? ???=? k m k m k m fff 可以证明 mkmkm ff +?=? 1+?=? kk ff 2 22 +?=? kk ff 3 33 +?=? kk ff 如 kkk fff ?=? +1 kkk fff ?=? ++ 11 kkk fff ???=? +1 2 122 2 +++ ???=? kkk fff 44 33 22 11 00 fx fx fx fx fx fx kk 四阶差分三阶差分二阶差分一阶差分 0f? 1f? 2f? 3f? 0 2 f? 1 2 f? 2 2 f? 0 3 f? 1 3 f? 0 4 f? 差分表 4f? 3f? 2f? 1f? 4 2 f? 3 2 f? 2 2 f? 4 3 f? 3 3 f? 4 4 f? 在等距节点的前提下 ,差商与差分有如下关系 ],[ 1+ii xxf hfi?= ],,[ 21 ++ iii xxxf 2 1 2h ff ii ? ???= + 2 2 2h fi?= h fi 1+?= 2 21 2h ff ii ? ???= ++ 2 2 2 2h fi +?= ],,,[ 321 +++ iiii xxxxf 3 1 22 23 h ff ii ?? ???= + 3 3 !3 h fi ? ?= ii ii xx ff ? ?= + + 1 1 2 211 ],[],[ + +++ ? ?= ii iiii xx xxfxxf 3 32121 ],,[],,[ + +++++ ? ?= ii iiiiii xx xxxfxxxf 3 3 2 2 2 23 h fxf ii ?? ???= ++ 3 3 3 !3 h fi ? ?= + ],,,[ 1 miii xxxf ++ L 依此类推 m i m hm f ? ?= ! m mi m hm f ? ?= + ! ],,,[ 10 kxxxf L k k hk f ? ?= ! 0 k k k hk f ? ?= ! 三 、 Newton基本插值公式 )())(( ))(()()( 110 102010 ????+ +??+?+= nn xxxxxxa xxxxaxxaaxP L L 设插值多项式 满足插值条件 nifxP ii ,,1,0,)( L== 则待定系数为 00 fa = ],[ 101 xxfa = ],,[ 2102 xxxfa = ],,,[ 10 nn xxxfa L= )())(( ))(()()( 110 102010 ????+ +??+?+= nn n xxxxxxa xxxxaxxaaxN L L ∑ ∏ = ? = ?+= n k k j jk xxxxxff 1 1 0 100 )(],,,[ L 称 基本插值多项式次的关于节点为 Newtonnxxf i)( 定义 3. )()()( xNxfxR nn ?= )()!1( )( 1 )1( xnf n n + + += w x 由插值多项式的唯一性 ,Newton基本插值公式的余项为 ∑ = += n k kk xxxxff 1 100 )(],,,[ wL ∏? = ?= 1 0 )( k j jxx)(xkw 为 k次多项式 ],,,,[ 10 kxxxxf L ],,,,[ 110 ?kxxxxf L 则视为一个节点若将 ,),,1,0(, nixx i L=≠ 因此可得 )](,[)( 000 xxxxffxf ?+= )))(](,,[],[( 0110100 xxxxxxxfxxff ??++= ))(](,,[)](,[ 10100100 xxxxxxxfxxxxff ??+?+= LL ∏∑ ∏ == ? = ?+?+= n j jn n k k j jk xxxxxxfxxxxxff 0 10 1 1 0 100 )(],,,,[)(],,,[ LL k kk xx xxxfxxxxf ? ?= ? ],,,[],,,,[ 10110 LL )](,,,,[],,,[ 1010 kkk xxxxxxfxxxf ?+= LL )(xRn )()!1( )( 1 )1( xnf n n + + += w x )(],,,,[ 110 xxxxxf nn += wL ∏ = ?+= n j jnn xxxxxxfxN 0 10 )(],,,,[)( L )()( xRxN nn += 因此 )!1( )()1( += + n f n x],,,,[ 10 nxxxxf L ! )()( k f k x=],,,[ 10 kxxxf L )(xRk )(],,,[ 1110 xxxxf kk ++≈ wL nk <一般 Newton插值 估计误差的 重要公式 另外 四 、 Newton插值公式 即是等距节点如果节点 ,,,, 10 nxxx L n abhnkkhxx k ?==+= ,,,1,0, 0 L ],,,[ 10 kxxxf L k k hk f ? ?= ! 0由差商与向前差分的关系 )(xNn ∑ = += n k kk xxxxff 1 100 )(],,,[ wL Newton插值基本公式为 如果假设 thxx += 0 1.Newton向前 (差分 )插值公式 ∏? = ?= 1 0 )( k j jxx)(xkw ∏ ? = ??+= 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 fk?∑ = += n k f 1 0 ])( 1 0 ∏? = ? k j jt )(xNn ∑ = += n k kk xxxxff 1 100 )(],,,[ wL )( 0 thxNn + )(xRn )()!1( )( 1 )1( xnf n n + + += w x 则插值公式 化为 其余项 )( 0 thxRn + )!1( )( )1( += + n f n x ∏ = + ? n j n jth 0 1 )(化为 )( 0 thxRn + )!1( )( )1( += + n f n x ∏ = + ? n j n jth 0 1 )( ![ 0 k fk?∑ = += n k f 1 0 ])( 1 0 ∏? = ? k j jt)( 0 thxNn +称 为 Newton向前 插值公式 插值余项为 ![ k fnk?∑ = += n k nf 1 ])( 1 0 ∏? = + k j jt)( thxN nn + )( thxR nn + )!1( )( )1( += + n f n x ∏ = + + n j n jth 0 1 )( 插值余项为 根据向前差分和向后差分的关系 mk m k m ff +?=? 如果假设 thxx n += )0( <t 可得 Newton向后插值公式 2.Newton向后 (差分 )插值公式 五 、 Newton插值公式的使用 由于高次插值多项式的 Runge现象 ,Newton插值公式 一般也采用分段低次插值 )()(1 xN k )](,[ 1 kkkk xxxxff ?+= + 1,,1,0 ?= nk L分段线性 Newton插值 (1) )()(2 xN k ))(](,,[)](,[ 1211 ++++ ??+?+= kkkkkkkkk xxxxxxxfxxxxff(2) 2,,1,0 ?= nk L )()(1 xR k )(!2 )( 2 xf wx′′= )(],,[ 221 xxxxf kkk w++≈ 1+≤≤ kk xxx 1+≤≤ kk xxx Newton分段二次插值 )()(3 xN k ∑ ∏ = ? = ?++ ?+= 3 1 1 0 1 )(],,,[ i i j jkikkkk xxxxxff L(3) Newton分段三次插值 1+≤≤ kk xxx 3,,1,0 ?= nk L )()(3 xR k )(],,,[ 441 xxxxf kkk w++≈ L )()(2 xR k )(],,,[ 3321 xxxxxf kkkk w+++≈)(!3 )( 3 xf wx′′′= 余项为 余项为 )(!4 )( 4 )4( xf wx= )(xNk ∑ ∏ = ? = ???????? ?+= k i i j jmnimnmnmnmn xxxxxff 1 1 0 1 )(],,,[ L (4) mnxkNewton ?? 为阶基本后插公式 ， 起点 从 (2),(3)两种情况可知 ,若 nn xxx ≤≤?1 对分段二次及分段三次插值都没有相应的插值公式 12 ?? ≤≤ nn xxx若 对分段三次插值也没有相应的插值公式 此时应改用 Newton基本后插公式 ,此处只列出公式 )(xRk )()!1( )( 1 )1( xkf k k + + += w x余项为 )(],,,[ 111 xxxxf kkmnmnmn +??????≈ wL nk ,,2,1 L= L,2,1,0=m (5) )()(1 thxR kk + 2 )(xf ′′= )1(2 ?tth tfk ??+= kf)()(1 thxN kk + 插值余项为 10 << t 2 2 kf?≈ )1( ?tt 分段线性 Newton向前 (差分 )插值 1,,1,0 ?= nk L )( 0)(2 thxR k + !3 )( )3( xf = )2)(1(3 ?? ttth )()(2 thxN kk +(6) tfk ??+= kf )1(2 2 ???+ ttfk 10 << t 2,,1,0 ?= nk L !3 3 kf?≈ )2)(1( ?? ttt 分段二次 Newton 向前 (差分 )插值 次插值多项式则使用在误差范围内很接近差分商 阶差如果 m m ),()( 1+ )( 0)(2 thxR k + !3 )( )3( xf = )2)(1(3 ++ ttth )()(2 thxN kk + tfk ??+= kf )1(2 2 +??+ ttfk !3 3 kf?≈ )2)(1( ++ ttt (7) 01 <<? t 1, ?= nnk 分段二次 Newton 向后 (差分 )插值 依此类推 ,请同学们写出分段三次 向前和向后 Newton公式 及余项 在实际应用中 ,究竟使用几次插值多项式呢 ? 五 、 Newton基本插值公式的算法设计 Newton插值法的优点是计算较简单 ,尤其是增加节点时 , 计算只要增加一项 ,这是 Lagrange插值无法比的 . 但是 Newton插值仍然没有改变 Lagrange插值的插值曲线 在节点处有尖点 ， 不光滑 ， 插值多项式在节点处不可导 等缺点