计算方法第四章插值方法演示

（优选）计算方法第四章插值方法课件当前第1页\共有89页\编于星期三\11点§4插值方法§4.1多项式插值问题的一般提法§4.2

拉格朗日(Lagrange)插值§4.3

差商与差分及其性质§4.4

牛顿插值公式

§4.5

分段插值法§4.6曲线拟合的最小二乘法当前第2页\共有89页\编于星期三\11点§4.0引言

插值法是广泛应用于理论研究和生产实践的重要数值方法,它是用简单函数(特别是多项式或分段多项式)为各种离散数组建立连续模型；为各种非有理函数提供好的逼近方法。众所周知，反映自然规律的数量关系的函数有三种表示方法：

解析表达式

图象法

表格法当前第3页\共有89页\编于星期三\11点§4.0引言

许多数据都是用表格法给出的(如观测和实验而得到的函数数据表格)，可是，从一个只提供离散的函数值去进行理论分析和进行设计，是极不方便的,甚至是不可能的。因此需要设法去寻找与已知函数值相符，并且形式简单的插值函数(或近似函数)。另外一种情况是，函数表达式完全给定，但其形式不适宜计算机使用，因为计算机只能执行算术和逻辑操作，因此涉及连续变量问题的计算都需要经过离散化以后才能进行。如数值积分方法、数值微分方法、差分方程以及有限元法等，都必须直接或间接地应用到插值理论和方法。当前第4页\共有89页\编于星期三\11点§4.1多项式插值问题的一般提法

当精确函数y=f(x)非常复杂或未知时，在一系列节点x0…xn

处测得函数值

y0

=f(x0),…,yn

=f(xn)，

由此构造一个简单易算的近似函数

p(x)f(x)，满足条件:p(xi)=f(xi)(i=0,…n)。

这里的p(x)称为f(x)的插值函数。最常用的插值函数是…?

代数多项式、三角多项式、有理分式…当前第5页\共有89页\编于星期三\11点

插值函数p(x)作为f(x)的近似，可以选自不同类型的函数,如p(x)为代数多项式、三角多项式、有理分式；其函数性态可以是光滑的、亦可以是分段光滑的。其中，代数多项式类的插值函数占有重要地位：

(a)

结构简单、计算机容易处理、任何多项式的导数和积分也易确定，并且仍是多项式。(b)

著名的Weierstrass逼近定理(定义在闭区间上的任何连续函数f(x),存在代数多项式p(x)一致逼近f(x),并达到所要求的精度)。因此，我们主要考虑代数多项式的插值问题。当前第6页\共有89页\编于星期三\11点x0

,

x1,…,xn插值节点,

函数P(x)称为函数y=f(x)的插值函数，区间[a,b]称为插值区间。

当前第7页\共有89页\编于星期三\11点例题:已知函数f(x)有如下数据:求f(x)的插值多项式p(x)，并求f(x)在x=0.5处的近似值。当前第8页\共有89页\编于星期三\11点当前第9页\共有89页\编于星期三\11点

插值的几何意义

从几何上看，插值就是求一条曲线使其通过给定的个点，并且与已知曲线有一定的近似度。从几何上看x

0y

y=p(x)a=x0x1x2x3xn=b

•(xi,yi)y=f(x)曲线P

(

x)

近似f

(

x)

当前第10页\共有89页\编于星期三\11点插值方法的研究问题（1）满足插值条件的P

(

x)

是否存在唯一？（2）若满足插值条件的P

(

x)

存在，如何构造P(x)？（3）如何估计用P

(

x)近似替代f

(

x)产生的误差？x

0y

y=p(x)a=x0x1x2x3xn=b

•(xi,yi)y=f(x)曲线P

(

x)

近似f

(

x)

当前第11页\共有89页\编于星期三\11点求n

次多项式使得:条件：无重合节点，即§4.2拉格朗日多项式

/*LagrangePolynomial*/

根据插值条件，有：其系数矩阵的行列式为Vandermonde行列式当前第12页\共有89页\编于星期三\11点注意到插值节点两两相异，而故方程组(1)有惟一解于是满足插值条件的多项式存在且惟一。由n+1个不同插值节点可以惟一确定一个n次多项式满足插值条件(唯一性)Return当前第13页\共有89页\编于星期三\11点n=1已知x0,x1;

y0,

