拉格朗日插值逐次线性插值法.ppt

《拉格朗日插值逐次线性插值法.ppt》由会员分享，可在线阅读，更多相关《拉格朗日插值逐次线性插值法.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 插值与拟合第二章第二章 函数的插值函数的插值学学习习目目标标：掌掌握握多多项项式式插插值值的的LagrangeLagrange插插值值公公式式、牛牛顿顿插插值值公公式式等等，等等距距节节点点插插值值、差差分分、差差商商、重重节节点点差差商商与与埃埃米米特特插插值值。重点是多项式插值方法。重点是多项式插值方法。第二章 插值与拟合 2.1.5 Hermite插值多项式插值多项式2.1.4 均差和均差和Newton插值多项式插值多项式2.1.3 逐次线性插值逐次线性插值2.1.2 Lagrange插值多项式插值多项式2.1.1 问题的提出问题的提出2.1 多项式插值多项式插值第二章 插值与拟

2、合 给定空间一组有序的控制点给定空间一组有序的控制点（control point），），得到得到一条光滑的分段参数多项式曲线的方法一条光滑的分段参数多项式曲线的方法:曲线顺序经过所有的控制点，则称为对这些控制点曲线顺序经过所有的控制点，则称为对这些控制点进行插值，得到的曲线称为进行插值，得到的曲线称为插值曲线插值曲线。构造一条在某种意义下最靠近控制点的曲线，这称为对构造一条在某种意义下最靠近控制点的曲线，这称为对这些控制点进行逼近，得到的曲线称为这些控制点进行逼近，得到的曲线称为逼近逼近(拟合拟合)曲线曲线。(a)5(a)5个控制点的插值曲线个控制点的插值曲线 (b)5(b)5个控制点的逼近曲

3、线个控制点的逼近曲线第二章 插值与拟合 本章先讨论插值问题，然后再讨论数据拟本章先讨论插值问题，然后再讨论数据拟合的有关问题。合的有关问题。拟合法拟合法就是考虑到数据不一定准确，不要求近似表就是考虑到数据不一定准确，不要求近似表达式达式 经过所有的点经过所有的点 ，而只要求在给定的，而只要求在给定的 上误差上误差 （i=0，1,n）按某种标准最小按某种标准最小。若记若记=(1,2,n)T，就是要求向量就是要求向量的范数的范数|最小最小。第二章 插值与拟合问题：问题：基于未知函数或复杂函数的某些已知信息，基于未知函数或复杂函数的某些已知信息，如何构造这些函数的近似表达式如何构造这些函数的近似表达

4、式?情形情形函数函数f(x)在x点的点的Taylor展开式展开式称为函数称为函数f(x)的的Taylor插值插值第二章 插值与拟合解解:设设例如：例如：利用利用TaylorTaylor插值插值求求利用利用TylorTylor插值，有插值，有第二章 插值与拟合y=f(x)x0p(x)TylorTylor插值的缺陷：插值的缺陷：TylorTylor插值中有导数运算，而插值中有导数运算，而计算机实现求导运算存在困难；计算机实现求导运算存在困难；近似区间小近似区间小,在大在大的区间上不可行的区间上不可行第二章 插值与拟合情形情形在区间a,b上考虑函数函数f(x)的近似y=f(x)a b 求解：求解：y

5、=f(x)在在 a,b 上的近似曲线？上的近似曲线？第二章 插值与拟合利用函数利用函数f(x)在区间区间a,b上一系列点的值一系列点的值 yi=f(xi)（可通过观察、测量、试验等方法得到）（可通过观察、测量、试验等方法得到）y=f(x)xx0 x1x2xnyy0y1y2yn插插值值法法解决思路解决思路第二章 插值与拟合 根据根据 f(x)在在n+1个已知点的值，求一个足够光个已知点的值，求一个足够光滑又比较简单的函数滑又比较简单的函数p(x)，作为，作为 f(x)的近似表达的近似表达式，式，x0 x1x2x3x4 xf(x)p(x)曲线曲线 P(x)近似近似 f(x)第二章 插值与拟合从代数

