数值分析第六章插值法.ppt

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

1、,6.1 引言 问题的提出函数解析式未知,通过实验观测得到的一组数据,即在某个区间a,b上给出一系列点的函数值 yi=f(xi)或者给出函数表,y=f(x),y=p(x),第六章 插值法,插值法的基本原理设函数y=f(x)定义在区间a,b上,是a,b上取定的n+1个互异节点,且在这些点处的函数值 为已知,即 若存在一个f(x)的近似函数,满足则称 为f(x)的一个插值函数,f(x)为被插函数,点xi为插值节点,称(6.1)式为插值条件,而误差函数R(x)=称为插值余项,区间a,b称为插值区间,插值点在插值区间内的称为内插,否则称外插,(6.1),插值函数 在n+1个互异插值节点(i=0,1,n

2、)处与 相等,在其它点x就用 的值作为f(x)的近似值。这一过程称为插值，点x称为插值点。换句话说,插值就是根据被插函数给出的函数表“插出”所要点的函数值。用 的值作为f(x)的近似值,不仅希望 能较好地逼近f(x),而且还希望它计算简单。由于代数多项式具有数值计算和理论分析方便的优点。所以本章主要介绍代数插值。即求一个次数不超过n次的多项式。,满足,则称P(x)为f(x)的n次插值多项式。这种插值法通常称为代数插值法。其几何意义如下图所示,定理6.1 n次代数插值问题的解是存在且惟一的,证明:设n次多项式,是函数 在区间a,b上的n+1个互异的节点(i=0,1,2,n)上的插值多项式,则求插

3、值多项式P(x)的问题就归结为求它的系数(i=0,1,2,n)。,由插值条件:(i=0,1,2,n),可得,这是一个关于待定参数 的n+1阶线性方程组,其系数矩阵行列式为,称为Vandermonde（范德蒙）行列式，因xixj（当ij），故V0。根据解线性方程组的克莱姆（Gramer）法则，方程组的解 存在惟一，从而P(x)被惟一确定。,惟一性说明，不论用何种方法来构造，也不论用何种形式来表示插值多项式,只要满足插值条件(6.1)其结果都是相互恒等的。,6.3 拉格朗日（Lagrange）插值 为了构造满足插值条件(i=0,1,2,n)的便于使用的插值多项式P(x),先考察几种简单情形,然后再

4、推广到一般形式。（线性插值与抛物插值）（1）线性插值线性插值是代数插值的最简单形式。假设给定了函数f(x)在两个互异的点的值，,现要求用线性函数 近似地代替f(x)。选择参数a和b,使。称这样的线性函数P(x)为f(x)的线性插值函数。,线性插值的几何意义:用通过点 和 的直线近似地代替曲线 y=f(x)由解析几何知道,这条直线用点斜式表示为,为了便于推广，记,这是一次函数,且有性质,与 称为线性插值基函数。且有,于是线性插值函数可以表示为与基函数的线性组合,例6.1 已知,求,解:这里x0=100，y0=10，x1=121，y1=11,利用线性插值,拉格朗日插值多项式 两个插值点可求出一次插

5、值多项式,而三个插值点可求出二次插值多项式。插值点增加到n+1个时,也就是通过n+1个不同的已知点,来构造一个次数为n的代数多项式P(x)。与推导线性插值的基函数类似,先构造一个特殊n次多项式 的插值问题,使其在各节点 上满足,即,由条件()知,都是n次 的零点,故可设,其中 为待定常数。由条件,可求得,于是,代入上式,得,称 为关于基点 的n次插值基函数(i=0,1,n),以n+1个n次基本插值多项式为基础,就能直接写出满足插值条件的n次代数插值多项式。事实上，由于每个插值基函数都是n次值多项式,所以他们的线性组合,是次数不超过n次的多项式,称形如（6.8）式的插值多项式为n次拉格朗日插值多

6、项式。并记为,（6.8）,例6.2 已知y=f(x)的函数表 求线性插值多项式,并计算x=1.5 的值,X 1 3 y 1 2,解:由线性插值多项式公式得,例6.3 已知x=1,4,9 的平方根值,用抛物插值公式,求,(x0 x1)(x0 x2),(xx1)(xx2),y0,+,(x1x0)(x1x2),(xx0)(xx2),y1,+,(x2x0)(x2x1),(xx0)(xx1),y2,p2(7)=,x0=1,x1=4,x2=9,y0=1,y1=2,y2=3,(14)(19),(74)(79),*1,+,(41)(49),(71)(79),*2,+,(91)(94),(71)(74),*3,

