计算方法第三章(插值法)

1、第三章第三章 插值法插值法 第一节第一节 插值多项式的基本概念插值多项式的基本概念 假设已经获得假设已经获得n+1点上的函数值点上的函数值 即提供了一张数据表即提供了一张数据表 如何利用这张表求如何利用这张表求 f (x) 在在其他给定点上的合其他给定点上的合 理的近似值呢理的近似值呢? ,0,1, , ii f xy in x 0 x 1 x 2 x n x yf x 0 y 1 y 2 y n y 在实验数据的处理、难以计算的函数的逼近、在实验数据的处理、难以计算的函数的逼近、 数值微积分等方面需要解决这样的问题，这是数值微积分等方面需要解决这样的问题，这是 数值逼近中的一个基本问题。一个

2、自然的想法数值逼近中的一个基本问题。一个自然的想法 是找一个简单易计算的函数是找一个简单易计算的函数 x)，使得，使得 ()(0,1, ) ii xyin 将将(x)作为作为 f (x) 在一定范围内的近似函数，对于在一定范围内的近似函数，对于 这个范围内的某个给定点这个范围内的某个给定点a，取，取 f (a) (a)。这种。这种 近似方法称为近似方法称为插值法插值法。(x)称为称为 f (x)的以的以xi (i=0,1,n)为插值节点的为插值节点的插值函数插值函数。插值节点上。插值节点上 所给的函数值称为所给的函数值称为样本值样本值。 (xi)=yi 称为称为插值条件插值条件。函数值待求的点

3、称为函数值待求的点称为插值插值 点点。插值节点所界定的范围称为。插值节点所界定的范围称为插值区间插值区间。如。如 果所给插值点位于插值区间之内，这种插值过程果所给插值点位于插值区间之内，这种插值过程 称为称为内插内插，否则称为，否则称为外插外插。 若用多项式来作为插值函数，则称其为若用多项式来作为插值函数，则称其为插值插值 多项式。多项式。通常用通常用 n 次多项式作为次多项式作为n+1个插值条件个插值条件 的插值多项式。如果插值条件只是给出节点的函的插值多项式。如果插值条件只是给出节点的函 数值，称为数值，称为拉格朗日插值拉格朗日插值，如果既有函数值也有，如果既有函数值也有 节点处函数的导数

4、值，称为节点处函数的导数值，称为埃尔米特插值埃尔米特插值。 因式定理：多项式因式定理：多项式P(x)具有具有r 次因式次因式 (x-a)r 的的 充充 要条件是要条件是 最一般的插值条件：最一般的插值条件： 是是 重插值节点，重插值节点， (1)(1) ( ),( ),( ) ii rr iiiiii xyxyxy 定理：给定上述定理：给定上述n+1个插值条件，则个插值条件，则n次插值次插值 多项式是多项式是存在唯一存在唯一的。的。 i r i x 01 1 m rrrn (1) ( )( )( )0 r P aP aPa 设函数设函数 y = f (x) 在闭区间在闭区间 a , b 上有上

5、有n + 1 阶导数，阶导数， 满足前面的一般插值条件，且插值节点各不相同，满足前面的一般插值条件，且插值节点各不相同， 则插值截断误差为则插值截断误差为 01 (1) 01 1 ( )( )( )( )( ) (1)! ( )() ()() m n nnn rrr nm R xf xP xfx n xxxxxxx 01 01 1 , m m rrrn x xxx 在之间，与 有关 证明思路：构造辅助函数，用罗尔定理。证明思路：构造辅助函数，用罗尔定理。 33 (4)2 012 ( )( )( ) 1 ( )() ()() 4! R xf xP x fxxxxxx 300300311322 (

6、),(),( ),()P xy P xy P xy P xy 2 3012 2 3012 ( )( )( )() ()() ( )( )/() ()() g tf tP ttxtxtx f tP txxxxxx 值得注意的是在较大区间上进行插值时，误差可能会值得注意的是在较大区间上进行插值时，误差可能会 很大！另外，一般情况下，外推不如内插好！很大！另外，一般情况下，外推不如内插好！ 第二节第二节 Lagrange插值公式插值公式 插值条件是插值条件是 0011 (,),( ,),(,) nn xyx yxy Lagrange插值实质上是求通过上面插值实质上是求通过上面 n+1 个点的个点的