y1，求使得111001)(,)(y1x1Ly0x0L==可见L1(x)是过(x0,y0)和(x1,y1)两点的直线。l0(x)l1(x)§4.2拉格朗日多项式

/*LagrangePolynomial*/

线性插值基函数1.构造线性插值基函数的方法:当前第14页\共有89页\编于星期三\11点线性插值与其基函数示意图当前第15页\共有89页\编于星期三\11点显然,是过、、三点的一条抛物线。已知,求，n=2使得当前第16页\共有89页\编于星期三\11点显然,是过、、三点的一条抛物线。已知,求，n=2使得仿照线性插值基函数的构造方法，令抛物线基函数称其为抛物线插值基函数(如上右图所示)。

当前第17页\共有89页\编于星期三\11点抛物线插值基函数于是抛物线基函数当前第18页\共有89页\编于星期三\11点希望找到li(x)，i=0,…,n

使得

li(xj)=ij

；然后令，则显然有Pn(xi)=yi

。每个li有n

个根x0,…

xi,…xn一般情形，

k=0,1

,⋯,

n

.k=0,1

,⋯,

n

.由得:当前第19页\共有89页\编于星期三\11点设函数表则满足插值条件的多项式（Lagrange）插值多项式其中,.当前第20页\共有89页\编于星期三\11点以下的问题：如何分析插值的余项？

(1)先求插值基函数.

(2)构造插值多项式.构造插值多项式的方法：当前第21页\共有89页\编于星期三\11点x-1

0

1

2f(x)-2

-2

12

已知连续函数f(x)的函数表如下：求方程f(x)=0在(-1,2)内的近似根。例题当前第22页\共有89页\编于星期三\11点解：利用Lagrange插值法有

取初值x=0.5，利用牛顿法求解可得f(x)在(-1,2)内的近似根为0.67433。

解方程x-1

0

1

2f(x)-2

-2

12

已知连续函数f(x)的函数表如下：求方程f(x)=0在(-1,2)内的近似根。例题当前第23页\共有89页\编于星期三\11点

，且f

满足条件,

Lagrange插值法插值余项设节点在[a,b]内存在,考察截断误差:当前第24页\共有89页\编于星期三\11点Lagrange插值法的插值余项

，且f

满足条件,设节点在[a,b]内存在,截断误差(或插值余项):当前第25页\共有89页\编于星期三\11点Lagrange插值法的插值余项

，且f

满足条件,设节点在[a,b]内存在,截断误差(或插值余项):证明：由已知条件得到：于是有：其中是与x

有关的待定函数。当前第26页\共有89页\编于星期三\11点任意固定xxi(i=0,…,n),考察根据插值条件及余项定义，可知在点故处均为零，在上有n+2个个零点，根据Roll定理

在的每两个零点间至少有一个零点，故在内至少有一个零点，对再用Roll定理，可知在内至少有n

个零点，依此类推，在内至少有一个零点，记为使得:当前第27页\共有89页\编于星期三\11点由于是不能确定，因此我们并不能确定误差的大小但如能求出，那么用逼近的截断误差限是：当时，当时当前第28页\共有89页\编于星期三\11点当

f(x)为任一个次数n

的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。注意当前第29页\共有89页\编于星期三\11点

给定xi=i+1,i=0,1,2,3,4,5.

下面哪个是l2(x)的图像？问题当前第30页\共有89页\编于星期三\11点算例1Lagrange插值法已知，，用线性插值及抛物线插值计算的值并估计截断误差。当前第31页\共有89页\编于星期三\11点算例1Lagrange插值法已知，，用线性插值及抛物线插值计算的值并估计截断误差。线性插值时取

解:当前第32页\共有89页\编于星期三\11点其截断误差为：其中,因为可取于是：

当前第33页\共有89页\编于星期三\11点用抛物线插值时，取所有节点，得到余项讨论：其中：当前第34页\共有89页\编于星期三\11点算例2Lagrange插值法利用100，121的开方计算.由于:

解:利用Lagrange插值法有于是,的精确值为10.72380529…,因此,近似值10.71428有3位有效数字.

Return当前第35页\共有89页\编于星期三\11点§4.3差商与差分

Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。寻求如下形式的插值多项式：其中的为待定系数，由插值条件确定.由线性代数的知识可知：任何一个n次多项式都可以表示成共n+1个线性无关的多项式的线性组合。那么，是否可以将这n+1个多项式作为插值基函数呢？当前第36页\共有89页\编于星期三\11点设插值多项式P(x)具有如下形式：

再继续下去,待定系数的形式将更复杂,为此引入差商和差分的概念.P(x)应满足插值条件：有：当前第37页\共有89页\编于星期三\11点§4.3.1差商的概念从零阶差商出发，归纳地定义各阶差商:称为函数关于点的一阶差商.

一般地，关于的k

阶差商:记函数在的值，称为关于的零阶差商。当前第38页\共有89页\编于星期三\11点

一般地，关于的n阶差商:n阶差商的概念当前第39页\共有89页\编于星期三\11点差商的基本性质性质1：差商可表示为函数值的线性组合，即：性质2：差商关于所含节点是对称的，即：可用归纳法证明当前第40页\共有89页\编于星期三\11点差商的基本性质性质3：性质4：设在存在n阶导数，且则，使得:当前第41页\共有89页\编于星期三\11点差商的计算-差商表一阶差商二阶差商三阶差商四阶差商当前第42页\共有89页\编于星期三\11点已知计算三阶差商解：列表计算算例当前第43页\共有89页\编于星期三\11点§4.3.2差分

在前面的讨论中，节点是任意分布的，但实际上经常遇到等距节点的情况，这时插值公式可以得到简化，为此，我们先介绍差分的概念。设函数在等距节点上的值为已知，这里为常数，称为步长。

下面来讨论差分的定义。当前第44页\共有89页\编于星期三\11点差分的定义记号分别称为在处以为步长的

向前差分、向后差分、中心差分符号、、分别称为向前差分算子、向后差分算子、中心差分算子.当前第45页\共有89页\编于星期三\11点高阶差分用一阶差分可以定义二阶差分一般地可定义m阶差分为：中心差分定义为:

以此类推。当前第46页\共有89页\编于星期三\11点不变算子I、移位算子E定义从而可得：于是得到：同理，由于：得到：由于：得到：由差分的定义及不变算子和移位算子有如下性质:

当前第47页\共有89页\编于星期三\11点差分的性质性质1：各阶差分均可用函数值表示，如：性质2：某点的函数可用各阶差分来表示：当前第48页\共有89页\编于星期三\11点性质3：差商与差分有如下关系：性质4：差分与导数有如下关系：当前第49页\共有89页\编于星期三\11点差分的计算Return当前第50页\共有89页\编于星期三\11点4.4牛顿插值公式根据差商的定义，把看成上的一点，可得：当前第51页\共有89页\编于星期三\11点4.4牛顿插值公式根据差商的定义，把看成上的一点，可得：把后一式代入前一式当前第52页\共有89页\编于星期三\11点其中

显然满足插值条件，且次数不超过,它就是插值多项式，其系数为：我们称为牛顿插值多项式.当前第53页\共有89页\编于星期三\11点

已知的函数表，求4次牛顿插值多项式,

并求算例当前第54页\共有89页\编于星期三\11点从表中可以看到4阶差商几乎为0，故取4次插值多项式即可，于是：0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012解：列表计算

已知的函数表，求4次牛顿插值多项式,

并求算例当前第55页\共有89页\编于星期三\11点0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012解：列表计算

已知的函数表，求4次牛顿插值多项式,

并求算例截断误差为：当前第56页\共有89页\编于星期三\11点

和均是n次多项式,且均满足插值条件:

由多项式的唯一性,,因而,两个公式的余项是相等的,即当插值多项式从n-1

次增加到n次时,拉格朗日型插值必须重新计算所有的基本插值多项式;而对于牛顿型插值,只需用表格再计算一个n阶差商,然后加上一项即可。牛顿插值公式和Lagrange插值公式比较Return当前第57页\共有89页\编于星期三\11点4.5分段插值公式

在区间[a,b]上用插值多项式P逼近函数f时，f和P在每个节点上的差异(理论上)应该为零。自然，我们期望在一切中间点上也能很好地逼近f，并且当插值点增加时这种逼近效果应该越来越好。 但上述的期望不可能实现的。当认识到这一点时，在数学界曾引起强烈的震动。20世纪初，Runge就给出了一个等距节点插值多项式不收敛到的例子。当前第58页\共有89页\编于星期三\11点

设函数，在该区间上取个等距节点,构造的次拉格朗日插值多项式为

其matlab的lagrange.m文件及相关图形如下.Runge现象当前第59页\共有89页\编于星期三\11点%lagrange.mfunctiony=lagrange(x0,y0,x)n=length(x0);m=length(x);fori=1:mz=x(i);s=0;

fork=1:nL=1;

forj=1:n

ifj~=kL=L*(z-x0(j))/(x0(k)-x0(j));

endend

s=s+L*y0(k);

end

y(i)=s;endy;Lagrange插值多项式求插值的Matlab程序.当前第60页\共有89页\编于星期三\11点%Compare_Runge.mx=-5:0.1:5;z=0*x;y=1./(1+x.^2);plot(x,z,'k',x,y,'r')axis([-55-1.52]);pause,holdonforn=2:2:20x0=linspace(-5,5,n+1);y0=1./(1+x0.^2);x=-5:0.1:5;y1=lagrange(x0,y0,x);plot(x,y1),pauseendy2=1./(1+x0.^2);y=interp1(x0,y2,x);plot(x,y,'k'),holdoffgtext('n=2'),gtext('n=4'),gtext('n=6')gtext('n=8'),gtext('n=10')gtext('f(x)=1/(1+x^2)')比较不同的插值多项式次数对插值的影响当前第61页\共有89页\编于星期三\11点不同次数的Lagrange插值多项式的比较图Runge现象当前第62页\共有89页\编于星期三\11点令，则，下表列出了和的值。当前第63页\共有89页\编于星期三\11点

结果表明,随着的增加，的绝对值几乎成倍地增加，这说明当时在上不收敛。

Runge证明了，存在一个常数,使得当时，

;而当时发散。说明:并不是插值多项式的次数越高,插值效果越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由Runge发现,故称为Runge现象.当前第64页\共有89页\编于星期三\11点

分段线性插值特别简单，从几何上看，就是用折线逼近曲线。分段线性插值的数学定义设是区间上的函数，在节点上的函数值为，求一分段折线函数满足：（1）（2）在上，是一次多项式。（3）则称为的分段线性插值函数。4.5.1分段线性插值当前第65页\共有89页\编于星期三\11点易知,P(x)是个折线函数，在每个区间上,有在[a,b]上是连续的，但其一阶导数是不连续的.当前第66页\共有89页\编于星期三\11点

当时,

当时,4.5.1分段线性插值的基函数

当时,当前第67页\共有89页\编于星期三\11点显然是的线性组合：

在区间上的值为：，表达式在区间上，只有是非零的，其它基函数均为零。即注意当前第68页\共有89页\编于星期三\11点算例节点（如下表），求区间上分段线性插值函数，并利用它求出已知函数近似值。在区间[0,5]上取等距插值当前第69页\共有89页\编于星期三\11点解:在每个分段区间于是，实际值:

当n=7时，P(4.5)=0.04762270321996;当n=10时，P(4.5)=0.04705882352941由此可见，对于光滑性要求不高的插值问题，分段线性插值的效果非常好！计算也简单!当前第70页\共有89页\编于星期三\11点4.5.2埃尔米特(Hermite)插值拉格朗日和牛顿均只保证函数插值；实际问题有时需要导数也插值；满足这种需要的插值称为埃尔米特插值.当前第71页\共有89页\编于星期三\11点埃尔米特插值的一般提法为：设函数在节点的函数值与导数值为：其中是正整数，寻求一个次数尽可能低的多项式，满足：埃尔米特插值的一般提法当前第72页\共有89页\编于星期三\11点

以如下数据构建埃尔米特插值

埃尔米特插值算例当前第73页\共有89页\编于星期三\11点

以如下数据构建埃尔米特插值

埃尔米特插值算例共有个条件，可唯一确定一个次数不超过的多项式，其形式为：目标：求出所有的,方法：基函数法.当前第74页\共有89页\编于星期三\11点可如下构造：均为2n+1次插值基函数.这样可表示为：显然有：当前第75页\共有89页\编于星期三\11点现在求及，令其中从而有：由此得：，故：，当前第76页\共有89页\编于星期三\11点由的表达式可得：于是得到：同理可得当前第77页\共有89页\编于星期三\11点例：已知分别利用sinx的1次、2次Lagrange插值计算sin50

并估计误差。解：n=1分别利用x0,x1

以及x1,x2

计算利用这里而sin50=0.7660444…)185(50sin10pL0.77614外推/*extrapolation*/

的实际误差0.01001

利用sin500.76008,内插/*interpolation*/

的实际误差0.00596内插通常优于外推。选择要计算的x

所在的区间的端点，插值效果较好。当前第78页\共有89页\编于星期三\11点n=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的实际误差0.00061高次插值通常优于低次插值Return当前第79页\共有89页\编于星期三\11点巴尔末，1825-1898)

特殊爱好:数字游戏职业:数学教师，瑞士某女子中学，兼巴塞尔大学无薪讲师“我能用公式把任意4个数字有规律地联系起来”4—