浙江大学：《数值分析》课程PPT教学课件（双语版）第六章 插值 Interpolation §2 牛顿插值 Newton’s Interpolation §3 厄米插值 Hermite Interpolation §4 Piecewise Polynomial Approximation

§2牛顿插值/ Newton's Interpolation lAgrange插值虽然易算,但若要增加一个节点时, 全部基函数l(x)都需重新算过 将Ln(x)改写成a+a1(x-x)+a2(x-x)(x-x)+… +an(x-x)…(-xn)的形式,希望每加一个节点时, 只附加一项上去即可。 >差商(亦称均差)/ divided difference 1阶差商/the1st fIx,,x= f(x;)-f(x) (i≠x≠x) divided difference of f w.r.t. x and x*/ 八x,x,联/=1,x几x,x i≠k)2阶差商 x.-x

§2 牛顿插值 /* Newton’s Interpolation */ Lagrange 插值虽然易算，但若要增加一个节点时， 全部基函数 li(x) 都需重新算过。 将 Ln (x) 改写成 ( ) ( )( ) ... a0 a1 x x0 a2 x x0 x x1  ( )...( ) an xx0 xxn1 的形式，希望每加一个节点时， 只附加一项上去即可。 ? ? ? ?  差商(亦称均差) /* 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阶差商

82 Newton's Interpolation (k+1)阶差商: ∫[x n…,xk1=n,,…, ∫Lx1 195k5~k+1 xn-x 0 05··5~k-15k l-∫ 0,···9k-19~k+1 x;- k k+1 事实上几xn,,x1=∑/(x) k+1 其中a k+1 (x)=I(x-x),0+(x ∏ j=0 差商的值与x的顺序无关!

§2 Newton’s Interpolation 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 x x xi        k j i j k i i j x x x 0 1  ( ) ( ) Warning: my head is exploding… Wh差at商is的the值po与int of this formula? xi 的顺序无关！

82 Newton's Interpolation 牛顿插值/ Newton' s Interpolation N(x)=a0+a1(x-x0)+a2(x-x0(x-x1)+…an(x-x0)…(x-xn1) f(=f(o)+(x-xoflx,xol fx,xo=fo,x,+(x-xuflx,xo,cI 2 fMo,,xu+(x-xunflx,xo ①+(x-x)x②+……+(x-x)…(x-xn-)×(mD f(x)=f(x)+∫x,x1(x-x)+∫x,x1,x2l(x-x0)(x-x1) (+ fIxo,,xmIx-xo)(x-xn-1) fx,x0,…,xnl(x-x)…(x-xn1)(x f[x0,…,x; Rn(r)

§2 Newton’s Interpolation  牛顿插值 /* Newton’s Interpolation */ ( ) ( ) ( ) [ , ] 0 0 x x0 f x  f x  x  x f [ , ] [ , ] ( ) [ , , ] 0 0 1 1 0 1 f x x  f x x  x  x f x x x [ , , ..., ] [ , ..., ] ( ) [ , , ..., ] 0 n 1 0 n n x x0 xn f x x x  f x x  x  x f  ( ) ( ) ( )( ) ... ( )...( ) Nn x a0 a1 x x0 a2 x x0 x x1  an x x0 x xn1 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  [ , ... , ]( )...( )  0 n  0  n1 f x x x x x x [ , , ... , ]( )...( )( ) 0 n 0 n 1 n  f x x x x  x x  x x  x  Nn (x) Rn (x) ai = f [ x0 , …, xi ]

82 Newton's Interpolation 注:G由唯一性可知Nn(x)≡Ln(x),只是算法不同,故其 余项也相同,即 (n+1) fx,x0,…, xm,o+(x)= (n+1)!k →fx0,…,xk1= f() k i ,5∈(x min 2"max G实际计算过程为 (x HW ∫pxo,x1 p12#4 ∫(x2)∫x1,xl ∫xo,x1,x2l f∫ ∫(x)xn1,xn/{xn2xn1,xnl…∴∫lxn…,xn f(xn+1). flam xn+il fln-1,tm,xn+ll. fxi,., xn+ flo, ··5

§2 Newton’s Interpolation 注： 由唯一性可知 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] HW: p.112 #4

82 Newton's Interpolation 等距节点公式 P Formulae with Equal Spacing 当节点等距分布时:x;=x0+ih(i=0,…,n) 向前差分 I forward difference * △f1=△=(△f/)=△=f计+-△-f1 向后差分 V1=f1-f1 /* backward difference* V=VR-fi-VK-Jf 中心差分 δ"f;=δ∫ /* centered I+ differenceη其中f!=∫(x±分 More given on p 113-114

§2 Newton’s Interpolation  等距节点公式 /* 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 More given on p.113-114