第二章插值法数值分析课件.ppt

《第二章插值法数值分析课件.ppt》由会员分享，可在线阅读，更多相关《第二章插值法数值分析课件.ppt（90页珍藏版）》请在三一办公上搜索。

1、第二章 插值法/* Interpolation */,Interpolation_introduction,1 引 言,1.函数表达式过于复杂不便于计算, 而又需要计算许多点处的函数值2.仅有几个采样点处的函数值, 而又需要知道非采样点处的函数值 上述问题的一种解决思路：建立复杂函数或者未知函数的一个便于计算的近似表达式.解决方法插值法,1. 插值概念,求插值函数(x)的问题(方法)称为插值问题(方法)。,2. 几何意义、内插法、外插法,内插,外插,2 拉格朗日多项式 /* Lagrange Polynomial */,2 Lagrange Polynomial,多项式插值是数值分析的基本工具

2、，常用来计算被插函数的近似函数值，零、极点，导数、积分（第四章 数值积分和数值微分），解微分方程（第五章）、积分方程,Pn(x) f(x),解 几何上看，即求多项式曲线与被插值函数曲线间满足：,特点：插值曲线Pn(x)过被插值曲线f (x)的上给定的n+1个点。,n = 1,可见 P1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。,称为拉氏基函数 满足条件 li(xj)=ij,2 Lagrange Polynomial,提问：上面所提的多项式Pn(x)是否存在？ 若存在，是否唯一？如何求？,证明 插值条件(2.2)等价于线性方程组,定理1 满足插值条件(2.2)的

3、不超过n次的插值多项式唯一存在。,系数行列式（n+1阶范德蒙行列式）,由克莱默法则知，方程组有唯一解,2-1 插值多项式的存在唯一性,唯一性的另一证明 满足 的 n 阶插值多项式是唯一存在的。,证明 ( 前面已利用Vandermonde 行列式论证),反证：若不唯一，则除了Ln(x) 外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 。,考察 则 Qn 的阶数, n,而 Qn 有 个不同的根,注：若不将多项式次数限制为 n ，则插值多项式不唯一。,例如 也是一个插值多项式，其中 可以是任意多项式。,2 Lagrange Polynomial,Interpolation pol

4、ynomial,2-2 线性插值与抛物插值,x0,x1,(x0 ,y0),(x1 ,y1),P1(x),f (x),可见 P1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。,直线方程为:,1. 线性插值,引入记号:,则:,分析两个基函数有:,对于三个点,类似有:,x0,x1,x2,P2(x) f(x),f(x),2. 抛物线(二次)插值,将以上思路推广到n+1个节点情形，即可得到类似的插值基函数和插值多项式表示形式。,P2(x),x,n 1,Lagrange Polynomial,与节点有关，而与 f无关,基函数法（n=1情形的推广）,2 Lagrange Pol

5、ynomial,2-3 Lagrange插值多项式,2-4 插值余项 /* Remainder */,Rolles Theorem: 若 充分光滑， ，则存在 使得 。,推广：若,使得,Rn(x) 至少有 个根,n+1,任意固定 x xi (i = 0, , n), 考察,(x)有 n+2 个不同的根 x0 xn x,注意这里是对 t 求导,2 Lagrange Polynomial,1 Lagrange Polynomial,注： 通常不能确定 x , 而是估计 , x(a,b) 将 作为误差估计上限。,当 f(x) 为任一个次数 n 的多项式时， , 可知 ，即插值多项式对于次数 n 的多

6、项式是精确的。,Quiz: 给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是 l2(x)的图像？,1 Lagrange Polynomial,解：,n = 1,分别利用x0, x1 以及 x1, x2 计算,利用,这里,而,sin 50 = 0.7660444,外推 /* extrapolation */ 的实际误差 0.01001,利用,内插 /* interpolation */ 的实际误差 0.00596,内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。,1 Lagrange Polynomial,n = 2,sin 50 = 0.7

7、660444,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 want to take more interpolating points into account.,Righ

8、t. Then all the Lagrange basis, li(x), will have to be re-calculated.,Excellent point !We will come to discuss this problemnext time.,1 Lagrange Polynomial,练习：,设f(x)=x4,利用 Lagrange 插值写出以-1,0,1,2为节点,的插值多项式。,练习：,已知插值节点满足xi-xi-1=h,i=1,2,3, 证明三次插值多项式L3(x)与被插函数f(x)的差有如下关系：,1 Lagrange Polynomial,练习：,证明,In

9、terpolation_introduction,问题的提出： 如果需要增加精度，一般采用增加插值节点来实现。但是由于插值基函数的性质，使得计算新的插值多项式时，原来的计算量不能很好地利用，造成计算的浪费，为了克服这一缺点，我们将要介绍下面的逐步线性插值和Newton插值。,3 逐次线性插值 /* Lagrange Polynomial */,3 逐次线性插值法 /* Lagrange Polynomial */,实际上，,是对两个低次插值的线性插值，这种通过低次插值再作线性插值生成高次插值的方法称为逐次线性插值。, Aitken法(按下表计算),线性插值基函数,增加,如果精度不够，增加节点x

