《三次样条插值算法详解.ppt》由会员分享，可在线阅读，更多相关《三次样条插值算法详解.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、三次样条插值算法详解三次样条插值算法详解样条函数的定义样条函数的定义定义定义4.1设区间设区间a,b上给定一个节点划分上给定一个节点划分a=x0 x1xn-1xn=b如果存在正整数如果存在正整数k使得使得a,b上的分段函数上的分段函数s(x)满足如满足如下两条：下两条：(1)在在a,b上有直到上有直到k-1阶连续导数。阶连续导数。(2)在每个小区间在每个小区间xi,xi+1上是次数不大于上是次数不大于k的多项式。的多项式。则称则称分段函数分段函数s(x)是以是以(2.6)为节点集的为节点集的k次样条函数。次样条函数。2三次样条插值函数的定义三次样条插值函数的定义并且关于这个节点集的三次样条函数
2、并且关于这个节点集的三次样条函数s(x)满足满足插值条插值条件：件：则称这个三次样条函数则称这个三次样条函数s(x)为为三次样条插值函数三次样条插值函数。3三次样条插值函数的边界条件三次样条插值函数的边界条件插值条件：插值条件：连续性条件：连续性条件：一阶导数连续条件：一阶导数连续条件：二阶导数连续条件：二阶导数连续条件：4（1）因为）因为s(x)在每个小区间上是一个次小于三次的多在每个小区间上是一个次小于三次的多项式，故有四个未知系数；项式，故有四个未知系数；（2）因为）因为s(x)有有n分段，从而共有分段，从而共有4n个未知系数！个未知系数！（3）但）但插值条件与样条条件插值条件与样条条件
3、仅给出仅给出4n-2个条件，无法个条件，无法定出定出4n个未知系数，还差个未知系数，还差2个条件！这个条件！这2个条件我们用个条件我们用边界条件边界条件给出！给出！5通常我们对插值多项式在两端点的状态加以要求也就是所谓的边界条件:第一边界条件：由区间端点处的一阶导数给出即第一边界条件：由区间端点处的一阶导数给出即6第二边界条件：由区间端点处的二阶导数给出即第二边界条件：由区间端点处的二阶导数给出即 特殊情况为特殊情况为自然边界条件自然边界条件：由区间端点处的二阶导数恒为由区间端点处的二阶导数恒为0给出即给出即 7这样三次样条插这样三次样条插值问题就分成三值问题就分成三类！其实不止这类！其实不止
4、这三类三类!第三类又称周期边界条件：第三类又称周期边界条件：由区间端点处的函数值或导数值满足周期条件给出由区间端点处的函数值或导数值满足周期条件给出 8样条函数的例子样条函数的例子容易验证：容易验证：是满足如下数据的第一类边界样条插值问题解：是满足如下数据的第一类边界样条插值问题解：x0123y0000y109样条函数的例子样条函数的例子10通常有通常有三转角法、三弯矩法、三转角法、三弯矩法、B样条基函数法样条基函数法。三次样条插值函数的求法三次样条插值函数的求法这三种方法的基本思想是类似的，都是这三种方法的基本思想是类似的，都是通通过待定某些参数过待定某些参数来确定插值函数，但肯定来确定插值
5、函数，但肯定不是待定不是待定4n个参数。而是利用已知条件将个参数。而是利用已知条件将待定参数减小到最少。待定参数减小到最少。比如：比如：待定一阶导数、待定二阶导数待定一阶导数、待定二阶导数、采采用基函数方法用基函数方法来确定插值函数。来确定插值函数。11三转角法三转角法:待定一阶数待定一阶数为了确定三次样条插值函数的表达式为了确定三次样条插值函数的表达式 S(x)，我们采用待定系数法来求解，我们待定什么系数呢？我们采用待定系数法来求解，我们待定什么系数呢？考虑到带一阶导数的分段三次考虑到带一阶导数的分段三次Hermite插值多项式插值多项式12我们采用待定一阶导数的方法即设我们采用待定一阶导数
6、的方法即设因为因为分段三次分段三次Hermite插值多项式已经至少是一阶连续插值多项式已经至少是一阶连续可导可导了，为了让它成为三次样条函数只需确定节点处了，为了让它成为三次样条函数只需确定节点处的一阶导数使这些节点处的二阶导数连续即可！的一阶导数使这些节点处的二阶导数连续即可！1314由于在内部节点处二阶导数连续条件：整理化简后得：整理化简后得：15称为三转称为三转角法基本角法基本方程组方程组以上推导还没有考虑边界以上推导还没有考虑边界条件！针对不同类型的三条件！针对不同类型的三次样条问题，就可以导出次样条问题，就可以导出不同的方程组！不同的方程组！16第一类三次样条插值问题方程组第一类三次
7、样条插值问题方程组基本方程组化为基本方程组化为n-1阶方程组阶方程组由于已知：由于已知：化为矩阵形式化为矩阵形式17这是一个严格对角占优的三对角方程组，这是一个严格对角占优的三对角方程组，用追赶法可以求解！用追赶法可以求解！18第二类三次样条插值问题的方程组第二类三次样条插值问题的方程组由于已知：由于已知：故得：故得：19稍加整理得联合基本方程组得一个联合基本方程组得一个n+1阶三对角方程组，阶三对角方程组，化成矩阵形式为：仍然是严格对角占优化成矩阵形式为：仍然是严格对角占优20第三类样条插值问题的方程组立即可得下式：由于：21其中：联合基本方程得一个广义三对角或周期三对角方程组：联合基本方程
8、得一个广义三对角或周期三对角方程组：这个方程这个方程组的系数组的系数矩阵仍然矩阵仍然是严格对是严格对角占优阵！角占优阵！22求解这些不同类型的样条插值问题的方程组，我们可得求解这些不同类型的样条插值问题的方程组，我们可得所要待定的一阶导数：所要待定的一阶导数：称为三次样条插称为三次样条插值问题三转角公值问题三转角公式！式！再代入再代入S(x)的每一段表达式，就求得三次样条函数的表达式的每一段表达式，就求得三次样条函数的表达式!23例1.对于给定的节点及函数值解:这是自然边界条件下的样条问题。24我们可以将上述计算列于表中：k0123xk1245yk1342mk?Mk0?0hk121*k*2/3
9、1/3*k*1/32/3*gk69/2-7/2-625由些得如下方程组：利用三转角公式：26同样可以求得第三段表达式！272829三弯矩法三弯矩法:待定二阶导数待定二阶导数选择二阶导数作为待定参数选择二阶导数作为待定参数:由于三次样条由于三次样条S(x)是三次多项式是三次多项式,故它的二阶导数是一次多项故它的二阶导数是一次多项式式,从而从而思考思考:(1)的原因的原因?3031从而推导出了三次样条从而推导出了三次样条S(x)在第在第k个小区间个小区间xk,xk+1上的上的表达式为表达式为:它的系数都是它的系数都是用二阶导数与用二阶导数与函数值表示函数值表示!32对所有中间节点对所有中间节点xk
10、,k=1,2,n-1,左边小区间与右边小区间上左边小区间与右边小区间上的三次多项式的一阶导数应当连续的三次多项式的一阶导数应当连续!确定二阶导数确定二阶导数33三弯矩法基本方程三弯矩法基本方程注意到这个基本方程只注意到这个基本方程只包括了包括了n-1个方程个方程!但却但却有有n个二阶导数需要待定个二阶导数需要待定,这是一个欠定方程组这是一个欠定方程组,还还需要根据边界条件再确定两个方程需要根据边界条件再确定两个方程!34曲率调整样条曲率调整样条这种样条的边界条件是已知两端点的二阶导数值这种样条的边界条件是已知两端点的二阶导数值!这样从三弯矩基本方程可以导数确定其它这样从三弯矩基本方程可以导数确
11、定其它n-2个待定参数个待定参数的方程组的方程组:35自然样条自然样条这种样条的边界条件是这种样条的边界条件是:已知两端点的二阶导数值为已知两端点的二阶导数值为0!这样从三弯矩基本方程可以导数确定其它这样从三弯矩基本方程可以导数确定其它n-2个待定参数个待定参数的方程组的方程组:36固支样条固支样条这种样条的边界条件是这种样条的边界条件是:已知两端点的一阶导数值已知两端点的一阶导数值!根据前面推导过程中得到的样条函数根据前面推导过程中得到的样条函数S(x)的一阶导数的表的一阶导数的表达式达式(2.11),得方程得方程37固支样条固支样条这样从三弯矩基本方程可以导数确定这样从三弯矩基本方程可以导
12、数确定n个待定个待定参数的方程组参数的方程组:38非扭结样条非扭结样条这种样条的边界条件是这种样条的边界条件是:要求样条要求样条S(x)在开始的两个小在开始的两个小区间区间x0,x1,x1,x2上的三阶导数相同上的三阶导数相同,在最后两个小区间在最后两个小区间xn-2,xn-1,xn-1,xn上的三阶导数相同上的三阶导数相同.对表达式对表达式(2.9)再求一次导数得方程再求一次导数得方程39非扭结样条非扭结样条再由三弯矩基本方程再由三弯矩基本方程,可得可得40周期样条周期样条这种样条的边界条件是这种样条的边界条件是:要求样条要求样条S(x)及其导数是以区及其导数是以区间长度间长度xn-x0为周
13、期的函数即为周期的函数即这些条件可以确定如下两个方程这些条件可以确定如下两个方程:41再由三弯矩基本方程再由三弯矩基本方程,可得可得周期样条周期样条421.1.在在MatlabMatlab中数据点称之为断点。如果三次样条插值没有边中数据点称之为断点。如果三次样条插值没有边界条件，最常用的方法，就是采用非扭结（界条件，最常用的方法，就是采用非扭结（not-a-knotnot-a-knot）条件。这个条件强迫条件。这个条件强迫第第1 1个和第个和第2 2个三次多项式的三阶导数个三次多项式的三阶导数相等，对最后一个和倒数第相等，对最后一个和倒数第2 2个三次多项式也做同样地处理。个三次多项式也做同样
14、地处理。2.2.MatlabMatlab中三次样条插值也有现成的函数：中三次样条插值也有现成的函数：y=interp1(x0,y0,x,spline)y=interp1(x0,y0,x,spline)；y=spline(x0,y0,x)y=spline(x0,y0,x)；pp=csape(x0,y0,conds),pp=csape(x0,y0,conds),pp=csape(x0,y0,conds,valconds)pp=csape(x0,y0,conds,valconds)，y=ppval(pp,x)y=ppval(pp,x)。其中其中x0,y0 x0,y0是已知数据点，是已知数据点，x x
15、是插值点，是插值点，y y是插值点的函是插值点的函数值。数值。3.3.对于三次样条插值，我们提倡使用函数对于三次样条插值，我们提倡使用函数csapecsape，csapecsape的返的返回值是回值是pppp形式，要求插值点的近似函数值，必须调用函数形式，要求插值点的近似函数值，必须调用函数ppvalppval。MATLAB中三次样条函数法实现中三次样条函数法实现43pp=csape(x0,y0,conds,valconds)pp=csape(x0,y0,conds,valconds)condsconds指定插值的边界条件，其值可为：指定插值的边界条件，其值可为：complete comple
16、te 边界为一阶导数，一阶导数的值在边界为一阶导数，一阶导数的值在valcondsvalconds参数中给出。参数中给出。not-a-knot not-a-knot 非扭结条件非扭结条件periodic periodic 周期条件周期条件second second 边界为二阶导数，二阶导数的值在边界为二阶导数，二阶导数的值在valcondsvalconds参数中给出，若忽略参数中给出，若忽略valcondsvalconds参数，二阶导数的参数，二阶导数的缺省值为缺省值为0,00,0。MATLAB中三次样条函数法实现中三次样条函数法实现44例例2：第一边界条件的例题：第一边界条件的例题x1245
17、y1342y17/8-19/8clear;x=1,2,4,5;y=1,3,4,2;pp=csape(x,y,complete,17/8,-19/8);pp.coefsMATLAB代码代码45第一边界条件的例题第一边界条件的例题pp=form:pp breaks:1 2 4 5 coefs:3x4 double pieces:3 order:4 dim:1pp.coefs -0.1250 0 2.1250 1.0000 -0.1250 -0.3750 1.7500 3.0000 0.3750 -1.1250 -1.2500 4.0000分段多项式结构与系数矩阵分段多项式结构与系数矩阵46如下代码
18、求解上述样条问题：如下代码求解上述样条问题：x-4-3-2-101234y00.151.122.362.361.460.490.060y00例例3：自然边界条件例题：自然边界条件例题47x=-4-3-2-101234;y=00.151.122.362.361.460.490.060;pp=csape(x,y,second);xx=-4:0.01:4;yy=ppval(pp,xx);hold on;plot(x,y,ok);plot(xx,yy,k-);hold off;MATLAB程序程序48pp=form:pp breaks:-4-3-2-1 0 1 2 3 4 coefs:8x4 doub
19、le pieces:8 order:4 dim:1分段多项式结构：分段多项式结构：49 pp.coefs=0.18085603829161 0.00000000000000 -0.03085603829161 0 -0.08428019145803 0.54256811487482 0.51171207658321 0.15000000000000 -0.39373527245950 0.28972754050074 1.34400773195876 1.12000000000000 0.14922128129602 -0.89147827687776 0.74225699558174 2.3
20、6000000000000 0.13685014727540 -0.44381443298969 -0.59303571428571 2.36000000000000 0.13337812960236 -0.03326399116348 -1.07011413843888 1.46000000000000 -0.06036266568483 0.36687039764359 -0.73650773195876 0.49000000000000 -0.06192746686303 0.18578240058910 -0.18385493372607 0.06000000000000分段多项式的系
21、数矩阵：分段多项式的系数矩阵：50图像图像51例例4：对如下：对如下Runge现象中的函数，求用现象中的函数，求用n分点作节分点作节点的三次样条插值多项式点的三次样条插值多项式s3(x)的图象。的图象。取取n=5,10,15,20等，将区间等分成等，将区间等分成n份，取分点作为插值份，取分点作为插值节点，利用节点，利用matlab函数函数csape()作出它的三次样条插值函作出它的三次样条插值函数，并作出这些插值函数与被插函数的图像。数，并作出这些插值函数与被插函数的图像。但由于插值节点数目较多，故不列出插值函数的表达式，但由于插值节点数目较多，故不列出插值函数的表达式，只画出它们的图象与被插
22、函数的图象的复合，从这些图象只画出它们的图象与被插函数的图象的复合，从这些图象可以看出，随着节点数目的增多，样条插值函数图象越来可以看出，随着节点数目的增多，样条插值函数图象越来越符合被插函数，因此避免越符合被插函数，因此避免Runge现象，也就是说三次样现象，也就是说三次样条插值函数具有收敛性。条插值函数具有收敛性。5253545556三次样条函数的一致收敛性三次样条函数的一致收敛性这个定理告诉我们：当插值节点较这个定理告诉我们：当插值节点较多时，三次样条插值函数可以十分多时，三次样条插值函数可以十分接近被插函数！不会产生接近被插函数！不会产生Runge现现象中的不收敛情况！象中的不收敛情况！57设被插函数设被插函数f(x)f(x)有直到四阶的连续导数，则对第一、二类样有直到四阶的连续导数，则对第一、二类样条插值问题的样条插值函数条插值问题的样条插值函数S(x)S(x)有如下估计：有如下估计：三次样条函数的插值余项三次样条函数的插值余项58在三次样条插值法中，插值节点处函数值的波动，只对这个在三次样条插值法中，插值节点处函数值的波动，只对这个节点两边的分段有影响，而对离该点较远的分段的影响会逐节点两边的分段有影响，而对离该点较远的分段的影响会逐渐变小，因此样条插值法具有较好的稳定性！渐变小，因此样条插值法具有较好的稳定性！三次样条函数法的稳定性三次样条函数法的稳定性59结束结束