《第二部分插值法Chapter2Interpolation.ppt》由会员分享，可在线阅读，更多相关《第二部分插值法Chapter2Interpolation.ppt（32页珍藏版）》请在三一文库上搜索。
1、第二章 插值法 /* Chapter 2 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) 的插值函数。最常用的插值函数是 ?,多项式,x,g(x) f(x),2.1 多项式插值 /* Polynomial Interpolation */,2.2 拉格朗日多项式 /* Lagrange Polynomial */,n = 1,可见 P1
2、(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。,称为拉氏基函数 /* Lagrange Basis */， 满足条件 li(xj)=ij /* Kronecker Delta */,线性插值,n = 2,抛物线插值,多项式：,2.2 Lagrange Polynomial,2.2 Lagrange Polynomial,n 1,Lagrange Polynomial,与 有关，而与 无关,节点,f,证明：,反证：若不唯一，则除了Ln(x) 外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 。,考察 则 Qn 的阶数, n,而 Qn 有 个不同的根
3、,注：若不将多项式次数限制为 n ，则插值多项式不唯一。,例如 也是一个插值多项式，其中 可以是任意多项式。,2.2 Lagrange Polynomial, 插值余项 /* Remainder */,Rolles Theorem: 若 充分光滑， ，则 存在 使得 。,推广：若,使得,2.2 Lagrange Polynomial,Rn(x) 至少有 个根,n+1,(x)有 n+2 个不同的根 x0 xn x,注意这里是对 t 求导,2.2 Lagrange Polynomial,注： 通常不能确定 x , 而是估计 , x(a,b) 将 作为误差估计上限。,当 f(x) 为任一个次数 n
4、的多项式时， , 可知 ，即插值多项式对于次数 n 的多项式是精确的。,2.2 Lagrange Polynomial,注： 小的区间上插值有利于减少误差； 依靠增多插值节点不一定能减少误差； 多项式插值，外推误差可能要比内插误差大。,解：,n = 1,分别利用x0, x1 以及 x1, x2 计算,利用,这里,而,sin 50 = 0.7660444,外推 /* extrapolation */ 的实际误差 0.01001,利用,内插 /* interpolation */ 的实际误差 0.00596,内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。,2.2 Lagran
5、ge Polynomial,n = 2,sin 50 = 0.7660444,2次插值的实际误差 0.00061,高次插值通常优于低次插值,但绝对不是次数越高就越好,2.2 Lagrange Polynomial,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 want
6、 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.3 牛顿插值 /* Newtons Interpolation */,Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x) 都需重新算过。, 差商(亦称均差) /* divided differ
7、ence */,1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */,2阶差商,2.3 Newtons Interpolation,(k+1)阶差商：,Warning: my head is exploding What is the point of this formula?,差商的值与 xi 的顺序无关！, 牛顿插值 /* Newtons Interpolation */, ,Nn(x)-牛顿插值多项式,Rn(x),ai =,f x0, , xi ,2.3 Newtons Interpolation,注： 由唯一性可知 N
8、n(x) Ln(x)， 只是算法不同，故其余项也相同，即, 实际计算过程为,f (x0) f (x1) f (x2) f (xn1) f (xn),f x0, x1 f x1, x2 f xn1, xn,f x0, x1 , x2 f xn2, xn1, xn,f x0, , xn,f (xn+1) f xn, xn+1 f xn1, xn, xn+1 f x1, , xn+1 f x0, , xn+1,2.3 Newtons Interpolation,2.3 Newtons Interpolation,例4 (P32): 给出f (x)的函数表，求4次牛顿插值多项式，并由此计算f (0.5
9、96)的近似值。,N4(x)=0.41075+1.116(x-0.4)+0.28(x-0.4)(x-0.55)+0.19733(x-0.4)(x-0.55)(x-0.65) +0.03134 (x-0.4)(x-0.55)(x-0.65)(x-0.8),f(0.596)N4(0.596)=0.63192,R4(x)=fx,x0, xn (x-0.4)(x-0.55)(x-0.65)(x-0.8)(x-0.9),R4(0.596)=?, 差分形式等距节点公式 /* Formulae with Equal Spacing */,向前差分,向后差分,中心差分,其中,当节点等距分布时:,2.3 New
10、tons Interpolation, 差分的重要性质：, 线性：例如, 若 f (x)是 m 次多项式，则 是 次多项式，而, 差分值可由函数值算出：, 函数值可由差分值算出：,2.3 Newtons Interpolation,牛顿公式, 牛顿前插公式 /* Newtons forward-difference formula */, 牛顿后插公式 /* Newtons backward-difference formula */,将节点顺序倒置：,注：一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为表初公式和表末公式。,2.3 Newtons Interpolat
11、ion,2.4 埃尔米特插值 /* Hermite Interpolation */,不仅要求函数值重合，而且要求若干阶导数也重合。 即：要求插值函数 (x) 满足 (xi) = f (xi), (xi) = f (xi), , (mi) (xi) = f (mi) (xi).,注： N 个条件可以确定 阶多项式。,N 1,一般只考虑 f 与f 的值。,2.4 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) =
12、 f (x1), 并估计误差。,模仿 Lagrange 多项式的思想，设,解：首先，P 的阶数 =,3,h0(x),有根,x1, x2，且 h0(x1) = 0 x1 是重根。,又: h0(x0) = 1 C0,h2(x),h1(x),有根 x0, x2 ,由余下条件 h1(x1) = 1 和 h1(x1) = 0 可解。,与h0(x) 完全类似。,有根 x0, x1, x2 ,与 Lagrange 分析完全类似,一般地，已知 x0 , , xn 处有 y0 , , yn 和 y0 , , yn ，求 H2n+1(x) 满足 H2n+1(xi) = yi ， H2n+1(xi) = yi。,解
13、：设,hi(x),由余下条件 hi(xi) = 1 和 hi(xi) = 0 可解Ai 和 Bi ,有根 x0 , , xn, 除了xi 外都是2重根 ,这样的Hermite 插值唯一, 埃尔米特插值构造基函数的方法,2.4 Hermite Interpolation,斜率=1, 求Hermite多项式的基本步骤：, 根据多项式的总阶数和根的个数写出表达式；, 根据尚未利用的条件解出表达式中的待定系数；, 最后完整写出H(x)。,2.4 Hermite Interpolation,2.5 分段低次插值 /* piecewise polynomial approximation */,Remem
14、ber 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)。取,n 越大， 端点附近抖动 越大，称为 Runge 现象,2.5 Piecewise Polynomial Approximation, 分段线性插值 /* piecewise linear interpolation */,在每个区间 上，用1阶多项式
15、(直线) 逼近 f (x):, 分段三次Hermite插值 /* Hermite piecewise polynomials */,How can we make a smooth interpolation without asking too much from f ? Headache ,2.6 三次样条插值 /* Cubic Spline */,注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f 在所有插值点的导数值。,f(x),H(x),S(x),2.6 Cubic Spline,
16、构造三次样条插值函数的三弯矩法 /* method of bending moment */,对每个j, 此为3次多项式,则 Sj”(x) 为 次多项式，需 个点的值确定之。,1,2,设 Sj”(xj1) = Mj1， Sj”(xj) = Mj,对应力学中的梁弯矩，故名,对于x xj1, xj 可得到,Sj”(x) =,积分2次，可得 Sj(x) 和 Sj(x) ：,下面解决 Mj ：,利用S 在 xj 的连续性,xj1, xj : Sj(x) =,xj , xj+1: Sj+1(x) =, j ,1,n1,即：有 个未知数， 个方程。,n1,n+1,还需2个边界条件 /* boundary
17、conditions */,2.6 Cubic Spline, 第1类边条件 /* clamped boundary */： S(a) = y0， S(b) = yn,类似地利用 xn1, b 上的 Sn(x), 第2类边条件： S”(a) = y0” = M0， S”(b) = yn” = Mn,这时：,特别地，M0 = Mn = 0 称为自由边界 /* free boundary */，对应的样条函数称为自然样条 /* Natural Spline */。, 第3类边条件 /* periodic boundary */ ： 当 f 为周期函数时， yn = y0 ， S(a+) = S(b
18、) M0 = Mn,2.6 Cubic Spline,注：另有三转角法得到样条函数，即设 Sj(xj) = mj，则易知xj1, xj 上的Sj(x) 就是Hermite函数。再利用S”的连续性，可导出关于mj 的方程组，加上边界条件即可解。,Cubic Spline 由边界条件boundary conditions 唯一确定。,即:提高精度只须增加节点, 而无须提高样条阶数。,稳定性：只要边条件保证 | 0 |, | 0 |, | n |, | n | 2，则方程组系数阵为SDD阵，保证数值稳定。,2.6 Cubic Spline,Sketch of the Algorithm: Cubic Spline 计算 j , j , gj ; 计算 Mj (追赶法等) ; 找到 x 所在区间 ( 即找到相应的 j ) ; 由该区间上的 Sj(x) 算出 f(x) 的近似值。,2.6 Cubic Spline,