10、4,同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。,k1,k0,k2,k3,k4, Neville法(按下表计算),如果精度不够，增加节点x4,同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。,k1,k0,k1,k1,k1,HW: 用类似于前面的方法构造Neville计算公式,注：Atkin方法和Neville方法与Lagrange公式相比，当需要增加节点时，很容易由低次插值构造高次插值，而Lagrange插值公式中，每个基函数都需要作适当变化。,误差估计：由插值多项式的存在唯一性知，仍有,但这里可采用一种更简便的方法。当f (n+1)(x)在插值区间变化不大时，设f (

11、n+1)(x)L，则有,根据前面的计算结果估计当前的误差：事后误差估计（实用），前面给出的误差估计（事先误差估计）不实用,4 牛顿插值 /* Newtons Interpolation */, 差商(亦称均差) /* divided difference */,1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */,2阶差商,f(x0),1阶差商的几何意义：弦截线的斜率,4 Newtons Interpolation,4 Newtons Interpolation,(k+1)阶差商：,Warning: my head is exp

12、lodingWhat is the point of this formula?,差商的值与 xi 的顺序无关！,1.线性：,2.差商可以表示为函数值的线性组合：,3. 对称性：由2知，差商的值与节点的顺序无关！,4. 差商的另一种定义：由2，3及均差定义可得,4 Newtons Interpolation,4 Newtons Interpolation, 牛顿插值 /* Newtons Interpolation */, ,Nn(x)n次多项式，满足： Nn(xi)= f(xi),Rn(x)插值余项，满足Rn(xi)=0，i=0,n,ai =,f x0, , xi ,(1),(2),(n),

13、(n)(n-1) (2) (1),4 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+1 f xn1, xn, xn+1 f x1, , xn+1 f x0, , xn+1,如果精度不够，增加节点xn+1,同时表中增加一行，三角形斜边上即为所要求的各次项系数

14、。,1 Lagrange Polynomial,练习：,设f(x)=3x2+5,求fx0,x1,x2 , fx0,x1,x2, x3,练习：,练习：,4 Newtons Interpolation, 等距节点公式 /* Formulae with Equal Spacing */,向前差分 /* forward difference */,向后差分 /* backward difference */,中心差分 /* centered difference */,其中,当节点等距分布时:,fi= f(xi), 差分的重要性质：, 线性：例如, 各阶差分可用函数值表示：,4 Newtons Int

15、erpolation, 函数值可用各阶差分表示：, 差商与差分的关系：, 若 f (x)是 n 次多项式，则 是 次多项式，而, 差分与导数的关系(由差分与差商、差商与导数的关系得）：,4 Newtons Interpolation,等距节点牛顿公式, 牛顿前差公式 /* Newtons forward-difference formula */,注：一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为表初公式和表末公式。, 牛顿后差公式 /* Newtons forward-difference formula */,例：,6 埃尔米特插值 /* Hermite Inte

16、rpolation */,不仅要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数 (x) 满足 (xi) = f (xi), (xi) = f (xi), (mi) (xi) = f (mi) (xi).,注： n+1 个条件可以确定指数不超过n次的多项式。,一般只考虑 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), 并估计误差。,模仿 Lagra

17、nge 多项式的思想，设,解：首先，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 分析完全类似,3 Hermite Interpolation,一般地，已知 x0 , , xn 处有 y0 , , yn 和 y0 , , yn ，求 H2n+1(x) 满足 H2n+1(xi) = yi ， H2n+1(xi) = yi。,解

