数值分析--22插值2

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

2、xfxf xxf 1阶差商阶差商 /* the 1st divided difference of f w.r.t. xi and xj */ )( , ,ki xx xxfxxf xxxf ki kjji kji 2阶差商阶差商 2 Newtons Interpolation 1 11010 10 1110 10 ,.,., ,.,., ,., kk kkkk k kkk k xx xxxfxxxf xx xxxfxxxf xxf (k+1)阶差商：阶差商： k i ik i k x xf xxf 0 1 0 )( )( ,., 事实上事实上 其中其中,)()( 0 1 k i ik xxx

3、 k ij j jiik xxx 0 1 )()( 差商的值与差商的值与 xi 的顺序无关！的顺序无关！ 2 Newtons Interpolation 牛顿插值牛顿插值 /* Newtons Interpolation */ ,)()()( 000 xxfxxxfxf ,)(, 101100 xxxfxxxxfxxf ,.,)(,.,., 0010nnnn xxxfxxxxfxxxf ).(.)()()( 10102010 nnn xxxxaxxxxaxxaaxN 1 2 n 1 1+ (x x0) 2+ + (x x0)(x xn 1) n 1 .)(,)(,)()( 102100100

4、xxxxxxxfxxxxfxfxf ).(,., 100 nn xxxxxxf )().(,., 100nnn xxxxxxxxxf Nn(x) Rn(x) ai = f x0, , xi 注：注： 由唯一性可知由唯一性可知 Nn(x) Ln(x)， 只是算法不同，只是算法不同， 故其余项也相同，即故其余项也相同，即 )( ! ) 1( )( )(,., 1 ) 1( 10 x n f xxxxf n x n nn 2 Newtons Interpolation 实际计算过程为实际计算过程为 f (x0) f (x1) f (x2) f (xn 1) f (xn) f x0, x1 f x1,

5、 x2 f xn 1, xn f x0, x1 , x2 f xn 2, xn 1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn 1, xn, xn+1 f x1, , xn+1 f x0, , xn+1 ),(, !)1( )( ,., maxmin )1( 0 xx n f xxxf n n ),(, ! )( ,., maxmin )( 0 xx k f xxf k k 2 Newtons Interpolation 等距节点公式等距节点公式 /* Formulae with Equal Spacing */ 向前差分向前差分 /* forward dif

6、ference */ iii fff 1 i k i k i k i k ffff 1 1 11 )( 向后差分向后差分 /* backward difference */ 1 11 i k i k i k fff i 1ii fff 中心差分中心差分 /* centered difference */ 2 1 2 1 11 i k i k i k fff 其中其中 )( 2 2 1 h i i xff 当节点当节点等距等距分布时分布时: ),.,0( 0 nihixxi More given on p. 37-38. 2 Newtons Interpolation 差分的重要性质：差分的重要

7、性质： 线性：例如 线性：例如gbfaxgbxfa )()( 若 若 f (x)是是 m 次多项式，则次多项式，则 是是 次多项次多项 式，而式，而 )0()(mkxf k km )(0)(mkxf k 差分值可由函数值算出： 差分值可由函数值算出： n j jkn j k n f j n f 0 )1( n j njk jn k n f j n f 0 ) 1( ! )1).(1( j jnnn j n 其中其中 /* binomial coefficients */ 函数值可由差分值算出： 函数值可由差分值算出：k j n j kn f j n f 0 k k k hk f xxf ! ,

8、., 0 0 k n k knnn hk f xxxf ! ,., 1 k k k h f f 0 )( )( 由由 Rn 表达式表达式 2 Newtons Interpolation 牛顿公式牛顿公式 ).(,.,.)(,)()( 1000100 nnn xxxxxxfxxxxfxfxN 牛顿向前插值公式牛顿向前插值公式 /* Newtons forward-difference formula */ 牛顿向后插值公式牛顿向后插值公式 /* Newtons backward-difference formula */ 将节点顺序倒置：将节点顺序倒置： ).(,.,.)(,)()( 101 x

9、xxxxxfxxxxfxfxN nnnnnnn 设设htxx 0 ，则，则 )()()( 0 0 0 xf k t htxNxN k n k nn ),(,).(1( )!1( )( )( 0 1 )1( n n n n xxhnttt n f xR 设设htxx n ，则，则)() 1()()( 0 n k n k k nnn xf k t htxNxN 注：注：一般当一般当 x 靠近靠近 x0 时用时用向前插值向前插值，靠近，靠近 xn 时用时用向后插向后插 值值，故两种公式亦称为，故两种公式亦称为表初公式表初公式和和表末公式表末公式。 0 ),(,).(1( )!1( )( )()( 0

10、 1 )1( t xxhnttt n f thxRxR n n n nnn 3 厄米插值厄米插值 /* Hermite Interpolation */ 不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数也重合。也重合。 即：要求插值函数即：要求插值函数 (x) 满足满足 (xi) = f (xi), (xi) = f (xi), , (mi) (xi) = f (mi) (xi). 注：注： N 个条件可以确定个条件可以确定 阶多项式。阶多项式。N 1 要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插 值多项式即为值多项式即为Ta

11、ylor多项式多项式 0 0 )( ! )( .)()()( 0 0 0 )( 000 m m xx m xf xxxfxfx 其余项为其余项为 )1( 0 0 )1( 0 0 )( )!1( )( )()()( m m xx m f xxfxR 一般只考虑一般只考虑 f 与与f 的值。的值。 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), 并估计误差。并估计误

12、差。 模仿模仿 Lagrange 多项式的思想，设多项式的思想，设解：解：首先，首先，P 的阶数的阶数 = 3 2 13 )()()()()( 0 i ii xhx1f xhxfxP h0(x) 有根有根x1, x2，且且 h0(x1) = 0 x1 是重根。是重根。)()()( 2 2 100 xxxxCxh 又又: h0(x0) = 1 C0 )()( )()( )( 20 2 10 2 2 1 0 xxxx xxxx xh h2(x) h1(x) 有根有根 x0, x2 )()()( 201 xxxxBAxxh 由余下条件由余下条件 h1(x1) = 1 和和 h1(x1) = 0 可解

13、。可解。 与与h0(x) 完全类似。完全类似。 (x) h1 有根有根 x0, x1, x2 h1)()()( 2101 xxxxxxCx h1又又: (x1) = 1 C1 可解。可解。 其中其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x1) = 1 h1 h1 ),()()()()()( 2 2 1033 xxxxxxxKxPxfxR !4 )( )( )4( x f xK 与与 Lagrange 分析分析 完全类似完全类似 3 Hermite Interpolation 一般地，已知一般地，已知 x0 , , xn 处有处有 y0 , , yn 和和

14、y0 , , yn ，求，求 H2n+1(x) 满足满足 H2n+1(xi) = yi ， H2n+1(xi) = yi。 解：解：设设 n i )()()( 0 i i xhxhyixH2n+1 n 0 i yi 其中其中 hi(xj) = ij , hi(xj) = 0, (xj) = 0, (xj) = ij hi hi hi(x) 有根有根 x0 , , xi , , xn且都是且都是2重根重根 )()()( 2 xlBxAxh iiii ij ji j i xx xx xl )( )( )( 由余下条件由余下条件 hi(xi) = 1 和和 hi(xi) = 0 可解可解Ai 和和

15、Bi )()(21 )( 2 xlxxxlxh iiiii (x) hi 有根有根 x0 , , xn, 除了除了xi 外都是外都是2重根重根 hi)()( ii li2(x)xxCx hi又又: (xi) = 1 Ci = 1 hi)(x)( i li2(x)x x 设设 ,. 2 10 baCfbxxxa n n 则则 2 0 )22( )( )!22( )( )( n i i x n n xx n f xR 这样的这样的Hermite 插值唯插值唯 一一 3 Hermite Interpolation Quiz: 给定给定 xi = i +1, i = 0, 1, 2, 3, 4, 5.

16、 下面哪个是下面哪个是 h2(x)的图像？的图像？ x 0 - -1 0.5 123456 y x y 0 - - -1 0.5 123456 斜率斜率=1 求求Hermite多项式的基本步骤：多项式的基本步骤： 写出相应于条件的写出相应于条件的hi(x)、 hi(x) 的组合形式；的组合形式； 对每一个对每一个hi(x)、 hi(x) 找出尽可能多的条件给出的根；找出尽可能多的条件给出的根； 根据多项式的总阶数和根的个数写出表达式；根据多项式的总阶数和根的个数写出表达式； 根据尚未利用的条件解出表达式中的待定系数；根据尚未利用的条件解出表达式中的待定系数； 最后完整写出最后完整写出H(x)。

17、 4 分段低次插值分段低次插值 /* piecewise polynomial approximation */ 例：例：在在 5, 5上考察上考察 的的Ln(x)。取。取 2 1 1 )( x xf ),., 0( 10 5nii n xi -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) 高次多项式插值的缺陷高次多项式插值的缺陷: (1)产生产生Runge现象；现象；(2) 计算差分计算差分 和差商时，由于舍入误差而造成高阶差商和

18、差分的准确性，和差商时，由于舍入误差而造成高阶差商和差分的准确性， 而严重影响插值的精度。而严重影响插值的精度。 4 Piecewise Polynomial Approximation 分段线性插值分段线性插值 /* piecewise linear interpolation */ 在每个区间在每个区间 上，用上，用1阶多项式阶多项式 (直线直线) 逼近逼近 f (x): , 1 ii xx 1 11 1 1 )()( i ii i i ii i y xx xx y xx xx xPxf , 1 ii xxx anyfor 记记 ，易证：当，易证：当 时，时，|max 1ii xxh 0h

19、 )()( 1 xfxP h 一致一致 失去了原函数的光滑性。失去了原函数的光滑性。 分段分段Hermite插值插值 /* Hermite piecewise polynomials */ 给定给定 nnn yyyyxx ,.,;,.,;,., 000 在在 上利用两点的上利用两点的 y 及及 y 构造构造3次次Hermite函数函数 , 1 ii xx 导数一般不易得到。导数一般不易得到。 解决方案：采用分段解决方案：采用分段低次低次插值插值 分段分段Lagrange插值插值 /* Lagrange piecewise polynomials */ 给定给定 ;,.,;,., 00nn yyxx 在每个区间断在每个区间断 上作函数上作函数f(x)的的3次次Lagrange插值插值 多项式。多项式。 , 333ii xx 4 Piecewise Polynomial Approximation 当使用分段当使用分段3次次Lagrange 插值与分段插值与分段3次次Hermite插插 值多项式时，哪种计算效果更好值多项式时，哪种计算效果更好? 从误差上看，假设从误差上看，假设 ，分段，分段3次次Lagrange 插值：插值： 24/ )()()()()()( 3132333 )4( iiiin xxxxxxx