科学计算(计算方法).课件.ppt

1、第4章 函数的插值 4.1 引 言背景背景： 实际问题中，函数 f(x)多样、复杂，通常只能观测到一些离散数据；或者 f(x) 过于复杂而难以进行一些运算，例如求导。希望用简单函数 g(x) 近似 f(x) 。 最简单的办法：在所有的离散点(节点)处，让 g(x)= f(x)；在其它点处,让 g(x) f(x).x0 x1x2x3x4xg(x) f(x)定义定义4.1.1 设 f(x) 是定义在区间a, b上的函数， 为区间a, b中n+1个互异的点（称为节点节点）， 是给定的函数类。插值问题就是在 求函数 g(x)，使得问题：问题：(1) 函数类的选取：多项式，样条函数，有理函数，？(2)

2、插值问题是否有解？如果存在解，解是否唯一？(3) 如何构造问题的解？(4) 截断误差多大？(5) 随着节点增加， g(x)是否收敛于f(x) ？0 niix( )( ),0,1,iig xf xin 设 是函数类子空间 的一组基，则对 ，则其中01( ),( ),( )nxxx01( ),( ),( )nspanxxx ( )g x 0011( )( )( )( )nng xaxaxax0011( )( ),0,1,( )( )( )( ),0,1,iiiinniig xf xinaxaxaxf xinAab0010000011111101()()()()()()()(),.()()()()n

3、nnnnnnnxxxaf xxxxaf xAabxxxaf x定理定理4.1.1 设 f(x) 是定义在区间a, b上的函数， 为区间a, b中n+1个互异的节点， 。则插值问题存在惟一解当且仅当如下矩阵非奇异01( ),( ),( )nspanxxx 001000111101()()()()()()()()()nnnnnnxxxxxxAxxx0 niix如果取 ，即 则4.2 Lagrange插值( )(0,1, )iixxin1 (1, ,)nnR xspanxx 0011011det( )()01nnijj i nnnnxxxxAxxxx 定理定理4.2.1 设 f(x) 是定义在区间a

4、, b上的函数， 为区间a, b中n+1个互异的节点。则存在惟一次数不超过 n 的多项式 ,使得0 niix( )nL x( )( ) (0,1, ).niiL xf xin1. Lagrange插值0 niix( )(0,1, )il x in1,()( ,0,1, )0,ijijijl xi jnij定义定义4.2.1 设 为区间a, b中n+1个互异的节点。如果存在次数不超过 n 的多项式 ,使得则称 为Lagrange插值基函数插值基函数。( )(0,1, )il x in011011()()()()( )()()()()jiinij iiiiiiinijxxxxxxxxxxl xxx

5、xxxxxxxx 容易求得Lagrange插值基函数 则插值问题的解为0( )( ) ( ).nniiiL xf x l x 线性插值01011010)( , )(xxxxxlxxxxxl)()()()()(11001xlxfxlxfxL 二次插值)()()()()()( )()()(120210221012012010210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl2001122( )() ( )() ( )() ( )L xf x lxf x l xf x lx)3 , 3(),1 , 2(),0 , 0(),2 , 1(例例.)31)(21)(01()3)(2)(0(

6、)(0 xxxxl)23)(03)(13()2)(0)(1()(3xxxxl)32)(02)(12()3)(0)(1()(2xxxxl)30)(20)(10()3)(2)(1()(1xxxxl3023( )2 ( )( )3 ( ).L xlxlxl x定理定理4.2.2 设函数 f(x) 在区间a, b上具有n 阶连续导数，并且在(a, b)内n+1阶导数存在， 为区间a, b中n+1个互异的节点， 是代数插值问题的解。则用插值多项式 近似 f(x) 的截断误差为0 niix( )nL x( )nL x(1)0( )( )( )( )(),(1)!nnnniifR xf xL xxxn2.

7、误差估计)()()(xLxfxRnn其中0101(min ,max ,).nnx x xxx x xx解解.0 x1x2x185500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL这里这里)3,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外外推推 (extrapolation) 的实际误差的实际误差

8、 0.010010.010013,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插(interpolation) 的实际误差的实际误差 0.005960.00596例例. 已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)