6、上看，看从代数上看，看p(x)满足以下代数条件满足以下代数条件p(xi)=yi i =0,1,2,n这就是所谓的插值这就是所谓的插值然后计算然后计算 p(x)在在a,b 上其它点上其它点x 处的函数值作为处的函数值作为原来函数原来函数 f(x)在此点函数值的近似值。在此点函数值的近似值。代数多项式、三角多项式、有理函数或样条函数代数多项式、三角多项式、有理函数或样条函数第二章 插值与拟合(2.1)式称为式称为插值条件插值条件，x2 xn b 点上的值点上的值 y0,y1,yn.若存在一简单若存在一简单 函数函数 p(x),使得使得 p(xi)=yi i =0,1,2,n (2.1)定义定义2.

7、1f(x)称为称为被插函数被插函数，a,b 称为称为插值区间插值区间，称为称为插值节点插值节点，求求 p(x)的方法就是的方法就是插值法插值法。设函数设函数 f(x)在在a,b上有定义，且已知在上有定义，且已知在 a x0 x1成立成立,则称则称 p(x)为为 f(x)的的插值函数插值函数。近似计算近似计算 f(x)的值、零点、极的值、零点、极值点、导数、积分，值点、导数、积分，插值点在插值区间内的称为插值点在插值区间内的称为内插内插,否则称否则称外插外插.第二章 插值与拟合最常用的插值函数是最常用的插值函数是?代数多项式代数多项式用用代数多项式代数多项式作插值函数的插值称为作插值函数的插值称

8、为多项式插值多项式插值本章主要讨论的内本章主要讨论的内容容插值函数的类型有很多种插值函数的类型有很多种插值问题插值问题插值法插值法插值函数插值函数分段函数分段函数三角多项式三角多项式第二章 插值与拟合x0 x1x2x3x4f(x)p(x)曲线曲线 P(x)近似近似 f(x)研究问题：研究问题：（1）满足插值条件的）满足插值条件的P(x)是否是否存在唯一存在唯一？（2）若满足插值条件的）若满足插值条件的P(x)存在，存在，如何构造如何构造P(x)？（3）如何如何估计估计用用P (x)近似替代近似替代 f(x)产生的产生的误差误差？第二章 插值与拟合问题问题2 2插值多项式的构造插值多项式的构造

9、可设可设p(x)=a0 +a1 x+an x n 确定多项式确定多项式 p(x)的次数的次数方法：待定系数法方法：待定系数法要求插值多项式要求插值多项式 p(x)，可以通过求，可以通过求n+1个方程的解个方程的解:得到。但这样做不但计算复杂，得到。但这样做不但计算复杂，而且难于得到而且难于得到pn(x)的简单表达式。的简单表达式。结论：结论：n+1n+1个插值节点产生的插值多项式至多是个插值节点产生的插值多项式至多是n n次的次的第二章 插值与拟合问题插值多项式的存在唯一性问题插值多项式的存在唯一性 设设 pn(x)是是 f(x)的插值多项式，的插值多项式，Hn表示次数不超过表示次数不超过n

10、的所有多项的所有多项且且 pn(x)Hn.称插值多项式存在且唯一，就是指在称插值多项式存在且唯一，就是指在由由(2.1)可得可得(2.2)方程组方程组(2.2)有唯一解有唯一解插值多项式的唯一性插值多项式的唯一性0(xixj)定理定理2.1 满足条件满足条件(2.1)的插值多项式存在且唯一。的插值多项式存在且唯一。范德蒙行列式范德蒙行列式a0,a1,a2,an存在唯一存在唯一p(xi)=yi i =0,1,2,nHn 中有且仅有一个中有且仅有一个 pn(x)满足插值条件满足插值条件(2.1)式。式。式的集合。式的集合。n+1个节点互异第二章 插值与拟合为求得便于使用的简单插值多项式为求得便于使