7、n 次多项式。次多项式。 一次插值：一次插值： 问题为求一次多项式，即一次函数，过以下问题为求一次多项式，即一次函数，过以下 两点：两点： 容易求出，该函数为：容易求出，该函数为： 0011 (,), ( ,)xyx y 01 01 0110 xxxx yyy xxxx 一般插值问题：求过一般插值问题：求过n+1n+1个点个点 的不超过的不超过n n次多项式次多项式 。 称为称为LagrangeLagrange插值基函数，满足：插值基函数，满足： 0011 (,), (,),(,) nn xyx yxy ( ) n L x 0 ( )( ) n nii i L xy l x ( ) i l x

8、 1, (), 0, ijijij ij l x ij 011 011 ()()()() ( ) ()()()() iin i iiiiiin xxxxxxxx l x xxxxxxxx 求过求过n+1n+1个点的不超过个点的不超过n n次多项式的插值多项次多项式的插值多项 式是唯一的。式是唯一的。 插值公式的误差为：插值公式的误差为： (1) 01 () ( )( )( )()()() (1)! n x nnn f Rxf xL xxxxxxx n (1) 1 , 1 01 max( ) ( )()()() (1)! n n xa b n nn Mfx M R xxxxxxx n 计算程序计

9、算程序 框图框图 始 终 输入数据 x 及 ,0,1, ii x yin 0,0yi 计算权系数 i 存单元 中 ?in i yyy = 1ii Lagrange 公式的计算流程 第三节第三节 逐次线性插值逐次线性插值 函数函数 y = f (x)在节点在节点 上的插值多项上的插值多项 式记为式记为 ，则有，则有 , ijk x xx , , ( ) i jk Nx , , , , , , , , , , , ( )( )( ) ( )( ) () i jk p qi jk p i jk qi jk p p qp NxL xNx NxNx xx xx Aitken（埃特肯）算法埃特肯）算法 N

10、eville（列维尔）算法列维尔）算法 0,1, ,0,1, 0,1,1,0,1, ( )( )( ) ( )( ) () k pk kpk k pk NxL xNx NxNx xx xx ,1,1,1 1,2,1,1 ( )( )( ) ( )( ) () i iki ik iiki ik i ki NxL xNx NxNx xx xx Aitken（埃特肯）算法埃特肯）算法 0 x 0 N 1 x 1 N 0,1( ) Nx 2 x 2 N 0,2 ( )Nx 0,1,2 ( )Nx 3 x 3 N 0,3 ( )Nx 0,1,3 ( )Nx 0,1,2,3 ( )Nx Neville（列

11、维尔）算法列维尔）算法 0 x 0 N 1 x 1 N 0,1( ) Nx 2 x 2 N 1,2 ( )Nx 0,1,2 ( )Nx 3 x 3 N 2,3 ( )Nx 1,2,3 ( )Nx 0,1,2,3 ( )Nx 例子：求方程例子：求方程 x3-2x-5=0 在在(2 , 3)内的根内的根 思路思路: 设设 y = f(x) =x3-2x-5 ，其反函数为，其反函数为 x=f -1(y)，则，则 根为根为x* =f -1(0) 。先用。先用3= f -1(16)， 2= f -1(-1)插值，得插值，得 N0,1 (y) f -1(y), 计算计算N0,1 (0)= 2.058823