9、(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次次插值的实际误差插值的实际误差 0.000610.00061 Lagrange插值的缺点无承袭性：增加一个节点，所有的基函数都要重新计算1. 差分差分4.3 Newton插值 设 f(x) 是定义在区间a, b上的函数，n为正整数。记(0,1,)ixaihinbahn0 niix称h为步长步长。称 为等距节点等距节点。记1( ),iiiiiff xfff称 为f(x) 在节点 处的1阶向前差分阶向前差分。ifixix记211111,kkkiiiiiiiiifffffffff 依次称为f(x

10、) 在节点 处的2阶阶，k 阶向前差分阶向前差分。ix记21111,kkkiiiiiiffffff 依次称为f(x) 在节点 处的1阶阶，2阶阶，k 阶向后差分阶向后差分。ix1111222211,kkkiiiiiiffffff20().2iiff xh记称为f(x) 在节点 处的1阶阶，2阶阶，k 阶中心差分阶中心差分。 分别称为向前差分算子，向后差分算子和中心差分算子，用 表示恒等算子和位移算子，即, , I E,iiiiIffE ff1()iiiiiifffEffEI f11221,.EIIEEE 则从而0( 1).mmjjimm ijjfC f 利用差分和差分算子的定义，容易证明如下结

11、论。0.mjjm imijfCf定理定理4.3.1 (1) 设 , c, d 是常数，则(2) 设 ,则(3) 如果f(x)是m次多项式，则f(x)的一阶差分是m-1次多项式。(4) f(x)的各阶差分均可用函数值表示，即(5) f(x)的函数值也可用各阶差分表示，即.iiifc ud v ( )( ) ( )f xu x v x1().iiiiiiifu vuvvu ( )( )( )f xcu xdv x2. 差商差商( )() ,ijijijf xf xf x xijxx , ,ijjkijkikf x xf xxf x xxxx0 niix为f(x) 在节点 处的1阶差商阶差商。称,i

12、jx x 设 f(x) 是给定的函数， 为n+1个互异的节点。称为f(x) 在节点 处的2阶差商阶差商。称,ijkx xx011110110, ,kkkkkkf x xxf xxxf x xxxxx为f(x) 在节点 处的k阶差商阶差商。011,kkxxxx差商表差商表1阶差商2阶差商3阶差商4阶差商( )if x1x3x2x0 xix4x0()f x1()f x2()f x3()f x4()f x01,f x x12 ,f x x23,f x x34,f x x012,f x x x123 ,f x x x234,f x x x0123,f x x x x1234 ,f x x x x012

13、34,f x x x x x , , ,ijjiijkjikikjf x xf xxf x xxf xxxf x xx010101,.kkkf x xxcu x xxdv x xx0110011(),.()()()()kjkkjjjjjjjkf xf x xxxxxxxxxxx利用差商的定义和数学归纳法，容易证明如下结论。定理定理4.3.2 (1) 设 , c, d 是常数，则(2) 设 ,则(3) 如果f(x)是m次多项式，则f(x)的一阶差商是m-1次多项式。(4) f(x)的各阶差商均可用函数值表示，即(5) f(x)的各阶差商具有对称性，即(6) 如果 ，则( )( ) ( )f xu

14、 x v x011010, ,.kkkjjkjf x xxxu x xx v xx( )( )( )f xcu xdv x(0,1,)ixaihin01,.!kkkkff x xxk h3. Newton插值插值0000011010101220120101 ( )()() , ,() , ,() , ,(nnf xf xxxf x xf x xf x xxxf x x xf x x xf x x xxxf x x x xf x xxf x xxx01) ,nnxf x x xx0 niix 设 f(x) 是给定的函数， 为n+1个互异的节点，则上面各式两边依次乘 ,然后左右两边全部等式相加，得

15、0010111, ()(),()()()nxxxxxxxxxxxx0010012010101001( )(),(),()() ,()()()() ,nnnnf xf xf x xxxf x x xxxxxf x xxxxxxxxxxf x x xx记则001001201010110101( )(),(),()() ,()()()( )()()() ,nnnnnnNxf xf x xxxf x x xxxxxf x xxxxxxxxR xxxxxxxf x x xx并且( )( )(0,1, )niiNxf xin( )( )( )nnf xNxR x即 是满足插值条件的n次插值多项式，称为n次

16、Newton插值多项式。( )nNx 事实上. 设 表示在节点 处的k次Lagrange插值多项式，则 对 ，因为010211( )( )( )( )( )( )( )( )nnnL xL xL xL xL xL xL xLx并且 是k 次多项式, 则 是的全部根。因此kxx( )kL x011,kkxxxx1( )( )kkL xLx将 代入上式，得1( )( )( )( )0 (0,1,1)kikiiiL xLxf xf xik1( )( )kkL xLx1( )( )0kkL xLx1011( )( )()()()kkkL xLxA xxxxxx011,kxxx1011()()()()(

17、)kkkkkkkkL xLxA xxxxxx得( )( ).nnL xL x从而101110011101101101101()()()()()()()()()()()()()()()()()() ()()()()()(kkkjkjkkjjjjjjjjkkkkkkkkkkjkkkkkjjjjxxxxxxxxf xxxxxxxxxf xAxxxxxxxxxxxxf xf xxxxxxxxxxxx101101)()() ,kjjjkjkkxxxxxf x xx1101100()()()()()kkkikjkkkkjijiijxxf xf xA xxxxxxxx 于是101011( )( ),()()

18、()kkkkL xLxf x xxxxxxxx利用11100( )()kkikjjijiijxxLxf xxx 例例. . 2点Newton插值多项式)()()()()(0010101xxxxxfxfxfxN利用差商表，容易构造Newton插值多项式)()(,)(,)()(1000100nnnxxxxxxfxxxxfxfxN 设函数 f(x) 在区间a, b上具有n 阶连续导数，并且在(a, b)内n+1阶导数存在， 为区间a, b中n+1个互异的节点.因为 ，则由定理4.2.2，有用Newton插值多项式 近似 f(x) 的截断误差为0 niix( )nNx0101(min ,max ,)n

19、nx x xxx x xx( )( )nnNxL x(1)0( )( )( )( )(),(1)!nnnniifR xf xNxxxn其中 ，从而0101( )( )( )()()() ,nnnnR xf xNxxxxxxxf x x xx(1)01( ) ,.(1)!nnff x x xxn4.4 Hermite插值背景背景： 实际问题中，构造函数f(x)的插值多项式除利用函数值的条件外，还可以利用函数的导数值，这样的插值问题称为Hermite插值问题插值问题。Hermite插值问题的提法插值问题的提法2121( )( ),( )( ),0,1,niiiniiiHxf xyHxfxyin21

20、( )nHx0 niix 设 f(x) 是定义在区间a, b上的可微函数， 为区间a, b中n+1个互异的节点，给定的函数f(x)在节点处的函数值和导数值。求次数不超过2n+1的多项式 ,使得定理定理4.4.1 设 f(x) 是定义在区间a, b上的可微函数， 为区间a, b中n+1个互异的节点。则存在惟一次数不超过 2n+1 的多项式 ,使得0 niix21( )nHx2121( )( ),( )( ),0,1,niiiniiiHxf xyHxfxyinHermite插值问题的解插值问题的解 构造一个次数不超过 2n+1 的多项式 ,使得( )jx0010000000( )jxx( )jx0

21、 x1jxjx1jxnx因为 是 的二重零点，则011,jjnxxxx( )jx20( )()nijjjjijiijxxxab xxxx由 ，可得()1jjx1ja 记则0( )nijijiijxxlxxx由 ，可得()0jjx22( )1() ( )( )( )21() ( ) ( )jjjjjj jjjjjxb xxlxxb lxb xxlx lx012 ()2njjjijiijblxxx 2()()2 () ()2 ()0jjj jjjjjjjjjxb lxlx lxblx 再构造一个次数不超过 2n+1 的多项式 ,使得0000000100( )jxx( )jx0 x1jxjx1jxn

22、x因为 是 的二重零点，而 是 的单零点，则011,jjnxxxx( )jx2011( )()()()()()jjjjjnxcxxxxxxxxxx由 ，可得()1jjx20111()()()()jjjjjjjncxxxxxxxxjx( )jx( )jx 从而 和 称为Hermite插值基函数，则Hermite插值问题的解为( )jx210( ) ()( )()( )nnjjjjjHxf xxfxx容易证明：Hermite插值问题的解是惟一的。( )(0,1, )jxjn2( )() ( )jjjxxx lx201( )1 2() ( )njjjijiijxxxlxxx定理定理4.4.2 设函数

23、 f(x) 在区间a, b上具有2n+1 阶连续导数，并在(a, b)内2n+2阶导数存在， 为区间a, b中n+1个互异的节点， 是Hermite插值问题的解。则用插值多项式 近似 f(x) 的截断误差为0 niix21( )nHx21( )nHx2(22)21210( )( )( )( )(),(22)!nnnniifRxf xHxxxn误差估计误差估计)()()(1212xHxfxRnn其中0101(min ,max ,).nnx x xxx x xx一般一般Hermite插值问题插值问题( )( )( )1( )( ),0,1, ,0,1,1jjjmiiiiPxfxyinjm0.nii

24、mm0 niix 设 f(x) 是定义在区间a, b上的可微函数， 为区间a, b中n+1个互异的节点，给定的函数f(x)在节点处的函数值和导数值，求次数不超过m-1的多项式 ,使得其中1( )mPx( )( )( ),( ),0,1, ,1,1jiiiiiif xyfxyinjm例例.设f(x) 是区间a, b上4次可微函数，给定函数及导数表1y2yx( )fx0 x1x2x构造一个次数不超过3 的多项式 ,使得并估计误差。0y1y( )f x3( )P x33111( )( )(0,1,2),()()iiiP xf xyiP xfxy例例.设f(x) 是区间a, b上4次可微函数，给定函数

25、及导数表1iy3( )P xx( )fxix1ix构造一个次数不超过3 的多项式 ,使得并估计误差。iy1iy( )f x33()(),()()(,1)jjjjjjP xf xyP xfxyji iiyHermite插值问题的解为31111( )( )( )()( )( )( )()( )iiiiiiiiP xf xxf xxfxxfxx截断误差为2211111( )(),( )()iiiiiiiiiixxxxxxxxxxxxxx221111111( )12,( )12iiiiiiiiiiiiiixxxxxxxxxxxxxxxxxx(4)22331( )( )( )( )() ()4!iifR

26、 xf xP xxxxx4.5 分段低阶插值 Runge现象例： 1 , 1 2511)(2xxxf等距节点构造10次Lagrange插值多项式)(10 xLx)()(10 xLxf-0.900.047061.57872-0.700.07547-0.22620-0.500.137930.25376-0.300.307690.23535例：例：在在 5, 5上考察上考察 的的Ln(x)。取。取211)(xxf),., 0(105niinxi -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端点附近抖动端点附近抖动越大，称为越大，

27、称为Runge 现象现象Ln(x) f (x) 是否次数越高越好呢？ 分段线性插值每个小区间上，作线性插值,),()()(11111iiiiiiiiiiixxxxfxxxxxfxxxxxs, )()(1iiinxxxxSxp(1),)(baCxpn(2)(xpn在每个小区间上为一个不高于1次的多项式特性特性误差估计,1iixxx2121)2(22M )(!2)()()(iiiiixxxxxxfxSxf可以看出nxfxpn),()(2)2 , max |( )|,max ixa bMfxhh222()|( )( )|, , 88nnMba Mf xpxhhxa b 分段Hermite插值 每个小

28、区间上，作Hermite插值1iy( )iS xx( )fxix1ix构造一个次数不超过3 的多项式 ,使得iy1iy( )f x()(),()()(,1)ijjjijjjS xf xyS xfxyji iiy子区间 上Hermite插值多项式为1111( )( )( )()( )( )( )()( )iiiiiiiiiS xf xxf xxfxxfxx在区间a, b上分段Hermite插值问题的解为2211111( )(),( )()iiiiiiiiiixxxxxxxxxxxxxx221111111( )12,( )12iiiiiiiiiiiiiixxxxxxxxxxxxxxxxxx, )(

29、)(1iiinxxxxSxp1 ,iix x误差估计可以看出nxfxpn),()(4)4 , max |( )|,max ixa bMfxhh4344()|( )( )|, , 384384nnMba Mf xpxhhxa b (4)2214411( )|( )( )| |() () |4! | , ,4! 16iiiiiiiff xS xxxxxMxxxx x 分段低阶插值 优点：收敛 缺点：不够光滑。4.6 样条插值1.1.背景背景： 实际问题中，构造函数f(x)的近似除利用节点处函数值的条件外，还希望近似函数具有较好的光滑性、保凸性和流线型。2. 样条函数样条函数01naxxxb: 对区