18、：设,其中 i (xj) = ij , i (xj) = 0, (xj) = 0, (xj) = ij,i,i(x),由余下条件 i (xi) = 1 和 i (xi) = 0 可解Ai 和 Bi ,有根 x0 , , xn, 除了xi 外都是2重根 ,又 i (xi) = 1 Ci = 1,i,),(,x,=,这样的Hermite 插值唯一,i ,n+1次,所以,类似有：, 则,证明略.,3 Hermite Interpolation,斜率=1, 求Hermite多项式的基本步骤：, 根据多项式的总阶数和根的个数写出表达式；, 根据尚未利用的条件解出表达式中的待定系数；, 最后完整写出H2n

19、+1(x)。,注：待定系数法仍适用，但插值节点多时比较麻烦。,1,分析（方法1）：,误差：,#,例,2,:,建立插值多项式,使之满足插值条件,方法2：（用带有重节点的差商表）,#,7 分段低次插值 /* piecewise polynomial approximation */,为了保证插值函数的逼近效果，需要较多的插值节，导致较高的多项式次数。,然而在实际应用中, 很少采用高次插值: 在两相邻插值节点间, 插值函数未必能够很好地近似被插值函数;,对于等距节点的牛顿插值公式, 函数值的微小扰动可能引起高阶差分有很大的变化。,7-1 多项式插值的问题,Remember what I have s

20、aid? Increasing the degree of interpolating polynomial will NOT guarantee a good result, since high-degree polynomials are oscillating.,例：在5, 5上考察 的Ln(x)。取,n 越大，端点附近抖动越大，称为Runge 现象,分别采用10次、15次、20次的等距节点插值多项式。随着插值次数的提高, 在 范围内的近似程度并没有变好, 反而变坏. 高次插值并不一定带来更好的近似效果。,4 Piecewise Polynomial Approximation,7-2

21、 分段线性插值 /* piecewise linear interpolation */,在每个区间 上，用1阶多项式 (直线) 逼近 f (x):, 分段Hermite插值 /* Hermite piecewise polynomials */,How can we make a smooth interpolation without asking too much from f ?Headache ,7-3 分段三次Hermite插值 /* Hermite piecewise polynomials */,8 三次样条 /* Cubic Spline */,分段插值法具有一致的收敛性,

22、但它只保证插值函数整体的连续性, 但在连接处不一定光滑，不能够满足精密机械设计（如船体、飞机、汽车等的外形曲线设计）对函数光滑性的要求。 早期的工程技术人员在绘制给定点的曲线时，使用一种具有弹性的细长木条（或金属条），称之为样条（Spline），强迫它弯曲通过已知点。弹性力学理论指出样条的挠度曲线具有二阶连续的导函数，并且在相邻给定点之间为三次多项式，即为数学上的三次样条插值曲线。,注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f 在所有插值点的导数值。,f(x),H(x),S(x),三次样

23、条插值函数 在每一个小区间上是3次的多项式, 在整个插值区间上有4n个系数. 且有4n-2个约束:,内节点,边界节点,要确定4n个系数，还需附加2个约束条件. 常用的约束条件有以下三类：,此时一般有 成立.,.周期性边界条件 ,.弯矩边界条件 特别的称 为自然边界条件.,.转角边界条件, 构造三次样条插值函数的三转角方程 /* method of bending moment */, 构造三次样条插值函数的三转角方程 /* method of bending moment */, 构造三次样条插值函数的三转角方程 /* method of bending moment */, 构造三次样条插值

24、函数的三转角方程 /* method of bending moment */, 构造三次样条插值函数的三转角方程 /* method of bending moment */, 构造三次样条插值函数的三转角方程 /* method of bending moment */,5 Cubic Spline, 构造三次样条插值函数的三弯矩法 /* method of bending moment */,对每个j, 此为3次多项式,则 Sj”(x) 为 次多项式，需 个点的值确定之。,1,2,设 Sj”(xj1) = Mj1， Sj”(xj) = Mj,对应力学中的梁弯矩，故名,对于x xj1, x

25、j 可得到,Sj”(x) =,积分2次，可得 Sj(x) 和 Sj(x) ：,5 Cubic Spline,下面解决 Mj ：,利用S 在 xj 的连续性,xj1, xj : Sj(x) =,xj , xj+1: Sj+1(x) =, j ,1,n1,即：有 个未知数， 个方程。,n1,n+1,还需2个边界条件 /* boundary conditions */,5 Cubic Spline, 第1类边条件 /* clamped boundary */： S(a) = y0， S(b) = yn,类似地利用 xn1, b 上的 Sn(x), 第2类边条件： S”(a) = y0” = M0，

26、S”(b) = yn” = Mn,这时：,特别地，M0 = Mn = 0 称为自由边界 /* free boundary */，对应的样条函数称为自然样条 /* Natural Spline */。, 第3类边条件 /* periodic boundary */ ： 当 f 为周期函数时， yn = y0 ， S(a+) = S(b) M0 = Mn,5 Cubic Spline,注：另有三转角法(p.49-53)得到样条函数，即设 Sj(xj) = mj，则易知xj1, xj 上的Sj(x) 就是Hermite函数。再利用S”的连续性，可导出关于mj 的方程组，加上边界条件即可解。,Cubic Spline 由boundary conditions 唯一确定。,即:提高精度只须增加节点, 而无须提高样条阶数。,稳定性：只要边条件保证 | 0 |, | 0 |, | n |, | n | 2，则方程组系数阵为SDD阵，保证数值稳定。,例 给定数据如下 ：,5 Cubic Spline,Sketch of the Algorithm: Cubic Spline 计算 j , j , gj ; 计算 Mj (追赶法等) ; 找到 x 所在区间 ( 即找到相应的 j ) ; 由该区间上的 Sj(x) 算出 f(x) 的近似值。,后面为链接,