《第二部分插值法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(x)是过(x0,y0)和(x1,y1)两点的直线。,称为拉
2、氏基函数/*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 有 个不同的根,注：若不将多项式次数限制为 n，则插值多项式不唯一。,例如 也是一个插值多项式，其中 可以是任意多项式。,2.2
3、 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 的多项式时，,可知，即插值多项式对于次数 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,高次插值通常优于低次插值,但绝对不是次数越高就越好,2.2 Lagrange Pol
5、ynomial,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 the Lagrange basis,li(x),will have to
6、 be re-calculated.,Excellent point!We will come to discuss this problemnext time.,2.3 牛顿插值/*Newtons Interpolation*/,Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x)都需重新算过。,差商(亦称均差)/*divided difference*/,1阶差商/*the 1st divided difference of f w.r.t.xi and xj*/,2阶差商,2.3 Newtons Interpolation,(k+1)阶差商：,Warning:my
7、 head is explodingWhat 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(xn1)f(xn),f x0,x1f x1,x2 f xn1,xn,f x0,x1,x2 f xn2,xn1,xn,f x0,xn,f(xn+1)f xn,xn+
8、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(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)
9、(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 次多项式，则 是 次多项式，而,差分值可由函数值算出：,函数值可由差分值算出：,2.3 Newtons Interpolation,牛顿公式,牛顿前插公式/*Newtons forward-difference formula*/,牛顿后插公式/*Newtons back
10、ward-difference formula*/,将节点顺序倒置：,注：一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为表初公式和表末公式。,2.3 Newtons Interpolation,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,
11、已知 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,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)满足
12、H2n+1(xi)=yi，H2n+1(xi)=yi。,解：设,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 approximatio
13、n*/,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)。取,n 越大，端点附近抖动越大，称为Runge 现象,2.5 Piecewise Polynomial Approximation,分段线性插值/*piecewise linear interpolation*/,在每个区间 上，用1阶多项式(直
14、线)逼近 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,构造三次样条插值函数的三弯矩法
15、/*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 conditions*/,2.6 Cubic Spline,第1类边条件/*clamp
16、ed 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)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,
