§2牛顿插值/“ Newton' iNterpolation Lagrange插值虽然易算,但若要增加一个节点时, 全部基函数l(x)都需重新算过。 将Ln(x)改写成a+a(x-x0)+a2(x-xx-x)+ +an(x-x)(x-xn1)的形式,希望每加一个节点时, 只附加一项上去即可。 >差商(亦称均差)/ divided difiference f(x)-f(x,) 1阶差商/the1st flx,x; I Ci-xi (≠,x≠x) divided difference of f w.r.t. x and x: * nx,x,x-/,(2阶差商 copyright@湘潭大学数学与计算科学学院 上一真下一真
11 上一页 下一页 §2 牛顿插值 /* Newton’s Interpolation */ Lagrange 插值虽然易算，但若要增加一个节点时， 全部基函数 l i (x) 都需重新算过。 将 Ln (x) 改写成 ( ) ( )( ) ... a0 + a1 x - x0 + a2 x - x0 x - x1 + ( )...( ) + n - 0 - n-1 a x x x x 的形式，希望每加一个节点时， 只附加一项上去即可。 ? ? ? ? ➢ 差商(亦称均差) /* divided difference */ ( , ) ( ) ( ) [ , ] i j i j i j i j i j x x x x f x f x f x x - - = 1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */ ( ) [ , ] [ , ] [ , , ] i k x x f x x f x x f x x x i k i j j k i j k - - = 2阶差商
(k+1)阶差商: ∫Lx fx0,x1,…,kl-Lx1,…,xk,xk+1 09··9~k+1 0 k+1 fIx 0 xk-1,xk-flxo k-19k+1 k' k+1 事实上几xn…,x1=∑《x) i=0k+1 (x;) 其中a,(x)=(x-x),al,(x)-x-x) 差商的值与x;的顺序无关! copyright@湘潭大学数学与计算科学学院 上一真下一真
12 上一页 下一页 1 0 1 0 1 1 0 1 0 1 1 1 0 1 [ , ... , , ] [ , ... , , ] [ , , ... , ] [ , ... , , ] [ , ... , ] + - - + + + + - - = - - = k k k k k k k k k k k x x f x x x f x x x x x f x x x f x x x f x x (k+1)阶差商： = + = k i k i i k x f x f x x 0 1 0 ( ) ( ) [ , ... , ] 事实上 其中 ( ) ( ) , 0 1 = + = - k i k i x x x = + = - k j i j k xi xi x j 0 1 ( ) ( ) 差商的值与 xi 的顺序无关！
>牛顿插值/ Newton' iNterpolation (x)=a0+a1(x-x0)+a2(x-x0)(x-x1)+…+an(x-x0)(x-xn-1) f(x)=f(ro)+(x-xo)flx,xoI fIx,xol=fxo,x,+(x-x,flx, xo,x, fx,xo ∫x0,…,xnl+(x-xn)∫[x,x,…,x ① +(x-x0)× +(x-x0…(x-xn1)×(二 →f(x)=(x)+x,x1(x-x)+1x,x1,x2(x-x0)x-x1)+ +fxo,, x,(x-xo)(x-x) ∫x,x,…,xn(x-x0)(x-x n-1儿(x flx rn(r) copyright@湘潭大学数学与计算科学学院 上一真下一真
13 上一页 下一页 ➢ 牛顿插值 /* Newton’s Interpolation */ ( ) ( ) ( ) [ , ] 0 0 0 f x = f x + x - x f x x [ , ] [ , ] ( ) [ , , ] 0 0 1 1 0 1 f x x = f x x + x - x f x x x [ , , ... , ] [ , ... , ] ( ) [ , , ... , ] 0 n 1 0 n n 0 n f x x x = f x x + x - x f x x x - ( ) ( ) ( )( ) ... ( )...( ) n = 0 + 1 - 0 + 2 - 0 - 1 + + n - 0 - n-1 N x a a x x a x x x x a x x x x 1 2 … … … … n-1 1 + (x - x0 ) 2 + … … + (x - x0 )…(x - xn-1 ) n-1 ( ) ( ) [ , ]( ) [ , , ]( )( ) ... f x = f x0 + f x0 x1 x - x0 + f x0 x1 x2 x - x0 x - x1 + [ , ... , ]( )...( ) + x0 xn x - x0 x - xn-1 f [ , , ... , ]( )...( )( ) x x0 xn x x0 x xn 1 x xn + f - - - - Nn (x) Rn (x) ai = f [ x0 , …, xi ]
注:⑨由唯一性可知N(x)=Ln(x),只是算法不同,故其 余项也相同,即 n x,x0,…,xn1ok+(x)=m03;+(x) n →f1x0,…,x f() ! ,5∈(xmin,xmx) 实际计算过程为 ∫(x)f,x ∫(x ∫x1,x f∫Lx0,x1,x2l ∫(x)xn1, riFle2xn1,xn1…∫xn…,xn f(ru+i flEn, xu+il flrm-lsxm xu+1. fl,..., xu+ fxo,., xu+l copyright@湘潭大学数学与计算科学学院 上一真下一真
14 上一页 下一页 注： 由唯一性可知 Nn (x) Ln (x)， 只是算法不同，故其 余项也相同，即 ( ) ( 1)! ( ) [ , , ... , ] ( ) 1 ( 1) 0 1 x n f f x x x x k x n n k + + + + = , ( , ) ! ( ) [ , ... , ] min max ( ) 0 x x k f f x x k k = 实际计算过程为 f (x0 ) f (x1 ) f (x2 ) … f (xn-1 ) f (xn ) f [x0 , x1 ] f [x1 , x2 ] … … … … f [xn-1 , xn ] f [x0 , x1 , x2 ] … … … … f [xn-2 , xn-1 , xn ] f [x0 , …, xn ] f (xn+1) f [xn , xn+1] f [xn-1 , xn , xn+1] f [x1 , …, xn+1] f [x0 , …, xn+1]
>等距节点公式/ Formulae with Equal Spacing 当节点等距分布时:x1=x+ih(i=0,…,n) 向前差分△fn=f1-f forward diff+△f=△(△f)=△f+1-△4f 向后差分Vf1=f1-f1 I backward difference V kf=fk-I fi -Vk-fi-I 中心差分6,=61J1-6 difference*其中J=∫(x±) copyright@湘潭大学数学与计算科学学院 上一真下一真
15 上一页 下一页 ➢ 等距节点公式 /* Formulae with Equal Spacing */ 向前差分 /* forward difference */ i i i f = f - f +1 i k i k i k i k f f f f 1 1 1 1 ( ) - + - - = = - 向后差分 /* backward difference */ 1 1 1 - - - = - i k i k i k f f f i i i-1 f = f - f 中心差分 /* centered difference */ 2 1 2 1 1 1 - - + - = - i k i k i k f f f 其中 ( ) 2 2 1 h i xi f = f 当节点等距分布时: ( 0, ... , ) xi = x0 + i h i = n