12、, f(2.058823) = -0.39 ，以，以-0.39为新的节点，继续为新的节点，继续 yixiNi,i+1 (0)Ni,i+1,i+2 (0) Ni,i+1,i+2,i+3 (0) 163 -122.058823 -0.392.058232.0965892.095659 0.0122.0956592.0945292.0945542.094553 1.51E-52.094553 第四节第四节 牛顿插值牛顿插值 设插值点为设插值点为 插值多项式形如插值多项式形如 称为称为Newton形式的插值多项式。形式的插值多项式。 001122 (,),( ,),(,),(,) nn xfxfxfx

13、f 010201 011 ( )()()() ()()() n nn Nxcc xxcxxxx cxxxxxx 差商概念：差商概念： 设函数设函数 f (x) ，定义函数在两个不同点的一阶差商为定义函数在两个不同点的一阶差商为 三个不同点的二阶差商为：三个不同点的二阶差商为： 在点在点 处处 K+1 阶差商为：阶差商为： ( )() ( ,),(,) ij ijij ij f xf x f x xxxij xx ( ,)(,) ( ,) ijjk ijk ik f x xf xx f x xx xx 011 , kk x xxx 0111 011 01 (,)( ,) (,) kkk kk k

14、 f x xxf xx x f x xx x xx 给定给定 n +1个点的函数值个点的函数值 0010 01201 01011 1 01011 ( )()(,)() (,)()() (,)()()() ( )( ) (,)()()() n nn nn nn Nxf xf x xxx f x x xxxxx f x xxxxxxxx NxNx f x xxxxxxxx (),0,1,2, ii f xfin（） 则牛顿插值公式为：则牛顿插值公式为： 差商的计算简表：差商的计算简表： 00 1101 2212012 33231230123 4434234123401234 ( ) ( )( ,

15、) ( )( , )( , , ) ( )( , )( , , )( , , , ) ( )( , )( , , )( , , , )( , , , , ) x f x x f xf x x x f xf x xf x x x x f xf x xf x x xf x x x x x f xf x xf x x xf x x x xf x x x x x 例子：例子：用用0、30、45、60、90五个点作出五个点作出sinx 牛顿插值多项式。牛顿插值多项式。 做差商表做差商表 00 300.50.016667 450.70710.013807-0.000063556 600.8660.0105

16、95-0.00010707-0.0000007 9010.0044658-0.0001362-0.00000049 牛顿插值的截断误差：牛顿插值的截断误差： 1 01101 ( )( ) (,)()()() nn nn NxNx f x xxxxxxxx 1111 01110111 ()()() (,)()()() nnnnn nnnnn f xNxNx f x xxxxxxxx 1 0101 ( )( )( ) (, )()()() nn nn f xNxNx f x xxxxxxxxx 0101 ( )( )( ) (, )()()() nn nn Rxf xNx f x xxxxxxxx

17、x 例子：例子：用用0、90、180、270、360五个点作出五个点作出sinx 牛顿插值多项式。牛顿插值多项式。 做差商表做差商表 00 9010.01111 1800-0.01111 -1.235e-4 270-1-0.0111104.572e-7 36000.011111.235e-44.572e-70 差商的性质 差商的计算公式：差商的计算公式： 01 0 00 () (,) () ( )() ,()() k j k j kj kk kikjji ii ij f x f x xx x xxxxxx 通过比较插值多项式的Lagrange形式和 Newton形式即可得。 ()()()()

18、( ,)(,) ijji ijji ijji f xf xf xf x f x xf xx xxxx ( ,)(,)( ,) ijkjikikj f x xxf xx xf x xx 010101 ( )( )( ), (,)(,)(,) nnn f xu xv x f x xxu x xxv x xx 若则 差商的对称性：差商的对称性： 差商的线性性：差商的线性性： 由于由于n次插值多项式是唯一的，所以牛顿插值公式与次插值多项式是唯一的，所以牛顿插值公式与LagrangeLagrange 插值多项式一样，这意味着余项也一样，插值多项式一样，这意味着余项也一样，LagrangeLagrange

