数值计算：插值(2)

1、3 牛顿插值牛顿插值 /* Newtons Interpolation */Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函数全部基函数 li(x) 都需重新算过。都需重新算过。将将 Ln(x) 改写成改写成 )()(102010 xxxxcxxcc).(10 nnxxxxc的形式，希望每加一个节点时，的形式，希望每加一个节点时，只附加一项只附加一项上去即可。上去即可。? 差商差商( (亦称均差亦称均差) ) /* divided difference */),()()(,jijijijixxjixxxfxfxxf 1阶差商阶差商 /* the

2、 1st divided difference of f w.r.t. xi and xj */)(,kixxxxfxxfxxxfkikjjikji 2阶差商阶差商3 Newtons Interpolation11101010111010,.,.,.,.,., kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)阶差商：阶差商： Warning: my head is explodingWhat is the point of this formula?差商的值与差商的值与 xi 的顺序无关！的顺序无关！注：注： 阶差商必须由阶差商必须由 个节点构成，个节点构成， 个

3、节点是构造不个节点是构造不出出 阶差商的。阶差商的。k1kkk 为统一起见为统一起见, ,补充定义函数补充定义函数 为零阶差商。为零阶差商。)(0 xf,0120110 xxxfxxxxfxxxfkkk 2).2).差商具有对称性，即差商具有对称性，即3).3).若若 在在 上有上有 阶导数阶导数, ,且节点且节点 则则 阶差商与阶差商与 阶导数有如下关系式：阶导数有如下关系式：)(xf,ban),(,nibaxi10 nn!)(,)(10nfxxxfnn ,ba 4).4).若若 是是 次多项式，则其次多项式，则其 阶差商阶差商 当当 时是一个时是一个 次多项式，而当次多项式，而当 时恒为零