7、=2.7,p2(x)=,例6.4 已知f(x)的观测数据 x 0 1 2 4 f(x)1 9 23 3 构造Lagrange插值多项式,解 四个点可构造三次Lagrange插值多项式:基函数为,Lagrange插值多项式为,为便于上机计算,常将拉格朗日插值多项式(6.8)改写成,例6.5 已知f(x)的观测数据,x 1 2 3 4f(x)0-5-6 3,构造插值多项式,解:四个点可以构造三次插值多项式,将数据 代入插值公式，有,这个例子说明p(x)的项数不超过n+1项，但可以有 缺项。,拉格朗日插值算法实现,x0 x1 xixi+1 xn-1 xn,y=f(x),y=p(x),a,b,在插值区

8、间a,b上用插值多项式p(x)近似代替f(x),除了在插值节点xi上没有误差外，在其它点上一般是存在误差的。,若记 R(x)=f(x)-p(x)则 R(x)就是用 p(x)近似代替 f(x)时的截断误差,或称插值余项我们可根据后面的定理来估计它的大小。,6.3.2 插值多项式的误差,定理6.3 设f(x)在a,b有n+1阶导数，x0,x1,xn 为 a,b上n+1个互异的节点,p(x)为满足 p(xi)=f(xi)(i=1,2,n)的n 次插值多项式，那么对于任何x a,b有 插值余项,其中,ab 且依赖于x,证明(略),对于线性插值，其误差为对于抛物插值（二次插值），其误差为,例6.6 已知

9、=100,=121,用线性插值估计 在x=115时的截断误差,解:由插值余项公式知,因为,例6.7 已知x0=100,x1=121,x2=144,当用抛物插值求 在x=115时的近似值，估计其的截断误差,解,=,例6.8 设f(x)=x4,用余项定理写出节点-1,0,1,2的三次插值多项式,解:根据余项定理,6.4 均差与牛顿插值多项式 拉格朗日插值多项式结构对称，使用方便。但由于是用基函数构成的插值，这样要增加一个节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。这就启发我们去构造一种具有承袭性的插值多项式来克服这个缺点，也就是说，每增加一个节点时，只需增加相应的一项即

10、可。这就是牛顿插值多项式。,6.4.1 差商及其性质,定义 函数y=f(x)在区间xi,xi+1上的平均变化率,自变量之差和因变量之差之比叫差商,称为f(x)关于xi,xi+1 的一阶差商,并记为fxi,xi+1 二阶差商,m阶差商,fxi,xj,xk是指,fxi,xj,xk=,fxj,xk-fxi,xj,xk-xi,一般的,可定义区间xi,xi+1,xi+n上的n阶差商为,差商及其性质,差商表,例6.9 求 f(xi)=x3在节点 x=0,2,3,5,6上的各阶差商值解:计算得如下表,牛顿(Newton)插值多项式,的系数 可根据插值条件推出,即由 有,这是关于 的下三角方程组,可以求得,一

11、般，用数学归纳法可证明,所以n次牛顿(Newton)插值公式为,（6.12）,可见，牛顿插值多项式Nn(x)是插值多项式p(x)的另一种表示形式,与Lagrange多项式相比它不仅克服了“增加一个节点时整个计算工作重新开始”的缺点,且可以节省乘除法运算次数,同时在Newton插值多项式中用到差分与差商等概念，又与数值计算的其他方面有密切的关系.,它满足其中ak(k=0,1,2,n)为待定系数，形如（6.12）的插值多项式称为牛顿(Newton)插值多项式。,fx0,x(x-x0),=f(x)-f(x0),f(x),+fx0,x(x-x0),=f(x0),fx1,x0,x(x-x1),=fx0,