19、余项为：余项为： 所以牛顿余项也一样，所以牛顿余项也一样， (1) 01 () ( )()()() (1)! n x nn f R xxxxxxx n 01101 (1) 01 ( ) 01 ()()()() ( ,) () ()()() (1)! ( ) (,) ! nnn n x n k k xxxxxxxxf x x xx f xxxxxx n f f x xx k 差商与导数的关系差商与导数的关系 重节点差商重节点差商 推论：当推论：当n个节点全为同一个点，牛顿插值变成个节点全为同一个点，牛顿插值变成 泰勒多项式。泰勒多项式。 ( ) 01 1 (,)( ) ! n n f x xxf

20、 n ( ) 0000 1 (,)() ! n f x xxfx n 差商的导数差商的导数 n 次多项式的的次多项式的的 1 阶差商是阶差商是 n-1 次多项式。次多项式。 (1)* 011011 () (, )(, , ) (1)! n nn df f xxxxf xxxx x dxn 推论：设推论：设 p(x) 是是 n 次多项式，次多项式，k n 时时 k 阶差商阶差商 是是 n - k 次多项式，次多项式，k n 时时 k 阶差商为零。阶差商为零。 000 00 0 0 0 ( )( )()()0( )() ( ) ( )()() ( ) ( )() ( ,)( ) g xp xp x

21、g xg xxx q x p xp xxx q x p xp x p x xq x xx 差分差分 设函数设函数 ，定义，定义 为该函为该函 数在数在 i 点的点的一阶向前差分一阶向前差分，记为，记为 类似地，定义类似地，定义二阶向前差分为二阶向前差分为： K 阶差分为阶差分为： 此差分称为此差分称为向前差分向前差分。 ( ) ii f xxf在的函数值为 1ii ff , (0,1,2,) i fi 2 1 , (0,1,2,) iii fffi 11 1 , (0,1,2,) kkk iii fffi 类似地，类似地，向后差分向后差分定义为：定义为： 中心差分中心差分定义为：定义为： 1

22、, (0,1,2,) iii fffin 11 1 , (0,1,2,) kkk iii fffi 1/21 , (0,1,2,) iii fffin 1/21/2 , (0,1,2,) iii fffin 11 1/21 , (0,1,2,) kkk iii fffi 差商与差分的关系：差商与差分的关系： 等距节点时等距节点时 0/2 01 ()()() (,) ! nnn nn n nnn f xf xf x f x xx n hn hn h 0i xxih 第五节第五节 带导数的插值带导数的插值 问题的提出：如果在已知节点处不仅知道函数值，问题的提出：如果在已知节点处不仅知道函数值， 同

23、时还知道导数同时还知道导数值，这样，插值多项式就要求在值，这样，插值多项式就要求在 已知节点处与已知节点处与函数值和导数值都相等函数值和导数值都相等。这就是所。这就是所 谓谓埃尔米特（埃尔米特（Hermite）插值）插值。 1、推广牛顿插值法、推广牛顿插值法 如果已知如果已知某个点某个点 i 的的 ，则，则 插值节点应视为插值节点应视为 个相同节点个相同节点 ，并注意到，并注意到k+1 重节点的差商重节点的差商 (1) , i r iiii y y yy i r i x ( ) 1 ( ) ( ,) ! k i iiii k fx f x x xx k 例子：例子：已知关于函数已知关于函数 y

24、 = f (x)的函数值、导数值的函数值、导数值 00 1111 221 1:0 0:4,0,6 1:2,5 xy xyyy xyy xif(xi) f(xi, xi+1) f(xi, xi+1 ,xi+2) 3阶差商阶差商4阶差商阶差商5阶差商阶差商 -10 0-4-4 0-404 0-403-1 1-222-10 1-253121 (0,0)(0)0 (0,0,0)(0)/2!3 (1,1)(1)5 fy fy fy 2、构造基函数法构造基函数法 已知函数在已知函数在n个不同的节点处的函数值和导数值：个不同的节点处的函数值和导数值： 求次数不超过求次数不超过2n-1次的多项式次的多项式 设

