三次样条插值

1、高次插值出现龙格现象高次插值出现龙格现象代数插值代数插值Hermite插值插值 分段分段插值插值 但分段线性插值在节点处不一定光滑但分段线性插值在节点处不一定光滑分段分段Hermite插值插值但但导数值导数值不容易得到不容易得到三次样条插值（先由三次样条插值（先由函数值函数值确定确定导数值导数值，再由，再由分段分段Hermite插值解决问题插值解决问题）举例：举例： 汽车、船的外形设计，流体力学等要求流线型（光滑）汽车、船的外形设计，流体力学等要求流线型（光滑） 木样条的来源木样条的来源背景背景应用最为广泛应用最为广泛3 三次样条插值三次样条插值 /* Cubic Spline Interpo

2、lation */ 样条是绘图员用于描绘光滑曲线的由一些易弯曲材料制成的窄样条是绘图员用于描绘光滑曲线的由一些易弯曲材料制成的窄条或棒条条或棒条. .在绘制需要通过某点的光滑曲线时在绘制需要通过某点的光滑曲线时, ,对它在这些点的位置对它在这些点的位置上上“压铁压铁”, ,它就被强制通过或接近图表上确定的描绘点它就被强制通过或接近图表上确定的描绘点.“.“样条函样条函数数”这个术语意在点出这种函数的图象与机械样条画出的曲线很像这个术语意在点出这种函数的图象与机械样条画出的曲线很像. .定义定义设设 。三次样条函数三次样条函数 , 且在每个且在每个 上为上为三次多项式三次多项式 /* cubic

3、 polynomial */。若它同。若它同时还满足时还满足 ，则称，则称 S(x) 为为 f(x) 在结点在结点 xj ( j = 0, 1, , n) 上的上的三次样条插值函数三次样条插值函数 .bxxxan .10,)(2baCxS ,1 iixx()(), (0,1, )iiS xf xin 注：注：三次样条与分段三次样条与分段 Hermite 插值的根本区别在于插值的根本区别在于S(x)自自身光滑身光滑，不需要知道，不需要知道 f 的导数值（除了在的导数值（除了在2个端点可能需个端点可能需要）；而要）；而Hermite插值依赖于插值依赖于f 在所有插值点的导数值。在所有插值点的导数值

4、。f(x)H(x)S(x) 三次样条插值问题三次样条插值问题Cubic Spline 三次样条插值函数是分段三次多项式三次样条插值函数是分段三次多项式，在每个小区间，在每个小区间 上可以写成上可以写成1,iix x 32( ),0,1,1,iiiiS xa xb xc xdin 共有共有 4n 个待定参数。个待定参数。S(x) 在在a, b上二阶导数连续，故在内上二阶导数连续，故在内结点结点 处应满足连续性条件处应满足连续性条件 (1,2,-1)ixin 0(0),0,1, 2,kkiiSxSxk 共有共有 3(n-1) 个条件。再加上个条件。再加上 n+1 个插值条件，共有个插值条件，共有4

5、n-2 个个条件。条件。如何计算？误差估计？如何计算？误差估计？3 3次样条插值函数次样条插值函数 是否存在唯一是否存在唯一?)(xSCubic Spline 因此，还需要因此，还需要2 2个条件才能确定个条件才能确定S(x)。通常在区间。通常在区间 端点端点 a = x0 和和 b = xn 上各加一个条件（称为上各加一个条件（称为边界条件边界条件），可），可根据实际问题的要求给定。根据实际问题的要求给定。（2）已知两端的一阶导数值，即）已知两端的一阶导数值，即000(),().nnnSxfmSxfm （II类）类） （1）已知两端的二阶导数值，即）已知两端的二阶导数值，即000(),().

6、nnnSxfMSxfM （I 类）类）此时，对函数值有周期条件此时，对函数值有周期条件0()().nfxfx 其特殊情况为其特殊情况为0()0,()0,nSxSx （自由边界自由边界） （3）周期边界条件）周期边界条件0()(),0,1,2.kknSxSxk （III 类）类）常用常用边界条件边界条件 /* boundary conditions */对应的样条函数称为对应的样条函数称为自然样条自然样条 /* Natural Spline */.Cubic Spline 由由boundary conditions 唯一唯一确定。确定。定理定理三次样条插值问题的解存在且三次样条插值问题的解存在且

7、唯一唯一。Cubic Spline 三弯矩法三弯矩法 /* method of bending moment */ 三次样条插值函数三次样条插值函数 S(x) 可以有多种表达式，有时用二阶可以有多种表达式，有时用二阶导数值导数值 表示时，使用更方便。表示时，使用更方便。Mi 在在力学上解释为细梁在力学上解释为细梁在 xi 处的弯矩，并且得到的弯矩与相邻两处的弯矩，并且得到的弯矩与相邻两个弯矩有关，故称用个弯矩有关，故称用 Mi 表示表示 S(x) 的算法称为的算法称为三弯矩法三弯矩法。() (0,1, )iiSxMin 对对S (xi ) 积分两次得积分两次得11( ),iiiiiixxxxS

8、xMMhh 其中其中 hi = xi+1 - xi . . 由于由于S(x) 在区间在区间 上是上是3 次多项式次多项式, , 故故 S (xi ) 在在 上是上是1 次多项式次多项式, , 可表示为可表示为10,1,(1,) iiixnx 1,iixx 331112()()( )66iiiiiixxxxS xMMC xChh Cubic Spline这是三次样条插值函数的表达式这是三次样条插值函数的表达式, ,当求出当求出Mi 后后, , S(x)就完全确定就完全确定. .定出积分常数定出积分常数, ,可以得到可以得到11(),()iiiiS xyS xy 利用插值条件利用插值条件33112

9、2111()()( ) (3.1) 66 66iiiiiiiiiiiiiiiixxxxS xMMhhM hxxMhxxyyhh 1,0,1,1iixx xin 221111()()( ) 226(3.2)iiiiiiiiiiiixxxxyyhS xMMMMhhh 为了求为了求 Mi , ,需要利用需要利用S(x)在内结点处一阶导数连续的条件在内结点处一阶导数连续的条件, 由上式可得由上式可得Cubic Spline这里有这里有 个未知数，个未知数， 个方程，个方程，n 1n+1还需还需增加增加 2 个方程个方程。0001122nnnnMMMM 对于对于I 类边界条件，类边界条件，00(),()

10、nnSxMSxM 0000, 20, 2nnnMM Cubic Spline0001111222211112000020000200000000200002nnnnnnnMMMMM即得关于即得关于Mi (i = 0, 1, , n)的的 n+1 元线性方程组元线性方程组注意其系数矩阵是按行严格对角占优阵，故它有唯一解。注意其系数矩阵是按行严格对角占优阵，故它有唯一解。可用可用追赶法追赶法求解。求解。Cubic Spline 在实际应用中，如果不需要规定内节点处的一阶导在实际应用中，如果不需要规定内节点处的一阶导数值，那么使用三次样条插值函数会得到很好的效果。数值，那么使用三次样条插值函数会得到

11、很好的效果。三次样条插值函数三次样条插值函数 S(x) 不仅在内节点处的二阶导数是不仅在内节点处的二阶导数是连续的，而且连续的，而且 S(x) 逼近逼近 f(x) 具有很好的收敛性，也是数具有很好的收敛性，也是数值稳定的。由于误差估计与收敛性定理的证明比较复杂，值稳定的。由于误差估计与收敛性定理的证明比较复杂，下面只给出误差估计的结论。下面只给出误差估计的结论。三次样条插值函数三次样条插值函数 S(x) 有估计式有估计式 定理定理5.5 设函数设函数4( ) , ,f xC a b 记记( 4 )4m ax() ,axbMfx 则则 , ,xa b 满足满足 I 类或类或 II 类边界条件的类

12、边界条件的 三次样条插值函数的误差估计三次样条插值函数的误差估计( )( )44( )( ),0,1,2kkkxxkkfMSC h 其中其中021511,.384248CCC 101max (),iiinhxx Cubic SplineCubic Spline注：注：提高精度只须提高精度只须增加节点增加节点, 而无须提高样条阶数。而无须提高样条阶数。稳定性：稳定性：只要方程组系数矩阵为只要方程组系数矩阵为SDD阵阵，保证数保证数值稳定值稳定.另有另有三转角法三转角法得到样条函数，即设得到样条函数，即设 S (xi) = mi，则，则易知易知xi, xi+1 上的上的S(x) 就是就是Hermi

13、te函数函数. 再利用再利用S (x)的连续性，可导出关于的连续性，可导出关于mi 的方程组，加上边界条件的方程组，加上边界条件即可解即可解. 在实际应用中，不仅常用在实际应用中，不仅常用S(x) 式式(3.1)计算计算 f(x) 的的近似值，而且常用近似值，而且常用 S (x) 式式(3.2)近似计算近似计算 f (x) . Sketch of the Algorithm: Cubic Spline 计算计算 i , i , i ; 计算计算 Mi (追赶法等追赶法等) ; 找到找到 x 所在区间所在区间 ( 即找到相应的即找到相应的 i ) ; 由该区间上的由该区间上的 S(x) 算出算出

14、 f(x) 的近似值。的近似值。1 (0,1,2)ihi 解：用三弯矩方程（第二种边界条件）ii i i 212121210123161-336-78计算得Cubic Spline得方程组得方程组783636210021221002122100123210MMMM3280M1283M 解得解得21063M 31703M 将此解代入将此解代入式式 (3.1) 即即得得 2111430,13xxxx 3212491108351,23xxxx 321463297325252,33xxxx( )S x Cubic SplineHW: 习题习题 #24插值法小结插值法小结 Lagrange Ln(x)

15、: 给出给出 y0 yn，选基函数，选基函数 li(x)，其次数为，其次数为节点数节点数 1. Newton Ln(x)，只是形式不同；渐增节点或节点等距只是形式不同；渐增节点或节点等距时方便处理时方便处理. Hermite： 给出给出 yi 及及 yi . Spline：分段低次：分段低次, 自身光滑自身光滑, f 的导数只在边界给出的导数只在边界给出. yi = interp1(x,Y,xi,method) ：用指定的算法计算插值；linear：线性插值（缺省方式），直接完成计算；pchip：分段三次Hermite插值。对于该方法，命令interp1 调用函数pchip，用于对向量x 与y

16、 执行分段三次内插值。该方法保留单调性与数据的外形；cubic：与pchip操作相同；spline：三次样条函数插值。对于该方法，命令interp1 调用函数spline、ppval、mkpp、umkpp。这些命令生成一系列用于分段多项式操作的函数。命令spline 用它们执行三次样条函数插值；注意它默认使用的是not-a-knot边界条件，也就是第一个点的三次导数和第二点的三次导数一样；最后一个点的三次导数和倒数第一个点一样。当Y=df1,y,df2时，表示第一点和最后一个点的一阶导数分别为df1,df2。pp = csape(x,y,conds)：计算在各种边界条件下的三次样条插值。 help csape例: