1、第3次 分段线性插值与三次样条插值计算方法(Numerical Analysis)内容高次插值的龙格现象分段线性插值与误差估计三次样条插值与误差估计2.4.1 高次插值的龙格现象 插值多项式余项公式b)(a,)，x(x)x)(xx(x1)!(n()fR(x)n101)(n 例：设函数f(x)定义在区间0,1上，并且满足|f(4)(x)|1，x?0,1。在4个插值节点x0=0,x1=1/3,x2=2/3,x3=1,对f(x)进行插值得多项式P3(x)，估计误差。0.0031648213231314！1|)x)(xx)(xx)(xx(x|4！1|)x)(xx)(xx)(xx(x4!()f|R(x)
2、|差则3次插值多项式的误32103210(4)01x下面讨论误差的情况：(0,1)x1,|(x)f|设(4)但是当区间a,b比较大的时候，误差可能很大。适当提高插值多项式的次数，有可能提高计算结果的准确程度，但并非次数越高越好。当插值节点增多时，也不能绝对保证非节点处的插值精度得到改善，有时反而误差更大。影响误差的因素：一般地说插值节点的个数：插值节点越多，即使用高次插值，误差越小f(x)的高阶导数绝对值：越小，误差越小考察函数 5x5,x11f(x)2右图给出了和 的图像,当n增大时,在两端会发生激烈的振荡，称为龙格现象。y P10(x)f(x)P5(x)-5 0 5 x (x x)P P5
3、 5(x x)P P1 10 0(x x)P Pn n该现象表明：在大范围内使用高次插值,逼近的效果往往是不理想的。另外，从舍入误差来看，高次插值误差的传播也较为严重，一个节点上产生的舍入误差会在计算中不断放大，并传播到其它节点上。因此，次数太高的高次插值多项式往往并不实用，因为节点数增加时，计算量增大了，但插值函数的精度未必能够提高。称为龙格现象。Home 为克服龙格现象，可以采用分段插值的方法：将插值区间分成若干个小的区间，在每个小区间进行线性插值，然后相互连接，用连接相邻节点的折线逼近被插函数而不是在整个区间a,b上做线性插值。ab2.4.2 分段线性插值n0,1,.,k,x,x1kk)
4、f(xxxxx)f(xxxxx(x)S1kk1kkk1kk1k1设f(x)在n+1个节点 上的函数值为 。上作线性插值，得)xx(x1kk在每个小区间 b bx xx xx xa an n1 10 0)f f(x x,),f f(x x),f f(x xn n1 10 0y=f(x)y=p(x)x1x2x0 xnxy在几何上就是用折线替代曲线,如图所示。例2.19 已知f(x)在四个节点上的函数表如下：求f(x)在区间 30,90 上的分段连续线性插值函数S(x)。解：将插值区间 30,90 分成连续的三个小区间x xi i30456090f(xf(xi i)1212223 30,45,45,
5、60,60,90 S(x)在区间 45,60 上的线性插值为：32322x3023)f(xxxxx)f(xxxxxS(x)21211212S(x)在区间 60,90 上的线性插值为：2233x6032)f(xxxxx)f(xxxxxS(x)32322323223x3012)f(xxxxx)f(xxxxxS(x)10100101则S(x)在区间 30,45 上的线性插值为：将各小区间的线性插值函数连接在一起，得 90 x602233x603260 x4532322x302345x30223x3012S(x)30 xy60904510.50.870.7连续但不光滑连续但不光滑y=S(x)y=S(x
6、)3,4,5。节点取为0，1,2,线性插值多项式。插值分段求其在0,5上的,x11函数f(x)练习2xi012345f(xi)12151101171261f(1)010 xf(0)101xS(x)解：在0,1上（课堂练习）12x2xx154x1031)(x512)(x21f(2)121xf(1)212xS(x)在1,2上，52x1012)(x1013)(x51f(3)232xf(2)323xS(x)在2,3上，8519x17073)(x1714)(x101f(4)3-43xf(3)434xS(x)在3,4上，22131x44294)(x2615)(x171f(5)4-54xf(4)545xS(
7、x)在4,5上，1,2x,54x103S(x)2,3x,52x101S(x)3,4x,8519x1707S(x)4,5x,22131x4429S(x)0,1 x1，2xS(x)将这些分段线性函数拼接在一起，得：分段线性插值的误差估计（仅对充分光滑的f(x)成立）定理 设f(x)在 a,b 有2阶导数，则在a,b上的分段线性插值S(x)，的截断误差满足：其中：|)x-)(xx-(x|max2M|S(x)f(x)|max1kkxxx2xxx1kk1kk22bxah8M|S(x)f(x)|maxbxxxan10|,(x)f|maxMbxa2)x-(xmaxhk1kk由此，即得结论。|)x-)(xx-
8、(x2！()f|S(x)f(x)|1kk 时，x,x当x1kk证明：，2xx0，得x(x)g解),x-)(xx-(xg(x)记1kk*1kk代入g(x)：将x是g(x)的极值点得知x*，|)x-)(xx-(x|412M|S(x)f(x)|1kkk1k2)x-(x21)x-(x21)x-)(xx-(x)g(x1kkk1k1k*k*|)x-)(xx-(x|8M1kkk1k2练习：给出本题的S(x)在0,5上的误差估计。g(x)x(126x(x)f,x11f(x)3222 (x)单调减少f1，x0,(x)单调增加f0,1，x0,)x(1x-124x(x)g42222bxah8M|S(x)f(x)|m
9、ax17576148(5)f,21(1)f-2,(0)f 41h41h82|S(x)f(x)|max22bxa现在对f(x)的2阶导数进行估计。Home 41h82|S(x)f(x)|max2bxaxy2x11y12345y=S(x)：分段线性函数综上可得现象：在0,1上逼近效果最差，在其 它区间，逐渐变好。在船体、飞机等外形曲线的设计中,不仅要求曲线连续,而且要有二阶光滑度,即有连续的二阶导数。要求分段插值函数在整个区间上具有连续的二阶导数。因此有必要寻求一种新的插值方法,这就是样条函数插值法 2.5.1 三次样条函数样条函数来历定义5.4.设函数f(x)定义在区间 a,b 上，在给定的n+
10、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)在 a,b 上有连续的二阶导数（隐含：三次样条函数插值比线性插值要求严苛得多！(x x)S S(x x),S SS S(x x),则称S(x)为三次样条插值函数。在 a,b 上连续)xy回答：不是。原因：1）在每个区间内都是3次多项式；2）在小区区间端点xi处连续并且：f(xi)=S(xi)；3）S”(x)在xi 点不连续，即不光滑。y=S(x)（蓝色）（蓝色）
11、问题：这个S(x)是三次样条插值函数吗？y=f(x)(黑色黑色)x0 xixi+1xnxyS(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 上的表达式：3 3i i3 32 2i i2 2i i1 1i i0 0i ix xa ax xa ax xa aa a(x x)S Si i3 3i i2 2i i1 1i i0 0a a,a a,a a,a a1 1n n0 0,1 1,.
12、,i i确定多项式的系数分析：待定系数：，n个子区间，要确 定S(x)，需要确定4n个待定系数。1）要求 S(xi )=f(xi),i=0,1,n 已知：能产生多少个方程？(x x)S S(x x),S SS S(x x),1 1n n1 1x x,x x2）要求 在整个插值区间 a,b 上连续，因此在连接点 上连续。1）插值条件(n+1个节点)n,0,1,i),f(x)S(xii满足条件：2）连接条件(3n-3个节点)上述二式共给出了4n-2个条件,而待定系数有4n个,因此还需要2个条件才能确定S(x)。xx0 x2 x5 x1 x4 x3 x6 0)(xS0)(xS1n,1,2,i0)(x
13、S0)(xS0)S(x0)S(xiiiiii 不包括端点a,b类型1：给定两端点f(x)的一阶导数值：)(x xf f)(x xS S),(x xf f)(x xS Sn nn n0 00 0常用边界条件的三种类型(略去了第3种)(x xf f)(x xS S),(x xf f)(x xS Sn nn n0 00 0 类型2：给定两端点f(x)的二阶导数值：n n0 0 x xb b,x xa a通常在区间端点 上各加一个条件,称为边界条件。0 0)(x xS S)(x xS Sn n0 0 特别地,称为自然边界条件。满足自然边界条件的三次样条插值函数称为自然样条插值函数。这样，由上给定的任一
14、种边界条件加上插值条件和连接条件，则得出4n个方程，可以唯一确定4n个系数。从而得到三次样条插值函数S(x)在各个子区间 xi,xi+1 上的表达式S(xi）(i=1,2,)。但是，这种做法当n较大时，计算工作量很大，不便于实际应用。希望找到一种方便计算机计算简单的构造方法-显式方法。i31iii3i1ii6h)x(xM6hx)(xM(x)S i1i2iiiii2i1i1ih)x(xh6Myhx)(xh6My2.5.2 三次样条插值函数的求法;iiiy)f(x)S(x记：1iiixxh经推导(略)，得到如右的在每个小区间上的三次样条插值函数的显式表达式。(5.32)n,1,2i,x,xxi1i
15、 注意：这里有n个区间，n+1个节点，需要确定 这n+1个值。n10M,M,M 只要确定 这n+1个值,就可定出三样条插值函数S(x)。n10M,M,M 经过艰苦的推导，得到如下的确定n10M,M,M的方程组。i1iii1iigM2MMn)i(01nn1n1n2n1n232212121101gM2MMgM2MMgM2MM(5.36)即 i1ii1ii1iiii1hhhhhh；其中（5.35）x,fxx,fxhh6gi1i1ii1iii 这是一个含有n+1个未知数、n-1个方程的线性方程组.要完全确定 的值还需要补充两个条件,这两个条件通常根据实际问题的需要，根据插值区间 a,b 的两个端点处的
16、边界条件来补充。n)n),0,1,0,1,(i(iMMi i第一边界条件：nnn000y)(xf)(xS,y)(xf)(xS则确定 的线性方程组为：n n1 10 0MM,MM,MMn1n10n1n101n1n11ggggMMMM212212(5.39)三对角线方程组)x,fxy(6/hg)yx,(fx6/hgn1nnnn010101)n,1,2,(ii1ii1ii1iiii1hhh,hhhx,fxx,fxhh6gi1i1ii1iii1iiixxh用到边界条件第二边界条件:取nnn000y)(xSM,y)(xSM n1n1n2n20111n2n211n2n2n221ygggygMMMM2222
17、(5.40)(5.40)则确定 的线性方程组为：1 1n n1 1MM,MM-三对角线方程组1iiiihhhi1ii1ii1hhhx,fxx,fxhh6gi1i1ii1iii1)n,1,2,(i例2.20 已知的函数值如下：在区间 1,5 上求三次样条插值函数S(x),使它满足边界条件 0(5)S0,(1)S 解:这是在第二种边界条件下的插值问题，故确定 (4个节点，4个未知数)的方程 组形如（5.40）所示，3 32 21 10 0MM,MM,MM,MMxi1245f(xi)1342xx0=1x1=2x2=4x3=5由已知边界条件,有0My)(xS0,My)(xS333000 2 21 1M
18、M,MM212121ggMM22则得求解 的方程组为 只需根据给定数据计算出：i ii ii ig g,1h2h1h3212x,fx21x,fx2x,fx32211032hhh,32hhh3222212132)21(36)x,fxx,(fxhh6g10212115)212(36)x,fxx,(fxhh6g213232252MM323M322M2121则得方程组 i i1 1i i1 1i ii i1 1 i ii ii ii i1 1 i ii i1 1i ii i1 1 i ii ii ii ix x,x xf fx x,x xf fh hh h6 6g g 1 1h hh hh h h h
19、h hh h 解得：49M,43M210M,49M,43M0,M3210代入式代入式(5.32)(5.32)即得即得3 3 2 2,1 1,i i(x x),S Si i1301131016h)x(xM6hx)(xM(x)S102111112100h)x(x)h6M(yhx)(x)h6M(y在x0,x1 上:i=1i31iii3i1ii6h)x(xM6hx)(xM(x)Si1i2iiiii2i1i1ih)x(xh6Myhx)(xh6My)()(5.32)将将4 43 3MM0 0,MM1 1,h h3 3,y y1 1,y y2 2,x x1 1,x x1 10 01 11 10 01 10
20、0 11)(x643-31x)(2161)(x43-(x)S31代入上式，得：代入上式，得：1x47x83x81(x)S2311301131016h)x(xM6hx)(xM(x)S102111112100h)x(x)h6M(yhx)(x)h6M(y在x1,x2 上:i=22 21 12 22 22 22 22 22 22 22 21 11 12 23 31 12 22 23 32 21 12 2h h)x x(x xh h6 6MMy yh hx x)(x xh h6 6MMy y6 6h h)x x(x xMM6 6h hx x)(x xMM(x x)S S4 49 9，MM4 43 3MM
21、2 2,h h4 4,y y3 3,y y4 4,x x2 2,x x2 21 12 22 21 12 21 12 22 2)(x x4 42 24 49 94 42 2x x)(4 44 48 81 13 31 12 22 2)(x x4 49 91 12 2x x)(4 44 43 3(x x)S S3 33 32 22 2)(x x4 41 11 1x x)(4 44 47 72 2)(x x1 16 63 34 4)(x x1 16 61 1(x x)S S3 33 32 21-x47x83x81(x)S232在x2,x3 上:i=33 32 22 23 33 33 33 33 32
22、23 32 22 23 33 32 23 33 33 33 32 23 3h h)x x(x xh h6 6MMy yh hx x)(x xh h6 6MMy y6 6h h)x x(x xMM6 6h hx x)(x xMM(x x)S S0 0MM,4 49 9MM1 1,h h2 2,y y4 4,y y5 5,x x4 4,x x3 32 23 33 32 23 32 21 14 4)(x x2 21 1x x)(5 52 24 49 94 46 6x x)(5 54 49 9(x x)S S3 33 33 32 23 33 33 32 23 32 22 23 33 33 32 23
23、3h h)x x(x xy yh hx x)(x xh h6 6MMy y6 6h hx x)(x xMM(x x)S S4 4)2 2(x xx x)(5 58 83 35 55 5)(x x8 83 3(x x)S S3 33 333x4103x845x83(x)S233故所求的三次样条插值函数S(x)在区间1,5上的表达式为 5)x(433x4103x845x83 4)x(21x47x83x812)x(11x47x83x81-S(x)232323练习：使用MATLAB画出如上的曲线。在这两个区间表达式是一样的都连续。(x)在连接点2和4S(x)和SS(x),经验证,三次样条插值的误差界与
24、收敛性（仅对充分光滑的f(x)成立）特别，当k=0的时候：4(4)bxabxah|(x)f|max3845|s(x)f(x)|max3/8.C1/24,C5/384,其中C(6.17)0,1,2.k ,h|(x)f|maxC|(x)s(x)f|max则有估计式1),n,0,1,(ixxh,hmax令h 边界条件,S(x)满足第1或2 b,a,C设f(x)定理4.210k4(4)bxak(k)(k)bxai1iii1ni04 例2.21 f(x)=lnx，将0.5,3分为5个等分区间，在每个区间上进行三次样条插值。估计利用三次样条插值的误差。解：误差估计f(4)(x)=-6/x4 max|f(x
25、)-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用三次样条绘制的曲线不仅有很好的光滑度，而且当节点逐渐加密时，其函数值在整体上能很好地逼近被插函数，相应的导数值也收敛于被插函数的导数，不会发生龙格现象。因此三次样条在计算机辅助设计中有广泛的应用。三次样条插值总结：作业：P48:6P49:20本章小结本章小结 本章介绍的插值法是实用性很强的方法。它们解决的实际问题虽然各式各样，但抽象为数学问题却有它的共性，即利用已知的数据去寻求某个较为简单的函数P(x)来逼近f(x)。插值法给出了寻求这种近似函数的原则，以及构造近似函数的几种具体方法。插值法要求近似函数在已知的数据点必须与f(x)完全一致。Home 谢谢
