第五章 数值插值方法ppt课件.ppt

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

1、第五章 插值方法,第五章 插值方法,插值的基本概念Lagrange插值分段低次插值均差与Newton插值Hermite插值三次样条插值,5.1 代数插值问题,例. 某地区某年夏季时节间隔 30 天的日出日落时间为,插值：研究用简单函数为各种离散数据建立连续数学模型的方法。,日照时间的变化设为 y(x)=a0+ a1x + a2x2,求出a0，a1，a2，即可得到5、6月份的日照时间的变化规律。,根据三组数据:(1, 15.2167)， (31, 14.35)， (61, 14.6667),导出关于a0，a1，a2的线性方程组,定义,已知函数y=f(x)在a,b有定义，且已知它在n+1个互异节点

2、a x0 x1xnb,上的函数值 y0=f(x0)，y1=f(x1) ,yn=f(xn)，,若存在一个次数不超过n次的多项式 Pn (x)=a0 + a1x + a2x2 + + anxn,满足条件 Pn (xk)= yk (k = 0,1,n),则称Pn (x)为f(x)的n次插值多项式。,点x0,x1,xn称插值节点， f(x)为被插值函数。a,b称插值区间，点x称插值点。,插值点在插值区间内的叫内插，否则叫外插。,设 Pn (x)=a0 + a1x + a2x2 + + anxn是y=f(x)在a,b上的n+1个互异节点x0,x1,xn的插值多项式，则求Pn (x)问题归结为求系数a0,

3、a1,an。,定理 n次插值问题的解是存在而且唯一的。,证明：,由插值条件： Pn (xk)= yk (k = 0,1,n),得关于a0,a1,an的n+1阶线性方程组,故Pn (x)存在且唯一。,因,故上式不为0。,据Cramer法则，方程组解存在且唯一。,其系数行列式是Vandermonde行列式,给定插值节点 x0,x1， y0=f(x0)，y1=f(x1).求线性插值多项式L1 (x)=a0+ a1x，使满足: L1(x0)=y0 , L1(x1)=y1.,5.2 Lagrange插值,一、线性插值与抛物插值,1. 线性插值：n=1情形,y= L1 (x)的几何意义就是过点(x0, y

4、0)，(x1, y1)的直线。,L1 (x)的表达式：,点斜式:,两点式:,由两点式可以看出， L1 (x)是由两个线性函数,的线性组合得到，其系数分别为y0， y1。即,显然， l0 (x)及l1 (x)也是线性插值多项式，在节点x0,x1上满足条件：l0(x0)=1 , l0(x1)=0.l1(x0)=0 , l1(x1)=1.,称l0 (x)及l1 (x)为线性插值基函数。,(j,k=0,1),即,l0(x0)=1 , l0(x1)=0 , l0(x2)=0.l1(x0)=0 , l1(x1)=1 , l1(x2)=0.l2(x0)=0 , l2(x1)=0 , l2(x2)=1.,2.

5、 抛物插值：n=2情形,假定插值节点为x0, x1, x2 ，求二次插值多项式 L2 (x)，使 L2(xj)=yj (j=0,1,2),y= L2 (x)的几何意义就是过 (x0, y0)，(x1, y1) ，(x2, y2)三点的抛物线。,采用基函数方法，设L2 (x)=l0(x)y0+l1(x)y1+l2(x)y2,此时基函数l0(x), l1(x), l2(x)是二次函数，且在节点上满足：,满足上式的插值基函数很容易求出。如求l0(x), 因x1, x2 为其零点，故可表为,故,即,(j,k=0,1,2),其中A为待定系数，由l0(x0)=1 , 得,显然L(x)=l0(x)y0+l1

