计算方法—插值法-(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,.,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第二章 插 值 法,（,Interpolation,）,2.1,引言,2.2,拉格朗日插值,2.3,均差与牛顿插值公式,2.5,分段低次插值,2.6,三次样条插值,2.4,埃尔米特插值,Chapter2,插值法,2024/12/3 周二,1,.,Chapter2,插值法,表示两个变量,x,y,内在关系一般由函数式,y=f(x,),表达。但在实际问题中的函数是多种多样的,有下面两种情况：,（,1,）由实验观测而得的一组离散数据,(,函数表,),，显然这种函数关系式,y=f(x,),存在且连续，但未知。,（,2,）函数解析表达式已知，但计算复杂，不便使用。通常也列函数表，如,y=sin(x),y=lg(x,),2.1,引言,2024/12/3 周二,2,.,办法是：根据所给的,y=,f,(x,),的函数表，构造一个简单的连续函数,P(X),近似替代,f,(x,),。,Chapter2,插值法,2.1,引言,近似代替即逼近的方法有很多种：插值方法、最佳一致逼近、最佳平方逼近、曲线拟合。,由于问题的复杂性,直接研究函数,f(x,),可能,很困难,但为了研究函数的变化规律,有时要求,不在表上的函数值，怎么办？,？,简单连续函数,P(x,),指可用四则运算计算的函数,:,如有理函数,(,分式函数,),多项式或分段多项式。,2024/12/3 周二,3,.,Chapter2,插值法,2.1,引言,插值问题的数学提法：,已知函数,y=f(x,),在,n+1,个点,x,0,x,1,x,n,上的函数值,y,i,=f(x,i,)(i,=0,1,n,),，求一个简单函数,y=P(x,),，使其满足,P(x,i,)=y,i,（,i=0,1,n,）。即要求该简单函数曲线要经过,y=f(x,),上已知的这,n+1,个点,(x,0,y,0,),(x,1,y,1,),(x,n,y,n,),同时在其它,xa,b,上要估计误差,R(x)=f(x)-P(x,),。,2024/12/3 周二,4,.,Chapter2,插值法,2.1,引言,重要术语,对于,n+1,个基点的插值问题，我们称：,f(x,),为被插值函数；,P(x,),为插值函数；,x,0,x,1,x,n,为插值基点或插值节点；,P(x,k,)=f(x,k,),k,=0,1,n,为插值条件；,a,b,为插值区间。,注释：对于早期的插值问题来说，,f(x,),通常是已知的，比如对数函数，指数函数，三角函数等，这些问题现在已经不用插值法来计算了；对于现在的许多实际问题来说，我们并不知道,f(x,),的具体形式，所对应的函数值可能是由测量仪器或其他物理设备中直接读出来的，,f(x,),只是一个概念中的函数。,2024/12/3 周二,5,.,Chapter2,插值法,2.1,引言,多项式插值,对于,n+1,个基点的插值问题，如果要求插值函数是次数不超过,n,的多项式，记为,P,n,(x,),，则相应的问题就是多项式插值，并且把,P,n(,x,),称为插值多项式。,实际上，我们所考虑的插值函数通常都是多项式函数或分段多项式函数。由于次数不超过,n,的多项式的一般形式为：,P,n,(x,)=a,0,+a,1,x+a,2,x,2,+,+a,n,x,n,所以只要确定了,n+1,个系数,a,0,，,a,1,，,，,a,2,，,a,n,，我们便确定了一个插值多项式。,2024/12/3 周二,6,.,Chapter2,插值法,y,x,2.1,引言,x,0,x,1,x,2,x,n-1,x,n,y,0,y,1,y,2,多项式插值的几何意义：,多项式,P,n,(x,),，其几何曲线过给定的,y=f(x,),的,n+1,个点,(x,i,y,i,)i=0,1,2,n,。,y,n,y,n-1,2024/12/3 周二,7,.,Chapter2,插值法,2.2,拉格朗日插值,Lagrange插值,2024/12/3 周二,8,.,Chapter2,插值法,2.2,拉格朗日插值,2-1,插值多项式的唯一性,已知,y=f(x,),的函数表，,且,x,i,(i,=0,1,n),两两互异，,x,i,a,b,。,求次数不超过,n,的多项式,使得,P,n,(x,i,)=y,i,i,=0,1,2,n,此问题中,P,n,(x,),是否存在？存在是否唯一？如何求？,显然关键是确定多项式,P,n,(x,),的系数,a,0,a,1,a,n,。,2024/12/3 周二,9,.,Chapter2,插值法,2.2,拉格朗日插值,2-1,插值多项式的唯一性,定理：,在,n+1,个互异的插值节点,x,0,x,1,x,n,上满足插值条件,P,n,(x,i,)=y,i,i,=0,1,2,n,的次数不超过,n,的代数多项式,P,n,(x,),存在且唯一。,分析：为求,主要考虑插值条件,2024/12/3 周二,10,.,Chapter2,插值法,2.2,拉格朗日插值,2-1,插值多项式的唯一性,证明：,由插值条件，有,其系数矩阵的行列式为,关于未知量,a,0,a,1,a,n,的,非齐次线性方程组,2024/12/3 周二,11,.,Chapter2,插值法,2.2,拉格朗日插值,例 给定,f(x,),的函数表，求,f(x,),的次数不超过,3,的插值多项式。,x -1 1 2 5,y -7 7 -4 35,解：设,则，,解方程组得,a,0,=10,a,1,=5,a,2,=-10,a,3,=2,即,P,3,(x)=10+5x-10 x,2,+2x,3,当,n=20,在,10,9,次,/,秒的计算机上计算需几万年！,！,2024/12/3 周二,12,.,Chapter2,插值法,2.2,拉格朗日插值,2-2,线性插值与抛物插值,问题的提法：,已知函数,y=f(x,),的函数表,求次数不超过,1,的多项式,L,1,(x)=a,0,+a,1,x,满足插值条件,L,1,(x,k,)=y,k,L,1,(x,k+1,)=y,k+1,。,x x,k,x,k+1,y y,k,y,k+1,分析,:,过两点,(x,k,y,k,),(x,k+1,y,k+1,),作直线,y=L,1,(x),线性插值,解,:,由点斜式方程,称为线性,插值基函数,而,L,1,(x),是它们的线性组合。,2024/12/3 周二,13,.,Chapter2,插值法,2.2,拉格朗日插值,L,1,(X),L,1,(X),lg2.718 L,1,(2.718)=0.43428,2024/12/3 周二,14,.,2.2,拉格朗日插值,Chapter2,插值法,2-2,线性插值与抛物插值,利用线性插值法对函数,y=f(x,),进行逼近时，即用直线,y=L,1,(x),代替曲线,y=f(x,),。,显然当插值区间较大或曲线,x,0,x,1,凸凹变化大时，线性插值的误差很大。,为了减小这种误差，我们用简单的曲线,(,抛物线,),去近似代替复杂曲线,y=f(x,),。二次多项式函数的曲线为抛物线，所以我们构造插值函数,L,2,(x),，即,n=2,。,2024/12/3 周二,15,.,2.2,拉格朗日插值,Chapter2,插值法,问题的提法：,已知,y=f(x,),的函数表，,x,0,x,1,x,2,为互异节点，求一个次数不超过,2,的多项式,L,2,(x)=a,0,+a,1,x+a,2,x,2,：,L,2,(x,0,)=y,0,L,2,(x,1,)=y,1,L,2,(x,2,)=y,2,x x,0,x,1,x,2,y y,0,y,1,y,2,几何意义,:L,2,(x),为过三点,(x,0,y,0,),(x,1,y,1,),(x,2,y,2,),的抛物线。,方法：,基函数法，构造基函数,l,0,(x),l,1,(x),l,2,(x),(,三个二次式,),使,L,2,(x)=y,0,l,0,(x)+y,1,l,1,(x)+y,2,l,2,(x),满足插值条件。,2024/12/3 周二,16,.,2.2,拉格朗日插值,Chapter2,插值法,求二次多项式,l,0,(x),：,l,0,(x,0,)=1,l,0,(x,1,)=0,l,0,(x,2,)=0,l,0,(x)=C(x-x,1,)(x-x,2,),只须求,C=?,由,l,0,(x,0,)=1,得,C(x,0,-x,1,)(x,0,-x,2,)=1,C=1/(x,0,-x,1,)(x,0,-x,2,),同理求得,l,1,(x),l,2,(x),即抛物插值的插值基函数如下,:,抛物插值问题的解,:,2024/12/3 周二,17,.,2.2,拉格朗日插值,Chapter2,插值法,2-3,拉格朗日插值多项式,已知,y=f(x,),在两两互异节点,x,0,x,1,x,n,的函数值,y,1,y,2,y,n,求,n,次多项式,L,n,(x,)=a,0,+a,1,x+a,2,x,2,+,+a,n,x,n,满足插值条件,L,n,(x,i,)=y,i,.i=0,1,2,3,n,。,基函数法：求,n+1,个,n,次多项式,l,0,(x),l,1,(x),l,n,(x,),使,L,n,(x,)=y,0,l,0,(x)+y,1,l,1,(x)+y,n,l,n,(x,),。,L,n,(x,),须满足插值条件,L,n,(x,i,)=y,i,i=0,1,2,3,n,即,y,0,l,0,(x,i,)+y,1,l,1,(x,i,)+,+y,i,l,i,(x,i,),+y,n,l,n,(x,i,)=y,i,2024/12/3 周二,18,.,2.2,拉格朗日插值,Chapter2,插值法,l,i,(x,0,)=0,l,i,(x,i-1,)=0,l,i,(x,i+1,)=0,l,i,(x,n,)=0,即,l,i,(x,),有,n,个零点，,x,0,x,1,x,k-1,x,k+1,x,n,。,求插值基函数,l,i,(x,),与节点有关，而与,f,无关,2024/12/3 周二,19,.,2.2,拉格朗日插值,Chapter2,插值法,于是，满足插值条件,L,n,(x,i,)=y,i,.i=0,1,2,3,n,的插值多项式为：,上式即为拉格朗日（,Lagrange,）,插值多项式。当,n=1,，或,n=2,时分别就是线形插值与抛物插值公式。,基函数的,等价形式,2024/12/3 周二,20,.,2.2,拉格朗日插值,Chapter2,插值法,2-4,插值余项,函数,y=f(x,),与其,Lagrange,插值多项式,L,n,(x,),：,(1)L,n,(x,i,)=f(x,i,)=y,i,i=0,1,2,n,；,(2),而对于插值区间,a,b,内插值节点,x,i,(i,=1,2,n),以外的点,x,一般,L,n,(x,),f(x,),，存在误差。,Def:,对于一般的,n+1,个基点的多项式插值问题，设,f(x,),为被插值函数,L,n,(x,),为相应的插值多项式,记,R,n,(x,),为,f(x,),与,L,n,(x,),的差,即,R,n,(x)=f(x)-L,n,(x,),则,R,n,(x,),就是用,L,n,(x,),近似替代,f(x,),的误差,我们称它为插值余项。,显然，由插值多项式的唯一性可以导出插值余项的唯一性。,2024/12/3 周二,21,.,2.2,拉格朗日插值,Chapter2,插值法,利用,Lagrange,插值公式,L,n,(x,),来计算，结果是否可靠，要看余项,R,n,(x,),是否足够小。,R,n,(x,)=,？,设,ax,0,x,1,x,n,b,，且满足条件,f,c,n,a,b,f,(,n,+1),在,a,b,内存在,考察,插值误差,，,R,n,(x)=f(x)-L,n,(x,),。,R,n,(,x,),至少有个,n,+1,根,把,x,看作是（任意）固定的点，作辅助函数,(,t,),有,n,+2,个不同的根,x,0,x,n,x,根据,Rolle,定理,注意：此处是对,t,求导,2024/12/3 周二,22,.,Chapter2,插值法,2.2,拉格朗日插值,定理：,设,ax,0,x,1,x,n,b,，且满足条件,f,c,n,a,b,f,(,n,+1),在,a,b,内存在,L,n,(x,),为相应的插值多项式，,R,n,(x,),为插值余项，则对任意固定的,x(a,b,),，有,其中,(a,b,),依赖于,x,，,(,x,),=(,x-x,0,)(x-x,1,),(,x-x,n,),注：,通常不能确定,，而是估计,将,作为误差上限。,当,f,(,x,),为任一个次数,n,的多项式时,可知 ，即插值多项式对于次数,n,的多项式是精确的。,2024/12/3 周二,23,.,Chapter2,插值法,线性插值的截断误差为,二次插值的截断误差为,:,2.2,拉格朗日插值,2-4,插值余项,2024/12/3 周二,24,.,2.2,拉格朗日插值,Chapter2,插值法,L,2,(x),2024/12/3 周二,25,.,例求过点,(2,0)(4,3)(6,5)(8,4)(10,1),的拉格朗日型插值多项式。,2.2,拉格朗日插值,Chapter2,插值法,解：用,4,次插值多项式对,5,个点插值。,x,0,=2,，,x,1,=4,，,x,2,=6,，,x,3,=8,，,x,4,=10,，,y,0,=0,，,y,1,=3,，,y,2,=5,，,y,3,=4,，,y,4,=1;,2024/12/3 周二,26,.,2.2,拉格朗日插值,Chapter2,插值法,解,:,2024/12/3 周二,27,.,Chapter2,插值法,2.2,拉格朗日插值,程序设计,:,程序流程图,2024/12/3 周二,28,.,2.2,拉格朗日插值,Chapter2,插值法,高度,(m)0 100 300 1000 1500 2000,压强,(kgf/m,2,)0.9689 0.9322 0.8969 0.8515 0.7984 0.7485,试用二次插值法求,1200,米处的压强值。,实际应用：,已测得某地大气压强随高度变化的一组数据，,2024/12/3 周二,29,.,解：设,x,为高度，,y,为大气压强的值，,选取,(1000,0.8515),(1500,0.7984),(2000,0.7485),三点构造二次插值多项式,代入已知的数值，得,L,2,(1200)=0.82980,2.2,拉格朗日插值,Chapter2,插值法,2024/12/3 周二,30,.,Newton,插值,2.3,均差与牛顿插值,Chapter2,插值法,2024/12/3 周二,31,.,2.3,均差与牛顿插值,Chapter2,插值法,拉格朗日插值多项式形式对称，计算较方便，但由于,L,n,(x,),依赖于全部节点，若算出所有,L,n,(x,),后精度不满足要求，又需要增加节点，则必须全部重新计算,为了克服这个缺点，我们引进牛顿插值多项式（,Newton,插值,具有承袭性,）。,不具有承袭性,2024/12/3 周二,32,.,Chapter2,插值法,2.3,均差与牛顿插值,假设对于具有,k+1(k0),个插值节点的多项式插值问题，已经得到了相应的插值多项式 ，,如果它不能满足我们的精度要求，,则希望通过增加一个插值节点 ，并利用已得到的 来构造新的，具有,k+2,个插值节点的插值多项式 ，为此,把 表为 与一个修正项 的和的形式是合理的,即,从而只要确定了,，,我们即可写出,。,此时我们称,上面的式子是具有承袭性的插值多项式。,承袭性的含义：,2024/12/3 周二,33,.,Chapter2,插值法,2.3,均差与牛顿插值,由线性代数的知识可知，任何一个,n,次多项式都,可以表示成,共,n+1,个多项式的线性组合。,那么，是否可以将这,n+1,个多项式作为插值基函数呢？,显然，多项式组,线性无关，,因此，可以作为插值基函数。,2024/12/3 周二,34,.,Chapter2,插值法,2.3,均差与牛顿插值,2024/12/3 周二,35,.,2.3,均差与牛顿插值,Chapter2,插值法,有,再继续下去待定系数的形式将更复杂,为此引入差商的概念,2024/12/3 周二,36,.,2.3,均差与牛顿插值,Chapter2,插值法,设,f,(x,),是定义在某区间内,取连续变量值或离散变量值的实值函数，且已知,f,(x,),在,在,n+1,个互异的离散点,x,0,x,1,x,n,处的函数值,f,(x,0,),，,f,(x,1,),，,，,f,(x,n,),称,为,f,(x,),在,x,k,处的,零阶差商,。,均差,(,差商,),为,f,(x,),在,x,i,x,j,处的,一阶差商,。,注,:(1),差商的几何意义：,B,A,x,0,x,1,X,Y,0,f,x,0,x,1,为弦,AB,的斜率。,(2),显然，,fx,0,x,1,=fx,1,x,0,/,*,divided difference,*,/,2024/12/3 周二,37,.,2.3,均差与牛顿插值,Chapter2,插值法,为,f,(x,),在,x,i,x,j,x,k,处的二阶差商。,均差,(,差商,),/,*,divided difference,*,/,称,一般地,如果定义了,f,(x,),的,k-1,阶差商,则可以定义,f,(x,),的,k,阶差商为,:,这里,k,可取值,2,n,。,2024/12/3 周二,38,.,2.3,均差与牛顿插值,Chapter2,插值法,差商具有如下性质,(,请同学们自证,),：,可用归纳法证明,例：,这个性质也表明均差与节点的排列顺序无关,(,均差的对称性）,2024/12/3 周二,39,.,2.3,均差与牛顿插值,Chapter2,插值法,2024/12/3 周二,40,.,2.3,均差与牛顿插值,Chapter2,插值法,性质,2,差商具有对称性,即任意调换节点的次序,差商的值不变。,依对称性，对调定义公式左端,k,阶均差中,x,0,与,x,k-1,的位置，,2024/12/3 周二,41,.,2.3,均差与牛顿插值,Chapter2,插值法,性质,4,：若,f(x,),是,x,的,n,次多项式，则一阶均差，,f,x,x,0,是,x,的,n-1,次多项式，二阶均差,f,x,x,0,x,1,是,x,的,n-2,次多项式；,一般地，函数,f,(x,),的,k,阶均差,f,x,x,0,x,k-1,是,x,的,n-k,次多项,式（,kn,时，,k,阶均差为零。,2024/12/3 周二,42,.,2.3,均差与牛顿插值,Chapter2,插值法,差商的计算方法,(,表格法,):,规定函数值为,零阶差商,差商表,2024/12/3 周二,43,.,计算规律：任一个,k,(1),阶均差的数值等于一个分式的值，其分子为所求均差左侧的数减去左上侧的数，分母为所求均差同一行最左边的节点值减去由它往上数第,k,个节点值。,2.3,均差与牛顿插值,Chapter2,插值法,x,i,f(x,k,),1,阶,2,阶,3,阶,4,阶,x,0,f(x,0,),x,1,f(x,1,),f(x,0,x,1,),x,2,f(x,2,),f(x,1,x,2,),f(x,0,x,1,x,2,),x,3,f(x,3,),f(x,2,x,3,),f(x,1,x,2,x,3,),f(x,0,x,1,x,2,x,3,),x,4,f(x,4,),f(x,3,x,4,),f(x,2,x,3,x,4,),f(x,1,x,2,x,3,x,4,),f(x,0,x,1,x,2,x,3,x,),对角线上的均差是构造牛顿型插值公式的重要数据。,2024/12/3 周二,44,.,例,已知函数,y=f(x),的观测数据如表，试构造均差表，并求,f2,4,5,及,f2,4,5,6,的值。,x,0 2 4 5 6,f(x),1 5 9 -4 13,解,n,=4,构造均差表,x,i,f(x,i,),1,阶,2,阶,3,阶,4,阶,0,2,4,5,6,2,1,1,5,9,-4,13,2,-13,17,0,-5,15,-1,5,f2,4,5=-5,f2,4,5,6=5,2.3,均差与牛顿插值,Chapter2,插值法,2024/12/3 周二,45,.,2.3,均差与牛顿插值,Chapter2,插值法,例：计算三阶均差,解：,2024/12/3 周二,46,.,均差表的数据构成一个矩阵,F,：,F,00,=f(x,0,),F,10,=f(x,1,),F,11,=fx,0,x,1,F,20,=f(x,2,),F,21,=fx,1,x,2,F,22,=fx,0,x,1,x,2,F,30,=f(x,3,),F,31,=fx,2,x,3,F,32,=fx,1,x,2,x,3,F,33,=fx,0,x,1,x,2,x,3,F,i,j-1,=fx,i-j+1,x,i,F,i-1,j-1,=fx,i-j,x,i-1,计算机上计算均差表的公式,一般有,F,i,j,=fx,i-j,x,i-j+1,x,i-1,x,i,2.3,均差与牛顿插值,Chapter2,插值法,2024/12/3 周二,47,.,2.3,均差与牛顿插值,Chapter2,插值法,牛顿插值,/*Newton,s Interpolation*/,根据线性插值的点斜式,可得牛顿均差型线性插值多项式：,牛顿均差型二次插值多项式：,2024/12/3 周二,48,.,2.3,均差与牛顿插值,Chapter2,插值法,牛顿插值公式的构造,2024/12/3 周二,49,.,Chapter2,插值法,2.3,均差与牛顿插值,只要把后一式代入前一式，得,:,牛顿插值公式的构造,2024/12/3 周二,50,.,Chapter2,插值法,2.3,均差与牛顿插值,最后一项中,均差部分含有,x,是余项部分,记为,R,n,(x,);,牛顿插值公式的构造,前面,n+1,项中,均差部分都不含有,x,因而前面,n+1,项是关于,x,的,n,次多项式,记作,N,n,(x,)_,牛顿插值公式。,由于,R,n,(x,i,)=0 i=0,1,2,n,;,所以,N,n,(x,i,)=f(x,i,)i=0,1,2,n,2024/12/3 周二,51,.,计算牛顿均差插值多项式的步骤：,2.3,均差与牛顿插值,Chapter2,插值法,（,1,）作均差表,（,2,）根据公式计算牛顿型插值多项式（表中对角线上各均差值就是,N,n,(x,),的各项系数）。,2024/12/3 周二,52,.,Chapter2,插值法,2.3,均差与牛顿插值,例,2:,已知,12,15,2,0,f,(x,i,),7,4,2,1,x,i,求满足以上插值条件的牛顿型插值多项式。,-1.25,-3.5,-1,12,7,4,13,15,4,1,2,3,0,1,三阶均差,二阶均差,一阶均差,f,(x,i,),x,则牛顿三次插值多项式为,2024/12/3 周二,53,.,拉格朗日插值与牛顿插值的比较,2.3,均差与牛顿插值,Chapter2,插值法,1,、,L,n,(x),与,N,n,(x,),均是,n,次多项式,且均满足插值条件,由多项式的唯一性,因而,两个公式的余项是相等的,即,2,、当插值多项式从,n-1,次增加到,n,次时,拉格朗日型插值必须重新计算所有的基本插值多项式,;,而对于牛顿型插值,只需用表格再计算一个,n,阶均差,然后加上一项即可。,2024/12/3 周二,54,.,2.4,埃尔米特插值,许多实际问题不仅要求插值函数在节点上与原来的函数相等,(,满足插值条件,),，而且还要求在节点上的各阶导数值也相等。满足这些条件的插值，称为埃尔米特,(Hermite,),插值。本节讨论已知两个节点 的函数值 和一阶导数,的情形。,Chapter2,插值法,2024/12/3 周二,55,.,2.4,埃尔米特插值,Chapter2,插值法,2024/12/3 周二,56,.,2.4,埃尔米特插值,基函数,函数值,一阶导数,X,0,X,1,X,0,X,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,Chapter2,插值法,2024/12/3 周二,57,.,2.4,埃尔米特插值,Chapter2,插值法,2024/12/3 周二,58,.,2.4,埃尔米特插值,Chapter2,插值法,2024/12/3 周二,59,.,2.4,埃尔米特插值,Chapter2,插值法,2024/12/3 周二,60,.,2.4,埃尔米特插值,Chapter2,插值法,2024/12/3 周二,61,.,Chapter2,插值法,2.5,分段低次插值,/*Piecewise polynomial approximation*/,多项式插值,对于,y=,f,(x,),a x,b,给定插值节点,x,0,x,1,x,n,，构造插值多项式,P,n,(x,),，,为使,P,n,(x,),更好地逼近,f,(x,),，我们已经知道插值有多种方法：,Lagrange,插值、,Newton,插值等多种方式。,插值的目的就是数值逼近，而数值逼近，为的是得到一个数学问题的足够精确的数值解。,分段插值,2024/12/3 周二,62,.,Chapter2,插值法,高次插值使,P,n,(x,),在较多点上与,f(x,),相等,，,但在插值节点外,，,误差如何？,节点间距较小,=,节点多,(n,较大,),=,插值多项式,P,n,(x,),的次数很高,(,高次插值,),我们已经知道：,f,(x,),在,n+1,个节点,x,i,(i,=0,1,2,n),上的,n,次插值多项式,P,n,(x),的余项,设想当节点数增多时会出现什么情况,?,是否插值多项式,P,n,(x,),的次数越高越好,?,2.5,分段低次插值,2024/12/3 周二,63,.,Chapter2,插值法,例,并作图比较。,定义在区间,-5,，,5,上，这是一个光滑函数，它的任意阶导数都存在。,分析：,龙格,(Runge,),现象,2.5,分段低次插值,2024/12/3 周二,64,.,Chapter2,插值法,解：,龙格,(Runge,),现象,2.5,分段低次插值,2024/12/3 周二,65,.,%lagrangen.m,function,y=lagrangen(x0,y0,x),n=length(x0);m=length(x);,for,i=1:m,z=x(i);s=0;,for,k=1:n,L=1;,for,j=1:n,if,j=k,L=L*(z-x0(j)/(x0(k)-x0(j);,end,end,s=s+L*y0(k);,end,y(i)=s;,end,y;,Chapter2,插值法,龙格,(Runge,),现象,2.5,分段低次插值,2024/12/3 周二,66,.,%Chazhibijiao.m,x=-5:0.1:5;z=0*x;y=1./(1+x.2);,plot(x,z,k,x,y,r,),axis(-5 5-1.5 2);pause,hold on,for,n=2:2:10,x0=linspace(-5,5,n+1);y0=1./(1+x0.2);,x=-5:0.1:5;y1=lagrangen(x0,y0,x);,plot(x,y1),pause,end,y2=1./(1+x0.2);y=interp1(x0,y2,x);,plot(x,y,k,),hold off,gtext(,n,=2,),gtext(,n=4,),gtext(,n=6,),gtext(,n,=8,),gtext(,n=10,),gtext(,f(x,)=1/(1+x2),),Chapter2,插值法,龙格,(Runge,),现象,2.5,分段低次插值,2024/12/3 周二,67,.,Chapter2,插值法,不同次数的,Lagrange,插值多项式的比较图,2.5,分段低次插值,2024/12/3 周二,68,.,Chapter2,插值法,结果表明,并不是插值多项式的次数越高,插值效果,越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由,Runge,发现,故称为,Runge,现象,.,从图中，可见，在靠近,-5,或,5,时，余项会随,n,值增大,而增大；,在,0,附近插值效果是好的，即余项较小；另一,种现象是插值多项式随节点增多而振动更多。,龙格,(Runge,),现象,2.5,分段低次插值,2024/12/3 周二,69,.,上述现象和定理，告诉我们用高次插值多项式是不妥当的，从数值计算上可解释为高次插值多项式的计算会带来舍入误差的增大，从而引起计算失真。因此，实践上作插值时一般只用一次、二次最多用三次插值多项式。,那么如何提高插值精度呢？采用分段插值是一种办法。,Chapter2,插值法,这个任意阶可导的光滑函数之所以出现这种现象，跟它在复平面上有,x=,1,是奇点有关。,2.5,分段低次插值,2024/12/3 周二,70,.,2.5,分段低次插值,Chapter2,插值法,随着插值节点数增加，插值多项式的次数也相应增加，,而对于高次插值容易带来剧烈振荡，带来数值不稳定。为,了既要增加插值节点，减小插值区间，以便更好的逼近被,插值函数，又要不增加插值多项式的次数，以减小误差，,我们可以采用分段插值的办法。,在区间,a,b,上取,n=1,个节点,x,0,=a,，,x,1,，,，,x,n,=b,，对应的函数值,f,(x,)=y,0,，,f,(x,1,)=y,1,，,，,f,(x,n,)=y,n,，构造函数,I,h,(x,),满足：,（,1,）插值条件：,I,h,(x,k,)=y,k,(k,=0,1,n);,（,2,）在每个区间,x,k,x,k+1,(k=0,1,n-1,),上，,I,h,(x,),是低次多项式；,（,3,）在整个区间,x,0,x,n,上,I,h,(x,),连续。,I,h,(x,),称为分段低次插值函数。,2024/12/3 周二,71,.,Chapter2,插值法,2.5,分段低次插值,分段线性插值,所谓分段线性插值就是通过插值点，用折线段连接起来逼近函数,f,(x,),。设已知节点,a=x,0,x,1,x,n,=b,上的函数值,f,0,f,n,，记,h,k,=x,k+1,-x,k,，,h=,max,h,k,求一折线函数,I,h,(x,),，满足：,（,1,）插值条件：,I,h,(x,k,)=y,k,(k,=0,1,n);,（,2,）在每个区间,x,k,x,k+1,(k=0,1,n-1,),上，,I,h,(x,),是线性函数；,（,3,）在整个区间,x,0,x,n,上,I,h,(x,),连续。,几何上看，,I,h,(x,),是由点,(x,i,f,i,)(i,=0,1,n,),连成的一条折线，在整个区间连续，在节点处,1,阶导数不连续。,2024/12/3 周二,72,.,2.5,分段低次插值,Chapter2,插值法,由定义可得,I,h,(x,),在每个小区间,x,k,x,k+1,上的表达式为,:,在每个区间,x,k,x,k+1,(k=0,1,n-1,),上，,I,h,(x,),是线性函数；,且,I,(x,k,)=,f,k,，,I,(x,k+1,)=,f,k+1,。,2024/12/3 周二,73,.,2.5,分段低次插值,Chapter2,插值法,2024/12/3 周二,74,.,2.5,分段低次插值,Chapter2,插值法,为了紧凑，也可通过分段插值基函数,l,i,(x)(i,=0,1,2,n),的线性组合将分段线性插值函数表示为一个表达式。,每个插值结点上所对应的插值基函数,l,i,(x,),应当满足：,(1),l,i,(x,),是分段线性函数；,2024/12/3 周二,75,.,2.5,分段低次插值,Chapter2,插值法,每个插值结点上所对应的插值基函数,l,i,(x,),应当满足：,Y,X,1,x,0,x,1,x,2,x,n-1,x,n,(3),Y,X,1,x,0,x,1,x,n-1,x,n,x,i+1,x,i,x,i-1,Y,X,1,x,0,x,1,x,2,x,n-1,x,n,2024/12/3 周二,76,.,2.5,分段低次插值,Chapter2,插值法,分段线性插值基函数,l,i,(x,),只在,x,i,附近不为零，在其他地方均为零，这种性质称为,局部非零性质,。,在区间,x,k,x,k+1,上，只有,l,k,(x),l,k+1,(x),是非零的，其它,基函数均为零，即,因此：表达式,与表达式,是相同的。,2024/12/3 周二,77,.,2.5,分段低次插值,Chapter2,插值法,-(1),-(2),显然,我们称由,(1)(2),式构成的插值多项式 为,分段线性,Lagrange,插值多项式,2024/12/3 周二,78,.,2.5,分段低次插值,Chapter2,插值法,内插,外插,外插,2024/12/3 周二,79,.,2.5,分段低次插值,Chapter2,插值法,例,:,已知函数,在区间,0,5,上取等距插值节点（如下表），,并利用它求出 的近似值。,0.03846,0.05882,0.1,0.2,0.5,1,y,i,5,4,3,2,1,0,x,i,解：在每个分段区间,上，,2024/12/3 周二,80,.,2.5,分段低次插值,Chapter2,插值法,分段线性插值的误差估计,根据拉格朗日一次插值函数的余项,可以得到分段线性插值函数的插值误差估计。,定理：设,f,(x,),在,a,b,上有二阶连续导数,f,(x,),，且,|,f,(x,)|M,2,记,h=max|x,i+1,-x,i,|,就有估计：,证明：,n,次,Lagrange,插值多项式的余项为,2024/12/3 周二,81,.,2.5,分段低次插值,Chapter2,插值法,分段线性插值的误差估计,2024/12/3 周二,82,.,收敛性证明：,2.5,分段低次插值,Chapter2,插值法,当,x x,k,x,k+1,时,另一方面，这时,现在证明,考虑：,这里,(,h,),是函数,f,(,x,),在区间,a,b,上的连续模，,即对任意,两点,x,，,x,a,b,，只要,|x,x,|,h,，就有,称,(,h,),为,f,(,x,),在,a,b,上的连续模，当,f,(,x,),C,a,b,时，就有,2024/12/3 周二,83,.,2.5,分段低次插值,Chapter2,插值法,由前式可知，当,x,a,b,时有,收敛性证明：,因此，只要,f,(,x,),C,a,b,，就有,在,a,b,上一致成立，故,I,h,(,x,),在,a,b,上一致收敛到,f,(,x,),。,2024/12/3 周二,84,.,2.5,分段低次插值,Chapter2,插值法,例：设,-1,x 1,(1),将,-1,，,1 10,等份，用分段线性插值近似计算,f(-0.96),。,(2),将,-1,，,1 n,等份，用分段线性插值近似计算,问如何选择步长,h,可使近似计算误差,R10,-4,?,解：,(1),插值节点为,x,i,=-1+i/5 (i=0,1,10),h=1/5,因为,-0.96-1,-0.8,取此区间为线性插值区间，其上的插值函数为,所以,f(-0.96),I,h,(-0.96)=0.04253,2024/12/3 周二,85,.,2.5,分段低次插值,Chapter2,插值法,(2),插值节点为,x,i,=-1+ih (i=0,1,n),h=(b-a)/n,=2/n,由分段线性插值的余项估计：,|,f,(x,)-,I,h,(x)|=|R(x,)|M,2,h,2,/8,2024/12/3 周二,86,.,2.6,三次样条