12、x-fx1,x0,fx0,x,+fx1,x0,x(x-x1),=fx1,x0,f(x),+(x-x0)fx1,x0,=f(x0),+(x-x0)(x-x1)fx1,x0,x,牛顿插值公式(另一种推导方法）,f(x)=f(x0)+(x-x0)fx1,x0+(x-x0)(x-x1)fx1,x0,x,fx1,x0,x,=(x-x2)fx2,x1,x0,x,+fx2,x1,x0,f(x)=f(x0)+(x-x0)fx1,x0,+(x-x0)(x-x1)fx2,x1,x0+(x-x0)(x-x1)(x-x2)fx2,x1,x0,x,Nn(x),Rn(x),如当n=1时，f(x)=f(x0)+(x-x0)

13、fx1,x0+(x-x0)(x-x1)fx1,x0,xN1(x)=f(x0)+(x-x0)fx1,x0,R1(x)=(x-x0)(x-x1)fx1,x0,x,其中Nn(x)称为牛顿插值多项式 Rn(x)称为牛顿插值余项,Rn(x)为牛顿插值的误差。由插值多项式的存在惟一性定理6.1知，满足同一组插值条件的拉格朗日插值多项式Ln(x)与牛顿插值多项式Nn(x)实际上是同一个多项式，仅是同一插值多项式的不同表达形式而已，因此得到牛顿插值多项式的误差与拉格朗日插值多项式的误差也完全相等。故有,可以看出，牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而Nn(x)的各项系数恰好是各阶差商值，很有

14、规律,这个性质可用数学归纳法证明（用Lagrange插值多项式比较最高项系数来得到）,性质1 函数 f(x)的 n 阶差商 f x0,x1,xn 可由 函数值 f(x0),f(x1),f(xn)的线性组 合表示,且,6.4.2 差商及其性质,fx0,x1=,fx1,x0,f(x1)-f(x0),x1 x0,性质2 差商具有对称性,即在k阶差商中 任意交换两个节点 和 的次序,其值不变。例如,性质3 若fx,x0,x1,xk 是 x 的 m 次多项式,则 fx,x0,x1,xk,xk+1是 x 的 m-1 次多项式证：由差商定义,右端分子为 m 次多项式,且当 x=xk+1 时,分子为0,故分子

15、含有因子 xk+1 x，与分母相消后，右端为m-1 次多项式。,4.4.1 差商及其性质,性质4 若 f(x)是n次多项式,则f x,x0,x1,xn 恒为0 证：f(x)是n次多项式，则f x,x0 是 n-1次多 项式,f x,x0,x1 是 n-2 次多项式,依次递推，f x,x0,x1,xn-1 是零次多项式，所以 fx,x0,x1,xn 0,性质5 k阶差商 和k阶导数之间有下 列关系 这个性质可直接用罗尔（Rolle）定理证明.,N2(7)=1+(7-1)*0.33333+(7-1)*(7-4)*(-0.01667)=2.69992,+(x-x0)(x-x1)fx1,x0,x2,+

16、(x-x0)fx1,x0,=f(x0),N(x),例 6.10 已知 x=1,4,9 的平方根值，求解：,4.4.1 差商及其性质,例6.11 已知 x=0,2,3,5 对应的函数值为 y=1,3,2,5,作三次Newton插值多项式。xi f(xi)一阶差商 二阶差商 三阶差商 0 1 2 3 1 3 2-1-2/3 5 5 3/2 5/6 3/10 所求的三次Newton插值多项式为,4.4.1 差商及其性质,例6.12 已知 f(x)=x7+x4+3x+1 求 f 20,21,27 及 f 20,21,27,28 分析：本题 f(x)是一个多项式,故应利用差商的性质解:由差商与导数之间的

17、关系,例6.13 求 并估计其误差,解：作函数 f(x)=,取 x0=4,x1=9,x2=6.25,建立差商表,N2(7)=2,+(7-4)*0.2,+(7-4)*(7-9)*(-0.00808),=2.64848,f(3)(x)=,Rn(x),在区间 4,9 上，,余式近似 0.5*10-2,N2(7)=2.64848 可舍入为2.65,|f(x)(n+1)|Mn+1,由,6.4.3 差分与等距节点插值,等距节点 xi+1-xi=h，函数在等距节点上的值为y0,y1,yn，称 yi-1=yi-yi-1为函数f(x)在xi-1,xi上的一阶差分。称 2yi-1=yi-yi-1=yi+1-2yi

18、+yi-1为函数f(x)在xi-1,xi+1上的二阶差分。称 kyi-1=k-1yi-k-1yi-1为函数f(x)在xi-1,xi+k-1上的 k 阶差分。,当插值节点等距分布时,被插值函数的变化率就可用差分来表示,这时牛顿插值公式的形式更简单,计算量更小,y0=y1 y0,y1=y2 y1,y2=y3 y2,y3=y4 y3,2y0=y1-y0,2y1=y2-y1,2y2=y3-y2,3y0=2y1-2y0,3y1=2y2-2y1,4y0,等距节点插值,y0=y1 y0y1=y2 y1y2=y3 y2,=y2 2y1+y0,2y0=y1-y0,3y0=2y1-2y0,=y3 2y2+y1,(

19、y2 2y1+y0),=y3 3y2+3y1 y0,2y1=y2-y1,=y3 2y2+y1,(a-b)3=a3-3a2b+3ab2-b3,(a-b)2=a2-2ab+b2,(a-b)4=a4-4a3b+6a2b2-4ab3+b3,结论：各阶差分中函数值的系数正好等于(a-b)r展开式中的系数,等距节点情况下xi=x0+ih，用差分表示差商：,=,y1 y0,h,=,y0,1!h,fx1,x2=,y2 y1,h,=,y1,1!h,fx0,x1,x2=,fx1,x2-fx0,x1,x2 x0,=,2h,=,y1-y0,2h2,=,2y0,2!h2,fx1,x2,x3=,fx3,x2-fx2,x1

20、,x3 x1,=,2h,=,=,fx0,x1,x2,x3=,3h,=,2y1-2y0,2*3h3,=,3y0,3!h3,ny0,n!hn,例6.14 计算 f(x)=x3在等距节点0，1，2，3,4上的各 阶差分值,1,7,19,37,6,12,18,6,6,0,牛顿前插公式,取间距为h,等距节点 x0 x1 xn 顺序建立牛顿差商公式,fx0,x1=,y0,1!h,fx0,x1,x2=,2y0,2!h2,fx0,x1,x2,x3=,3y0,3!h3,Nn(x),=y0,+(x-x0),+(x-x0)(x-x1),+,(x-x0)(x-x1)(x-xn-1),牛顿前插公式,Nn(x),Rn(x

21、),因,设,则,向后差分,函数y=f(x),若记y-1=f(x0-h),y-2=f(x0-2h),则各阶向后差分一阶 y0=y0-y-1，y1=y1-y0，y2=y2-y1，二阶 2y0=y0-y-1=y0-y-1-(y-1-y-2)=y0-2y-1+y-2 2y1=y1-y0=y1-y0-(y0-y-1)=y1-2y0+y-1 K阶 ky0=k-1y0-k-1y-1 ky1=k-1y1-k-1y0,牛顿后插公式,将节点排列为 xn xn-1 x0,建立牛顿差商公式,fxn,xn-1=,yn,1!h,fxn,xn-1,xn-2=,2yn,2!h2,fxn,xn-1,xn-2,xn-3=,3yn

22、,3!h3,Nn(x),=yn,+(x-xn),+(x-xn)(x-xn-1),+,(x-xn)(x-xn-1)(x-x1),牛顿后插公式,Nn(x),Rn(x),因,设,则,解：建立差分表,=-1+1+0+0.375,=0.375,例6.15 按下列数值表用牛顿前插公式求y(-0.5)的近似值,N3(x),许多实际问题不但要求插值函数p(x)在插值节点处与被插函数f(x)有相同的函数值p(xi)=f(xi)(i=0,1,2,n),而且要求在有些节点或全部节点上与f(x)的导数值也相等，甚至要求高阶导数值也相等，能满足这种要求的插值问题就称为埃尔米特插值(Hermite),6.5 埃尔米特(H

23、ermite)插值,定义 已知 n+1个互异点上 的函数值 和导数值,若存在一个次数 不超过2n+1的多项式H(x)，满足 则称H(x)为f(x)的2n+1次埃尔米特(Hermite)插值,6.5.1 埃尔米特插值,上式给出了2n+2个条件，可惟一确定一个次数不超过2n+1的多项式H2n+1(x)，采用类似于求Lagrange插值多项式的基函数方法求埃尔米特(Hermite)插值多项式H2n+1(x),次数不超过2n+1次的多项式的形式为：，H2n+1(x)=H(x),H2n+1(x)=a0+a1x+a2x2+a2n+1x2n+1由2n+2个条件来确定2n+2个系数a0,a1,a2,a2n+1

24、显然非常复杂,所以要用求Lagrange插值多项式的基函数的方法,求插值基函数i(x)及i(x)(i=0,1,2,n)共有2n+2个,设每一个基函数为次数不超过2n+1次的多项式，且满足条件,(i,j=0,1,2,n),Hermite插值多项式可写成插值基函数表示的形式,验证：,根据插值条件可求出 和,H2n+1(x)为满足条件的2n+1次Hermite插值多项式。,于是,同理,定理 满足插值条件 的Hermite插值多项式是惟一的。证:设 和 都满足上述插值条件,令则每个节点 均为 的二重根,即有2n+2个根，但 是不高于2n+1次的多项式，所以，即 惟一性得证。,定理 若f(x)在a,b上

25、存在2n+2阶导数，则 2n+1次Hermite插值多项式的余项为,其中,定理的证明可仿照Lagrange插值余项的证明方法请同学们自行证明,实际中使用最广泛的是三次Hermite插值多项式,即n=1的情况,余项,例6.16 已知函数 y=f(x)的数据如下表所示,求次数 不超过三次的Hermite的插值多项式H3(x)使 H3(xi)=yi(i=0,1,2)H3(xi)=yi,解 所求三次Hermite的插值多项式为,解 所求三次Hermite的插值多项式为,由插值条件得到以下方程组,解上述方程组,故得,6.6 分段线性插值,6.6.1 高次插值的龙格现象 插值多项式余项公式说明插值节点越多

26、，一般说来误差越小，函数逼近越好，但这也不是绝对的，因为余项的大小既与插值节点的个数有关，也与函数f(x)的高阶导数有关。换句话说，适当地提高插值多项式的次数，有可能提高计算结果的准确程度，但并非插值多项式的次数越高越好。当插值节点增多时，不能保证非节点处的插值精度得到改善，有时反而误差更大。考察函数,考察函数,右图给出了和 的图像,当n增大时,在两端会发出激烈的振荡,这就是所谓龙格现象。该现象表明,在大范围内使用高次插值,逼近的效果往往是不理想的,另外，从舍入误差来看，高次插值误差的传播也较为严重，在一个节点上产生的舍入误差会在计算中不断扩大，并传播到其它节点上。因此，次数太高的高次插值多项

27、式并不实用，因为节点数增加时，计算量增大了，但插值函数的精度并未提高。为克服在区间上进行高次插值所造成的龙格现象，采用分段插值的方法，将插值区间分成若干个小的区间，在每个小区间进行线性插值，然后相互连接，用连接相邻节点的折线逼近被插函数，这种把插值区间分段的方法就是分段线性插值法。,6.6.2 分段线性插值 分段线性插值就是通过插值节点用折线段连接起来逼近f(x)。设f(x)在n+1个节点 上的函数值为,在每个小区间(k=0,1,，n）上作线性插值，得,在几何上就是用折线替代曲线,如右图所示若用插值基函数表示,则在a,b上,其中,显然，是分段线性连续函数，且 称S(x)为f(x)的分段线性插值

28、函数。由线性插值的余项估计式知,f(x)在每个子段上有误差估计式其中,例6.17 已知f(x)在四个节点上的函数值如下表所示,30 45 60 90,1,求f(x)在区间30,90上的分段连续线性插值函数S(x),解 将插值区间30,90分成连续的三个小区间 30,45,45,60,60,90 则S(x)在区间30,45上的线性插值为,S(x)在区间45,60上的线性插值为,S(x)在区间60,90上的线性插值为,将各小区间的线性插值函数连接在一起，得,本章小结,本章介绍的插值法是实用性很强的方法。它们解决的实际问题虽然各式各样，但抽象为数学问题却有它的共性，即利用已知的数据去寻求某个较为简单的函数P(x)来逼近f(x)。插值法给出了寻求这种近似函数的原则，以及构造近似函数的几种具体方法。插值法要求近似函数在已知的数据点必须与f(x)完全一致，。,插值法中的拉格朗日插值多项式是研究数值微积分与微分方程数值解的重要工具。牛顿插值多项式是拉格朗日插值多项式的变形，具有承袭性，比拉格朗日插值多项式节省计算量。分段低次多项式插值由于具有良好的稳定性与收敛性，且算法简单，便于应用。特别是应用广泛的三次样条插值，不但有较好的稳定性和收敛性，而且具有较好的光滑性，从而满足了许多实际问题的要求。需对样条函数作进一步了解的读者可参阅有关文献,