30、间a, b的一个分划( , ).pSk如果函数 满足如下条件：(1) 在每个子区间 内是次多项式；(2) 及其 阶导数在a, b上连续，则称 是对应于分划 的k 次多项式样条函数样条函数， 称为样条节点， 称为内节点， 称为边界节点。 这样k 次样条函数的全体记为 ( )S x( )S x( )S x1 ,(0,1,1)iix xin01,nx xx( )S x1,2,1k 11,nxx0,nx x3. 二次样条插值二次样条插值01naxxxb: 给定区间a, b的一个分划( )( ,2)pS xS并给定函数 f(x)在节点 处的函数值，求2次样条函数 满足如下条件：01,nx xx( )S

31、x问题的提法问题的提法 称 为函数 f(x)关于分划 的2次样条插值函数。( )( )(0,1, ).iiS xf xin1 ,(0,1,1)iix xin,(0,1, )iiia b c in 由于 在 上是2次多项式，即( )( ,2)pS xS其中共有3n个待定参数 。确定 也就是要确定3n个待定参数。( )S x( )S x21( )( ), , (0,1,1)iiiiiiS xS xab xc xxx xin 因为 满足如下条件：11 ()()(0,1, )()(),()()(1,1)jjjjjjjjjjS xf xjnSxSxSxSxjn共有3n-1个条件。要唯一确定2次样条插值函

