计算方法 分段线性-三次样条插值

第3次分段线性插值与三次样条插值,计算方法(NumericalAnalysis),内容,高次插值的龙格现象分段线性插值与误差估计三次样条插值与误差估计,高次插值的龙格现象,2.4.1高次插值的龙格现象插值多项式余项公式,例：设函数f(x)定义在区间0,1上，并且满足|f(4)(x)|1，x0,1。在4个插值节点x0=0,x1=1/3,x2=2/3,x3=1,对f(x)进行插值得多项式P3(x)，估计误差。,下面讨论误差的情况：,但是当区间a,b比较大的时候，误差可能很大。,适当提高插值多项式的次数，有可能提高计算结果的准确程度，但并非次数越高越好。当插值节点增多时，也不能绝对保证非节点处的插值精度得到改善，有时反而误差更大。,影响误差的因素：一般地说插值节点的个数：插值节点越多，即使用高次插值，误差越小f(x)的高阶导数绝对值：越小，误差越小,考察函数,右图给出了和的图像,当n增大时,在两端会发生激烈的振荡，称为龙格现象。,该现象表明：在大范围内使用高次插值,逼近的效果往往是不理想的。,另外，从舍入误差来看，高次插值误差的传播也较为严重，一个节点上产生的舍入误差会在计算中不断放大，并传播到其它节点上。因此，次数太高的高次插值多项式往往并不实用，因为节点数增加时，计算量增大了，但插值函数的精度未必能够提高。称为龙格现象。,Home,分段线性插值与误差估计,为克服龙格现象，可以采用分段插值的方法：将插值区间分成若干个小的区间，在每个小区间进行线性插值，然后相互连接，用连接相邻节点的折线逼近被插函数,而不是在整个区间a,b上做线性插值。,2.4.2分段线性插值,设f(x)在n+1个节点上的函数值为。,上作线性插值，得,在每个小区间,y=f(x),y=p(x),x1,x2,x0,xn,x,y,在几何上就是用折线替代曲线,如图所示。,例2.19已知f(x)在四个节点上的函数表如下：,求f(x)在区间30,90上的分段连续线性插值函数S(x)。,解：将插值区间30,90分成连续的三个小区间,30,45,45,60,60,90,S(x)在区间45,60上的线性插值为：,S(x)在区间60,90上的线性插值为：,则S(x)在区间30,45上的线性插值为：,将各小区间的线性插值函数连接在一起，得,30,x,y,60,90,45,1,0.5,0.87,0.7,连续但不光滑,y=S(x),解：在0,1上（课堂练习）,将这些分段线性函数拼接在一起，得：,分段线性插值的误差估计（仅对充分光滑的f(x)成立）,定理设f(x)在a,b有2阶导数，则在a,b上的分段线性插值S(x)，的截断误差满足：,其中：,由此，即得结论。,证明：,练习：给出本题的S(x)在0,5上的误差估计。,现在对f(x)的2阶导数进行估计。,Home,x,y,1,2,3,4,5,y=S(x)：分段线性函数,综上可得,现象：在0,1上逼近效果最差，在其它区间，逐渐变好。,三次样条插值与误差估计,在船体、飞机等外形曲线的设计中,不仅要求曲线连续,而且要有二阶光滑度,即有连续的二阶导数。要求分段插值函数在整个区间上具有连续的二阶导数。因此有必要寻求一种新的插值方法,这就是样条函数插值法,2.5.1三次样条函数,样条函数来历,定义5.4.设函数f(x)定义在区间a,b上，在给定的n+1个节点xi,(i=0,n)上的函数值为f(xi)。,若存在函数S(x)，满足:在每个小区间xi,xi+1(i=0,1,n-1)上是一个三次多项式（注意：一共是n个区间）。在每个节点上满足S(xi)=f(xi)(i=0,1,n)在a,b上有连续的二阶导数（隐含：,三次样条函数插值比线性插值要求严苛得多！,则称S(x)为三次样条插值函数。,在a,b上连续),x,y,回答：不是。原因：1）在每个区间内都是3次多项式；2）在小区区间端点xi处连续并且：f(xi)=S(xi)；3）S”(x)在xi点不连续，即不光滑。,y=S(x)（蓝色）,问题：这个S(x)是三次样条插值函数吗？,y=f(x)(黑色),x0,xi,xi+1,xn,x,y,S(x)是三次样条插值函数：在每个区间内都是3次多项式，在小区区间端点处连续、光滑。,y=S(x),S(xi)=f(xi)(i=0,1,2,3),y=f(x),S(x)是分段3次多项式，在每个小区间xi,xi+1上要确定4个待定参数。用Si(x)表示在xi,xi+1上的表达式：,确定多项式的系数,分析：待定系数：，n个子区间，要确定S(x)，需要确定4n个待定系数。,1）要求S(xi)=f(xi),i=0,1,n,已知：,能产生多少个方程？,1）插值条件(n+1个节点),满足条件：,2）连接条件(3n-3个节点),上述二式共给出了4n-2个条件,而待定系数有4n个,因此还需要2个条件才能确定S(x)。,x,x0,x2,x5,x1,x4,x3,x6,类型1：给定两端点f(x)的一阶导数值：,常用边界条件的三种类型(略去了第3种),类型2：给定两端点f(x)的二阶导数值：,通常在区间端点上各加一个条件,称为边界条件。,特别地,称为自然边界条件。满足自然边界条件的三次样条插值函数称为自然样条插值函数。,这样，由上给定的任一种边界条件加上插值条件和连接条件，则得出4n个方程，可以唯一确定4n个系数。从而得到三次样条插值函数S(x)在各个子区间xi,xi+1上的表达式S(xi）(i=1,2,)。但是，这种做法当n较大时，计算工作量很大，不便于实际应用。希望找到一种方便计算机计算简单的构造方法-显式方法。,2.5.2三次样条插值函数的求法,记：,经推导(略)，得到如右的在每个小区间上的三次样条插值函数的显式表达式。,(5.36),即,其中,（5.35）,这是一个含有n+1个未知数、n-1个方程的线性方程组.要完全确定的值还需要补充两个条件,这两个条件通常根据实际问题的需要，根据插值区间a,b的两个端点处的边界条件来补充。,第一边界条件：,则确定的线性方程组为：,(5.39),三对角线方程组,第二边界条件:取,(5.40),则确定的线性方程组为：,三对角线方程组,例2.20已知的函数值如下：,在区间1,5上求三次样条插值函数S(x),使它满足边界条件,解:这是在第二种边界条件下的插值问题，故确定(4个节点，4个未知数)的方程组形如（5.40）所示，,由已知边界条件,有,则得求解的方程组为,只需根据给定数据计算出：,则得方程组,解得：,代入式(5.32)即得,在x0,x1上:i=1,(5.32),将,代入上式，得：,在x1,x2上:i=2,在x2,x3上:i=3,故所求的三次样条插值函数S(x)在区间1,5上的表达式为,练习：使用MATLAB画出如上的曲线。,在这两个区间表达式是一样的,三次样条插值的误差界与收敛性（仅对充分光滑的f(x)成立）,特别，当k=0的时候：,例2.21f(x)=lnx，将0.5,3分为5个等分区间，在每个区间上进行三次样条插值。估计利用三次样条插值的误差。,解：误差估计f(4)(x)=-6/x4max|f(x)-S(x)|=5/384max|6/x4|*0.54=5/384*(6/0.5-4)*0.54=0.078125,课堂练习：将0.5,3分为10个等分区间，估计进行三次样条插值时候的误差。,0.5=x=3,用三次样条绘制的曲线不仅有很好的光滑度，而且当节点逐渐加密时，其函数值在整体上能很好地逼近被插函数，相应的导数值也收敛于被插函数的导数，不会发生龙格现象。因此三次样条在计算机辅助设计中有广泛的应用。,三次样条插值总结：,作业：P