第四章 插值 /* Interpolation */

Presentation on theme: "第四章 插值 /* Interpolation */"— Presentation transcript:

1 第四章 插值 /* 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) 的插值函数。最常用的插值函数是 …? 多项式 g(x)  f(x) x0 x1 x2 x3 x4 x

2 称为拉氏基函数 /* Lagrange Basis */， 满足条件 li(xj)=ij /* Kronecker Delta */
§1 拉格朗日多项式 /* Lagrange Polynomial */ n i y x P , ... ) ( = 求 n 次多项式 使得 条件：无重合节点，即 n = 1 称为拉氏基函数 /* Lagrange Basis */， 满足条件 li(xj)=ij /* Kronecker Delta */ 已知 x0 , x1 ; y0 , y1 ，求 使得 1 ) ( , y x P = 可见 P1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。 ) ( 1 x y P - + = 1 x - = y y1  = 1 ) ( i y x l l0(x) l1(x)

3    希望找到li(x)，i = 0, …, n 使得 li(xj)=ij ；然后令 n  1
y x l P ) ( ，则显然有Pn(xi) = yi 。 n  1 li(x) 每个 li 有 n 个根 x0 … xi … xn 与 有关，而与 无关 Lagrange Polynomial 节点 f  = - n j j  i i x C l ) ( )...(  - = j  i j i x C l ) ( 1

4 定理 (唯一性) 满足 的 n 阶插值多项式是唯一存在的。 证明： ( p.105-106 利用Vandermonde 行列式论证)
反证：若不唯一，则除了Ln(x) 外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 。 考察 则 Qn 的阶数  n 而 Qn 有 个不同的根 n + 1 x0 … xn 注：若不将多项式次数限制为 n ，则插值多项式不唯一。 例如 也是一个插值多项式，其中 可以是任意多项式。

5    插值余项 /* Remainder */ 设节点 在[a , b]内存在, 考察截断误差 ，且 f 满足条件 ,
= - n i x K R ) ( Rn(x) 至少有 个根 Rolle’s Theorem: 若 充分光滑， ，则 存在 使得 。 n+1 注意这里是对 t 求导 任意固定 x  xi (i = 0, …, n), 考察  = -  n i x t K Rn ) ( j 推广：若 (x)有 n+2 个不同的根 x0 … xn x 使得 使得 = + - ! ) 1 )( ( n x K L f ! ) 1 ( + - n x K R 存在 使得 ! ) 1 ( + = n f x K

6 当 f(x) 为任一个次数 n 的多项式时， , 可知 ，即插值多项式对于次数 n 的多项式是精确的。
注： 通常不能确定 x , 而是估计 , x(a,b) 将 作为误差估计上限。 当 f(x) 为任一个次数 n 的多项式时， , 可知 ，即插值多项式对于次数 n 的多项式是精确的。 Quiz: 给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是 l2(x)的图像？ y - 1 0.5 2 3 4 5 6 x A B C 

7 内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。
例：已知 分别利用 sin x 的1次、2次 Lagrange 插值计算 sin 50 并估计误差。 解： n = 1 分别利用x0, x1 以及 x1, x2 计算 利用 内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。 ) 18 5 ( 50 sin 1  p L 这里 而 sin 50 = … 外推 /* extrapolation */ 的实际误差   利用 sin 50  , 内插 /* interpolation */ 的实际误差 

8 sin 50 = 0.7660444… 2次插值的实际误差  0.00061 高次插值通常优于低次插值
) 18 5 ( 50 sin 2  p L sin 50 = … 2次插值的实际误差  高次插值通常优于低次插值 但绝对不是次数越高就越好，嘿嘿……

9 §2 牛顿插值 /* Newton’s Interpolation */
Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x) 都需重新算过。 ? 将 Ln(x) 改写成 的形式，希望每加一个节点时， 只附加一项上去即可。  差商(亦称均差) /* divided difference */ 1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */ 2阶差商

10 Warning: my head is exploding… What is the point of this formula?
(k+1)阶差商： 1 ] , ... [ + - = k x f 事实上 其中 Warning: my head is exploding… What is the point of this formula? 差商的值与 xi 的顺序无关！

11 … … … … ai = f [ x0, …, xi ]  牛顿插值 /* Newton’s Interpolation */ Nn(x)
1 2 … … … … n1 1 + (x  x0)  2 + … … + (x  x0)…(x  xn1)  n1 Nn(x) ai = f [ x0, …, xi ] Rn(x)

12  实际计算过程为 注： 由唯一性可知 Nn(x)  Ln(x)， 只是算法不同，故其余项也相同，即 f (x0) f (x1)
… 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]

