《第二章插值法Chapter2Interpolation知识讲解》由会员分享,可在线阅读,更多相关《第二章插值法Chapter2Interpolation知识讲解(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,证明:,反证:若不唯一,则除了Ln(x) 外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 。,考察 则 Qn 的阶数, n,而 Qn 有 个不同的根,注:若不将多项式次数限制为 n ,则插值多项式不唯一。,例如 也是一个插值多项式,其中 可以是任意多项式。,2.2 Lagra
3、nge 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 的多项式时, , 可知 ,即插值多项式对于次数 n 的多项式是精确的。,2.2 Lagrange Polynomial,注: 小
4、的区间上插值有利于减少误差; 依靠增多插值节点不一定能减少误差; 多项式插值,外推误差可能要比内插误差大。,解:,n = 1,分别利用x0, x1 以及 x1, x2 计算,利用,这里,而,sin 50 = 0.7660444,外推 /* extrapolation */ 的实际误差 0.01001,利用,内插 /* interpolation */ 的实际误差 0.00596,内插通常优于外推。选择要计算的 x 所在的区间的端点,插值效果较好。,2.2 Lagrange Polynomial,n = 2,sin 50 = 0.7660444,2次插值的实际误差 0.00061,高次插值通常优
5、于低次插值,但绝对不是次数越高就越好,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 to take more interpolating points into account.,Right. Then all
6、 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 difference */,1阶差商 /* the 1st divided difference of f w.r.t. xi and xj
7、 */,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,注: 由唯一性可知 Nn(x) Ln(x), 只是算法不同,故其余项也相同,即, 实际计算过程为,f (x0) f (x1) f (x2) f (xn
8、1) 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.596)的近似值。,N4(x)=0.41075+1.116(x-0.4)+0.28(x-0.4)(x-0.55)+0.19733(
9、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 Newtons Interpolation, 差分的重要性质:, 线性:例如, 若 f (x)是 m 次多项式,则 是 次多项式,而,
10、 差分值可由函数值算出:, 函数值可由差分值算出:,2.3 Newtons Interpolation,牛顿公式, 牛顿前插公式 /* Newtons forward-difference formula */, 牛顿后插公式 /* Newtons backward-difference formula */,将节点顺序倒置:,注:一般当 x 靠近 x0 时用前插,靠近 xn 时用后插,故两种公式亦称为表初公式和表末公式。,2.3 Newtons Interpolation,2.4 埃尔米特插值 /* Hermite Interpolation */,不仅要求函数值重合,而且要求若干阶导数也重
11、合。 即:要求插值函数 (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) = f (x1), 并估计误差。,模仿 Lagrange 多项式的思想,设,解:首先,P 的阶数 =,3,h0(x),有根,x1,
12、 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。,解:设,hi(x),由余下条件 hi(xi) = 1 和 hi(xi) = 0 可解Ai 和 Bi ,有根 x0 , , xn,
13、除了xi 外都是2重根 ,这样的Hermite 插值唯一, 埃尔米特插值构造基函数的方法,2.4 Hermite Interpolation,斜率=1, 求Hermite多项式的基本步骤:, 根据多项式的总阶数和根的个数写出表达式;, 根据尚未利用的条件解出表达式中的待定系数;, 最后完整写出H(x)。,2.4 Hermite Interpolation,2.5 分段低次插值 /* piecewise polynomial approximation */,Remember what I have said? Increasing the degree of interpolating pol
14、ynomial 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阶多项式 (直线) 逼近 f (x):, 分段三次Hermite插值 /* Hermite piecewise polynomials *
15、/,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, 构造三次样条插值函数的三弯矩法 /* method of bending moment */,对每个j, 此为3次多项式,则 S
16、j”(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 conditions */,2.6 Cubic Spline, 第1类边条件 /* clamped boundary */: S(a) = y0, S(b) = yn,类似地利用 xn1, b 上的 Sn(x), 第2类边条件: