浙江大学：《数值分析》课程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

82 Newton's Interpolation 差分的重要性质: 命线性:例如Δ(a∫(x)+bg(x))=a△f+b△g 命若f(x)是m次多项式,则f(x)(0≤k≤m)是m-k次多项 式,而△f(x)=0(k>m) 中差分值可由函数值算出: △"f=∑( f=2(1) 其中()=a(n-1--+1) r binomial coefficients j! 函数值可由差分值算出:k=2"f △fo fxa,…,xA=2 由Rn表达式 fIx fr(6)=4 h

§2 Newton’s Interpolation  差分的重要性质：  线性：例如 (a f ( x )  b g( x ))  a f  b g 若 f (x)是 m 次多项式，则 是 次多项 式，而 f(x) (0 k m) k    m  k f (x) 0 (k m) k    差分值可由函数值算出：        n j n k j j k n f j n f 0 ( 1)        n j k j n n j k n f j n f 0 ( 1) ! ( 1)...( 1) j n n n j j n           其中 /* binomial coefficients */ 函数值可由差分值算出： k j n j n k f j n f      0  k k k k h f f x x ! [ , ... , ] 0 0   k n k n n n k k h f f x x x ! [ , , ... , ] 1     k k k h f f ( ) 0 ( )    由 Rn 表达式

82 Newton's Interpolation 牛顿公式N()=/(x)+/xx-)++几,…,xx-x-x) a牛顿前差公式/ Newton' s forward-difference formula 设x=x+tb,则N(x)=N,(xn+b)=∑14(xn) (n+1) R,(x)= (n+D)!t(t-1)(t-m)b,5∈(x0,xn) a牛顿后差公式/ Newton' s backward- difference formula 将节点顺序倒置: N(x)=f(x)+x,xnl(x-xn)+…+几xn,…,x(x-x)(-x) 设x=xn+th,则Nn(x)=N(xn+th)=∑(-1 d 注:一般当x靠近x时用前插,靠近xn时用后插,故两 种公式亦称为表初公式和表末公式

§2 Newton’s Interpolation 牛顿公式 ( ) ( ) [ , ]( ) ... [ , ..., ]( )...( ) n  0  0 1  0   0 n  0  n1 N x f x f x x x x f x x x x x x  牛顿前差公式 /* Newton’s forward-difference formula */  牛顿后差公式 /* Newton’s backward-difference formula */ 将节点顺序倒置： ( ) ( ) [ , ]( ) ... [ ,..., ]( )...( ) 1 x x0 x x x x1 N x f x f x x x x f n  n  n n  n   n  n  设 x  x0  t h ，则 ( ) ( ) ( ) 0 0 0 f x k t N x N x t h k n k n  n      ( 1)...( ) , ( , ) ( 1)! ( ) ( ) 0 1 ( 1) n n n n t t t n h x x n f R x          设 x  xn  t h ，则 ( ) ( ) ( 1) ( ) 0 n k n k k n n n f x k t N x N x t h        注：一般当 x 靠近 x0时用前插，靠近 xn时用后插，故两 种公式亦称为表初公式和表末公式

§3厄米插值/ Hermite Interpolation 不仅要求函数值重合,而且要求若干阶导数也重合。 即:要求插值函数q(x)满足p(x)=∫(x),g'(x)=f”(x) P(mi(xi)=f(()(xi. 注:N个条件可以确定N-1阶多项式。 要求在1个节点x处直到m阶导数都重合的插 值多项式即为ayor多项式 q(x)=f(x0)+f(x)(x-x0)+…+ (x-x0) (mo+1) 其余项为Rx)=f(x)-(x)=(m+Wx-5 (2 一般只考虑∫与∫的值

§3 厄米插值 /* Hermite Interpolation */ 不仅要求函数值重合，而且要求若干阶导数也重合。 即：要求插值函数  (x) 满足 (xi) = f (xi), ’ (xi) = f ’ (xi), …, (mi) (xi) = f (mi) (xi). 注： N 个条件可以确定 N  1 阶多项式。 要求在1个节点 x0处直到m0阶导数都重合的插 值多项式即为Taylor多项式 0 0 ( ) ! ( ) ( ) ( ) ( )( ) ... 0 0 0 ( ) 0 0 0 m m x x m f x  x  f x  f  x x  x    其余项为 ( 1) 0 0 ( 1) 0 0 ( ) ( 1)! ( ) ( ) ( ) ( )        m m x x m f R x f x x   一般只考虑 f 与f ’的值