6、(x)y1+l2(x)y2 满足条件L2(xj)=yj (j=0,1,2),同理,将l0(x), l1(x), l2(x)代入得,取x0=4,y0=2，x1=9, y1=3 ，x2=16, y2=4.,取x0=4, x1=9, x2=16,例,已知,求,解,（1）线性插值：,取x0=4, x1=9,（2）抛物插值：,设有n+1个互异节点x0 x1xn，且yi=f(xi)(i=0,1,2,n)构造Ln (x)，使 Ln (xj)= yj (j = 0,1,2,n),二、Lagrange插值多项式,定义,若n次多项式lj(x) (j = 0,1,n)在n+1个节点x0 x1xn上满足条件,(j,k

7、=0,1,n),则称这n+1个n次多项式l0(x), l1(x), ln(x)为节点x0 ,x1,xn上的n次插值基函数。,由n=1,2时的讨论可得,(k = 0,1,2,n),或记为,(k=0,1,2,n),故满足插值条件的多项式为,称Lagrange插值多项式。,定理 设 f(x)在a,b上具有n阶连续导数, 且f (n+1)(x) 存在,节点a x0 x1xnb， Ln (x)是满足条件Ln (xj)= yj (j = 0,1,2,n)的插值多项式，则对任何xa,b，插值余项,三、插值余项与误差估计,定义 若在a,b上用Ln (x)近似f(x)，则其截断误差Rn (x)f(x)- Ln

8、(x)称插值多项式的余项。,其中,证明：,因为,设,其中,根据Rolle定理,再由Rolle定理,依此类推，,由于,因此,所以,注：余项表达式只有在f(x)的高阶导数存在时才能使用，通常不能具体给出，可求出,故Ln(x)逼近f(x)的截断误差限是,当 f(x) 是n次的多项式时, Ln(x)= f(x)。即n次多项式的n次插值函数即为该n次多项式本身。,说明：,n=1时，,n=2时，,例:,解:,5.3 分段低次插值,高次插值的病态性质：,对于一个确定的区间，如果插值节点之间的距离较小，自然插值节点就增多，如果用一个多项式插值，自然次数就会升高，也就是说要用高次多项式插值。,但是否次数越高，插