4、时恒为零. .)(xfnk,110 xxxxfk nk kn nk 差商性质：3 Newtons Interpolation kjjkjxxf01)()( kjkjjjjjjjkxxxxxxxxxfxxf01100)()()()(, 1). 1). 阶差商可表为函数值阶差商可表为函数值 的线性组合，即的线性组合，即k)(,),(),(10kxfxfxf3 Newtons Interpolation三阶差商三阶差商二阶差商二阶差商一阶差商一阶差商ix0 x1x2x3x)(ixf)(0 xf)(1xf)(2xf)(3xf,10 xxf,21xxf,32xxf,210 xxxf,321xxxf,32

5、10 xxxxf0101)()(xxxfxf 1212)()(xxxfxf 2323)()(xxxfxf 021021,xxxxfxxf 132132,xxxxfxxf 差商计算可列差商表如下差商计算可列差商表如下03210321),(),(xxxxxfxxxf NewtonNewton插值是通过选取特殊的基函数来实现的，这时，取插值是通过选取特殊的基函数来实现的，这时，取作为作为NewtonNewton插值的以插值的以 为节点的基函数，而次数为节点的基函数，而次数不超过不超过 的多项式的多项式 可表示为可表示为nxxx,10n)(xNn)()(110 nnxxxxxxc)()()(10201

6、0 xxxxcxxccxNn 其中其中 是待定系数，由插值条件是待定系数，由插值条件 决定。决定。nccc,10) 1 . 2 ( 牛顿插值牛顿插值 /* Newtons Interpolation */1,1 ,0),()()(1)(10 nixxxxxiii 000)()(cxNxfn ,)()()()( )()()(10010110110011011xxfxxxfxfcxxcxfxxccxNxfn 得得3 Newtons Interpolation )(,)(,)()(102100100 xxxxxxxfxxxxfxfxNn 通过插值条件运用数学归纳法可以求得通过插值条件运用数学归纳法可

7、以求得因此就得到下列的满足插值条件因此就得到下列的满足插值条件(2.1)(2.1)的的 次插值多项式次插值多项式n)()(,110, 10 nnxxxxxxxxxf,10kkxxxfc 3 Newtons Interpolation3 Newtons Interpolation,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf )()()()()(10102010 nnnxxxxcxxxxcxxccxN12 n 11+ (x x0) 2+ + (x x0)(x xn 1) n 1.)(,)(,

8、)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ci = f x0, , xi 注：注： 由由唯一性可知唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其只是算法不同，故其余项也相同，即余项也相同，即)(!)1()()(,.,1)1(10 xnfxxxxfnxnnn ),(,!)(,.,maxmin)(0 xxkfxxfkk HW p.50 #6,#8,#9kx)(kxf0.41075 0.57815 0.69675 0.888110.40 0.55 0.65 0.8

9、0例例 已知函数已知函数)(xf在各节点处的函数值如下在各节点处的函数值如下,用用NewtonNewton插值插值)596. 0(f的值的值.法求法求3 Newtons Interpolation解解: 0.197330.280000.358931.116001.186001.275730.410750.578150.696750.888110.400.550.650.80三阶三阶二阶二阶一阶一阶kx)(kxf)65. 0)(55. 0)(4 . 0(19733. 0)55. 0)(4 . 0(28000. 0)4 . 0(11600. 141075. 0)(3 xxxxxxxN62836.

10、0)596. 0(f3 Newtons Interpolation3 Newtons Interpolation 等距节点公式等距节点公式 /* Formulae with Equal Spacing */向前差分向前差分 /* forward difference */iiifff 1向后差分向后差分 /* backward difference */111 ikikikfffi 1iifff 中心差分中心差分 /* centered difference */212111 ikikikfff 其中其中)(221hiixff 当节点当节点等距等距分布时分布时:),.,0(0nihixxi M

11、ore given on p.28.p.29ikikikikffff1111)( 3 Newtons Interpolation 差分的重要性质：差分的重要性质： 线性：例如线性：例如gbfaxgbxfa )()( 若若 f (x)是是 m 次多项式，则次多项式，则 是是 次多项次多项式，而式，而)0()(mkxfk km )(0)(mkxfk 差分值可由函数值算出：差分值可由函数值算出： njjknjknfjnf0)1( njnjkjnknfjnf0) 1(!)1).(1(jjnnnjn 其中其中/* binomial coefficients */ 函数值可由差分值算出：函数值可由差分值算

12、出：kjnjknfjnf 0kkkhkfxxf!,.,00 knkknnnhkfxxxf!,.,1 kkkhff0)()( 由由 Rn 表达式表达式归归纳纳法法3 Newtons Interpolation牛顿公式牛顿公式).(,.,.)(,)()(1000100 nnnxxxxxxfxxxxfxfxN 牛顿前插公式牛顿前插公式 /* Newtons forward-difference formula */ 牛顿后插公式牛顿后插公式 /* Newtons backward-difference formula */将节点顺序倒置：将节点顺序倒置：).(,.,.)(,)()(101xxxxxx

13、fxxxxfxfxNnnnnnnn 注：注：一般当一般当 x 靠近靠近 x0 时用前插，靠近时用前插，靠近 xn 时用后插，故两时用后插，故两种公式亦称为种公式亦称为表初公式表初公式和和表末公式表末公式。),(,).(1()!1()()(01)1(nnnnxxhntttnfxR ，n设设htxx 0则则)()()(000 xfkhtxNxNkknn ),(,).(1()!1()()(01)1(nnnnxxhntttnfxR )10( tt设设htxxn 则则)() 1()()(0nknkknnnxfkthtxNxN ) 01( t，使用使用NewtonNewton前插或后插公式，先构造差分表如

14、下前插或后插公式，先构造差分表如下: :kx0 x1x2x3x)(kxf0y1y2y3yky0y1y2yky202y12yky303yky43 Newtons Interpolation例例 已知数值表如下，分别用向前、向后已知数值表如下，分别用向前、向后Newton插值公式插值公式求求sin0.57891的近似值。的近似值。x0.40.50.60.7sinx0.389420.479430.564640.64422解解：作差分表作差分表-0.00083-0.00480-0.005630.090010.079580.389420.479430.564640.644220.40.50.60.7si

15、nxx 2 3 3 Newtons Interpolation使用向前插公式，取使用向前插公式，取x0=0.5，x1=0.6, x2=0.7, x=x0+th, h=0.1,t=(x-x0)/h=0.7891,于是于是200563. 0)17894. 0(7891. 008521. 07891. 047943. 02)1()57891. 0(02002 fttftfN误差误差)7 . 05 . 0)cos)(27891. 0)(17891. 0(7891. 0! 31 . 0)(32 ( xR故故5521095. 25 . 0cos1036. 3)( xR若用向后插公式，则可取若用向后插公式，

16、则可取x0=0.6，x-1=0.5, x-2=0.4, x=x0+th, t=-0.2109,于是于是0.54714 3 Newtons Interpolation误差误差)6 . 04 . 0( ),cos)(22109. 0)(12109. 0)(2109. 0(! 31 . 0)(32 xR故故521057. 4)( xR0.54707 3 Newtons Interpolation)00480. 0(2)12109. 0)(2109. 0(08521. 0)2109. 0(56464. 0! 2)1()57891. 0(02020 fttftfN4 埃尔米特插值埃尔米特插值 /* He

17、rmite Interpolation */不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数也重合。也重合。即：要求插值函数即：要求插值函数 (x) 满足满足 (xi) = f (xi), (xi) = f (xi), (mi) (xi) = f (mi) (xi).注：注： N 个条件可以确定个条件可以确定 阶多项式。阶多项式。N 1要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插值多项式即为值多项式即为Taylor多项式多项式00)(!)(.)()()(000)(000mmxxmxfxxxfxfx 其余项为其余项为)1(00)

18、1(00)()!1()()()()(mmxxmfxxfxR 低次埃尔米特插值多项式低次埃尔米特插值多项式x)(xf)( xf0 x0y0m1x1y1m设给定区间设给定区间 两端点处的函数值与导数值如下：两端点处的函数值与导数值如下：,10 xx求插值多项式求插值多项式 , ,使满足使满足)(3xH由于给出了四个条件，故可唯一确定出一个三次多项式，由于给出了四个条件，故可唯一确定出一个三次多项式，不妨设不妨设110011003)()()()()(mxmxyxyxxH 1.1.二点三次埃尔米特插值多项式二点三次埃尔米特插值多项式 113003113003mxHmxHyxHyxH)( ,)( )(,

19、)(4 Hermite Interpolation 0)(01)(jiijjixx ji ji 01)(ijjix ji ji 0)( jix )1 ,0,( ji);1 ,0,( ,)(22jijixxxxxljiji 取取再者，由插值条件易知再者，由插值条件易知 应该满足条件应该满足条件)(),(jijixx 2 , 1, ji首先，首先， 应该为三次式。应该为三次式。)()(),()(1100 xxxx 与与与与)()(),()(1100 xxxx 与与因此问题归结为构造因此问题归结为构造4 Hermite Interpolation 0)( )(21000000000 xlbxaabx

20、a解之得解之得令令 , ；1 ,0)()()()()()(22 ixlxxcxxlbxaxiiiiiiii 其中其中 为待定系数，由为待定系数，由 ， 知知 iiicba,1)(00 x 0)(00 x 00,ba满足满足100000010000121)(2112)(2xxxxlxbxxxla 4 Hermite Interpolation ,)(21 ()(20100111xxxxxxxxx ,)()(210100 xxxxxxx 201011)()(xxxxxxx 于是于是类似可以求得类似可以求得21011000)(21 ()(xxxxxxxxx 故故)()()()()()21 ()()2

21、1 ()(211120002101112010003xlxxmxlxxmxlxxxxyxlxxxxyxH 4 Hermite Interpolation i 1注：注：ix)(（特别的，（特别的，f(x)=1） 1133)()(mxHyxHii)2 , 1 , 0( i利用满足三个条件的利用满足三个条件的NewtonNewton插值多项式，我们设插值多项式，我们设要求三次多项式要求三次多项式 , ,使使)(3xH)()()(,)(,)(2101021001003xxxxxxkxxxxxxxfxxxxfyxH 2.2.三点三次带一个导数值的插值多项式三点三次带一个导数值的插值多项式假设给定的函数

22、表如下：假设给定的函数表如下：x)(xf)( xf0 x0y1x1y1m2x2y 4 Hermite Interpolation 11201012101013)()(,)( mxxxxkxxxxxfxxfxH 其中其中 为待定系数，显然为待定系数，显然 满足前三个插值条件，满足前三个插值条件，利用第四个条件确定常数利用第四个条件确定常数 ，于是，于是k)(3xHk将其代入，即可得到将其代入，即可得到 的表达式的表达式: :)(3xH)()(,211001210101xxxxxxxxxfxxfmk 4 Hermite Interpolation )()()()(, )(,)(,)(2102110

23、012101011021001003xxxxxxxxxxxxxxxfxxfmxxxxxxxfxxxxfyxH 4 Hermite Interpolation一般地，已知一般地，已知 x0 , , xn 处有处有 y0 , , yn 和和 y0 , , yn ，求，求 H2n+1(x) 满足满足 H2n+1(xi) = yi ， H2n+1(xi) = yi。解：解：设设ni)()()(0iixxyixH2n+1n0iyi其中其中 i(xj) = ij , i(xj) = 0, (xj) = 0, (xj) = ij i ii(x)有零点有零点 x0 , , xi , , xn且都是且都是2重零

24、点重零点 )()()(2xlBxAxiiii ijjijixxxxxl)()()(由余下条件由余下条件 i(xi) = 1 和和 i(xi) = 0 可解可解Ai 和和 Bi )()(21 )(2xlxxxlxiiiii i)()(iili2(x)xxCx i)(x)(ili2(x)xx 设设,.210baCfbxxxann 则则20)22()()!22()()( niixnnxxnfxR (x)i有零点有零点 x0 , , xn, 除了除了xi 外都是外都是2重零点重零点 又又: (xi) = 1 Ci = 1i这样的这样的Hermite 插值唯一插值唯一4 Hermite Interpol

25、ationQuiz: 给定给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是下面哪个是 2(x)的图像？的图像？x0-10.5123456yxy0-10.5123456斜率斜率=1 HW: p.50#10，#11，Remember what I have said? Increasing the degree of interpolating polynomial will NOT guarantee a good result, since high-degree polynomials are oscillating.例：例：在在 5, 5上考察上考察 的的

26、Ln(x)。取。取211)(xxf),., 0(105niinxi -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端点附近抖动端点附近抖动越大，称为越大，称为Runge 现象现象Ln(x) f (x) 5 分段低次插值分段低次插值 /* piecewise polynomial approximation */ 在区间在区间 上用插值多项式上用插值多项式 近似函数近似函数 ，是否，是否 的的次数越高，逼近效果越好呢，回答是否定的。由于次数越高次数越高，逼近效果越好呢，回答是否定的。由于次数越高计算工作量也越大，积累误差也越大

27、；在整个区间上作个高计算工作量也越大，积累误差也越大；在整个区间上作个高次多项式，当局部插值节点的值有微小误差时，就可能引起次多项式，当局部插值节点的值有微小误差时，就可能引起整个区间上函数值的较大变化，使计算不稳定。整个区间上函数值的较大变化，使计算不稳定。,ba)(xPn)(xf)(xPnkkkkkhhxxhmax,1 ,)() 1(baCxIh 所谓的分段线性插值就是通过插值点用折线段连接起来所谓的分段线性插值就是通过插值点用折线段连接起来逼近逼近 . .设已知节点设已知节点 上函数上函数值值 ，记记)(xf10 xxa bxn nfff,10), 1 , 0()() 2(nkfxIkk

28、h 求一折线函数求一折线函数 满足满足)(xIh则称则称 为分段线性插值函数。为分段线性插值函数。)(xIh0( )( )nhk kkIxf lx设设 分段线性插值分段线性插值 /* piecewise linear interpolation */分段分段低次低次插值插值5 piecewise polynomial approximation)() 3 (xIh在每个小区间在每个小区间 上上都是线性函数。都是线性函数。,1 kkxx,)(11111 kkkkkkkkkkhxxxfxxxxfxxxxxI由定义可知由定义可知 在每个小区间上可表示为在每个小区间上可表示为)(xIh ., 0)(,)0(,)(11111111kkkkkkkkk-kkkkxxxbaxnkxx xxxxxkxx xxxxxxl但但 )(xlk1kx1 kx1 kx一致一致记记 ，易证：当，易证：当 时，时，0h|max1kkxxh )()(xfxIh失去了原函数的光滑性