3 Hermite Interpolation 例:设x≠x1≠x2,已知(x)fx1)、x2)和f(x1,求多项式P(x) 满足P(x)=f(x),i=0,1,2,且P(x)=fx1,并估计误差。 解:首先,P的阶数=3模仿 Lagrange多项式的思想,设 P:(x)=∑f(x1)(x)+/餐)(x) i=0 其中(x)=4,h(x)=0,金(x)=0,金(x)=1 ()有根x,x,且h()=0→x是重根。A(x)=C(x=x(x-x) 又:h(x0)=1→C0 h,(xi(x-x(x-x2 h2()与h()完全类似。 (x0-x1)(x0-x2) h,(x )有根 0~2 hr 与 Lagrange分析 由余下条件h( 完全类似 有根MM,=1(=(xNx 又:金;(x)=1→C1可解 R3(x)=f(x)-P3(x)=K(x)(x-x0)(x-x1)2(x-x2),K(x)= 4!

§3 Hermite Interpolation 例：设 x0  x1  x2 , 已知 f(x0)、 f(x1)、 f(x2) 和 f ’(x1), 求多项式 P(x) 满足 P(xi) = f (xi)，i = 0, 1, 2，且 P’(x1) = f ’(x1), 并估计误差。 解：首先，P 的阶数 = 3 模仿 Lagrange 多项式的思想，设     2 3 1 ( ) ( ) ( ) ( ) ( ) i0 P x f xi hi x f ’ x1 h x  h0(x) 有根 x1 , x2，且 h0 ’(x1) = 0  x1是重根。 ( ) ( ) ( ) 2 2 h0 x  C0 x  x1 x  x 又: h0(x0) = 1  C0 ( ) ( ) ( ) ( ) ( ) 0 2 2 0 1 2 2 1 0 x x x x x x x x h x      h2(x) h1(x) 有根 x0 , x2  ( ) ( )( )( ) h1 x  Ax  B x  x0 x  x2 由余下条件 h1(x1) = 1 和 h1 ’(x1) = 0 可解。 与h0(x) 完全类似。 (x) h1 有根 x0 , x1 , x2  h1( ) ( )( )( ) x C1 x x0 x x1 x x2      又: h1 ’(x1) = 1  C1 可解。 其中 hi(xj) = ij , hi ’(x1) = 0, (xi) = 0, ’(x1) = 1 h1 h1 ( ) ( ) ( ) ( )( )( ) ( ), 2 2 R3 x  f x  P3 x  K x x  x0 x  x1 x  x 4! ( ) ( ) (4) x f K x   与 Lagrange 分析 完全类似

3 Hermite Interpolation 般地,已知x,…x处有,…,yn和y3,…,yn,求n(x) 满足H21(x)=y,H2m1(x)=y x-x 解:设H2m(x)=∑n(x)+∑r金(x) 其中(x)=6,h(x)=0.金 ()= x)春 这样的 Hermite插值唯 x)=(4x+B)2(x) 由余下条件(x)=1和h1(x)=0可解41和B;→ b1(x)=1-2l(x2)(x-x)l2(x) )有根x,…,x除了x外都是重根→(x)=C(x-x)(x) 又:金(x)=1 (x)=(x-x)l2(x) (2n+2) 设a=x4万<…x=bf∈C"b则Rx2(y2(x-x)

§3 Hermite Interpolation 一般地，已知 x0 , …, xn 处有 y0 , …, yn 和 y0 ’ , …, yn ’ ，求 H2n+1(x) 满足 H2n+1(xi) = yi， H’ 2n+1(xi) = yi ’ 。 解：设    n i ( ) ( ) ( ) i0 H2n+1 x yihi x h x   n i0 yi ’ 其中 hi(xj) = ij , hi ’(xj) = 0, (xj) = 0, ’(xj) = ij hi hi hi(x) 有根 x0 , …, xi  , …, xn且都是2重根  ( ) ( ) ( ) 2 hi x  Ai x  Bi l i x      j i i j j i x x x x l x ( ) ( ) ( ) 由余下条件 hi(xi) = 1 和 hi ’(xi) = 0 可解Ai 和 Bi  ( ) [1 2 ( )( )] ( ) 2 h x l x x x l x i i i  i i    (x) hi 有根 x0 , …, xn , 除了xi 外都是2重根  hi( ) ( ) i i li 2 x C x  x (x)  又 hi : ’(xi) = 1  Ci = 1 hi(x) ( )i li 2  x  x (x) 设 ... , [ , ] 2 a x0 x1 x b f C a b n     n   则 2 0 (2 2) ( ) (2 2)! ( ) ( )            n i i x n n x x n f R x  这样的Hermite 插值唯 一