数值分析插值ppt

1、第三章 插 值 法 v引言 v拉格朗日插值公式 v牛顿 (Newton) 插值v埃尔米特 (Hermite) 插值v逐步线性插值v样条插值v数据拟合1 引 言 发展历史发展历史 应用应用 插值问题的提出插值问题的提出 插值问题所需研究的问题插值问题所需研究的问题等距节点内插公式刘焯（隋 公元544610年）不等距节点内插公式张遂（唐 公元683727年）等距节点一般插值公式Newton & Gregory (17世纪）非等距节点一般插值公式J.L.Lagrange (18世纪）发展历史应应 用用v对观测数据的处理对观测数据的处理v函数的近似表示函数的近似表示v曲线曲面拟合曲线曲面拟合v

2、导出其它数值方法的依据（如数值积分、导出其它数值方法的依据（如数值积分、数值微分、微分方程数值解等）数值微分、微分方程数值解等）以近似计算函数值为例来说明散点上的函数值，即已知函数表例：设在实际问题中，某些变量之间的函数关系是存在的，但通常不能用式子表示，只能由实验、观测得到 yf x 在一系列离xy0 xnx1x0y1yny ijxxij,如何计算 fx 01ixx in, , ？我们希望寻求一个简单且易于计算的函数 P x来近似 fx f xP x ，即，一般 P x可选为多多项式、三角多项式、有理函数或样条函数等。有些函数虽有表达式，但较复杂，计算函数值不经济，这时也希望用简单的函数来逼

3、近。插值问题的提出 已知函数已知函数 在区间在区间 上有上有yf x( ) 01naxxxb ，求一个多 iiyfxin(),0,1, a b,定义，且已知 ，其中 yP x 项式,使其满足 iiP xy( ) , ,i0 1n 即要求该多项式的函数曲线要经过 ( )yf x 上已知的这n+1个点 0011nnx yx yx y,同时在其它点 上估计误差为 ,xa b ( )( )( )R xf xP xY( )p x( )f x0 x1x1nxnx2x0y1y2y1nynyX研究问题 若满足条件的若满足条件的 存在，又如何构造？存在，又如何构造？ nPx nPx 满足插值条件的多项式满足插值

4、条件的多项式 是否存在，是否存在，唯一？唯一？ nPx fx 用用 近似代替近似代替 的误差估计？的误差估计？2 拉格朗日插值v插值多项式的存在唯一性插值多项式的存在唯一性 v拉格朗日插值多项式拉格朗日插值多项式 插值基函数插值基函数 插值基函数的构造插值基函数的构造 n次拉格朗日型插值多项式次拉格朗日型插值多项式v截断误差截断误差v数值实例数值实例v拉格朗日插值多项式的优缺点拉格朗日插值多项式的优缺点插值多项式的存在唯一性Theorem. 存在唯一的存在唯一的n 次多项式次多项式 （1.1) 满足条件满足条件01( )nnnP xaa xa x0 1, , .niiPxyin证明：由证明：由

5、(1.1)可得可得 (1.2) （1.21.2）为一个你）为一个你n n1 1未知量未知量 的线性方程的线性方程组，要证明插值多项式存在唯一，只要证组，要证明插值多项式存在唯一，只要证明参数明参数 存在且唯一，即只要证明其系数存在且唯一，即只要证明其系数行列式不为零即可。行列式不为零即可。 nnnnnnnnnaa xa xyaa xa xyaa xa xy010000111101 iaia 方程组（方程组（1.21.2）的系数行列式为）的系数行列式为 此为范德蒙行列式。利用行列式性质可此为范德蒙行列式。利用行列式性质可得系数行列式为得系数行列式为 nnnnnnnnxxxxxxVxxxxxx20

6、00211101211(,)1 ninnijijVxxxxx10110(,)() 由于由于 时时 ，故所有因子，故所有因子 ，于是于是 即插值多项式存在唯一。即插值多项式存在唯一。 ij ijxx ijxx0 nnVxxx01(,)0 2001 ! 1.2121 120,9.7 10niinnannnnn如果线性方程组（）的系数行列式不为零，则该方程组有唯一解。若由克莱姆(Cramer)法则求解，则需要计算个阶行列式并作次除法，而每个阶行列式计算需作次乘法，计算量十分惊人。如阶线性方程组 需次乘法。如果用每秒一亿次乘法运算的计算机要。可见其在理论上是绝对正确，但在 较大时，在实际计算中确实不3

7、0万年可行的。 由方程组（由方程组（1.2）求）求 的系数的系数 ，计算量大，计算量大， 且难于得到且难于得到 的简单表达式，下面通过找插值的简单表达式，下面通过找插值 基函数的方法，可得到插值多项式基函数的方法，可得到插值多项式 的简单表的简单表 达式。达式。( )nP x ia( )nP x( )nP x线性插值线性插值。xpxxxxyyyxpyxyxxpyxpyxpxp达方式但是我们可以换一种表当然是唯一的一次多项式由直线的点斜式可得的一条直线和为过两点满足条件求作一次多项式问题,)()()(:),(),()()(,)(),(:10010101110011110011问题 求作一次式求作

8、一次式 ，使满足条件，使满足条件 从几何图形上看，从几何图形上看， 表示过两点表示过两点 的直线，的直线，因此可表为如下对称形式：因此可表为如下对称形式：其中其中 和和 分别满足条件分别满足条件 可见，插值问题的解可见，插值问题的解 可以通过插值基函数可以通过插值基函数 和和 的组合得出，且组合系数分别是所给数据的组合得出，且组合系数分别是所给数据 。100111,pxypxy 1px 1ypx0011(,),( ,)xyx y 1px 01010110,xxxxlxlxxxxx 10 01 1pxy lxy lx 0lx 1lx000111101,0,1,0lxlxlxlx 0lx 1lx0

9、1,yy拋物插值拋物插值问题 求作二次式求作二次式 ，使满足条件，使满足条件二次插值的几何解释是用通过三个点二次插值的几何解释是用通过三个点 的抛物线的抛物线 来近似考察曲线，故称为拋物插值。类似于线性插来近似考察曲线，故称为拋物插值。类似于线性插值，令值，令易知，易知， 应满足条件应满足条件所以有因子所以有因子 , ,故有，故有，类似的可以构造出类似的可以构造出 。 2px200211222,pxypxy pxy001122(,),( ,),(,)xyx yxy 2ypx 0lx 0001021,0lxlxlx 1200102xxxxlxxxxx 2001122pxlx ylx ylx y

10、12,lxlx1)(,0021xlxxxx又和拉格朗日插值多项式拉格朗日插值多项式1.插值基函数插值基函数定义：若定义：若n次多项式次多项式 在在n+1个节点个节点 上满足条件上满足条件则称这则称这n+1个个n次多项式次多项式 为节为节点上的点上的n次插值基函数。次插值基函数。01( ), ( ),( )nlx l xlx01( ),( ),( )nlxlxlx01nxxx 10 10, , jkkjlxj knkj2. 基函数的构造基函数的构造 由上述定义由上述定义 ，知存在常，知存在常数数 ，使得，使得由由 ，可以定出，可以定出 ，进而得到：，进而得到： 令令()0,ikl xki011(

11、 )()()()()iiiinl xA xxxxxxxxiA()1iil xiA011011()()()()( )()()()()iiniiiiiiinxxxxxxxxl xxxxxxxxx)()()(101nnxxxxxxx则则 于是于是 可改写成可改写成 1011( )()()()() niiiiiiinxxxxxxxxx()ilx110 1( )( ), ,()() niinixl xinxxx3. 3. n n次拉格朗日型插值多项式次拉格朗日型插值多项式 是是n+1个个n次插值基本多项式次插值基本多项式 的线性组合，相应的组合系数是的线性组合，相应的组合系数是即即 是一个次数不超过是一

12、个次数不超过n的多项式的多项式,且满足且满足( )nP x( )nP x01( ), ( ),( )nlx l xlx01,nyyy0 01 10( )( )( )( )( )nnn nk kkP xy lxy l xy lxy lx()niiPxy0,1,in，。拉格朗日插值多项式的截断误差拉格朗日插值多项式的截断误差 若在若在a,b上用多项式上用多项式 来近似代替来近似代替函数函数f (x) ,其截断误差记作其截断误差记作 ，即，即 也称为插值多项式的余项，关于插值也称为插值多项式的余项，关于插值余项估计，有以下定理：余项估计，有以下定理：( )nP x( )nR x( )( )( )nn

13、R xf xP x( )nR x定理：定理：设函数设函数y=f (x) 的的n 阶导数阶导数 y =f (n)(x)在在a,b上连续，上连续，y=f (n+1)(x)在在(a,b)上存在，上存在，插值节点为插值节点为ax0 x1xnb, 是是n次次拉格朗日插值多项式，则对任意拉格朗日插值多项式，则对任意x a,b有：有：其中其中(1)1( )( )( )(1)!nnnR xfxn (a,b), ，01( ) ()()()nnxx xx xx x( )nP x证明证明：由插值多项式的定义，显然有：由插值多项式的定义，显然有构造辅助函数构造辅助函数有有 。反复利用。反复利用Rolle定理，存在定理

14、，存在 (a,b), 使得使得g(n+1)( )=0,即即 ，结论成立。，结论成立。()( )( )0,0,1,niiniR xf xP xin nntg tf tP tf xP xx 000 1, ,ig xg xin 110! nnnffxPxx数值实例数值实例例求过点例求过点(2,0)(4,3)(6,5)(8,4)(10,1)的拉格的拉格朗日型插值多项式。朗日型插值多项式。解解：用：用4次插值多项式对次插值多项式对5个点插值个点插值 00112233442 04 36 58 410 1,xyx yxyx yxy0(4)(6)(8)(10)1( )(4)(6)(8)(10)(2 4)(2

15、6)(2 8)(2 10)384xxxxl xxxxx 1(2)(6)(8)(10)1( )(2)(6)(8)(10)(4 2)(4 6)(4 8)(4 10)96xxxxl xxxxx2(2)(4)(8)(10)1( )(2)(4)(8)(10)(6 2)(6 4)(6 8)(6 10)64xxxxl xxxxx3(2)(4)(6)(10)1( )(2)(4)(6)(10)(8 2)(8 4)(8 6)(8 10)96xxxxl xxxxx4(2)(4)(6)(8)1( )(2)(4)(6)(8)(10 2)(10 4)(10 6)(10 8)384xxxxl xxxxx40 01 12 2

16、3 34 4( )( )( )( )( )( )P xy l xyl xy l xy l xy l x13(4)(6)(8)(10)(2)(6)(8)(10)3849654(2)(4)(8)(10)(2)(4)(6)(10)64961(2)(4)(6)(8)384xxxxxxxxxxxxxxxxxxxx于是有例例. . 已知已知 sin0.32=0.314567,sin0.34=0.333487,sin0.36=0.352274, 用用Lagrange插值计算插值计算sin0.3367的值，并估计截断误差。的值，并估计截断误差。解解：f (x)= sinx ,取取 12021020120102

17、10122120 x x x xx xx xx x x xP xyyyxx xxx xx xxx xx 0011220 32 0 3145670 34 0 3334870 36 0 352274,., .,., .,., .x yx yx y于是有于是有可以发现，结果有六位有效数字的可以发现，结果有六位有效数字的sin x表表完全一致。完全一致。44407689 1003367031456700008389 1005511 1003334870352274000040000803303742.sin0.3367P.截断误差为截断误差为其中其中 故有故有 32012013,! fRxxxxxxx

18、xx x 3201 03145670828coscos. fx01, xx2260 33670 33670 33670 8280 01670 0330 02330 178 10.sin .1 n时恒为时恒为0证明证明: 运用Newton插值公式(6)进行计算时,先计算f(x)关于节点x0,xn的各阶差商.计算过程如下表所示 . xk f(xk) 一阶差商 二阶差商 三阶差商 n 阶差商123onxxxxx0123 nf xf xf xf xf x0112231, ,nnf x xf x xf x xf xx01212321 , ,nnnf x x xf x x xf xxx0123321 ,

19、, , nnnnf x x x xf xxxx0 1 , , , nf x xx计算Nn(x)时,常采用秦九韶算法,即 .00010101201101000110122012101( )( ) () , ()() , , ()() () , , , ( ) ()( , ()( , , ()( , , , () , ,) )nnnnnnnN xf xx x f x xx x x x f x x xx x x xx xf x xxf xx x f x xx x f x x xx xf x xxx xf x xx 下面给出下面给出Newton插值法的计算机插值法的计算机算法算法.开始时开始时,f(k

20、)存放函存放函数值数值f(xk),运算完毕运算完毕f(k)存放存放k阶差商阶差商fx0,xkNewton插值算法(1) 输入: xi, fi;di=fi (i=0,1,n);计算差商 对i=1,2,n 做 (3.1) 对j=i,i+1,n 做 fj=(dj-dj-1)/(xj-xj-i); (3.2) 对j=i,i+1,n 做 dj=fj;(4) 计算插值N(u) (4.1)输入插值点u; (4.2) v=0; (4.3) 对i=n,n-1,1,0 做 v=v(u-xi)+fi;(5) 输出u,v.五 等距节点的Newton插值公式与差分 当插值节点x0,xn为等距分布时,Newton插值公式

21、(6)可以简化. 设插值节点xj=x0+jh, j=0,1,n; h=(b-a)/n称为步长,且x0=a, xn=b. 令x=x0+th,则当x0 xxn时,0tn. 基函数 此时差商也可进一步化简,为此引进差分的概念. 定义 称 f(xi)=f(xi+h)-f(xi) 和 f(xi)= f(xi)-f(xi-h)分别为函数f(x)在点xi处的一阶向前差分和一阶向后差分. .011( )()()()(1)(2)(1)iiixxxxxxxt tttih 一般地,称k阶差分的差分为k+1阶差分,如二阶向前和向后差分分别为 计算各阶差分可按如下差分表进行.22( )( )( ()( )()( )(2

22、 )2 ()( )( )( )( ( )()( )()( )2 ()(2 )iiiiiiiiiiiiiiiiiif xf xf xhf xf xhf xf xhf xhf xf xf xf xf xhf xf xhf xf xhf xh 2300110222102333210231230niiiiiinnnnnnxfffffxfxffxfffxffffxfffff 向前差分表向前差分表 差分具有如下性质: . 性质1(差分与函数值的关系) 各阶差分均可表示为函值fj=f(xj)的线性组合: 性质2(前差与后差的关系): 性质3(多项式的差分)若f(x)Pn(n次多项式类), 则00( 1),(

23、 1)!()!kkkjjkkjjikij kikij kjjjkfC ffC fkCj kj kkii kff ,()!,0,nkknnPknfxa h nknkn其中其中 性质4(差分与差商的关系): 性质5(差分与导数的关系 利用这些性质,可将Newton公式 Nn(x)= f(x0)+(x-x0) fx0,x1+(x-x0)(x-x1) fx0,x1,x2 +(x-x0)(x-xn-1) fx0,xn进一步简化11,!,!kiiiikkkiiiikkffxxxkhffxxxkh1( )! ,( ),()kkiiii kkkii kfk h f x xxh fxx020000( )()(1

24、)(1) (1)1!2!nnnN xN xthtt tt tt nffffn (11)称公式称公式(11)为为Newton向前差分插值公式向前差分插值公式,其余项为其余项为1(1)00(1)()( )()( )(1)!(,)nnnnnt ttnR xR xthhfnx x(12)如果将式如果将式(6)改为按节点改为按节点xn,xn-1,x0的次序排列的的次序排列的Newton插插值公式值公式,即即11110( )() () ,()()() ,nnnnnnnnnN xf xxxf x xxxxxxxf x xx 令令x=xn-th, 则当则当x0 xxn时时,0tn.利用差商与向后利用差商与向后差分的关系差分的关系, 式式(13)可简化为可简化为22( )()(1)(1)2!(1)(1)(1)!nnnnnnnnnNxNxtht tftfft ttnfn (13)(14)称式称式(14)为为Newton向后差分插值公式向后差分插值公式,其余项为其余项为(1)110( )( )()( 1)(1)()(1)!nnnnnnnfRxRxthht ttnnxx22120,nnnnnnnffffff 若要计算的插值点若要计算的插值点x较靠近点较靠近点x0,则用向前插值公式则用向前插值公式(