32、数，还需要增加一个插值条件。通常利用边界节点处的导数作为补充条件。00()().S xfx 第第1 1边界条件边界条件：给定函数 f(x)在 处的导数值，即要求 还满足如下条件：( )S x( )S x0 x 第第2 2边界条件边界条件：给定函数 f(x)在 处的导数值，即要求 还满足如下条件：nx()().nnS xfx11( )( )()()(), , (0,1,1)iiiiiiiiiS xS xab xxc xxxxxx xin( )( )(0,1, )iiS xf xin定理定理4.6.1 二次样条插值问题的解存在且唯一。 设待求 的分段表达式为1( ), ,iiiiiaf xbf x

33、 x二次样条插值问题的解二次样条插值问题的解由插值条件可得( )( ,2)pS xS111,0,1,1iiiiiibc hbc hin1iiihxx00()()S xfx记01000,()f x xfxch由第1边界条件可得因为S(x)在a, b上连续可微，则在内部节点处有从而(0)(0),0,1,1iiS xS xin11( )( )()()(), , (0,1,1)iiiiiiiiiS xS xab xxc xxxxxx xin于是010001111,() ,1,1iiiiiiiiif x xfxchc hf x xf xxcinhh 因此，对第1边界条件，2次样条插值问题的解存在且唯一。