25、想其具有形式设想其具有形式： 要求：要求： ,(1,2, ) iii xyyin 2121 ( ),( ),(1,2, ) niinii HxyHxyin 21 11 ( )( )( ) nn njjjj jj Hxy h xy h x ( ),( )0,1,2, ( )0 ,( ),1,2, jiijji jijiij h xh xj in h xhxj in 由条件可得：由条件可得： 此外，由此外，由 得：得： 2 ( )()( ) jj h xAxB Wx 111 111 ()()()() ( ) ()()()() jjn j jjjjjjn xxxxxxxx W x xxxxxxxx

26、()1 ,()0 jjjj h xh x 1 2() 2()()0 12() j jj jjj jjj AxB AWx AAxB Wx Bx Wx 2 ( )12()()( ) jjjjj h xWxxxWx 同理：同理： 由由 ，可得：，可得： 最后，得到埃尔米特插值公式：最后，得到埃尔米特插值公式： 2 ( )()( ) jjj h xC xx Wx ()1 jj h x 22 ()11( )()( ) jjjjj CWxCh xxx Wx 21 11 22 11 ( )( )( ) 1 2()()( )()( ) nn njjjj jj nn jjjjjjjj jj Hxy h xy h

27、 x WxxxWx yxx Wx y 特别，当特别，当 n=2 时，三阶埃尔米特多项式为：时，三阶埃尔米特多项式为： 311322311322 (),(),(),()HxyHxyHxyHxy 2 12 31 1212 2 21 2 2121 22 21 1122 1221 ( )(12)() (12)() ()()()() xxxx Hxy xxxx xxxx y xxxx xxxx xxyxxy xxxx 埃尔米特插值公式唯一。埃尔米特插值公式唯一。 误差估计：设被插值函数在插值区间上误差估计：设被插值函数在插值区间上2n次连续可次连续可 导，则在导，则在n个节点上的个节点上的2n-1次插值

28、多项式的余项为：次插值多项式的余项为： 特别，对于特别，对于2个节点个节点3次插值，余项为：次插值，余项为： 2121 (2 ) 2 12 ( )( )( ) () ()()() (2 )! nn n x n Rxf xHx f xxxxxx n (4) 22 3312 () ( )( )( )() () 4! x f R xf xHxxxxx 例子：例子： 3333 (0)0,( )0,(0)1 ,( )1HHHH sinyx 22 3 ( )()()() xx Hxxx 如用距离较小的两个点插值，效果会好得多如用距离较小的两个点插值，效果会好得多 33 33 (0)0,(/2)1, (0)

29、1 ,(/2)0 HH HH 22 3 /2/2 ( )(12)()() /2/2/2 xxx Hxx 第六节第六节 样条函数样条函数 由于被插值函数高阶导数未知，因此，如果高由于被插值函数高阶导数未知，因此，如果高 阶导数随阶数增长出现无限增长，则由误差公阶导数随阶数增长出现无限增长，则由误差公 式可知，高阶插值公式就不一定无限接近被插式可知，高阶插值公式就不一定无限接近被插 值函数。这称为值函数。这称为龙格（龙格（Runge)现象现象。 所以，在进行多项式插值时，不宜进行高次多所以，在进行多项式插值时，不宜进行高次多 项式插值。项式插值。 一个解决的途径是一个解决的途径是分段低次插值分段低

30、次插值。 样条函数：给定区间一个样条函数：给定区间一个划分划分 如函数如函数 S(x) 满足下面条件：满足下面条件： （1）在每个小区间）在每个小区间 上为上为m 次多项式；次多项式； （2） S(x) 直至直至m1 阶导数在整个区间上连续。阶导数在整个区间上连续。 则称则称 S(x) 是关于该划分的是关于该划分的 m 次次样条函数样条函数，划分点，划分点 称为节点，称为节点，m3 时，就是最常用的时，就是最常用的 3 次样条函数。次样条函数。 01 , ,: N a baxxxb 1 ,(1,2,) jj xxjN 样条函数插值：样条函数插值：对给定的插值条件，寻找合适的样条对给定的插值条件

