数值分析第2章插值法part2

1、计 算 方 法南京大学计算机科学与技术系南京大学计算机科学与技术系第二章第二章 插值法（续）插值法（续）2021-10-122.6 分段低次插值 在区间在区间 a, b 上用插值多项式上用插值多项式 P 逼近函数逼近函数 f 时，时，f 和和P 在每个节点上的差异在每个节点上的差异(理论上理论上)应该为零。自然，我们期望应该为零。自然，我们期望在一切中间点上也能很好地逼近在一切中间点上也能很好地逼近 f ，并且当插值点增加时，并且当插值点增加时这种逼近效果应该越来越好。这种逼近效果应该越来越好。 但上述的期望不可能实现的。当认识到这一点时，在数但上述的期望不可能实现的。当认识到这一点时，在数学

2、界曾引起强烈的震动。学界曾引起强烈的震动。 20 世纪初，世纪初，Runge就给出了一个等距节点插值多项式就给出了一个等距节点插值多项式 不收敛到不收敛到 的例子。的例子。( )nLx( )f x2021-10-12 设函数设函数 ，在该区间在该区间 上取上取 个等距节点个等距节点, 构造构造 的的 次次 拉格朗日插值多项式为拉格朗日插值多项式为21( ), 5,51f xxx 5,51n( )f xn5 10(0,1, )iixinn 2,4,6,8,20n 其其matlab的的lagrange.m文件及相关图形如下文件及相关图形如下.njnjiiijijnxxxxxxL002)()(11)