13  等距节点公式 /* Formulae with Equal Spacing */
当节点等距分布时: 向前差分 /* forward difference */ i f - =  + 1 i k f 1 ) ( - +  = 向后差分 /* backward difference */ i1 i f - =  1 -  = i k f 中心差分 /* centered difference */ 其中

14    差分的重要性质：  线性：例如  若 f (x)是 m 次多项式，则 是 次多项式，而  差分值可由函数值算出： 其中
 线性：例如  若 f (x)是 m 次多项式，则 是 次多项式，而  差分值可由函数值算出：  = - + D n j k f ) 1 (  其中 /* binomial coefficients */ k j n f D  = +  函数值可由差分值算出： k h f x ! ] , ... [ D = n 1  - 由 Rn 表达式  k h f ) ( D = x

15    牛顿前差公式 /* Newton’s forward-difference formula */
牛顿公式  牛顿前差公式 /* Newton’s forward-difference formula */ 设 ，则 ) ( x f k t h N n  = +   牛顿后差公式 /* Newton’s backward-difference formula */ 将节点顺序倒置： 设 ，则 ) ( 1 n k x f t h N  - = +  注：一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为表初公式和表末公式。

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

17 例：设 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 1 3 ) ( i x h x1 f ’ f P  其中 hi(xj) = ij , hi’(x1) = 0, (xi) = 0, ’(x1) = 1  h1 有根 x1, x2，且 h0’(x1) = 0  x1 是重根。 h0(x) ) ( 2 1 x C h - = 又: h0(x0) = 1  C0 h2(x) 与h0(x) 完全类似。 h1(x) 有根 x0, x2  与 Lagrange 分析完全类似 ) )( ( 2 1 x B Ax h - + = 由余下条件 h1(x1) = 1 和 h1’(x1) = 0 可解。 (x)  h1  h1 ) )( ( 2 1 x C - = 有根 x0, x1, x2   h1 又: ’(x1) = 1  C1 可解。

18 一般地，已知 x0 , …, xn 处有 y0 , …, yn 和 y0’ , …, yn’ ，求 H2n+1(x) 满足 H2n+1(xi) = yi ， H’2n+1(xi) = yi’。
 + = n i ) ( x h yi H2n+1  yi’ 解：设 其中 hi(xj) = ij , hi’(xj) = 0, (xj) = 0, ’(xj) = ij  hi 这样的Hermite 插值唯一 hi(x) 有根 x0 , …, xi , …, xn且都是2重根   ) ( 2 x l B A h i + = 由余下条件 hi(xi) = 1 和 hi’(xi) = 0 可解Ai 和 Bi  (x)  hi  hi ) ( i li2(x) x C - = 有根 x0 , …, xn, 除了xi 外都是2重根   hi 又: ’(xi) = 1  Ci = 1  hi ) ( x i li2(x) - = 设 则

19   求Hermite多项式的基本步骤：  写出相应于条件的hi(x)、 hi(x) 的组合形式；
Quiz: 给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是 h2(x)的图像？  x - 1 0.5 2 3 4 5 6 y  斜率=1  求Hermite多项式的基本步骤：  写出相应于条件的hi(x)、 hi(x) 的组合形式；   对每一个hi(x)、 hi(x) 找出尽可能多的条件给出的根；   根据多项式的总阶数和根的个数写出表达式；  根据尚未利用的条件解出表达式中的待定系数；  最后完整写出H(x)。

20  §4 分段低次插值 /* piecewise polynomial approximation */ 分段低次插值
例：在[5, 5]上考察 的Ln(x)。取 - 5 4 3 2 1 0.5 1.5 2.5 Ln(x)  f (x)  Remember what I have said? Increasing the degree of interpolating polynomial will NOT guarantee a good result, since high-degree polynomials are oscillating. n 越大， 端点附近抖动 越大，称为 Runge 现象 分段低次插值

21  分段线性插值 /* piecewise linear interpolation */
在每个区间 上，用1阶多项式 (直线) 逼近 f (x): 记 ，易证：当 时， 一致 失去了原函数的光滑性。 How can we make a smooth interpolation without asking too much from f ? Headache …  分段Hermite插值 /* Hermite piecewise polynomials */ 给定 在 上利用两点的 y 及 y’ 构造3次Hermite函数 导数一般不易得到。

22 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? Right. Then all the Lagrange basis, li(x), will have to be re-calculated. Then you might want to take more interpolating points into account. Excellent point ! We will come to discuss this problem next time.