第2章牛顿插值法

1、数值分析 第二章 插值法 均差与牛顿插值公式均差与牛顿插值公式 Lagrange插值多项式的缺点插值多项式的缺点 )(xl j n ji iij i xx xx 0 )( )( nj,2 , 1 ,0 我们知道我们知道,Lagrange,Lagrange插值多项式的插值基函数为插值多项式的插值基函数为 理论分析中很方便，理论分析中很方便，但是但是当当插值节点增减插值节点增减时时全部插值全部插值 基函数基函数就要随之就要随之变化变化，整个公式也将发生变化，这在，整个公式也将发生变化，这在 实际计算中是很实际计算中是很不方便不方便的；的； Lagrange 插值虽然易算，但若要增加一个节点时，插值

2、虽然易算，但若要增加一个节点时， 全部基函数全部基函数 li(x) 都需重新算过。都需重新算过。 解决解决 由线性代数的知识可知由线性代数的知识可知, ,任何一个任何一个n n次多项式都可以表示成次多项式都可以表示成 , 1, 0 xx ),)( 10 xxxx)()( 110 n xxxxxx, 共共n+1n+1个多项式的线性组合个多项式的线性组合 那么，是否可以将这那么，是否可以将这n+1n+1个多项式作为插值基函数呢？个多项式作为插值基函数呢？ , 1, 0 xx ),)( 10 xxxx)()( 110 n xxxxxx, 显然，多项式组显然，多项式组 线性无关，线性无关， 因此，因此

3、，可以作为插值基函数可以作为插值基函数 , i x设插值节点为nifi, 1 , 0,函数值为 1,2 , 1 , 0, 1 nixxh iii i i hhmax nifxP ii , 1 , 0,)(插值条件为 具有如下形式设插值多项式)(xP 01 , n a aa其中 为待定系数 基函数基函数 )()( )()()( 110 102010 nn xxxxxxa xxxxaxxaaxP )()( )()()( 110 102010 nn xxxxxxa xxxxaxxaaxP nifxPxP ii , 1 , 0,)()(应满足插值条件 000) (afxP 有 )()( 011011

4、xxaafxP 00 fa 01 01 1 xx ff a )()()( 12022021022 xxxxaxxaafxP 12 01 01 02 02 2 xx xx ff xx ff a 再继续下去待定系再继续下去待定系 数的形式将更复杂数的形式将更复杂 。 为此引入差商和差分的概念为此引入差商和差分的概念 divided difference */ ),( )()( , ji ji ji ji xxji xx xfxf xxf 1阶差商阶差商 /* the 1st divided difference of f w.r.t. xi and xj */ )( , ,ki xx xxfxxf

5、 xxxf ki kjji kji 2阶差商阶差商 定义定义2.2.nifxxf ii , 1 , 0,)(处的函数值为在互异的节点设 1 11010 10 1110 10 ,.,., ,.,., ,., kk kkkk k kkk k xx xxxfxxxf xx xxxfxxxf xxf (k+1) 阶阶 差差 商商 )( )( )( )( )( )( 44 33 22 11 00 xfx xfx xfx xfx xfx xfx kk 四阶差商三阶差商二阶差商一阶差商 差商的计算方法差商的计算方法( (表格法表格法):): , 10 xxf , 21 xxf , 32 xxf , 43 x

6、xf , 210 xxxf , 321 xxxf , 432 xxxf , 3210 xxxxf , 4321 xxxxf , 410 xxxf 规定函数值为规定函数值为零阶差商零阶差商 差商表差商表 差商具有如下性质差商具有如下性质: : 且的线性组合表示 可由函数值阶差商的 ,)(,),(),( ,)()1( 10 110 k kk xfxfxf xxxxfkxf , 110kk xxxxf k i kiiiiii i xxxxxxxx xf 0 110 )()()( )( Warning: my head is exploding What is the point of this fo

7、rmula? 差商的值与差商的值与 xi 的顺序无关！的顺序无关！ NewtonNewton插值公式及其余项插值公式及其余项 ,)()()( 000 xxfxxxfxf ,)(, 101100 xxxfxxxxfxxf ,.,)(,.,., 0010nnnn xxxfxxxxfxxxf 1 2 n+1 1+ (x x0) 2+ + (x x0)(x xn 1) n+1 .)(,)(,)()( 102100100 xxxxxxxfxxxxfxfxf ).(,., 100 nn xxxxxxf )().(,., 100nnn xxxxxxxxxf Nn(x) Rn(x) ai = f x0, ,

8、xi NewtonNewton插值公式及其余项插值公式及其余项 i x 0 x 1 x 2 x 3 x i f x 0 ()f x 1 ()f x 2 ()f x 3 ()f x 1 , ii f x x 01 ,f xx 12 ,f x x 23 ,f xx 12 , iii f x xx 012 ,f xx x 123 ,f x xx 123 , iiii f x xxx 0123 ,f xx xx 001001210 01110 ( )()() ,()() , ()()() , n nn P xf xxxf x xxxxxf xx x xxxxxxf xx x NewtonNewton插

9、值公式及其余项插值公式及其余项 例：例： 已知已知x=1,4,9的平方根为的平方根为1,2,3，利用牛顿基本差商，利用牛顿基本差商 公式求公式求 的近似值。的近似值。 i x 1 4 9 i x 1 2 3 1 , ii f x x 2 1 0 33333 4 1 . 32 0 2 94 . 12 , iii f x xx 0 20 33333 0 01667 9 1 . . 7 解：解： 从而得二阶牛顿基本差商公式为从而得二阶牛顿基本差商公式为 2 10 3333310 0166714( ).().()()P xxxx 2 72 69992( ).P 因此计算得因此计算得 的近似值为的近似值

10、为7 性质性质3 3 练习练习 74017018 312 ,2 ,2 2 ,2 ,2 fxxxff已知 ，求及 ( )f x分析：本题是一个多项式，可利用差商的性质 解：由差商与导数之间的关系 (7) 017 ( )7! 2 ,2 ,2 1 77! f f ！ (8) 018 ( )0 2 ,2 ,2 0 88! f f ！ 上面我们讨论了节点任意分布的插值公式，但实际应上面我们讨论了节点任意分布的插值公式，但实际应 用时经常会遇到等距节点的情形，这时插值公式可以用时经常会遇到等距节点的情形，这时插值公式可以 进一步简化，计算也简单多了，为了给出等距节点的进一步简化，计算也简单多了，为了给出等

11、距节点的 插值公式，我们先来看一个新概念；插值公式，我们先来看一个新概念； 称 处的函数值为在等距节点设 , 1 ,0 ,)( 0 nk fkhxxxf kk kkk fff 1 处的一阶向前差分在为 k xxf)( 1, 1 ,0nk 1 kkk fff 处的一阶向后差分在为 k xxf)( nk,2 , 1 11 22 (/ 2)(/ 2) kkk kk ff xhf xhff ( ) k f xx为在处的中心差分 不在函数表上，要用到不在函数表上，要用到 函数表上的值函数表上的值 1111 22 , kkkk kk ffffff kkk fff 1 2 处的二阶向前差分在为 k xxf)