3、(Runge 现象现象2021-10-12% lagrange.mfunction y=lagrange (x0,y0,x)n=length(x0);m=length(x);for i=1:m z=x(i);s=0; for k=1:n L=1; for j=1:n if j=k L=L*(z-x0(j)/(x0(k)-x0(j); end end s=s+L*y0(k); end y(i)=s;endy; Lagrange插值多项式插值多项式求插值的求插值的Matlab程序程序.2021-10-12%Compare_Runge.mx=-5:0.1:5;z=0*x;y=1./(1+x.2);p

4、lot(x,z,k,x,y,r)axis(-5 5 -1.5 2);pause,hold onfor n=2:2:20 x0=linspace(-5,5,n+1); y0=1./(1+x0.2); x=-5:0.1:5; y1=lagrange(x0,y0,x); plot(x,y1), pauseendy2=1./(1+x0.2);y=interp1(x0,y2,x);plot (x,y,k),hold offgtext(n=2),gtext(n=4),gtext(n=6)gtext(n=8),gtext(n=10)gtext(f(x)=1/(1+x2)比较不同的插值多项式次数对插值的影响比

5、较不同的插值多项式次数对插值的影响2021-10-12-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)-5-4-3-2-1012345-1.5-1-0.500.511.5

6、2n=2n=4n=6n=8n=10f(x)=1/(1+x2)不同次数的不同次数的Lagrange插值多项式的比较图插值多项式的比较图Runge现象现象 2021-10-12令令 ，则，则 ， 下表列出了下表列出了 和和 的值。的值。1/211()2nnnxxx1/255nxn2,4,20n 1/2()nnL x1/2()nR x2021-10-12 结果表明结果表明,随着随着 的增加，的增加， 的绝对值几乎成倍地增的绝对值几乎成倍地增加，这说明当加，这说明当 时时 在在 上不收敛。上不收敛。 Runge证明了，存在一个常数证明了，存在一个常数 , 使得当使得当 时，时， ; 而当而当 时时 发

7、散。发散。 说明说明: 并不是插值多项式的次数越高并不是插值多项式的次数越高, 插值效果越好插值效果越好, 精度精度也不一定是随次数的提高而升高也不一定是随次数的提高而升高, 这种现象在上个世纪初由这种现象在上个世纪初由Runge发现发现, 故称为故称为Runge现象现象.n1/2()nR xn nL 5,53.63cxclim ( )( )nnL xf x xc ( )nL x 分段线性插值特别简单，从几何上看，就是用分段线性插值特别简单，从几何上看，就是用折线逼近折线逼近曲线曲线。 分段线性插值的数学定义分段线性插值的数学定义 设设 是区间是区间 上的函数，在节点上的函数，在节点 上的函数

8、值为上的函数值为 ，求一分段折线函数求一分段折线函数 满足：满足：（1 1） （2 2 在在 上，上， 是一次多项式。是一次多项式。（3 3）则称）则称 为为 的的分段线性插值函数分段线性插值函数。 分段线性插值( )f x , a b01naxxxb01,nfff( ) , P xC a b( ),0,1,iiP xf in1,iixx( )P x1,iixx( )P x( )P x2021-10-12 1,iixx0,1,1in( )P x易知易知, P(x) 是个折线函数，在每个区间是个折线函数，在每个区间上上,有有在在 a,b 上是连续的，但其一阶导数是不连续的上是连续的，但其一阶导数

9、是不连续的. 1111( )iiiiiiiixxxxyyxxxxp x2021-10-12 当当 时时, , 当当 时时, , 分段线性插值的基函数0i 10101001,( )0,xxxxxxxlxxxx1,2,1in11111111,( )( ,0,iiiiiiiiiiiiixxxxxxxl xxxxx xxxxxx 当当 时时, ,11110,( ),nnnnnnnnxxxlxxxxxxxxin2021-10-12显然显然 是是 的线性组合：的线性组合： 在区间在区间 上的值为：上的值为：( )P x( )il x0( )( )niiiP xf l x11111( )iiiiiiiiii

10、xxxxP xffxxxxxxx1,iixx，表达式表达式 在区间在区间上，只有上，只有是非零的，其它基函数均为零。即是非零的，其它基函数均为零。即注意注意( )P x1,iixx1( ) ,ilx( )il x11( )( )( )iiiiP xflxf l x2021-10-12算例算例节点（如下表），求区间上分段线性插值函数，并利用节点（如下表），求区间上分段线性插值函数，并利用它求出它求出21()1yfxx (4.5)f已知函数已知函数近似值。近似值。在区间在区间 0,5 上取等距插值上取等距插值2021-10-12 ,1k k 11(1)( )(1)(1)(1)()kkkkxkx k

11、P xyykkkky x kyx k (1) 0.5 , 0,10.5(2) 0.2(1), 1,2( )0.2(3) 0.1(2), 2,30.1(4) 0.05882(3), 3,40.05882(5) 0.038xxxxxxP xxxxxxxx 46(4),4,5xx (4.5)0.05882 (4.5 5)0.03846 (4.5 4)0.04864P (4.5)0.04705882352941f解解: : 在每个分段区间在每个分段区间于是，于是，实际值实际值: : 当当n=7 时，时， P(4.5)=0.04762270321996 ; 当当n=10时，时，P(4.5)=0.0470

12、5882352941由此可见，对于光滑性要求不高的插值问题，分段线性插值的由此可见，对于光滑性要求不高的插值问题，分段线性插值的效果非常好！计算也简单效果非常好！计算也简单!2021-10-122.7 三次样条插值三次样条插值2021-10-1201naxxxb划分X:（每个小区间作（每个小区间作Hermite插值）插值）2021-10-122021-10-122021-10-1201naxxxb(),(0,1, )*1jjjxs xyjn 在每一节点处满足（）2)称S(x)为在节点X上的三次样条插值函数三次样条插值函数1( )3,4jjS xxx从定义可以看出是分段 次多项式，在每个小区间上

13、要确定 个待定系数，共有n个小区间，要确定要确定4n4n个参数个参数. .2021-10-12 (1,2,1)jxjn处应满足连续性条件:2021-10-12n+1*共有（3n-3)个条件，再加上S(x)满足个插值条件（ 1），这样共有4n-2个条件，因此还需要2个条件才能确定S(x).(0)(0), (0)(0),(0)(0)jjjjjjS xS xS xS xSxSx00() ,()(*2)nnSxfSxf00() ,()(*3)nnSxfSxf2021-10-120()()0nSxSx3 3）周期性条件）周期性条件000(0)= (0)(*4)(0)= (0)(0)= (0)nnnS x

14、S xS xS xSxSxnyy 02021-10-1232032113( ) 1,022( )13( ) 0, 122SxxxxS xS xxxx 10.750.50.2500.250.50.75100.250.50.7511.251.51.75220S0 x( )S1 x( )11xS(x)=01( ) 1,0( ) 0, 1S xxS xx .三弯矩三弯矩算法推算法推导导2021-10-122021-10-12111( )( )( )(*5) ,0,1,1( )iiiiiiiiM xxxxxSxM xMMhhxx xinS x则可用分段线性插值表示为这隐含了满足内节点处的二阶导数连续性条

15、件。11(), ()iiiiM xMM xM331111*5()()66(*6), ,0,1,1iiiiiiiiiiiiiixxxxxxxMMhhhxxhxx xin对（）两边作两次不定积分，并写成S( )=*1,.(),(0,1, )*1iiiis xyin 由条件（）确定常数（）2211,= (),= ()66*6iiiiiiiiiiM hMhf xf x 其中为待定参数，即最后两项为待定线性函数。由插值条件（*1)式，易知代入（），2021-10-123311221111 ()()66( )()66(*7), ,0,1,1iiiiiii iiiiiiiiiiixxxxxMMhhMhxxM

16、 hxxf xf xhhxx xin即得三次样条插值多项式S( )=22111111()()22,(*8)6,0,1,1,iiiiiiiiiiiiiiixxxxxMMhhhf x xxx xinf x x对上式两边求一阶导数得S ( )=-(M-M）其中为一阶差商。2021-10-121+1+11+1 (0),+6(-0),+26iiiiiiiiiiiihSxf x xhSxf x x从而有(2MM）(MM）2021-10-12ii11111S(-0) =S(+0),(2) ,6(2)(*9)61,2,1iiiiiiiiiixxhf xxMMf x xhMMin于是，由一阶导数在内节点处的连续性条件，即得到2021-10-1211,iiiMM M这是关于的线性方程组。1111111, 1(*10)6 , iiiiiiiiiiiiiiiihhhhhhdf xx xf xx x若记其中的为二阶差商。2021-10-12110110 *+2