11、用的简单插值多项式 p(x)，我们先讨论我们先讨论n=1的情形。的情形。当当n=1n=1时，要构造通过两点时，要构造通过两点(x0,y0 )和和(x1,y1)的不超过的不超过1 1次的多项式次的多项式p1(x)(后面记后面记作作L1(x)，使得，使得2.1.2拉格朗日插值拉格朗日插值第二章 插值与拟合y 0 x y=f(x)y=L1(x)x0 x1 称为线性（一次）插值称为线性（一次）插值（两点式）（两点式）（点斜式）（点斜式）第二章 插值与拟合或或L1(x)是两个线性函数是两个线性函数的线性组合的线性组合称为节点称为节点x0 0,x1 1上上线性插值基函数线性插值基函数-线性线性Lagran

12、ge插值多项式形式插值多项式形式第二章 插值与拟合 y10 x0 x1 x l0(x)l1(x)节点上的节点上的线性线性 插值基函数：插值基函数：满足满足 y10 x0 x1 x(2.3)(2.4)x0 x1l0(x)10l1(x)01第二章 插值与拟合lk,lk+1称为节点上称为节点上线性插值基函数线性插值基函数.满足满足 y10 xk xk+1 x y10 xk xk+1 x lk(x)lk+1(x)(2.7)xkxk+1lk(x)10lk+1(x)01第二章 插值与拟合(2.6)式也称为拉格朗式也称为拉格朗日型插值多项式，其中基函数日型插值多项式，其中基函数lk,lk+1与与yk,yk+

13、1无无关，而由插值节点关，而由插值节点xk,xk+1决定决定因此，一次拉格朗日插值多项式是插值基函因此，一次拉格朗日插值多项式是插值基函数数lk,lk+1的线性组合，相应的组合系数是该点的函的线性组合，相应的组合系数是该点的函数值数值 yk,yk+1第二章 插值与拟合例例2.12.1 已知已知 ,解解:这里这里x0 0=100=100，y0 0=10=10，x1 1=121=121，y1 1=11,=11,利用线利用线性插值性插值 利用线性插值利用线性插值求求第二章 插值与拟合第二章 插值与拟合 先求先求 插值基函数插值基函数 l 0(x),l1(x),l 2(x),它们满足它们满足 (1)都

14、是二次函数；都是二次函数；(2)在节点满足在节点满足(2.8)x0 x1x2l0(x)100l1(x)010l2(x)001第二章 插值与拟合y 1 0 xy 1 0 xy 1 0 xx0 x1 x2 先求先求 l0(x):待定系数待定系数x0 x1 x2x0 x1 x2 由由l0(x)满足的两个条件满足的两个条件类似地类似地,可得可得知知l0(x)中含有两个因子中含有两个因子(x-x1)(x-x2)，且是二次的，且是二次的再由再由l0(x)满足的条件满足的条件即得即得所以有所以有 L2(x)=y0 l0 0(x)+y1 l1(x)+y2 l2(x)第二章 插值与拟合L2(x j)=y j,j

15、=k-1,k,k+1.L2(x)=yk-1 lk 1(x)+yk lk(x)+yk+1 lk+1(x)值值件件插插条条再构造再构造插值插值多项式多项式L2(x)是三个二次插值多项式的线是三个二次插值多项式的线性组合，且也满足插值条件性组合，且也满足插值条件(2.9)-过三点过三点(xk-1,yk-1),(xk,yk)与与(xk+1,yk+1)的的抛物线抛物线Y=L2(x)的几何意义的几何意义第二章 插值与拟合例例2.1*已知已知 ,解解:这里这里x0 0=100=100，y0 0=10=10，x1 1=121=121，y1 1=11,=11,x2 2=144=144，y2 2=12=12，利用

16、抛物线插值公式利用抛物线插值公式 利用抛物线插值利用抛物线插值求求第二章 插值与拟合这种用插值基函数表示的方法容易推广到更一般的情形。这种用插值基函数表示的方法容易推广到更一般的情形。n次次Lagrange 插值多项式插值多项式求通过求通过n+1个节点的个节点的n 次插值多项式次插值多项式Ln(x)：先求插值基函数先求插值基函数然后构造插值多项式然后构造插值多项式设设Ln(x)=满足插值条件：满足插值条件：L n(xj)=y j ,j=0,1,n定义定义2.2 若若n 次多项式次多项式 lk(x)(k=0,1,n)在各节点在各节点j,k=0,1,n上满足条件上满足条件 则称这则称这n +1个个

17、n 次多项式为这次多项式为这n+1个节点上的个节点上的n 次次插值基函数插值基函数。第二章 插值与拟合先求先求 插值基函数插值基函数，k=0,1,n.k=0,1,n.L2(x)=y0 l0(x)+y1 l1(x)+y2 l2(x)（类似于前面讨论（类似于前面讨论n n=1,2 =1,2 时的情形）时的情形）(2.10)第二章 插值与拟合再构造再构造插值多项式插值多项式（Ln(x)是是n+1个插值基函数的线性组合）个插值基函数的线性组合）定理定理2.2（Lagrange）插值多项式插值多项式通常次数通常次数=n,但特殊情形次数可但特殊情形次数可 n,如：过三点的二次插值多项式如：过三点的二次插值

18、多项式共线时共线时(2.11)第二章 插值与拟合显然，如此构造的显然，如此构造的L(x)是不超过是不超过n次多项式。当次多项式。当n=1时，时，称为线性插值。当称为线性插值。当n=2时，称为抛物线插值。时，称为抛物线插值。第二章 插值与拟合 设设 为插值节点，为插值节点，n次多项式次多项式 满足条件满足条件 由此可得由此可得称为称为lagrange插值基函数插值基函数。LagrangeLagrange插值多项式的另一种形式插值多项式的另一种形式第二章 插值与拟合于是，于是，lk(x)可以写成可以写成容易求得容易求得(2.12)第二章 插值与拟合x0 x1 xi xi+1 xn-1 xny=f(

19、x)y=p(x)ab在插值区间在插值区间 a,b 上用上用插值多项式插值多项式p(x)近似代替近似代替f(x),除了在插值节除了在插值节点点xi上没有误差外，在其它点上一般是存在误差的。上没有误差外，在其它点上一般是存在误差的。若记若记 R(x)=f(x)-p(x),则则 R(x)就是用就是用 p(x)近似代替近似代替 f(x)时的时的截断误差截断误差,或称插值余项或称插值余项.我们可根据后面的定理来估计它的大小我们可根据后面的定理来估计它的大小.问题问题 LagrangeLagrange插值多项式的截断误差插值多项式的截断误差第二章 插值与拟合定理定理2.3 设设f(x)在在 a,b 有有n

20、+1阶导数，阶导数，x0,x1,xn 为为 a,b 上上n+1个互异的节点个互异的节点,Ln(x)为满足为满足 Ln(xi)=f(xi)(i=1,2,n)的的n 次插值多项式，那么对于任何次插值多项式，那么对于任何x a,b ,(a,b),有插值余项有插值余项其中其中第二章 插值与拟合注意：注意：余项表达式仅当余项表达式仅当 存在时才能应用，且是唯一的。存在时才能应用，且是唯一的。在在(a,b)内的具体位置通常不能给出，因此内的具体位置通常不能给出，因此R(x)不能准确地计算出来，只能估计它的值不能准确地计算出来，只能估计它的值若有若有 ,则则截断误差限截断误差限是是 n次插值多项式对次数不高

21、于次插值多项式对次数不高于n次的多项式完全精确。次的多项式完全精确。（因为，若（因为，若f(x)为次数不高于为次数不高于n次的多项式次的多项式,从而从而Rn(x)=0.）则则f(n+1)()=0,=0,第二章 插值与拟合y 0 xxk xk+1 线性插值：线性插值：特别地，特别地，n=1,2 时的插值余项时的插值余项：第二章 插值与拟合y 0 x 抛物线插值：抛物线插值：xk-1 xk xk+1 第二章 插值与拟合第二章 插值与拟合练习练习 要制作三角函数要制作三角函数sin sin x的值表，已知表值有四位小数，的值表，已知表值有四位小数，要求用线性插值引起的截断误差不超过要求用线性插值引起

22、的截断误差不超过表值的舍入误差表值的舍入误差，试，试确定其最大允许的步长。确定其最大允许的步长。解解 f(x)=sin x,设设xi,xi为任意两个插值节点，最大允许步为任意两个插值节点，最大允许步长记为长记为 h=hi=xi xi，第二章 插值与拟合5 插值误差的事后估计法插值误差的事后估计法 在许多情况下，直接用插值余项公式（在许多情况下，直接用插值余项公式（2.132.13）来估计误差是困难）来估计误差是困难的。下面以线性插值为例，介绍另一种估计误差的方法。的。下面以线性插值为例，介绍另一种估计误差的方法。第二章 插值与拟合由上式可见，可以通过两个结果的偏差由上式可见，可以通过两个结果的

23、偏差来估计插值误差来估计插值误差第二章 插值与拟合第二章 插值与拟合2.1.3 逐次线性插值法逐次线性插值法为克服这一缺点，通常可用逐次线性插值方法求得高次插为克服这一缺点，通常可用逐次线性插值方法求得高次插值。例如在例值。例如在例2.1-2.1*中：中：第二章 插值与拟合则则第二章 插值与拟合现在令现在令 表示函数表示函数 关于节点关于节点 的的n-1次插值多项式，次插值多项式，是零次多项式是零次多项式,i1,in均为非负整数。均为非负整数。一般地，可通过利用两个一般地，可通过利用两个 k次插值多次式的线性插值得到次插值多次式的线性插值得到（k+1）次插值多项式：）次插值多项式：上式是关于上

24、式是关于x插值多项式，显然插值多项式，显然 i=0，1，2,k-1时时 (*)第二章 插值与拟合从而证明了插值多项式从而证明了插值多项式(*)满足插值条件。我们称满足插值条件。我们称(*)为为Aitken（埃特金）逐次线性插值多项式（埃特金）逐次线性插值多项式.而而第二章 插值与拟合当当k=0时为线性插值。时为线性插值。k=1时插值节点为时插值节点为 三点，公式为三点，公式为计算时可由计算时可由k=0到到k=n-1逐次求得所需的插值多项式。计算过程如下逐次求得所需的插值多项式。计算过程如下第二章 插值与拟合公式公式(*)也可以改成下面的计算公式也可以改成下面的计算公式称之为称之为NEVILLE

25、（列维尔）算法列维尔）算法，计算过程如下，计算过程如下第二章 插值与拟合 从表上看每增加一个节点就计算一行，斜线上是从表上看每增加一个节点就计算一行，斜线上是1 1次到次到4 4次插值多项式的值，如精度不满足要求，再增加一个节点，次插值多项式的值，如精度不满足要求，再增加一个节点，前面计算完全有效，这个算法适用于计算机上计算，且具前面计算完全有效，这个算法适用于计算机上计算，且具有自动选节点并逐步比较精度的特点，程序也比较简单。有自动选节点并逐步比较精度的特点，程序也比较简单。算例见教材算例见教材(略）。略）。下面介绍的牛顿插值多项式就克服了这个缺点。它能下面介绍的牛顿插值多项式就克服了这个缺

26、点。它能根据插值条件构造一个插值多项式，它既有具体的表达根据插值条件构造一个插值多项式，它既有具体的表达式，又很容易用它计算任何点的函数值。式，又很容易用它计算任何点的函数值。逐次线性插值法的优点是能够最有效地计算任何给定点逐次线性插值法的优点是能够最有效地计算任何给定点的函数值，而不需要写出各步用到的插值多项式的表达式。的函数值，而不需要写出各步用到的插值多项式的表达式。但如果解决某个问题是但如果解决某个问题是需要插值多项式的表达式需要插值多项式的表达式，那么，那么，它的这个优点就成了它的缺点了。它的这个优点就成了它的缺点了。第二章 插值与拟合 拉格朗日插值拉格朗日插值采用插值基函数的线性组

27、采用插值基函数的线性组合来构造插值多项式合来构造插值多项式含义直观含义直观形式对称形式对称优点：优点：缺点：缺点：计算量大计算量大 由插值多项式存在唯一性的定理说明，满足插值条由插值多项式存在唯一性的定理说明，满足插值条件的多项式存在，并且插值多项式与构造方法无关。然而，件的多项式存在，并且插值多项式与构造方法无关。然而，直接求解方程组直接求解方程组(1.3)(1.3)的方法，不但计算复杂，而且难于的方法，不但计算复杂，而且难于得得到到p(x)的简单表达式。类似于拉格朗日插值，我们还可的简单表达式。类似于拉格朗日插值，我们还可以给出不同形式的便于使用的其它插值多项式。以给出不同形式的便于使用的其它插值多项式。第二章 插值与拟合基本思想基本思想：在：在n n次多项式空间次多项式空间Pn中找一组合适的中找一组合适的基函数基函数 0 0(x),),1 1(x),),n n(x),),使使pn(x)=b0 0(x)+b1 1(x)+bn n(x)(bi 为常数为常数)不同的基函数的选取导致不同的不同的基函数的选取导致不同的插值方法插值方法Lagrange插值插值Newton插值插值