12、( 1 2 kkk fff处的二阶向后差分在为 k xxf)( 利用一阶差分可以定义二阶差分利用一阶差分可以定义二阶差分 差分差分 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 如 差分差分 44 33 22 11 00 fx fx fx fx fx fx kk 四阶差分三阶差分二阶差分一阶差分 0 f 1 f 2 f 3 f 0 2 f 1 2 f 2 2 f 0 3 f 1

13、 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 差分与函数值之间的关系差分与函数值之间的关系 010121232 ,yyyyyyyyy 2 010210 2 121321 2 232432 2 2 2 yyyyyy yyyyyy yyyyyy 222 2()abaabb 1 ()abab 322 0103210 322 1214321 322 2325432 33 33 33 yyyyyyy yyyyyyy yyyyyyy 32233 33()abaa babb 433 01043210 433 121

14、54321 433 23265432 464 464 464 yyyyyyyy yyyyyyyy yyyyyyyy 4322443 464()abaa ba babb 归纳可知，归纳可知，k阶差商可表示为阶差商可表示为 011 11 k ii ki kii kk kkkk yyyCCyCCy 在等距节点的前提下在等距节点的前提下, ,差商与差分有如下关系差商与差分有如下关系 , 1ii xxf h fi , 21iii xxxf 2 1 2h ff ii 2 2 2h fi h fi 1 2 21 2h fxf ii 2 2 2 2h fi ii ii xx ff 1 1 2 211 , ii

15、 iiii xx xxfxxf , 321iiii xxxxf 3 1 22 23h ff ii 3 3 ! 3 h fi 3 32121 , ii iiiiii xx xxxfxxxf 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 ! 即是等距节点如果节点, 10n xxx n ab hnkkhxxk , 1 , 0, 0 , 10k xxxf k k hk f ! 0 由差商与向前差分的关系 )(xNn n

16、 k kk xxxxff 1 100 )(, Newton插值基本公式为 如果假设 thxx 0 1.Newton向前向前(差分差分)插值公式插值公式 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 )( 化为 )( 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 称