《拉格朗日插值逐次线性插值法.ppt》由会员分享，可在线阅读，更多相关《拉格朗日插值逐次线性插值法.ppt（53页珍藏版）》请在三一办公上搜索。
1、第二章 函数的插值,学习目标：掌握多项式插值的Lagrange插值公式、牛顿插值公式等，等距节点插值、差分、差商、重节点差商与埃米特插值。重点是多项式插值方法。,2.1.5 Hermite插值多项式,均差和Newton插值多项式,逐次线性插值,2.1.2 Lagrange插值多项式,2.1.1 问题的提出,2.1 多项式插值,给定空间一组有序的控制点（control point），得到一条光滑的分段参数多项式曲线的方法:曲线顺序经过所有的控制点，则称为对这些控制点进行插值，得到的曲线称为插值曲线。构造一条在某种意义下最靠近控制点的曲线，这称为对这些控制点进行逼近，得到的曲线称为逼近(拟合)曲线
2、。,(a)5个控制点的插值曲线(b)5个控制点的逼近曲线,本章先讨论插值问题，然后再讨论数据拟合的有关问题。,拟合法就是考虑到数据不一定准确，不要求近似表达式 经过所有的点，而只要求在给定的 上误差（i=0，1,n）按某种标准最小。若记=(1,2,n)T，就是要求向量的范数|最小。,问题：基于未知函数或复杂函数的某些已知信息，如何构造这些函数的近似表达式?,情形函数f(x)在x点的Taylor展开式,称为函数f(x)的Taylor插值,解:设,例如：利用Taylor插值求,利用Tylor插值，有,y=f(x),x0,p(x),Tylor插值的缺陷：Tylor插值中有导数运算，而计算机实现求导运
3、算存在困难；近似区间小,在大的区间上不可行,情形在区间a,b上考虑函数f(x)的近似,y=f(x),a b,求解：y=f(x)在 a,b 上的近似曲线？,利用函数f(x)在区间a,b上一系列点的值 yi=f(xi)（可通过观察、测量、试验等方法得到）,y=f(x),插值法,解决思路,根据 f(x)在n+1个已知点的值，求一个足够光滑又比较简单的函数p(x)，作为 f(x)的近似表达式，,f(x),p(x),从几何上看,曲线 P(x)近似 f(x),从代数上看，看p(x)满足以下代数条件,p(xi)=yi i=0,1,2,n,这就是所谓的插值,然后计算 p(x)在a,b 上其它点x 处的函数值作
4、为原来函数,f(x)在此点函数值的近似值。,代数多项式、三角多项式、有理函数或样条函数,(2.1)式称为插值条件，,x2 xn b 点上的值 y0,y1,yn.若存在一简单 函数 p(x),使得 p(xi)=yi i=0,1,2,n(2.1),定义2.1,f(x)称为被插函数，,a,b 称为插值区间，称为插值节点，,求 p(x)的方法就是插值法。,设函数 f(x)在a,b上有定义，且已知在 a x0 x1,成立,则称 p(x)为 f(x)的插值函数。,近似计算 f(x)的值、零点、极值点、导数、积分，,插值点在插值区间内的称为内插,否则称外插.,最常用的插值函数是?,代数多项式,用代数多项式作
5、插值函数的插值称为多项式插值,本章主要讨论的内容,插值函数的类型有很多种,插值问题,插值法,插值函数,分段函数,三角多项式,f(x),p(x),从几何上看,曲线 P(x)近似 f(x),研究问题：,（1）满足插值条件的P(x)是否存在唯一？,（2）若满足插值条件的P(x)存在，如何构造P(x)？,（3）如何估计用P(x)近似替代 f(x)产生的误差？,问题2插值多项式的构造,可设p(x)=a0+a1 x+an x n,确定多项式 p(x)的次数,方法：待定系数法,要求插值多项式 p(x)，可以通过求n+1个方程的解:,得到。但这样做不但计算复杂，,而且难于得到pn(x)的简单表达式。,结论：n
6、+1个插值节点产生的插值多项式至多是n次的,问题插值多项式的存在唯一性,设 pn(x)是 f(x)的插值多项式，,Hn表示次数不超过n 的所有多项,且 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,n,Hn 中有且仅有一个 pn(x)满足插值条件(2.1)式。,式的集合。,n+1个节点互异,为求得便于使用的简单插值多项式 p(x)，我们先讨论n=1的情形。,当n=
7、1时，要构造通过两点(x0,y0)和(x1,y1)的不超过1次的多项式p1(x)(后面记作L1(x)，使得,拉格朗日插值,称为线性（一次）插值,（两点式）,（点斜式）,或,L1(x)是两个线性函数的线性组合,称为节点x0,x1上线性插值基函数,-线性Lagrange插值多项式形式,节点上的线性 插值基函数：,满足,y10 x0 x1 x,(2.3),(2.4),lk,lk+1称为节点上线性插值基函数.,满足,(2.7),(2.6)式也称为拉格朗日型插值多项式，其中基函数lk,lk+1与yk,yk+1无关，而由插值节点xk,xk+1决定因此，一次拉格朗日插值多项式是插值基函数lk,lk+1的线性
8、组合，相应的组合系数是该点的函数值 yk,yk+1,例2.1 已知,解:这里x0=100，y0=10，x1=121，y1=11,利用线性插值,利用线性插值求,先求 插值基函数 l 0(x),l1(x),l 2(x),它们满足(1)都是二次函数；(2)在节点满足,(2.8),先求 l0(x):,由l0(x)满足的两个条件,类似地,可得,知l0(x)中含有两个因子(x-x1)(x-x2)，且是二次的,再由l0(x)满足的条件,即得,所以有 L2(x)=y0 l0(x)+y1 l1(x)+y2 l2(x),L2(x j)=y j,j=k-1,k,k+1.,L2(x)=yk-1 lk 1(x)+yk
9、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=100，y0=10，x1=121，y1=11,x2=144，y2=12，利用抛物线插值公式,利用抛物线插值求,这种用插值基函数表示的方法容易推广到更一般的情形。,n次Lagrange 插值多项式,求通过n+1个节点的n 次插值多项式Ln(x)：,先求插值基函数然后构造插值多项式,设Ln(x)=满足插值条件：L n(xj)=y
10、 j,j=0,1,n,定义2.2 若n 次多项式 lk(x)(k=0,1,n)在各节点,j,k=0,1,n,上满足条件,则称这n+1个n 次多项式为这n+1个节点上的n 次插值基函数。,先求 插值基函数,，k=0,1,n.,k=0,1,n.,L2(x)=y0 l0(x)+y1 l1(x)+y2 l2(x),（类似于前面讨论n=1,2 时的情形）,(2.10),再构造插值多项式,（Ln(x)是n+1个插值基函数的线性组合）,定理2.2（Lagrange）插值多项式,通常次数=n,但特殊情形次数可n,如：过三点的二次插值多项式,(2.11),显然，如此构造的L(x)是不超过n次多项式。当n=1时，
11、称为线性插值。当n=2时，称为抛物线插值。,设 为插值节点，n次多项式 满足条件 由此可得,称为lagrange插值基函数。,Lagrange插值多项式的另一种形式,于是，lk(x)可以写成,容易求得,(2.12),x0 x1 xi xi+1 xn-1 xn,y=f(x),y=p(x),a,b,在插值区间a,b上用插值多项式p(x)近似代替f(x),除了在插值节点xi上没有误差外，在其它点上一般是存在误差的。,若记 R(x)=f(x)-p(x),则 R(x)就是用 p(x)近似代替 f(x)时的截断误差,或称插值余项.我们可根据后面的定理来估计它的大小.,问题 Lagrange插值多项式的截断
12、误差,定理2.3 设f(x)在a,b有n+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次插值多项式对次数不高于n次的多项式完全精确。,（因为，若f(x)为次数不高于n次的多项式,从而Rn(x)=0.）,则f(n+1)()=0,线性插值：,特别地，n=1,2 时的插值余项：,抛物线插值：
13、,练习 要制作三角函数sin x的值表，已知表值有四位小数，要求用线性插值引起的截断误差不超过表值的舍入误差，试确定其最大允许的步长。,解 f(x)=sin x,设xi,xi为任意两个插值节点，最大允许步长记为 h=hi=xi xi，,5 插值误差的事后估计法,在许多情况下，直接用插值余项公式（2.13）来估计误差是困难的。下面以线性插值为例，介绍另一种估计误差的方法。,2.1.3 逐次线性插值法,则,现在令 表示函数 关于节点 的n-1次插值多项式，是零次多项式,i1,in均为非负整数。一般地，可通过利用两个 k次插值多次式的线性插值得到（k+1）次插值多项式：,上式是关于x插值多项式，显然
14、,i=0，1，2,k-1时,(*),从而证明了插值多项式(*)满足插值条件。我们称(*)为Aitken（埃特金）逐次线性插值多项式.,而,当k=0时为线性插值。k=1时插值节点为 三点，公式为计算时可由k=0到k=n-1逐次求得所需的插值多项式。计算过程如下,公式(*)也可以改成下面的计算公式称之为NEVILLE（列维尔）算法，计算过程如下,从表上看每增加一个节点就计算一行，斜线上是1次到4次插值多项式的值，如精度不满足要求，再增加一个节点，前面计算完全有效，这个算法适用于计算机上计算，且具有自动选节点并逐步比较精度的特点，程序也比较简单。算例见教材(略）。,下面介绍的牛顿插值多项式就克服了这
15、个缺点。它能根据插值条件构造一个插值多项式，它既有具体的表达式，又很容易用它计算任何点的函数值。,逐次线性插值法的优点是能够最有效地计算任何给定点的函数值，而不需要写出各步用到的插值多项式的表达式。但如果解决某个问题是需要插值多项式的表达式，那么，它的这个优点就成了它的缺点了。,拉格朗日插值采用插值基函数的线性组合来构造插值多项式,含义直观,形式对称,优点：,缺点：,计算量大,由插值多项式存在唯一性的定理说明，满足插值条件的多项式存在，并且插值多项式与构造方法无关。然而，直接求解方程组(1.3)的方法，不但计算复杂，而且难于得到p(x)的简单表达式。类似于拉格朗日插值，我们还可以给出不同形式的便于使用的其它插值多项式。,基本思想：在n次多项式空间Pn中找一组合适的基函数0(x),1(x),n(x),使,pn(x)=b0 0(x)+b1 1(x)+bn n(x)(bi 为常数),不同的基函数的选取导致不同的插值方法,Lagrange插值,Newton插值,
