《数值分析Ch2 插值法综述》由会员分享，可在线阅读，更多相关《数值分析Ch2 插值法综述（32页珍藏版）》请在金锄头文库上搜索。
1、Ch2 插值法 /* Interpolation */ 当精确函数 y = f(x) 非常复杂或未知时，在一 系列节点 x0 xn 处测得函数值 y0 = f(x0), yn = f(xn)，由此构造一个简单易算的近似函 数 g(x) f(x)，满足条件g(xi) = f(xi) (i = 0, n)。这里的 g(x) 称为f(x) 的插值函数。最常 用的插值函数是 ? 多项式 x0 x1x2x3x4x g(x) f(x) 1 拉格朗日多项式 /* Lagrange Polynomial */ niyxP iin ,., 0,)(= 求 n 次多项式 使得 条件：无重合节点，即 n = 1 已
2、知 x0 , x1 ; y0 , y1 ，求使得 111001 )(,)(yxPyxP = 可见 P1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。 )()( 0 01 01 01 xx xx yy yxP += 10 1 xx xx 01 0 xx xx = y0 + y1 l0(x)l1(x) = = 1 0 )( i ii yxl 称为拉氏基函数 /* Lagrange Basis */， 满足条件 li(xj)=ij /* Kronecker Delta */ 1 Lagrange Polynomial n 1 希望找到li(x)，i = 0, , n 使
3、得 li(xj)=ij ；然后令 = = n i i in yxlxP 0 )()( ，则显然有Pn(xi) = yi 。 li(x) 每个 li 有 n 个根 x0 xi xn = = n j j i jiniii xxCxxxxxxCxl 0 0 )().().()( = j i ji iii xx Cxl )( 1 1)( Lagrange Polynomial 与 有关，而与 无关 节点f 1 Lagrange Polynomial 定理 (唯一性) 满足 的 n 阶插值多 项式是唯一存在的。 证明： 反证：若不唯一，则除了Ln(x) 外还有另一 n 阶多项 式 Pn(x) 满足 Pn
4、(xi) = yi 。 考察 则 Qn 的阶数 n 而 Qn 有 个不同的根n + 1x0 xn 注：若不将多项式次数限制为 n ，则插值多项式不唯一。 例如 也是一个插值 多项式，其中 可以是任意多项式。 1 Lagrange Polynomial 插值余项 /* Remainder */ 设节点 在a , b内存在, 考察截断误差 ，且 f 满足条件 , Rolles Theorem: 若 充分光滑， ，则 存在 使得 。 推广：若 使得使得 1 Lagrange Polynomial Rn(x) 至少有 个根n+1 = = n i in xxxKxR 0 )()()( 任意固定 x xi
5、 (i = 0, , n), 考察 = = n i i xtxKtRnt 0 )()()()( (x)有 n+2 个不同的根 x0 xn x !)1()()( )1( + + nxKR x n n 注意这里是对 t 求导 =+ + !)1)()()( )1()1( nxKLf x n nx n !)1( )( )( )1( + = + n f xK x n 1 Lagrange Polynomial 注： 通常不能确定 x , 而是估计 , x(a,b) 将 作为误差估计上限。 当 f(x) 为任一个次数 n 的多项式时， , 可知 ，即插值多项式对于次数 n 的多项式 是精确的。 1 Lag
6、range Polynomial 例：已知 分别利用 sin x 的1次、2次 Lagrange 插值计算 sin 50 并估计误差。 解： n = 1分别利用x0, x1 以及 x1, x2 计算 利用 这里 而 sin 50 = 0.7660444 ) 18 5 (50sin 1 0 p L0.77614 外推 /* extrapolation */ 的实际误差 0.01001 利用sin 50 0.76008, 内插 /* interpolation */ 的实际误差 0.00596 内插通常优于外推。选择 要计算的 x 所在的区间的 端点，插值效果较好。 1 Lagrange Poly
7、nomial n = 2 ) 18 5 (50sin 2 0 p L0.76543 sin 50 = 0.7660444 2次插值的实际误差 0.00061 高次插值通常优于 低次插值 但绝对不是次数越 高就越好，嘿嘿 When you start writing the program, you will find how easy it is to calculate the Lagrange polynomial. Oh yeah? What if I find the current interpolation not accurate enough? Then you might w
8、ant to take more interpolating points into account. Right. Then all the Lagrange basis, li(x), will have to be re-calculated. Excellent point ! We will come to discuss this problem next time. 2 牛顿插值 /* Newtons Interpolation */ Lagrange 插值虽然易算，但若要增加一个节点时， 全部基函数 li(x) 都需重新算过。 的形式，希望每加一个节点时， 将 Ln(x) 改写
9、成 只附加一项上去即可。 ? ? 差商(亦称均差) /* divided difference */ 1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */ 2阶差商 2 Newtons Interpolation 1 11010 10 1110 10 ,.,., ,.,., ,., + + + + + = = kk kkkk k kkk k xx xxxfxxxf xx xxxfxxxf xxf (k+1)阶差商： 事实上 其中 Warning: my head is exploding What is the point of
10、 this formula? 差商的值与 xi 的顺序无关！ 2 Newtons Interpolation 牛顿插值 /* Newtons Interpolation */ 1 2 n1 1 + (x x0) 2 + + (x x0)(x xn1) n1 Nn(x) Rn(x) ai = f x0, , xi 2 Newtons Interpolation 注： 由唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其 余项也相同，即 实际计算过程为 f (x0) f (x1) f (x2) f (xn1) f (xn) f x0, x1 f x1, x2 f xn1, xn f x0,
11、x1 , x2 f xn2, xn1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn1, xn, xn+1 f x1, , xn+1 f x0, , xn+1 2 Newtons Interpolation 等距节点公式 /* Formulae with Equal Spacing */ 向前差分 /* 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 i1ii fff=
12、 中心差分 /* centered difference */其中 当节点等距分布时: 2 Newtons Interpolation 差分的重要性质： 线性：例如 若 f (x)是 m 次多项式，则 是 次多项 式，而 差分值可由函数值算出： = + = n j jkn j k n f j n f 0 )1( = + = n j njk jn k n f j n f 0 ) 1( 其中/* binomial coefficients */ 函数值可由差分值算出： k j n j kn f j n f = + = 0 k k k hk f xxf ! ,., 0 0 = k n k knnn
13、hk f xxxf ! ,., 1 = k k k h f f 0 )( )( = 由 Rn 表达式 2 Newtons Interpolation 牛顿公式 牛顿前差公式 /* Newtons forward-difference formula */ 牛顿后差公式 /* Newtons backward-difference formula */ 将节点顺序倒置 ： 设，则 )()()( 0 0 0 xf k t htxNxN k n k nn =+= = 设，则 )() 1()()( 0 n k n k k nnn xf k t htxNxN =+= = 注：一般当 x 靠近 x0 时用
14、前插，靠近 xn 时用后插，故两 种公式亦称为表初公式和表末公式。 3 厄米插值 /* Hermite Interpolation */ 不仅要求函数值重合，而且要求若干阶导数也重合。 即：要求插值函数 (x) 满足 (xi) = f (xi), (xi) = f (xi), , (mi) (xi) = f (mi) (xi). 注： N 个条件可以确定 阶多项式。N 1 要求在1个节点 x0 处直到m0 阶导数都重合的插 值多项式即为Taylor多项式 其余项为 一般只考虑 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), 并估
