第七讲：代数插值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 )()( Warning: my head is exploding What is the point of this formula? 差商的值与差商的值与 xi 的顺序无关！的顺序无关！ 2 Newtons Interpolation 牛顿插值牛顿插值 /* Newtons Interpolation */ ,)()()( 000 xxfxxxfxf ,)(, 101100 xxxfxxxxfxxf ,.,)(,.,., 0010nnnn xxxfxxxxfxxxf ).(.)()()( 10102010 nnn xxxxaxxxxaxxaaxN

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

5、 ! )( ,., maxmin )( 0 xx k f xxf 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, xnf x0, , xn f (xn+1) f xn, xn+1 f xn 1, xn, xn+1 f x1, , xn+1 f x0, , xn+1 2 Newtons Interpolation 等距节点公式等距节点公式 /* Formulae with Equal Spacing */ 向前差分向前差

6、分 /* forward difference */ 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.174. 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

8、 k k hk f xxf ! ,., 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 */ 将节点顺序倒置：将节点顺序倒置： ).(,.,.)(,)

9、()( 101 xxxxxxfxxxxfxfxN 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 时用向后插时用向后插 值，故两种公式亦称为值，故两种公式亦称为表初公式表初公式和和表末公式表末公式。 3 埃尔米特插值埃尔米特插值 /*

10、 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 )( 000 m m xx m

11、 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), 并估计误差。并估计误差。 模仿模仿 Lagrange 多项式的思想，设多项式的思想，设解：解：首先，首先，P 的阶数的阶数

12、= 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 可解。可解。 与与h0(x) 完全类似。完全类似。 (x) h1 有根有根 x0, x1, x2 h1)()

13、()( 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 和和 y0, , yn ，求，求 H2n+1(x) 满满 足足 H2n+1(xi) = yi ， H2n+1(

14、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 和和 Bi )()(21 )( 2 xlxxxlxh iiiii (x) hi 有根有根 x0 , , xn,

15、 除了除了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 Q: 给定给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是下面哪个是 h2(x)的图像？的图像？ x 0 - -1 0.5 123456 y x y 0 -

16、 - -1 0.5 123456 斜率斜率=1 求求Hermite多项式的基本步骤：多项式的基本步骤： 写出相应于条件的写出相应于条件的hi(x)、 hi(x) 的组合形式；的组合形式； 对每一个对每一个hi(x)、 hi(x) 找出尽可能多的条件给出的根；找出尽可能多的条件给出的根； 根据多项式的总阶数和根的个数写出表达式；根据多项式的总阶数和根的个数写出表达式； 根据尚未利用的条件解出表达式中的待定系数；根据尚未利用的条件解出表达式中的待定系数； 最后完整写出最后完整写出H(x)。 4 分段低次插值分段低次插值 /* piecewise polynomial approximation *

17、/ 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上考察上考察 的的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) 分段分段低次低次插值插值 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 ,for 1 ii xxx 记记 ，易证：当，易证：当 时，时，|max 1ii xx