数值分析-第二章-插值ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章,插值法,1,引 言,一,、,引例,已经测得在某处海洋不同深度处的水温如下：,深度（,M,）,466 741 950 1422 1634,水温（,o,C,）,7.04 4.28 3.40 2.54 2.13,根据这些数据，希望合理地估计出其它深度（如,500,米，,600,米，,1000,米,）处的水温,.,这就是本章要讨论的“插值问题”,插值法是一种古老的数学方法。早在,1000,多年前，我国历法上已经记载了应用一次插值和二次插值的实例。,伟大的数学家：拉格朗日（,Lagrange,）、牛顿,Newton,）、埃尔米特（,Hermite,）等人分别给出了不同的解决方法。,二,、插值问题的定义,这个问题称为,“插值问题”,(2.1.1),这里,g,(,x,),称为,f,(,x,),的,插值函数,;,节点 称为,插值节点,;,条件,(2.1.1),称为,插值条件,;,区间 称为,插值区间,。,如果利用,g,(,x,),来求,f,(,x,),在,y,点的近似值，则称,y,为,插值点。,由此构造一个简单易算的近似函数,g,(,x,),f,(,x,),，满足条件,上一系列节点,处测得函数值,当函数,y,=,f,(,x,),非常复杂或未知时，设在区间,定义,2.,1,插值函数的类型有很多种,最常用的插值函数是,代数多项式。,用代数多项式作插值函数的插值称为,代数插值,，即,选取次数不超过,n,的多项式,P,n,(x),，,使得,代数插值,一、,插值多项式的存在唯一性？,二、,插值多项式的常用构造方法？,三、,插值多项式,的误差如何估计？,(2.1.2),一、插值多项式的存在唯一性,设所要构造的插值多项式为：,由插值条件,得到如下线性代数方程组,：,（,2.2.1,）,2,一般多项式,插 值,此方程组的系数行列式为,当,时,，,D,0,，,因此，,P,n,(,x,),由,a,0,a,1,a,n,唯一确定。,范得蒙行列式的转置！,定理,2.1,插值条件 的,n,阶插值,多项式,P,n,(,x,),存在且唯一。,插值多项式的构造：,插值多项式的存在唯一性说明，满足插值条件的,多项式存在，并且插值多项式,与构造方法无关,。,如何,构造,插值函数才能达到预期的效果呢？,对于给定的互异,节点,x,0,x,n,满足,，,用于插值的简单函数元素集,+,线性组合结构 插值多项式,简单函数元素集是指构成多项式的基函数集合，例如,自然形式（,2.2.1,）的自然基底,、,、,(,结构,),(,集合,),若求自然形式,(2.2.1),的插值多项式问题，只要求,解线性方程组（,2.2.2,）计算出多项式系数即可。,一般插值多项式的构造方法,通过解方程组,(2.2.2),求得插值多项式 的方法,并不可取,.,这是因为当,n,较大时解方程组的计算量,较大，而且方程组系数矩阵的条件数一般较大,（可能,是,病态方程组,）,当阶数,n,越,高时，,病态越重,。,怎样可以不通过求解方程组而获得插值多项式呢,?,在,n,次多项式空间,P,n,中找一组合适的基函数,使,不同的基函数的选取导致不同的,插值方法,.,Lagrange,插值,Newton,插值,Hermite,插值,1,n,次,拉格朗日插值多项式,设连续函数,在 上对给定的 个不同节点,上分别取函数值,试构造一个次数不超过,n,的插值多项式,使之满足插值条件,:,二、拉格朗日,(Lagrange),插值,定义,2.,2,若,n,次多项式 在 个节点,上满足条件,由定理,2.1,得：,则称这 个 次多项式 为节点,上的 次插值基函数。,因此，令,的表达式推导：,根据 的定义,，,以外所有的结点都是,的根,，,又由,，,得,：,2,线性插值,(n=1),x,k,x,k+1,(x,k,y,k,),(x,k+1,y,k+1,),f(x),P,1,(x),3,抛物插值,(n=2),p,2,(,x,),f,(,x,),x,k-1,x,k,x,k+1,f,(,x,),因过三点的二次曲线为抛物线，故称为,抛物插值,。,注,：,（,1,）,次数 。,（,2,）记 ，,则 ，,所以,4,、插值余项,定理,2.2,设 在,a,b,上连续， 在（,a,b,）内存在,则在,a,b,上的,n+,1,个互异的节点,，对,所作的,n,次,Lagrange,插值多项式 有误差估计,Rolles Theorem,的推论,:,若 充分光滑，且,存在,使得,构造,(,固定,),由,Roll,定理,知存在,证明,:,当,f,(,x,),为任一个次数,n,的多项式 时， ，可知,，即插值多项式对于次数,n,的,多项式是,精确,的。,插值多项式一般仅用来估计插值区间内点的函数值（即内,插），用它来计算插值区间外点的函数值（即外插）时，,误差可能很大。,注：,通常不能确定,而是估计 ，,x,(,a,b,),，,将 作为误差估计上限。通常取 。,也称为,Lagrange,插值多项式的插值余项,。,当,n,= 1,时，,当,n,= 2,时，,例：,已知,分别利用,1,次、,2,次,Lagrange,插值计算,sin 50,，,并估计误差。,解：,n,= 1,分别利用,x,0,x,1,以及,x,1,x,2,计算,利用,利用,计算得：,sin 50,0.76008,利用,x,0,x,1,作为插值节点的实际误差, ,0.01001,利用,x,1,x,2,作为插值节点的实际误差,0.00596,sin 50, = 0.7660444,n,= 2,2,次插值的实际误差,0.00061,三、牛顿插值,（,Newton,s Interpolation,）,Lagrange,插值虽然易算，但若要增加一个节点时，,全部,基函数,l,i,(,x,),都需要重新计算。,希望每加一个节点时，,只附加一项,上去即可,。,能否重新在,中寻找新的,基函数,？,回顾：,Lagrange,插值的优缺点：,优点：,具有严格的规律性,便于记忆。,缺点：,计算量大、不具有承袭性。,利用插值条件 代入上式，得关于,的线性代数方程组,:,设,当,互异时，系数矩阵非奇异，且容易求解,1,差商及其性质,(1),差商的定义,(,亦称均差,),定义,2.3,设已知函数,f,(,x,),在互不相等的节点,上的函数值为,，,称,为,f,(,x,),在点,x,i,x,j,处的,一阶差商,，,记作,f,x,i,x,j,；,称,为,f,(,x,),在点,x,i,x,j,x,k,处的,二阶差商,，记作,f,x,i,x,j,x,k,；,称,为,f,(,x,),在点,x,0,x,1, x,k,处的,k,阶差商,，记作,f,x,0,x,1, x,k,。,由差商定义知,高阶差商是两个低一阶差商的差商,(2),差商的性质,性质,1,(,差商与函数值的关系,),:,记,则,性质,2,（对称性）,：,差商的值与结点排列顺序无关，即,性质,3,(,差商与导数的关系,),:,设 在 上有 阶导数,且,则存在 使得,性质,4,(,特征定理,),:,差商可列表计算：,f,(,x,0,),f,(,x,1,),f,(,x,2,),f,(,x,n,1,),f,(,x,n,),f,x,0,x,1,f,x,1,x,2, , ,f,x,n,1,x,n,f,x,0,x,1,x,2, , ,f,x,n,2,x,n,1,x,n,f,x,0,x,n,x,i,y,i,一阶差商,二阶差商,n,阶差商, ,x,0,x,1,x,2,x,n-1,x,n,x,n+1,f,(,x,n,+1,),f,x,n,x,n,+1,f,x,n,1,x,n,x,n,+1,f,x,1,x,n,+1,f,x,0,x,n,+1,(3),差商的计算,利用差商的定义,可得,的,系数,:,从而,因此每增加一个结点，,Newton,插值多项式只增加一项，克服了,Lagrange,插值的缺点。,2.,牛顿插值公式,3.,牛顿插值余项,由插值多项式的,唯一性可知 ，,故其余项也相同，即,命题,Newton,插值多项式的余项为,其中,从而，,例,:,给定 的数据表,2.20 2.40 2.60 2.80 3.00,0.78846 0.87547 0.95551 1.02962 1.09861,1.,构造差商表,2.,分别写出二次、四次,Newton,插值多项式,解,:,构造差商表,一阶差商 二阶差商 三阶差商 四阶差商,余项,四、等距节点插值,引入,(,微商的离散化,),：,1,差分的定义,设函数 在等距节点 上的,值 已知,这里 为常数,称为,步长,，分别称,为 在 处以 为步长的,一阶向前差分,一阶,向后差分,以及,一阶,中心差分。,高阶差分：,定义,2.4,引进不变算子 ，移位算子 ，即,则有,2,、差分表（差分计算）,计算各阶向前差分可按如下差分表进行：,计算各阶向后差分可按如下差分表进行：,3,、差分的性质,性质,1,(,差分与函数值的关系,),:,各阶差分均可表示为函数值,的线性组合,:,其中,性质,2,(,向前差分与向后差分的关系,),:,性质,3,(,差分与差商的关系,),:,在等距节点的前提下，,性质,4,(,差分与导数的关系）,：,在等距节点的前提下，,性质,5,：,常数的差分等于零,.,性质,6,：,差分算子为线性算子，即,性质,7,：,这个性质类比于,4,、等距节点的牛顿插值公式,牛顿公式,:,牛顿前插公式,（用于计算最小节点附近的函数值,）,利用差分的性质,可将,Newton,公式简化为,(1),称公式,(1),为,Newton,向前差分插值公式,其余项为,(2),牛顿后插公式,（用于计算最大节点附近的函数值）,如果将,Newton,插值公式,改为按节点 的,次序排列的,Newton,插值公式,即,(3),令,x,=,x,n,-,th,则当,x,n-1,x,x,n,时,0,t,1.,利用差商与向后差分的关系,式,(3),可简化为,(4),称式,(4),为,Newton,向后差分插值公式,。,其余项为,注：,一般当,x,靠近,x,0,时用前插，靠近,x,n,时用后插，故两种公式亦称为,表初公式,和,表末公式,。,例,给定,f,(,x,),在等距节点上的函数值表如下,:,x,i,0.4 0.6 0.8 1.0,f,(,x,i,) 1.5 1.8 2.2 2.8,分别用,Newton,向前和向后公式求,f,(0.5),及,f,(0.9),的近似值,.,解,先构造向前差分表如下,:,x,i,f,i,f,i,2,f,i,3,f,i,0.4 1.5 0.3 0.1 0.1,0.6 1.8 0.4 0.2,0.8 2.2 0.6,1.0 2.8,x,0,=0.4,h,=0.2,x,3,=1.0.,分别用差分表中第一行上的值和对角线的值,得,Newton,向前和向后插值公式如下,:,(1),(2),当,x,=0.5,时,用公式,(1),这时,t,=(,x,-,x,0,)/,h,=0.5.,将,t,=0.5,代入,(1),得,f,(0.5)N,3,(0.5)=1.64375.,当,x,=0.9,时,用公式,(2),这时,t=(,x,3,-,x,)/,h,=0.5.,将,t,=0.5,代入,(2),得,f,(0.9)N,3,(0.9)=2.46875.,1,引入,在实际问题中，对所构造的插值多项式，,不仅,要求函数值重合，而且要求若干阶,导数,也重合。,即要求插值函数,P,(,x,),满足,:,（,1,）,把此类插值问题称为,相应的插值多项式称为,埃米尔特（,Hermite,）插,值多项式或称带导数的插值多项式，,记为,H,(,x,),。,H,(,x,),存在且唯一。,埃米尔特（,Hermite,）插值,3,Hermite,插值,2.,推导,只讨论函数值与导数值个数相等，且一阶情况。,设在节点 上,要求插值多项式,满足条件,(2),这里给出的 个条件,可唯一确定一个次数不超,过 的多项式 其形式为,根据条件,(2),来确定 个系数,显然非常复杂。,(3),插值基函数 及,共有 个,每一个基函数都是 次多项式,且满足条件,(Lagrange,型,Hermite,插值多项式,):,基函数方法,(3),于是满足条件,(2),的插值多项式 可写成用插值,基函数表示的形式,即,显然有,(4),下面利用,Lagrange,插值基函数 求 及 。,令,其中 是,由条件式,(3),有,整理,得,解得,由于,两端取对数再求导,得,于是,(5),同理可得,(6),（,1,）仿照,Lagrange,插值余项，,Hermite,插值余项可描述为：,(7),注：,设 在,a,b,上连续， 在（,a,b,）内存在,则,且依赖于 ，有插值余项,（,2,）,作为带导数插值多项式,(4),的重要特例是,n=1,的情形。,这时可取节点为 及,插值多项式为,满足条件：,(8),相应的插值基函数为,它们满足：,根据,(5),式及,(6),式的一般表达式,可得,于是满足条件,(8),的插值多项式是,其余项为,（,3,）,N,个条件可以确定,N-1,阶多项式，要求在,1,个节点 处直 到,阶导数都重合的插值多项式即为 在 点处的,Taylor,多项式,:,其余项为,Newton,型,Hermite,插值,（,1,）单节点的重节点差商,（,2,）多节点的重节点差商,插值条件：,重节点差商可列表计算：,重节点差商的计算,其中,，,例,1,：,已知,求三次多项式,P,(,x,),满足,4.,举例,解：,例,2,：,已知,求三次多项式,P,(,x,),满足,注意,:,解：,1.,多项式插值的龙格现象,例：,在,5, 5,上考察 的,L,n,(,x,),。取,-,5,-,4,-,3,-,2,-,1,0,1,2,3,4,5,-,0.5,0,0.5,1,1.5,2,2.5,L,n,(,x,),f,(,x,),n,越大，,端点附近抖动,越大，称为,Runge,现象,4,分段低次插值,2.,分段线性插值,在每个子区间 上，用,1,次多项式,(,直线,),逼近,f,(,x,):,记,易证：当 时，,一致,y,x,o,y=p(x),y= f(x),失去了原函数,的光滑性。,则 是分段一次的连续函数且满足条件,分段线性插值多项式的构造：,即为分段线性插值的基函数。,基函数 只在 附近不为零,在其它地方均为零。这种性质称为,局部非零性质,。相应的分段线性插值函数为：,分段线性插值的误差估计：,如果 在 上二阶连续可微,则分段线性,插值函数 的余项有以下估计,其中,3.,分段三次,Hermite,插值,其中基函数为,给定节点 ， 在节点 上的,函数值及导数值分别为,在每个子区间,上作两点三次,Hermite,插值，因此是分段三次，总,体是直至一阶导数连续，插值函数为,分段,Hermite,插值余项,:,由三次,Hermite,插值的余项可以估计分段,Hermite,插值的余项：设,是给定节点,上的分段三次,Hermite,插值函数， ， 与 的误差限为,其中，,要求：,插值曲线既要简单，又要在曲线的连接处比较光滑。,这样的分段插值函数在分段上要求多项式次数低，,这种插值方法称为,样条插值,。,它所对应的曲线称为,样条曲线,，其节点称为,样点,，,把满足这样条件的插值函数，称为,样条插值函数,，,而在节点上不仅连续，还存在连续的低阶导数，,图,2.1,早期机翼下轮廓的放样,如图,2.1,所示，在早期的板材曲线切割时，常把富有弹性的细长木条（样条）固定在样点上，其它地方让其自由弯曲，然后画出长条的曲线称为样条曲线，由此启发设计整体连续光滑的样条插值函数。,问 题,分段低次插值虽然具有简单、收敛性、整体连续性及数值计算的稳定性等优点，但在节点处常有,“,尖点,”,出现，光滑性较差。特别是需要给出节点处的导数值，这在多数问题中是不实际的。如何在没有节点导数数据时也能达到上述目的？为此引入样条插值函数,。,1.,引入,5,三次样条插值,定义,2.5,设对,y = f,(,x,),在区间,a, b,上给定一组节点,a = x,0,x,1,x,2,x,n,= b,和相应的函数值,y,0,y,1,y,n,，,如果,s,(,x,),具有如下性质：,（,1,）,在每个子区间,x,i-,1,x,i, (,i,= 1, 2,n,),上,s,(,x,),是不高,于三次的多项式,;,（,2,）,s,(,x,),， ，,s,(,x,),在,a, b,上连续；则称,s,(,x,),为,三次样条函数,.,如再有,（,3,）,s,(,x,i,),= f,(,x,i,) (,i,= 0, 1, 2,n,),，,则称,s,(,x,),为,y = f,(,x,),的,三次样条,插值函数,。,注：,三次样条与分段,Hermite,插值的根本区别在于,S,(,x,),自身光滑,，,不需要知道,f,的导数值（除了在,2,个端点可能需要）；而,Hermite,插值依赖于,f,在所有插值点的导数值。,S,(,x,),H,(,x,),f,(,x,),给定函数 在,a, b,上的一组节点：,及节点上的函数值,，,函数 是满足下列条件的函数：,的三次样条插值,；,2.,三次样条插值函数的构造,(3),在插值节点处连续，即,(4),即,(1),(2),在子区间,上是三次多项式，记为,。,要保证,S(x),的存在唯一性，必须附加两个边界条件。例如，满足下列四种,边界条件,中的任意一个：,(1),固支边界条件（,D1-,样条）：,3.,边界条件,(2),弯矩边界条件（,D2-,样条）：,(3),自然边界条件（自然样条）：,(4),周期边界条件,（周期样条）,：,上述几种边界条件都有它们的实际意义，从力学角度看，附加边界条件相当于在细梁两端加上约束。工程中常用自然边界条件求样条插值函数，这类插值函数称为自然样条函数，利用插值条件和连续线性条件列出线性方程组并求解，是一种构造样条的基本方法。,构造思想,:,通过构造含待定参数的分段三次,Hermite,插值多项式来构造三次样条插值函数。,构造,Hermite,插值多项式需要知道被逼近函数,f(x),的导数，而导数通常是不知道的。,三次样条插值函数的构造则不需要知道,f(x),的导数值，直接将其作为待定参数，利用各节点在连接处的光滑性与连续性条件，建立关系式来确定待定参数，从而构造插值多项式。,4.,三弯矩方程,设,f,(,x,),是定义在,a, b,区间上的一个二次连续可微函数,，,令,在每一个小区间,上都是三次多项式。,S,(,x,),在 上的表达式为：,（,1,）,(,注意,:,未知,),其中,，,将（,1,）两次积分得,：,A,i,和,B,i,为积分常数。,因为,所以它满足方程：,求得,（,2,）,同理求得,:,（,3,）,求,M,i,确定,S,(,x,),的表达式,。,由（,2,）,式得,由,得,（,4,）,则,（,5,）,可以写为,记,整理得,（,5,）,（,6,）,（,1,）,D1-,样条：,给定两端点导数值,有,分别补充为方程组,（,6,）,的第一个和最后一个方程组，得,D1-,样条的三弯矩方程为：,（,2,）,D2-,样条：,给定边界条件,（,6,）中第一个方程变为：,（,6,）中最后一个方程变为：,得三弯矩方程,若取,M,0,= M,n,=0,，称为,三次自然样条，,三弯矩方程为,（,3,）周期样条：,给定条件,:,， 得,由,整理得,整理得,令,则,补充（,6,）中的最后及第一个方程，可得周期样条的三弯矩方程：,上述第一个方程化为,所以周期样条三弯矩方程为,5,、三次样条插值的计算步骤,(1),根据已知条件顺次计算方程组系数,，,求出三次样条插值的三弯矩方程组；,(2),由给定边界条件，确定,；,(3),求解对应边界条件下的三弯矩方程组，,求出,；,(4),将求出的,代入,(2),式，求出,上的三次样条,插值函数,对给定的点,，,须首先确定 所在的子区间 ，,然后按三次样条插值的计算步骤计算,，,进而求出,6.,三次样条插值函数的收敛性,定义,2.6,设 是区间 上的连续函数，记,为函数 的范数。,定理,2.3,设被插值函数 为满足边,界条件的,3,次样条插值函数，则在插值区,间 上成立余项估计式,其中,其次求,:,得方程组,:,得,:,历史与注记,1756,年，拉格朗日被任命为普鲁士科学院通讯院士。,1766,年任普鲁士科学院数学部主任。,1786,年出任法国米制委员会主任。,1795,年拉格朗日被选为法兰西研究院科学院数理委员会主席。,1813,年,4,月,3,日，拿破仑授予他帝国大十字勋章,。,拉格朗日在数学上最突出的贡献是使数学分析与几何与力学脱离开来，使数学的独立性更为清楚。他在数值计算上的主要贡献是发展了欧拉所开创的变分法，为变分法奠定了理论基础。近百余年来，数学领域的许多新成就都可以直接或间接地溯源于拉格朗日的工作，在数学史上被认为是对数学的发展产生全面影响的数学家之一。,拉格朗日,(,Joseph-Louis Lagrange,，,1736,1813),拉格朗日,1736,年生于,意大利,都灵,，,1813,年卒于,巴黎,。,在近代，插值法是观测数据处理和函数制表所常用的工具，又是导出其它许多 数值方法（如数值积分、非线性方程求根、微分方程数值解等）的依据。插值法的一般参考资料见文献,1,2,，关于样条的一篇有重要影响的论文参见文献,3,。,插值一词最早是由,Wallis,提出的，公元,6,世纪，中国刘焯已将等距二次插值用于天文计算。,17,世纪，牛顿和格雷果里建立了等距节点上的插值公式。,18,世纪，拉格朗日给出了更一般的非等距节点上的插值公式。,1946,年, Schoenberg,首先提出了样条插值函数。,1 P. J. Davies. The Finite Element Method: A First,Approach. Oxford University Press, New York, 1980.,2 M. J. D. Powell. Approximation Theory and,Methods.Cambridge University Press, New York, 1981.,3 I. J. Schoenberg. Contributions to the problem of,approximation of equidistant data by analytic functions.,Quarterly of Applied Mathematics 4, 1946.,参考文献,