9、值多项式的逼近效果越好呢？,20世纪初，Runge就给出了一个等距节点插值多项式不收敛的例子。,Runge反例:,(-5x5),它在-5,5上各阶导数均存在，在该区间上取n+1个等距节点：,构造拉格朗日插值多项式为：,令,则,下表列出了n=2,4,20的Ln(xn-1/2)和R(xn-1/2)的值：,从表中可以看出，随着n的增加，R(xn-1/2)的绝对值几乎成倍地增加，这说明当n时Ln在-5,5上不收敛。,Runge证明了，存在一个常数c3.63，使得当|x|c时，lim(Ln(x)=f(x) (n)；而当 |x|c时，Ln(x)发散。,下图给出当n=10时，y=L10(x)及f(x)=1/

10、(1+x2)在-5,5上的图形。,取xk=-5+k 计算: f(xk) (k=0,1,10) 构造L10(x).取:tk=-5+0.05k (k=0,1,200),计算: L10(tk),一、分段线性Lagrange插值,构造Lagrange线性插值,1. 分段线性插值的构造,设插值节点为xi，函数值为yi，i=0,1,2,n,hi=xi+1-xi，i=0,1,2,n-1，,任取两个相邻的节点xk，xk+1，形成一个插值区间xk，xk+1,k=0,1,2,n-1,显然,我们称由上式构成的插值多项式L1(x)为分段线性Lagrange插值多项式。,i=0,1,2,n,内插,外插,外插,故也称折线

11、插值，如右图：,但曲线的光滑性较差，且在节点处有尖点。,如果增加节点的数量，减小步长，会改善插值效果。,因此,则,由前述余项定理可知，n次Lagrange插值多项式的余项为：,2. 分段线性插值的误差估计,则分段线性插值L1(x)的余项为,二、分段二次Lagrange插值,1. 分段二次插值的构造,设插值节点为xi，函数值为yi，i=0,1,2,n,hi=xi+1-xi，i=0,1,2,n-1，,任取三个相邻的节点xk-1，xk，xk+1，以 xk-1，xk+1为插值区间构造二次Langrange插值多项式：,2. 分段二次插值的误差估计,由于,那么分段二次插值L2(x)的余项为：,例:,解:

12、,(1) 分段线性Lagrange插值的公式为,同理,(2) 分段二次Lagrange插值的公式为,5.4 均差与Newton插值,一、均差及其性质,Lagrange插值多项式理论上较方便，但当节点增加时，全部基函数lk(x)都要变，在实际运算中并不方便。,可将插值多项式表示为如下形式：,其中a0,a1,an待定，可由Pn(xi)=fi (i=0,1,n)确定. fi 为节点处的函数值.,当x=x0时，,当x=x1时，,当x=x2时，,再继续下去待定系数的形式将更复杂，为此引入均差的概念:,定义,设f(x)在互异节点xi处的函数值为fi，i=0,1,n，称,为f(x)关于节点xi，xj的一阶均

13、差，,两个一阶均差的均差,称为f(x)关于节点xi，xj，xk的二阶均差，,一般地，两个n-1阶的均差,称为n阶均差（也称差商）。,均差的性质：,（2） 均差具有对称性，即任意调换节点的次序，均差的值不变。,如,（1）f(x)的k阶均差可表示为函数值f(x0),f(x1), f(xn)的线性组合，即,（3）设f(x)在a,b上具有n阶导数，且x0,x1,xn a,b，则n阶均差与导数的关系如下：,均差的计算方法(表格法):,规定函数值为零阶均差,均差表,例：,已知函数f(x)的函数值列表如下：,列出一至三阶的均差表。,解：,二、Newton插值公式,据均差定义，把xxi看成a,b上一点，则,即

14、,因此可得,将后一式代入前一式，得,其中,称Nn(x)为Newton均差插值多项式。,（1）Newton插值多项式的系数为均差表中各阶均差的第一个数据；,注：,（2）Newton插值多项式的基函数为i (x)，i=0,1,n；,（3）Newton插值多项式的插值余项为Rn(x)。,例：,已知f(x)的函数表，求4次牛顿插值多项式，并由此计算f(0.596)的近似值。,这说明截断误差很小。,可得,截断误差为：,从表中可以看到4阶均差几乎为常数，故取4次插值多项式即可，于是：,此例中，五阶均差fx,x0,x1,x4是用fx0,x1,x5来近似的。,另一种方法是取x=0.596，由f(0.596)0

15、.61392求得fx,x0,x1,x4的近似值，进而计算|R4(x)|。,截断误差的估计：,5.5 埃尔米特插值（Hermite）,Newton插值和Lagrange插值虽然构造比较简单，但都存在插值曲线在节点处有尖点，不光滑，插值多项式在节点处不可导等缺点。,已知节点处函数值及对应节点导数值，求使其函数值及导数值均相等的插值多项式。,埃尔米特插值的基本思想为：,设a x0 x1xnb上，,(j=0,1,2,n),求H(x)，使,(j=0,1,2,n),共有2n+2个条件，可唯一确定一次数 2n+1的多项式H2n+1 (x)H(x)。,形式：,一般来说，Hermite插值多项式的次数如果太高会

16、影响收敛性和稳定性，因此2n+1不宜太大，仍用分段插值。,故仅考虑n=1的情况，即三次Hermite插值。,一、三次Hermite插值公式,考虑只有两个节点的插值问题：,设f(x)在节点x0，x1处的函数值为y0，y1；在节点x0，x1处的一阶导数值为y0，y1 。,两个节点最高可以用3次Hermite多项式H3(x)作为插值函数。,H3(x)应满足条件：,采用基函数方法构造。,H3(x)应用四个插值基函数表示。,设H3(x)的插值基函数为0(x)， 1(x) ，0(x)， 1(x)， 则,其中,可知x1是0(x)的二重零点，即可假设,由,可得,Lagrange插值基函数,同理可得,将以上结果

17、代入,得两个节点的三次Hermite插值公式：,二、三次Hermite插值的余项,定理：,设f(x)在区间a,b上有定义，f(x)在(a,b)内有4阶导数，H3(x)是满足插值条件,(j=0,1),的三次Hermite插值函数，则对任意的xa,b，H(x)的插值余项为,证明：,由,(i=0,1),可知，x0，x1均为R3(x)的二重零点，因此可设,其中K(x)待定,构造辅助函数,i=0,1,因此(t)至少有5个零点。,连续4次使用Rolle定理可得，至少存在一点x0,x1，使得,即,所以，两点三次Hermite插值的余项为,例1.,解:,作为多项式插值，三次已是较高的次数，次数再高就有可能发生

18、Runge现象，因此，对有n+1个节点的插值问题，我们可以使用分段两点三次Hermite插值。,设节点x0 x1xn，分段插值函数Hn (x)在两个相邻节点构成的小区间xj , xj+1 (j=0,1,n-1)上满足条件：,三、分段三次Hermite插值,用三次Hermite插值，当x xj , xj+1 时，有,其中,5.6 三次样条插值,样条：是 指飞机或轮船等的制造过程中为描绘出光滑的外形曲线(放样)所用的工具。,样条本质上是一段一段的三次多项式拼合而成的曲线，在拼接处，不仅函数是连续的，且一阶和二阶导数也是连续的。,1946年，Schoenberg将样条引入数学，即所谓的样条函数。,因

19、分段线性插值导数不连续，埃尔米特插值导数连续但需要已知，故引入样条插值概念。,一、三次样条插值函数的定义,定义：,给定区间a,b上的一个划分： a = x0 x1xn=b，已知函数f(x)在点xj上的函数值为 f (xj) = yj, ( j= 0,1,2,n)如果存在分段函数,(1)S(x)在每一个子区间xj-1 , xj ( j= 0,1,2,n)上是一个三次多项式；(2) S(x)在每一个内接点xj ( j= 1,2,n-1)上具有直到二阶的连续导数；,则称S(x)为节点x0,x1, xn 上的三次样条函数。,若S(x)在节点x0,x1, xn 上还满足插值条件：(3) S (xj)=

20、yj ( j= 0,1,2,n),则称S(x)为三次样条插值函数。（即全部通过样点的二阶连续可微的分段三次多项式函数）,满足下述条件：,三次样条插值多项式的确定：,由(1)知， S(x)在每一个小区间xj-1 , xj 上是一三次多项式，若记为Sj(x)，则可设,要确定函数S(x)的表达式，须确定4n个未知系数aj，bj，cj，dj (j=1,2,n)。,由(2)知，S(x)，S(x)，S(x)在内节点x1,x2,xn-1上连续，则,j=1,2,n-1,可得3n-3个方程，又由条件(3),j=0,1,n,得n+1个方程，共可得4n-2个方程。,要确定4n个未知数，还差两个方程。,通常在端点x0

21、 =a, xn =b处各附加一个条件，称边界条件，常见有三种：,(1)自然边界条件：,(2)固定边界条件：,自然样条（最光滑）,(3)周期边界条件：,共4n个方程，可唯一地确定4n个未知数。,例 已知f(x)：f(-1)=1,f(0)=0,f(1)=1，求f(x)在-1,1上的三次自然样条插值函数。,解,设,由插值条件和函数连续条件得：,由一阶及二阶导数连续得：,由自然边界条件得：,联立上面8个方程，求解得,故,二、三次样条插值函数的建立,（1）用一阶导数值构造三次样条插值函数（m表达式）,设S(xj)=mj，(j=0,1,2,n),计算未知的mj，即可通过分段三次Hermite插值得到分段三

22、次样条插值多项式。,假设插值节点为等距节点，h=xj+1-xj， (j=0,1,2,n-1),当xxj,xj+1时，利用分段三次Hermite插值函数表示S(x)可得,其中,利用样条插值函数二阶导数连续性,即,又,所以有,上面两式右端相等，整理得,(j=1,2,n-1),共n-1个方程，n+1个未知量。,补充自然样条的边界条件：,同理得,得,令,(j=1,2,n-1),可得具有n+1个方程，n+1个未知数的方程组：,其矩阵形式为,用追赶法求解该方程组即可得mj，由此得三次样条插值函数的表达式。,（2）用二阶导数值构造三次样条插值函数（M表达式，又称三弯矩算法）,记 hj=xj-xj1， (j=

23、1,2,n),设S(xj)=Mj，(j=0,1,2,n),因为S(x)是三次多项式，故S(x)是线性函数。按线性插值公式可得,积分两次得,其中c1，c2为积分常数。,将S(xj-1)=yj-1， S(xj)=yj代入上式，可确定c1，c2。,故,上式称M表达式，只需确定Mi，即可确定三次样条插值函数。,将M表达式两端对x求导，得,令x=xj，得左导数,令x=xj-1，得右导数,故,因S(x)一阶导数连续，即,整理得,记,则得Mj的n-1个方程：,(j=1,2,n-1),对自然边界条件：M0=0，Mn=0,对固定边界条件：,得,或记为,其中,则求Mi的方程的矩阵形式为,对于周期边界条件：y0=yn，M0=Mn,只需确定n个未知量Mi(i=1,2,n)即可。,由,当j=n时，,方程组为,上述方程组是关于Mj(j=0,1,n)的三对角方程组。,Mj在力学上解释为细梁在xj截面处的弯矩，称为S(x)的矩，故称三弯矩方程组。,该方程组是严格对角占优的三对角方程组，有唯一解，可用追赶法求解。,P137习题五：1 ，2，3，4，7，8,本章作业,