34、类似可证明：对第2边界条件，2次样条插值问题的解存在且唯一。1( ), ,0,1,1iiiiiaf xbf x xin定理定理4.6.2 设函数 f(x) 在区间a, b上具有4阶连续导数， 为a, b中n+1个等距节点， 是2次样条插值问题的解。则对等距节点，即 ，可以证明如下结论。0 niix(0,1,1)ihh in( )S x32( )( ),( )( ),( )( ),f xS xLhfxS xLhfxSxLh 误差估计误差估计其中(3)(4)45( )()( ).312Lfxbafx4. 三次样条插值三次样条插值01naxxxb: 给定区间a, b的一个分划( )( ,3)pS x

35、S并给定函数 f(x)在节点 处的函数值，求3次样条函数 满足如下条件：01,nx xx( )S x问题的提法问题的提法 称 为函数 f(x)关于分划 的3次样条插值函数。( )( )(0,1, ).iiS xf xin1 ,(0,1,1)iix xin,(0,1, )iiiia b c d in 由于 在 上是3次多项式，即( )( ,3)pS xS其中共有4n个待定参数 。确定 也就是要确定4n个待定参数。( )S x( )S x231( )( ), , (0,1,1)iiiiiiiS xS xab xc xd xxx xin 因为 满足如下条件：111()()(0,1, )()()(1,

36、1)()()(1,1)()()(1,1)jjjjjjjjjjjjjjS xf xjnSxSxjnSxSxjnSxSxjn共有4n-2个条件。要唯一确定3次样条插值函数，还需要增加两个插值条件。00()(),()().nnS xfxS xfx第第1 1边界条件边界条件：给定函数 f(x)在 处的一阶导数值，即要求 还满足如下条件：( )S x( )S x0,nx x第第2 2边界条件边界条件：给定函数 f(x)在 处的二阶导数值，即要求 还满足如下条件：0,nx x00()(),()().nnSxfxSxfx第第3 3边界条件（周期边界条件）边界条件（周期边界条件）：如果给定函数 f(x)为周期

