插值方法基本思想.ppt

Computational Methods,西南交通大学峨眉校区基础课部 数学教研室,2010,年,插 值 法 基 本 思 路,张兴元,2011,年,8,月,一元多项式插值,教学内容,插值问题,插值问题求解方法（重点）,线性插值,二次插值,n,次插值,分段线性插值,Hermite,插值,分段三次,Hermite,插值,样条插值函数（难点）,要求,掌握以上方法的原理及其在,MATLAB,中的实现方法,插值问题,1.,提法,已知,n+1,个节点,(,x,j,y,j,),，,j=0,1,，,n,，其中,x,j,互不相同，不妨设,a=x,0,x,1,x,n,=b,，求任一插值点,x*(,xj,),处的插值,y*,。,(,x,j,，,y,j,),可以看成是由某个函数,y=,g(x,),产生的，,g,的解析表达式可能十分复杂，或不存在封闭形式，也可以未知。,2,、求解的基本思路,构造一个相对简单的函数,y=,f(x,),，使,f(x,),通过全部节点，即,f(x,j,)=,y,j,（,j=0,1,n,），再用,f(x,),计算插值，即,y*=,f(x,*),。,f(x,),称为,插值函数,。,如果,f(x,),为,k,次多项式，,f(x,),就是插值多项式，此时插值为,代数插值,；,如果,f(x,),为有理函数，就是,有理插值,；,如果,f(x,),为三角函数，则为,三角插值,。,多项式插值,线性插值,x,x,0,x,1,y,y,0,y,1,y=,f,(,x,),函数表,一次函数,通过两个不同的插值点,线性插值,-,两点式方程,Lagrange,插值：,是,l,0,(,x,),和,l,1,(,x,),的线性组合,基函数：,线性插值,-,点斜式方程,均差：,Newton,插值：,一阶均差的一般定义：,线性插值,-,余项,？两种不同的构造方式（,Lagrange,和,Newton,）效果一样吗？,此处一样！,？两种不同的构造方式（,Lagrange,和,Newton,）可以推广到多个点吗？,可以！,多项式插值,-,二次插值,x,x,0,x,1,x,2,y,y,0,y,1,y,2,一次函数,通过三个不同的插值点,y=,f,(,x,),函数表,二次插值,-Lagrange,基函数方法,Lagrange,插值：,二次插值,-Newton,均差法,二阶均差：,Newton,插值：,二次插值,-,余项,【,例,1】,已知,，试利用插值法近似计算 。,【,解,】,有几位有效数字？,多项式插值,-n,次插值,x,x,0,x,1,x,n,y,y,0,y,1,y,n,y=,f,(,x,),函数表,(,x,i,互不相同,),存在吗？,唯一吗？,如何构造？,n,次插值,-,存在性、唯一性,记,A=(a,n,，,a,n-1,，,，,a,0,),T,，,Y=(y,0,，,y,1,，,，,y,n,),T,存在且唯一！,x,x,0,x,1,x,n,y,y,0,y,1,y,n,n,次插值,-,插值多项式的构造,方法一：,Lagrange,型插值多项式,基函数：,基函数的特点：,Lagrange,插值多项式,n,次插值,-,插值多项式的构造,方法二：,Newton,型插值多项式,均差表,或,差商表,Newton,插值多项式：,n,次插值,-,插值余项与事后误差估计,插值余项,其中,事后误差估计方法,x,x,0,x,1,x,n,x,n+1,y,y,0,y,1,y,n,y,n+1,误 差,n,次插值,-,示例,【,例,2】,基于,5,个点（,k,cos(k,),），,k=0,1,2,3,4,，,1),构造,f(x,)=,cos(x,),的差商表；,(2),并用差商表找出牛顿插值多项式的系数,；,(3),写出四次牛顿插值多项式,N,4,(x),；,(4),计算,N,4,(2.5),。,【,解,】,第一步，明确插值点,(,x,k,y,k,),；,第二步，构造差商表；,第三步，写出相应的牛顿插值多项式,N,4,(x),；,第四步，计算近似值,N,4,(2.5),。,多项式插值的震荡性质,用,Lagrange,插值多项式,L,N,(x,),近似,f(x)(a,xb,),，,虽然随着节点个数的增加，,L,N,(x,),的次数,N,更大，多数情况下误差,|,R,N,(x,)|,会变小。但是,N增加时，,L,N,(x,),的光滑性变坏，有时会出现很大的震荡。理论上，当,N,时，在,a,，,b,内并不能保证,L,N,(x,),处处收敛于,f(x),。,Runge,给出了一个有名的例子：,多项式插值的震荡性质,Runge,给出了一个有名的例子：,取,x,j,=-5+10j/N,，,j=0,，,1,，,，,N,。对于,N=2,，,4,，,6,，,作,L,n,(x,),，,会得到如下图所示的结果。可以看出，对于较大的,|x|,，,随着,N,的增大，,L,N,(x,),振荡起来越大。事实上，有人证明了,仅当,|x|3.63,时，才有,而在此区间外，,L,N,(x,),是发散的。,多项式插值的震荡性质,高次插值多项式的这些缺陷，促使人们转而寻求简单的低次多项式插值。,多项式插值,-,分段线性插值,x,x,0,x,1,x,n,y,y,0,y,1,y,n,是线性函数,多项式插值,-,分段线性插值,分段线性插值函数为：,余项估计为：,多项式插值,-,分段线性插值,分段线性插值多项式,L,1,(x),的图像,上是连接各插值点的一条折线,如右图,:y=,sin(x,),的插值逼近图形变化。,特点：,曲线的光滑性较差,在节点处有尖点,增加节点，减小步长，会改善效果。,若,f(x,),在,a,b,上连续，则,多项式插值,-,Hermite,插值,考虑只有两个节点的插值问题,如何选择基函数,多项式插值,-,Hermite,插值,希望插值系数与,Lagrange,插值一样简单，假设,其中,多项式插值,-,Hermite,插值,可知,由,可得,Lagrange,插值基函数,类似可得,即,将以上结果代入,多项式插值,-,Hermite,插值,多项式插值,-,Hermite,插值,得两个节点的三次,Hermite,插值公式,多项式插值,-,Hermite,插值的插值余项,两点三次,Hermite,插值的余项为,【,例,3】,多项式插值,-,Hermite,插值的插值余项,【,解,】:,作为多项式插值,三次已是较高的次数，次数再高就有可能发生,Runge,现象,因此，对有,n+1,节点的插值问题我们可以使用分段两点三次,Hermite,插值,。,多项式插值,-,Hermite,插值的插值余项,多项式插值,-,分段三次,Hermite,插值,可构造两点三次,Hermite,插值多项式,多项式插值,-,分段三次,Hermite,插值,其中,分段三次,Hermite,插值多项式，,余项为,多项式插值,-,样条函数插值,分段插值的思想及优缺点,1,、思想：,将图形分段，每段为一个低阶多项式,S,k,(x,),，并在相邻点之间进行多项式插值，组成一个分段的多项式曲线。,2,、分类：,（,1,）、分段线性插值,优点：简单；,缺点：连续但不光滑，曲率不连续变化。,（,2,）、分段二次多项式插值,优点：简单；,缺点：偶数点,x,2k,处曲率变化很大，曲率不连续变化。,3,、改进方法：,利用分段三次样条插值：分段三次多项式，连续，光滑，曲率连续变化，多项式的次数较低。,多项式插值,-,样条函数插值,什么是样条,:,是 指飞机或轮船等的制造过程中为描绘,出光滑的外形曲线,(,放样,),所用的工具,样条本质上是一段一段的三次多项式拼合而成的曲线,在拼接处,不仅函数是连续的,且一阶和二阶导数也是连续的,1946,年,Schoenberg,将样条引入数学,即所谓的样条函数,多项式插值,-,样条函数插值,1.,三次样条插值函数的定义,多项式插值,-,样条函数插值,2.,确定三次样条插值函数的条件,多项式插值,-,样条函数插值,多项式插值,-,样条函数插值,3.,三次样条插值函数的构造方法,3.1,用节点处一阶导数表示的三次样条插值函数,多项式插值,-,样条函数插值,多项式插值,-,样条函数插值,多项式插值,-,样条函数插值,整理后，得到,引入记号,则有方程组,多项式插值,-,样条函数插值,该方程组为三对角方程组，可以利用追赶法求解。,多项式插值,-,样条函数插值,多项式插值,-,样条函数插值,多项式插值,-,样条函数插值,3.2,用节点处二阶导数表示的三次样条插值函数,多项式插值,-,样条函数插值,多项式插值,-,样条函数插值,其中,多项式插值,-,样条函数插值,多项式插值,-,样条函数插值,（,1,）压紧样条,多项式插值,-,样条函数插值,（,2,）自然样条,多项式插值,-,样条函数插值,二元插值,依据数据的规则与否，常见可分为规则数据和散乱数据插值。,