31、，寻找合适的样条 函数作为插值函数，使其满足插值条件。函数作为插值函数，使其满足插值条件。 3次样条插值三弯矩方法的基本思想：次样条插值三弯矩方法的基本思想： 将样条函数在每一个子区间端点的二阶导数值当作参将样条函数在每一个子区间端点的二阶导数值当作参 数，则用这两个二阶导数值可以将样条函数表示出来，数，则用这两个二阶导数值可以将样条函数表示出来， 再利用衔接条件，即每一段样条函数在相邻两个子区间再利用衔接条件，即每一段样条函数在相邻两个子区间 端点处的二阶导数相等，建立求解二阶导数的方程组。端点处的二阶导数相等，建立求解二阶导数的方程组。 设设S(x)在每个小区间在每个小区间 端点的二阶导端

32、点的二阶导 数为：数为： 则：则： 记记 ， 将上式积分两次，并利用端点函数值已将上式积分两次，并利用端点函数值已 知，有：知，有： 1 ,(1,2,) jj xxjN 11 (),() jjjj SxMSxM 1 1 11 ( ) jj jj jjjj xxxx SxMM xxxx 33 1 1 22 11 1 1 ()() ( ) 66 ()() 66 ,1,2, jj jj jj jjjjjj jj jj jj xxxx S xMM hh MhxxM hxx yy hh xxxjN 1jjj hxx 我们注意到，在相邻的两个子区间我们注意到，在相邻的两个子区间 和和 的共同端点处，样条函

33、数一阶导数相等，的共同端点处，样条函数一阶导数相等， 经过化简，最后得到：经过化简，最后得到： 11jjj xxx 1 , jj xx 1 , jj xx 11 1 1 111 1 2 ,1,1,2,1 ()/()/ 6 jjjjjj j jjj jj jjjjjj j jj MMMd h jN hh yyhyyh d hh 注意到上面的方程组总共只有注意到上面的方程组总共只有 N1个方程，而未知数却共有个方程，而未知数却共有 N +1 个，因此，要求解方程，还需要补充两个条件（即两个个，因此，要求解方程，还需要补充两个条件（即两个 方程），通常有以下几种方案之一方程），通常有以下几种方案之一

34、: 1、给出端点一阶导数值、给出端点一阶导数值 ，这相当于增加两个方程；，这相当于增加两个方程； 2、给定端点二阶导数值，得方程：、给定端点二阶导数值，得方程： 特别，令二阶导数在端点为零，得特别，令二阶导数在端点为零，得 10 010 11 1 1 6 2() 6 2() NN NNN NN yy MMy hh yy MMy hh 0 , N yy 00 , NN MyMy 0 0 ,0 N MM 3、样条件函数在第一个和最后一个区间上为二次多项样条件函数在第一个和最后一个区间上为二次多项 式，即样条函数在第一和最后一个区间上的二阶导式，即样条函数在第一和最后一个区间上的二阶导 数为常数，得

35、两个方程：数为常数，得两个方程： 总之，以上三种补充条件下，可将方程组统一写为：总之，以上三种补充条件下，可将方程组统一写为： 011 , NN MMMM 000 1111 1 20 2 02 N NNN Md Md Md 4、周期性条件（这只有在给的初值满足、周期性条件（这只有在给的初值满足 时才能用），时才能用）， 此时，由周期性，此时，由周期性， ，就得到两个，就得到两个 方程；第一个方程为方程；第一个方程为 ，第二个方程为，第二个方程为 最后一个方程为：最后一个方程为： 最后，方程组为：最后，方程组为： 0N yy 1111 , NN yyMM 10112111211 22 N MMMdMMMd 0N MM 11 11 2 2 NNNNNN NNNNN MMMd MMMd 1111 2222 1 2 2 2 N NNNN Md Md