37、b-a的周期函数，则要求S(x)也是周期函数，即要求S(x)还满足如下条件：( )( )0()(),0,1,2.kknSxfxk定理定理4.6.3 在第1,2,3边界条件下，三次样条插值问题的解存在且唯一。三次样条插值问题的解三次样条插值问题的解 m关系式设,)(,)()()(),()(,)(11111iiiiiiiiiiiiiiiiixxxmxSmxSxfxSxfxSmxS则这是Hermite插值问题，记iiixxh1213211321221121( )2()()( )1 2()()()1 ()()1 ()()iiiiiiiiiiiiiiiiiiiS xhxxxxf xhhxxxxf xhx

38、xxxmhxxxxmh131312126 ( )2() ( )6 2() ()1 6()2 1 6()2 iiiiiiiiiiiiiiiiiSxhxxf xhhxxf xhxxh mhxxh mh由)( )( 1iiiixSxS111112iiiiiiiiihhmmmhhhh111111( )()()( )3iiiiiiiiiiiihf xf xhf xf xhhhhhhiici1, 1ni112(, ,)iiiiiif xxf x x0111122221111222nnnnnmmcmcmcm两个边界条件即iiiiiicmmm1121, 1ni第1边界条件nnmxSmxS)( ,)( 00第2

39、边值条件nnMxSMxS)( ,)( 00nnnnnnMhxxfmmMhxxfmm2,322,3211011010周期边界条件)( )( ),( )( 00nnxSxSxSxS M关系式设,)( ,)( )()(),()(,)( 11111iiiiiiiiiiiiiiiiixxxMxSMxSxfxSxfxSMxS则记iiixxh111( )iiiiiiixxxxS xMMhh3次多项式求导2次后为线性函数,则积分2次33111()()( )()()66iiiiiiiiiiixxxxS xMMc xxd xxhh由 可确定 。iiiiiidMMM1121, 1ni111111()( )( )()66 ,iiiiiiiiiiif xf xf xf xf xx xhhhh11( )( ),()()iiiiiiS xf xS xf x,iic d1( )( )iiiiSxS x由 可得再加上边界条件，利用严格对角占优矩阵的性质，可导出三次样条插值问题有唯一解。