数值计算方法第05章插值法

1、1 第五章第五章 插值法插值法 拉格朗日拉格朗日Lagrange插值插值 牛顿牛顿Newton插值插值 埃尔米特埃尔米特Hermite插值插值 样条插值样条插值 分段线性差值分段线性差值一、引例一、引例已经测得在某处海洋不同深度处的水温如下：已经测得在某处海洋不同深度处的水温如下：深度（深度（M M） 466 741 950 1422 1634466 741 950 1422 1634水温（水温（o oC C）7.04 4.28 3.40 2.54 2.137.04 4.28 3.40 2.54 2.13根据这些数据，希望合理地估计出其它深度（如根据这些数据，希望合理地估计出其它深度（如500

2、500米，米，600600米，米，10001000米米）处的水温）处的水温. .这就是本章要讨论的这就是本章要讨论的“插值问题插值问题”问题驱动：汽车的刹车距离问题驱动：汽车的刹车距离 司机驾驶汽车时需要根据车速估计汽车的司机驾驶汽车时需要根据车速估计汽车的刹车距离以确保行车安全。刹车距离以确保行车安全。图图2.1.1 某车型干燥路况刹车距离示意图某车型干燥路况刹车距离示意图 美国的某司机培训课程的有如下驾驶规则：正常的驾美国的某司机培训课程的有如下驾驶规则：正常的驾驶条件下对车与车之间的距离的要求是每小时驶条件下对车与车之间的距离的要求是每小时1010英里的速英里的速率可以允许一辆车的跟随距

3、离。实现这一规则的简便方法率可以允许一辆车的跟随距离。实现这一规则的简便方法就是就是 “2 2秒法则秒法则”：这种方法不管车速为多少，后车司机：这种方法不管车速为多少，后车司机从前车经过某一标志开始默数从前车经过某一标志开始默数“一千零一，一千零二一千零一，一千零二”，这样用英文读完就是两秒。如果你在默数完这句话前就到这样用英文读完就是两秒。如果你在默数完这句话前就到了同一标志处，那么你的车和前面的车靠得太近了。了同一标志处，那么你的车和前面的车靠得太近了。 假设车长为假设车长为15英尺，根据这条法则可以得到如图英尺，根据这条法则可以得到如图1.1.2所示的图形，它表明该法则允许的距离间隔和速

4、率成比例，所示的图形，它表明该法则允许的距离间隔和速率成比例，即即 dkv。其中为比例常数其中为比例常数 159010mph88k 英尺图图1.1.2 “2秒法则秒法则”的几何解释的几何解释 下面给出一组经测试得到关于刹车距离与速度的下面给出一组经测试得到关于刹车距离与速度的的较为理想的实验数据，如表的较为理想的实验数据，如表1.1.1所示。要想了解刹所示。要想了解刹车的距离与车速的关系，试建立适当的数学模型，预车的距离与车速的关系，试建立适当的数学模型，预测车辆的总停止距离测车辆的总停止距离d（英尺）关于速度（英尺）关于速度v（英里（英里/小时）小时）的函数，检验的函数，检验2秒法则与驾驶规

5、则是否一致，并尝试寻秒法则与驾驶规则是否一致，并尝试寻找更好的驾驶规则。找更好的驾驶规则。v20253035404550d425673.591.5116142.5173v556065707580d209.5248292.5343401464表表2.1.1 刹车距离实验数据刹车距离实验数据 插值法是一种古老的数学方法。早在插值法是一种古老的数学方法。早在10001000多年前，我国历法上已经记载了应用一次插值多年前，我国历法上已经记载了应用一次插值和二次插值的实例。和二次插值的实例。 伟大的数学家：拉格朗日（伟大的数学家：拉格朗日（Lagrange）、牛顿）、牛顿Newton）、埃尔米特（）、埃

6、尔米特（Hermite）等人分别给出了）等人分别给出了不同的解决方法。不同的解决方法。 生产实践中常常出现这样的问题：给出一批离散样点，要求作出一条通过这些点的光滑曲线，以便满足设计要求或进行加工。反映在数学上，即已知函数在一些点上的值，寻求它的分析表达式。因为由函数的表格形式不能直接得出表中未列点处的函数值，也不便于研究函数的性质。此外，有些函数虽有表达式，但因式子复杂，不容易算其值和进行理论分析，也需要构造一个简单函数来近似它。 8解决这种问题的方法有两类：一类是一类是给出函数f(x)的一些样点值，选定一个便于计算的函数形式，如多项式、分式线性函数及三角多项式等，要求它通过已知样点，由此确

7、定函数f(x)作为f(x)的近似。这就是插值法。另一类方法另一类方法在选定近似函数的形式后，不要求近似函数过已知样点，只要求在某种意义下他在这些点上的总偏差最小。这类方法称为曲线（数据）拟合法。 二、插值问题的定义二、插值问题的定义 当精确函数当精确函数 y = f(x) 非常复杂或未知时，在区间非常复杂或未知时，在区间这个问题称为这个问题称为“插值问题插值问题” (2.1.1)近似函数近似函数 g(x) f(x)，满足条件，满足条件 ,由此构造一个简单易算的由此构造一个简单易算的 上一系列节点上一系列节点 处测得函数值处测得函数值 , a b01,mxxx00,mmyf xyf x0,1,j

8、jg xyjm这里的这里的 g(x) 称为称为f(x) 的的插值函数插值函数。节点节点 x0 xm称为称为插值节点插值节点, 条件（条件（2.1.1)称为称为插值条件插值条件，区间区间 称为称为插值区间插值区间。, a b如果利用如果利用g(x)来求来求f(x) 在在y点点的近似值，则称的近似值，则称y为为插值点。插值点。插值函数的类型有很多种插值函数的类型有很多种最常用的插值函数是最常用的插值函数是 ?代数多项式代数多项式用代数多项式作插值函数的插值称为用代数多项式作插值函数的插值称为代数插值代数插值，即，即选取次数不超过选取次数不超过n的多项式的多项式 Pn(x) ，使得使得 Pn (xj

9、) = yj (j = 0, 1 n) (2.1.2)本章主要讨论的内本章主要讨论的内容容插值问题插值问题插值法插值函数插值函数13 为什么需要插值为什么需要插值? 函数表达式复杂函数表达式复杂, 不便于计算和进行理论分析不便于计算和进行理论分析; 没有函数表达式没有函数表达式, 只给出离散样点只给出离散样点. 找简单函数近似找简单函数近似, 即函数逼近即函数逼近. 函数逼近常用方法函数逼近常用方法: 插值法插值法, 曲线拟合法曲线拟合法. 插值法插值法: 多项式插值多项式插值, 三角多项式插值三角多项式插值.14 已知函数已知函数 f (x)在区间在区间 a, b上上 (n+1) 个不同点个

10、不同点 x0, x1, x2, , xn 处的函数值处的函数值 yi= f (xi) (i=0, 1, 2, n), 求函数求函数 n(x), 使其满足使其满足(1) n(x)为至多为至多n次多项式，即次多项式，即(2) 满足插值条件满足插值条件nnnxaxaxaax 2210)( )., 1 , 0()()(niyxfxiiin n(x): 插值多项式插值多项式xi : 插值节点插值节点 a, b: 插值区间插值区间1 Lagrange插值插值15一次一次 二次二次 三次三次几何意义几何意义: n次多项式插值就是过次多项式插值就是过 (n+1)个点个点 (xi, f (xi) (i=0, 1

11、, , n), 作一条多项式曲线作一条多项式曲线 y= n(x)近似曲线近似曲线 y=f(x).16 三个基本问题三个基本问题 插值多项式插值多项式 n(x)是否存在唯一？是否存在唯一？ 若若 n(x)存在存在, 截断误差截断误差 f (x) n(x)=? 如何求如何求 n(x)？17 插值多项式插值多项式 n(x)的存在唯一性的存在唯一性 nnnnnnnnnnnnnnyxaxaxaaxyxaxaxaaxyxaxaxaax2210112121101002020100)()()( n 次多项式次多项式 n(x)有有(n+1)个待定系数个待定系数ai (i=0, 1, 2, , n), 插值条件插

12、值条件 n(xi)= f (xi)= yi (i=0, 1, 2, , n)也是也是(n+1)个个, 恰好给出恰好给出(n+1)个方程个方程.18 )()()()(11112102102222212110200nnnnnnnnnxfxfxfxfaaaaxxxxxxxxxxxx即即系数矩阵系数矩阵A的行列式是的行列式是Vandermonde行列式，其值为行列式，其值为 njijiijxxA,0,)()det( 当插值节点当插值节点xi (i=0, 1, 2, , n)互不相同时，此行列互不相同时，此行列式不为式不为0, 即系数矩阵即系数矩阵A可逆可逆. 因此因此ai (i=0, 1, 2, ,

13、n), 存在唯一，即存在唯一，即 n(x)存在唯一存在唯一.范得蒙行列式的转置！范得蒙行列式的转置！19 5.1.2插值多项式的误差估计插值多项式的误差估计)()()(xxfxRnn 截断误差或插值余项截断误差或插值余项定理定理 若若,)()1(baCxfn 则存在则存在 (a, b), 使得使得).()()!1()()(10)1(nnnxxxxxxnfxR 证明证明, 0)()()( iniinxxfxR 故故).()()()(10nnxxxxxxxKxR 其中其中 K (x)是与是与 x有关的待定函数有关的待定函数.如何求如何求 K (x) ?20现把现把x看成是看成是a, b上的固定点上

14、的固定点, 作辅助函数作辅助函数)()()()()()(10nnxtxtxtxKttftF )(0)()()(10 xFxFxFxFn 即即 F(t )在在a, b上有上有 n+2 个零点个零点. 根据根据Rolle定理定理, F (t )在在 F(t )的两个零点之间至少有一个零点的两个零点之间至少有一个零点, 故故 F (t )在在(a, b)内至少有内至少有 (n+1)个零点个零点. 对对F (t )再应用再应用Rolle 定理，定理， 可知可知F (t )在在(a, b)内内至少有至少有 n 个零点个零点. 依此类推依此类推, F(n+1) (t )在在(a, b)内至少内至少有一个零

15、点有一个零点, 记之为记之为 (a, b), 使得使得, 0)()!1(0)()()1()1( xKnfFnn 则则21因此因此.),(,)!1()()()1(xbanfxKn且依赖且依赖 )()()()(10nnxxxxxxxKxR ).()()!1()(10)1(nnxxxxxxnf 若若,)(max1)1(, nnbaxMxf则则| )()( |)!1(| )(|101nnnxxxxxxnMxR 22 当当 n =1时时, 线性插值余项为线性插值余项为).,(),)(2)( )(1010 xxxxxxfxR 当当 n =2时时, 抛物线插值余项为抛物线插值余项为).,(),)()(6)(

16、 )(20210 xxxxxxxxfxR 23求求 L1(x)(1) 至多至多1次多项式次多项式;).1 , 0()()(1 iyxfxLiii(2)已知已知ix1x)(iixfy 1y0 x0y Lagrange方法求插值多项式方法求插值多项式 当用当用Lagrange方法求插值多项式时方法求插值多项式时, 其其n次插次插值多项式记为值多项式记为Ln(x). n=1的情形的情形24x0 x1)()(0010101xxxxyyyxL 10100101yxxxxyxxxx 1100)()(yxlyxl )(0 xl1次多项式次多项式ix1x0 x01)(1xl1次多项式次多项式ix1x0 x01

17、n = 1 线性插值多项式线性插值多项式 L1(x)是过两点是过两点 (x0, y0), (x1, y1)的直线方程的直线方程25010101log101 , log201.3010log12( )log(10)1(20)1.3010102011.3010201101( )(20)( )(10)10201020 1010f xxffxxyyxxlxxl xx 例：已知，利用插值一次多项式求的近似值。解：，设，则插值基本多项式为：，10 01 1111.3010( )( )( )(20)(10)101011.3010(12)(1220)(12 10)1.06021010log12log10 lo

18、g20 log121.0792).L xy lxy l xxx 于是，拉格朗日型一次插值多项式为：故L即由和两个值的线性插值得到，且具有两位有效数字（精确解26已知已知ix1x)(iixfy 1y0 x0y求求 L2(x)(1) 至多至多2次多项式次多项式;).2 , 1 , 0()()(2 iyxfxLiii(2)2x2y 二次插值多项式二次插值多项式27n = 2)()()(2101201xxxxxxxxxl )()()(1202102xxxxxxxxxl )()()()()()()(2211002xfxlxfxlxfxlxL )(2010 xxxx )(0 xl)(1xx )(2xx )

19、(0 xl2次多项式次多项式ix1x0 x012x0)(1xl2次多项式次多项式)(2xl2次多项式次多项式ix1x0 x02x01ix1x0 x02x01 二次插值多项式二次插值多项式28l1(x)f (x1)l2(x)f (x2)l0(x)f (x0)x0 x1x2 二次插值多项式二次插值多项式L2(x)例：已知ixlgiiyxlog12利用此三值的二次插值多项式求的近似值29ixlgiiyx10152011.17611.3010012012101520(15)(20)1( )1520(10 15)(1020)50(10)(20)1( )1020(15 10)(1520)25(10)(15

20、)1( )1015(20 10)(20 15)50 xxxxxlxxxxxl xxxxxlxxx 解：设，则20 01 12 221( )( )( )( )2015501.17611.301010201015255011.1761(12)1220 12 1512 10 122050251.301012 10 12 151.076650log12log121.07923xy lxy l xy lxxxxxxx故L所以：L利用三个点进行抛物线插值得到的的值，与精确值相比，具有 位有效数字。30ixlgiiyx31已知已知ix2x1xnx)(iixfy 1y2yny0 x0y求求 Ln(x)(1)

21、至多至多n次多项式次多项式;)., 1 , 0()()(niyxfxLiiin (2)插值节点插值节点插值多项式插值多项式 n次次Lagrange插值多项式插值多项式32)()()()()(1100 xlyxlyxlyxlyxLnniin 其中其中 li (x) 为插值为插值基函数基函数)(xlin次多项式次多项式)()()(1110niiiiiiixxxxxxxxxx )(xli)(0 xx )(1xx )(1 ixx)(1 ixx)(nxx ,)()()(0 nijjjijixxxxxl)., 1 , 0(ni ixixnx0 x11x1 ix1 ix00000 n次次Lagrange插值

22、多项式插值多项式33例例 已知函数已知函数 y=lnx 的函数表如下的函数表如下xi2.56492.48492.39792.3026f (xi6391分别用分别用Lagrange线性插值和抛物线插值求线性插值和抛物线插值求ln11.5的近的近似值似值, 并估计误差并估计误差.解解线性插值线性插值. ,111211)12(121112)11()(1 xfxfxL)12()11(21)5 .11(5 .11ln1ffL 取两个节点取两个节点 x0=11, x1=12, 插值函数为插值函数为计算器计算器.4414. 2 34,1111max| )( |max2212,111

23、2,112 xxfMxx| )125 .11)(115 .11( |2| )5 .11(|21 MR.10033. 1811132 抛物线插值抛物线插值. )1213)(1113()12)(11(5649. 2)1312)(1112()13)(11(4849. 2)1311)(1211()13)(12(3979. 2)(2 xxxxxxxL取取x0=11, x1=12, x1=13, 插值多项式为插值多项式为35.442275. 2)5 .11(5 .11ln2 L,1122max| )( |max3312,1112,113 xxfMxx| )135 .11)(125 .11)(115 .11

24、( |6| )5 .11(|32 MR.1039. 9811153 442347. 25 .11ln 36例例 已知函数已知函数 y=lnx 的函数表如下的函数表如下xi2.56492.48492.39792.3026f (xi6391分别用分别用Lagrange线性插值和抛物线插值求线性插值和抛物线插值求ln11.5的近的近似值似值, 并估计误差并估计误差.解解线性插值线性插值. 取两个节点取两个节点 x0=11, x1=12, 插值函数为插值函数为计算器计算器X=11, 12Y=2.3979, 2.4849pp=polyfit(X,Y,1)ln11dot5=pol

25、yval(pp,11.5)37例例 已知函数已知函数 y=lnx 的函数表如下的函数表如下xi2.56492.48492.39792.3026f (xi6391分别用分别用Lagrange线性插值和抛物线插值求线性插值和抛物线插值求ln11.5的近的近似值似值, 并估计误差并估计误差.解解计算器计算器X=11, 12, 13Y=2.3979, 2.4849, 2.5649pp=polyfit(X,Y,2)ln11dot5=polyval(pp,11.5)抛物线插值抛物线插值. 取取x0=11, x1=12, x1=13, 插值多项式为插值多项式为120165644.

26、0e)23)(13()21 . 2)(11 . 2( e)32)(12()31 . 2)(11 . 2(e)31)(21()31 . 2)(21 . 2()1 . 2(e e)23)(13()2)(1(e)32)(12()3)(1(e)31)(21()3)(2()( .e 049787068. 0135335283. 0367879441. 0e321 3, 2, 1e 5.13-2-122.1-3-2-122.1-x-x LxxxxxxxLLagrangexx二次插值多项式为二次插值多项式为：解解计计估估差差误误的近似值，并进行的近似值，并进行插值公式求插值公式求试用二次试用二次的值如下的值

27、如下在在已知已知例例38 00607001. 0)31 . 2()21 . 2()11 . 2(! 2)1 . 2()1 . 2( , max122.1-121 eLeReexx故有误差估计故有误差估计因因39数值分析数值分析插值法插值法例例 已知函数已知函数表表?245sin解解1 1）线性插值线性插值 60 x41x取两点取两点，则，则 2264621464)(1xxxL0.603553)245(245sin1L抛物插值抛物插值 23)43)(63()4)(6(22)34)(64()3)(6(21)36)(46()3)(4()(2xxxxxxxL0.609577)247(247sin2Lx

28、643xysin2122232 2）0.60876140.6087614 )245sin(抛物比线性插值精确抛物比线性插值精确. . 【注注】40function yi=Lagrange(x,y,xi)%Lagrange%Lagrange插值多项式，其中，插值多项式，其中，%x%x为向量，全部的插值节点；为向量，全部的插值节点；%y%y为向量，插值节点处的函数值为向量，插值节点处的函数值; ;%xi%xi为标量或向量，被估计函数的为标量或向量，被估计函数的 自变量；自变量；%yi%yi为为xixi处的函数估计值处的函数估计值. .n=length(x); m=length(y);% %插值点与

29、它的函数值应有相同个插值点与它的函数值应有相同个 数数. .if n=merror(The lengths of X and Y must be equal!);return;endLagrangeLagrange插值的插值的MATLABMATLAB程序：程序：LagrangeLagrange.m.myi=zeros(size(xi);for k=1:nw=ones(size(xi);for j=1:k-1 k+1:n% %输入的插值节点必须互异输入的插值节点必须互异If abs(x(k)-x(j)epserror(the DATA is error!);return;Endw=(xi-x(j

30、)./(x(k)-x(j).*w;endyi=yi+w*y(k);end数值分析数值分析插值法插值法习题：P139 第三题4142 由于插值基函数只与由于插值基函数只与节点有关而与函数值无关节点有关而与函数值无关, 因此当插值节点相同而函数值不同时因此当插值节点相同而函数值不同时, 所有的所有的Lagrange插值基函数均不变插值基函数均不变, 此时用此时用Lagrange插值插值多项式比较方便多项式比较方便. 11110011001100, , , , :new2, , , :new1, , ,:original nnnnnnnnyxyxyxyxzxzxzxyxyxyx 当新增加插值节点时当

31、新增加插值节点时, 用用Lagrange插值多项式插值多项式, 则则需要重新计算所有的插值基函数需要重新计算所有的插值基函数, 计算量大且应用计算量大且应用不方便不方便.Lagrange插值插值Newton插值插值三、牛顿插值三、牛顿插值（NewtonNewtons Interpolation s Interpolation ）Lagrange Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部全部基函数基函数li(x) 都需要重新计算。都需要重新计算。希望每加一个节点时，希望每加一个节点时，只附加一项只附加一项上去即可上去即可。 1 1、能否重新在

32、能否重新在 中寻找新的中寻找新的基函数基函数 ？ 1, ,nnPxspanxxF回顾：回顾：Lagrange 插值的优缺点：插值的优缺点： 优点：优点：具有严格的规律性具有严格的规律性,便于记忆。便于记忆。 缺点：缺点：计算量大、不具有承袭性。计算量大、不具有承袭性。44 0010101xxxxxfxfxfxN 线性插值多项式的另一表现形式线性插值多项式的另一表现形式2 Newton插值插值Newton插值公式插值公式45 差商定义差商定义 一阶差商一阶差商 ( f (x)关于点关于点xi , xj的一阶差商的一阶差商)jijijixxxfxfxxf )()(, 二阶差商二阶差商( f (x)

33、关于点关于点xi , xj , xk的二阶差商的二阶差商)kikjjikjixxxxfxxfxxxf , 一阶差商的差商一阶差商的差商46 k阶差商阶差商kkkkxxxxxfxxxfxxxf 02111010, 差商定义差商定义47 差商的性质差商的性质 各阶差商具有各阶差商具有线性性线性性, 即若即若 f (x)=ag(x)+bh(x), 则有则有,101010kkkxxxbhxxxagxxxf k阶差商可表为阶差商可表为f (x0), f (x1), , f (xk)的线性组合的线性组合,例例 011100101010,xxxfxxxfxxxfxfxxf 一阶差商一阶差商48 202110

34、210,xxxxfxxfxxxf 2121101020)()()()(1xxxfxfxxxfxfxx).()()(210 xcfxbfxaf )(12010 xxxxa )(11202xxxxc )(1)(1)(1210120 xxxxxxb)(12101xxxx 二阶差商二阶差商49 3 阶以上的差商可用数学归纳法证明阶以上的差商可用数学归纳法证明. kjkjjjjjjjjxxxxxxxxxxxf01110)()()()(,10kxxxf50 各阶差商均具有各阶差商均具有对称性对称性, 即改变节点的位置即改变节点的位置, 差差商值不变商值不变.,2134043210 xxxxxfxxxxxf

35、 若若f (x)是是n次多项式次多项式, 则一阶差商则一阶差商 f x, xi 是是 (n 1)次多项式次多项式.例例51 计算各阶差商可按差商表计算计算各阶差商可按差商表计算ix1阶差商阶差商)(ixf2阶差商阶差商3阶差商阶差商 4阶差商阶差商0 x1x2x3x4x5x)(0 xf)(1xf)(2xf)(3xf)(4xf)(5xf 10,xxf 21,xxf 32,xxf 43,xxf 54,xxf 210,xxxf 321,xxxf 432,xxxf 543,xxxf,3210 xxxxf,4321xxxxf,5432xxxxf,43210 xxxxxf,54321xxxxxf计算公式？

36、计算公式？52差商的计算方法(表格法):规定函数值为零阶差商差商表)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四阶差商三阶差商二阶差商一阶差商,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf如果用如果用Matlab计算均差计算均差, 可用下面的主句可用下面的主句:n=length(x); d=f; %x, f为节点及函数值向量为节点及函数值向量for j=2:n for i=n:-1:j d(i)=(d(i)-d(i-1)/(x(i)-x(i

37、-j+1); endend 试列出试列出f f( (x xi i)=)=x x3 3在节点在节点x x=0,2,3,5,6=0,2,3,5,6上的各阶差商值。上的各阶差商值。53xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+200(8-0)/(2-0)=428(19-4)/(3-0)=5(27-8)/(3-2)=19(10-5)/(5-0)=13 27(49-19)/(5-2)=10(125-27)/(5-3)=49(14-10)/(6-2)=15 125(91-49)/(6-3)=14(216-125)/(6-5)=916 216例例: :已知下表，计算三阶差商

38、已知下表，计算三阶差商 54ix( )if x1 13 34 47 70 02 215151212解：列表计算解：列表计算ix( )if x一阶差一阶差商商二阶差商二阶差商三阶差三阶差商商1 10 03 32 21 14 4151513134 47 71212-1-1-3.5-3.5-1.25-1.2555Newton 插值多项式算法: 1输入数据),.,2 , 1(,niyxii及插值点 u 2 for j=2,3,n do 2.1 for i= n, n-1,j do 11:;iiiiijyyyxx 3. :nyyy; 4. for i=n-1,n-2,1 do *()iiyyyyuxy

39、5. 输出 yy. 56牛顿插值的牛顿插值的MATLABMATLAB程序：程序：Newton_interpNewton_interp.m.mfunctionfunction yi,Y=Newton_interp(x,y,xi)yi,Y=Newton_interp(x,y,xi)%Newton%Newton插值多项式，其中，插值多项式，其中，%x%x为向量，全部的插值节点为向量，全部的插值节点; ;%y%y为向量，插值节点处的函数值为向量，插值节点处的函数值; ;%xi%xi为标量，被估计函数的自变量；为标量，被估计函数的自变量；%yi%yi为为xixi处的函数估计值；处的函数估计值；%Y为差商

40、表为差商表.n=length(x); m=length(y);%插值点与它的函数插值点与它的函数值应有相同个数值应有相同个数.if n=merror(The lengths of X and Y must be equal!);return;end数值分析数值分析插值法插值法57% %计算差商表计算差商表. .Y=zeros(n);Y(:,1)=y;Y=zeros(n);Y(:,1)=y;for k=1:n-1for k=1:n-1 for i=1:n-k for i=1:n-k% %输入的插值节点必须互异输入的插值节点必须互异. . if abs(x(i+k)-x(i)eps if abs(

41、x(i+k)-x(i)eps error(the DATA is error(the DATA is error!);error!); return; return; end endY(i,k+1)=(Y(i+1,k)-Y(i,k+1)=(Y(i+1,k)-Y(i,k)/(x(i+k)-x(i);Y(i,k)/(x(i+k)-x(i); end endendend % %计算计算NewtonNewton插值公式插值公式N(xi).N(xi).yi=0;yi=0;for i=1:nfor i=1:n z=1; z=1; for k=1:i-1 for k=1:i-1 z=z z=z* *(xi-

42、x(k);(xi-x(k); end end yi=yi+Y(1,i) yi=yi+Y(1,i)* *z;z;end end 数值分析数值分析插值法插值法58ix)(ixf0 x1x2x3x)(0 xf)(1xf,10 xxf)(2xf,21xxf,210 xxxf)(3xf,32xxf,321xxxf,3210 xxxxf 一阶差商一阶差商 二阶差商二阶差商三阶差商三阶差商步骤步骤1 1：构造差商表：构造差商表NewtonNewton插值方法插值方法 步骤步骤2 2：牛顿插值公式：牛顿插值公式).()(,)(,)(,)()(110210102100100nnnxxxxxxxxxxfxxxxx

43、xxfxxxxfxfxN数值分析数值分析插值法插值法59xifxifxi,xi+1fxi,xi+1,xi+211420.33333930.2-0.01667例例 已知已知x=1,4,9的平方根值，求的平方根值，求71/2解：（解：（ 1 ）建立差商表）建立差商表60 xifxifxi,xi+1fxi,xi+1,xi+211420.33333930.2-0.01667N2(x)=f(x0)+(x-x0)fx1, x0+ (x-x0) (x-x1) fx2, x1 , x0N2(7)=1+(7-1)0.33333+ (7-1)(7-4)(-0.01667)= 2.69992（2）根据差商表建立）根

44、据差商表建立牛顿基本差商插值公式牛顿基本差商插值公式61)(,)()(000 xxxxfxfxf )(,110100 xxxxxfxxfxxf )(,)()(0100 xxxxfxfxf )(,1010 xxxxxxxf 由一阶差商定义得由一阶差商定义得 由二阶差商定义得由二阶差商定义得故故Newton线性插值多项式线性插值多项式余项余项62 )(,221021010 xxxxxxfxxxfxxxf )(,)()(0100 xxxxfxfxf )(,1010 xxxxxxxf )(,)(,)()(102100100 xxxxxxxfxxxxfxfxf )()(,210210 xxxxxxxxx

45、xf 二次二次Newton插值多项式插值多项式余项余项故故63)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf )()(,210210 xxxxxxxxxxf )(,332103210210 xxxxxxxfxxxxfxxxxf )(,)(,)()(102100100 xxxxxxxfxxxxfxfxf )()(,2103210 xxxxxxxxxxf )()()(,32103210 xxxxxxxxxxxxxf 三次三次Newton插值多项式插值多项式余项余项64)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf )()()(,21010nn

46、xxxxxxxxxxxxf )()(,11010 nnxxxxxxxxxf一般地有一般地有n次次Newton均差插值多项式均差插值多项式 Nn(x)余项余项 Rn(x)65)()()(xRxNxfnn Nn(x)的特点的特点Nn(x)为至多为至多n次多项式次多项式,., 1 , 0)()()()(nixNxRxNxfininini 因此因此Nn(x)是是 f (x)的的 n 次插值多项式次插值多项式.)()(,)(,)(,)()(11010102100100 nnnxxxxxxxxxfxxxxxxxfxxxxfxfxN)()()(,)(21010nnnxxxxxxxxxxxxfxR 66 .1

47、210102010 nnnxxxxxxxxbxxxxbxxbbxN nnnxxxxfbxxxfbxxfbxfb,.,110210210100 n阶阶Newton插值多项式插值多项式 系数系数bi (i=0, 1, 2, , n)就是差商表中对角线上的元素就是差商表中对角线上的元素.67 Newton插值多项式的优点插值多项式的优点: 增加一个节点增加一个节点, 插值插值多项式只增加一项多项式只增加一项, 即即)()(,)()(01101nnnnnxxxxxxxxfxNxN 便于递推计算便于递推计算, Newton插值计算量小于插值计算量小于Lagrange插值插值.)()(xLxNnn 由插值

48、多项式的唯一性知由插值多项式的唯一性知, n阶阶Newton插值多项插值多项式和式和n阶阶Lagrange插值多项式是一样的插值多项式是一样的, 只是表现只是表现形式不同而已形式不同而已.68 nnnxxxxxxxxxxfR .,.,1010 )!1()(,.,)1(10 nfxxxxfnn Newton插值多项式的余项插值多项式的余项 由插值多项式的唯一性得由插值多项式的唯一性得 nnnxxxxxxnfR .)!1()(10)1( 故故例例 用插值法求用插值法求 的值并计算误差。的值并计算误差。697n解：解：作函数作函数f(x)=x取取x0=4, x1=9, x2=6.25 ,建立差商表建

49、立差商表xf(x) f xi,xi+1,fxi,xi+1,xi+242936.25 2.50.20.18182-0.00808P2(7)= 2+(7-4)0.2+(7-4)(7-9)(-0.00808)=2.6484870在区间在区间4,9上，上，355331310011719884( )()().fxMx1012 12013177772 1747976 250 008793()()( )( )!( )( )!.!nnnnfRxxxxxxxnfRxxxM71 123560262090ix( )if x 已知下列函数表已知下列函数表, 求求 4次次newton插值多项式插值多项式.( )f x习

50、题习题72解 作差商表 ix( )if x 1 0 2 2 2 3 6 4 1 5 20 7 1 0 6 90 70 21 5 14432( )02(1) 1 (1)(2)1 (1)(2)(3)(5)11426230Nxxxxxxxxxxxx 123560262090ix( )if x过程过程:73的的近近似似值值。插插值值公公式式求求用用数数值值表表如如下下：已已知知例例)596. 0(02652. 188811. 069675. 057815. 041075. 0)(90. 080. 065. 055. 040. 0)()( 2 . 5 fNewtonxfxxshxfkk 解：先造差商表解

51、：先造差商表7463192. 0)596. 0()596. 0(596. 0)80. 0)(65. 0)(55. 0)(40. 00.034( )65. 0)(55. 0)(40. 00.197( )55. 0)(40. 00.2800( )40. 0(1160. 141075. 044 NfxxxxxxxxxxxN代代入入得得：将将 由由Newton公式得四次插值多项式为：公式得四次插值多项式为：解解 1 1）建立差商表）建立差商表75例题例题1.01.52.00.84150.99750.9093 0.312-0.1764-0.4884973884. 0)5 . 18 . 1 ()0 . 1

52、8 . 1 (4884. 0)0 . 18 . 1 (312. 08415. 0)8 . 1 (2N2 2）插值）插值 Newton插值多项式适用于节点任意分布的插值多项式适用于节点任意分布的情形。但当节点等距分布时，可以简化情形。但当节点等距分布时，可以简化Newton插值公式。插值公式。等距节点插值等距节点插值 设设a=x0 x1c时时Ln(x)发散发散. 这一现象称为这一现象称为Runge现象现象. 104 它表明用高次插值多项式它表明用高次插值多项式Ln(x)近似近似f (x)效果不见效果不见得好，因而通常得好，因而通常不用高次插值不用高次插值，而用分段低次插值，而用分段低次插值. 常

53、用分段低次插值常用分段低次插值: 分段线性插值分段线性插值, 分段三次分段三次Hermite插值插值, 三次样条插值三次样条插值.105 分段线性插值定义分段线性插值定义bxxxan .10.,)(baCx );,., 0(),()(nixfxii 定义定义 已知函数已知函数 y=f (x)在区间在区间a, b上的上的 (n+1)个节点个节点上的函数值上的函数值 yi=f (xi) (i=0,1,n), 求插值函数求插值函数 (x), 使得使得,1 iixx在每一个小区间在每一个小区间 上是线性函数上是线性函数;(1)(2)(3)称函数称函数 (x)为为a, b上关于数据上关于数据 (xi,

54、yi) (i=0,1,n)的的分分段线性插值函数段线性插值函数.106 nnnnnxxIxxIxxIyxyxyxyx, , , , :interval),( ,),(),(),( :points data11-211100221100 x0 x1x2x3 i (x) = ai x+ bi分段线性插值分段线性插值10711 , )(,)( )( iiiiiixxxxxxxfxfx 分段线性插值分段线性插值 nnnnnxxIxxIxxIyxyxyxyx, , , , :interval),( ,),(),(),( :points data11-211100221100 根据根据Newton插值公式

55、可写出插值公式可写出 (x)的分段表达式的分段表达式108 nnnnnnxxxxxxxfxfxxxxxxxfxfxxxxxxxfxfx1111211211100100 , )(,)( , )(, )( ),(, )( )( 分段线性插值分段线性插值 nnnnnxxIxxIxxIyxyxyxyx, , , , :interval),( ,),(),(),( :points data11-211100221100 109 分段线性插值的误差估计分段线性插值的误差估计定理定理 如果如果 f (x)在在a, b上二阶连续可微，则分段上二阶连续可微，则分段线性插值函数线性插值函数 (x)的余项有以下估计

56、的余项有以下估计8| )()(| )(|2MhxxfxR 其中其中. | )( |max),(max110 xfMxxhbxaiini 110 在每个小区间在每个小区间xi, xi+1 (i=0, 1, , n)上上, (x)是是f (x)的线性插值函数，故对任意的线性插值函数，故对任意 x xi , xi+1有有证明证明)(2)( )()()(1 iixxxxfxxfxR 442)(| )( |222111hhxxxxxxxxxxxxiiiiiii 故故.842| )(|22MhhMxR 而而111分段线性插值分段线性插值 分段线性插值简单易行分段线性插值简单易行, 收敛性收敛性, 稳定性有

57、保证稳定性有保证. 没有光滑性没有光滑性, 一阶导数不连续一阶导数不连续. 可用更高阶的分段插值来得到连续导数，如三次可用更高阶的分段插值来得到连续导数，如三次样条插值样条插值.112 有些实际的插值问题不但要求在节点上函数值相等，有些实际的插值问题不但要求在节点上函数值相等， 下面只讨论函数值与导数值个数相等的情况下面只讨论函数值与导数值个数相等的情况. . 满足这种要求的插值多项式就是满足这种要求的插值多项式就是埃尔米特插值多项式埃尔米特插值多项式. . 而且还要求对应的导数值也相等，甚至要求高阶导数也相等而且还要求对应的导数值也相等，甚至要求高阶导数也相等. .4 Hermite插值插值

58、113 Hermite插值多项式插值多项式求求 H(x).(1) 至多至多(2n+1)次多项式次多项式;)., 1 , 0(, )( ,)(niyxHyxHiiii (2)ix2x1xnx)(iixfy 1y2yny0 x0y)( iixfy 1y2yny0y已知已知H(x): Hermite插值多项式插值多项式114jxixnx0 x1)(jixh)( jixh)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHyxHyxHynn )(xHi(2n+1)次多项式次多项式)(xhi(2n+1)次多项式次多项式jxixnx0 x1)(jixH)( jixHHi (x)

59、, hi (x) ( i=0, 1, 2, n): Hermite插值基函数插值基函数115 )()( 21)(2xlxxxlxhiiiii 其中其中li (x)是是 Lagrange插值基函数插值基函数.)(xhijxixnx0 x1(2n+1)次多项式次多项式)()(2xlxhii )(ixxba 1)( iixh 0)( ),( )(2)()()( 2 iiiiiiixhxlxlxxbaxblxh)( 2iixlb )(jixh)( jixh1 a116)()()(2xlxxxHiii 其中其中li (x)是是 Lagrange插值基函数插值基函数.)(xHijxixnx0 x1(2n+

60、1)次多项式次多项式)()(2xlxHii )(ixxba 0)( iixH 1)( ),( )(2)()()( 2 iiiiiiixHxlxlxxbaxblxH1 b)(jixH)( jixH0 a117)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHyxHyxHynn )()( 21)(2xlxxxlxhiiiii )()()(2xlxxxHiii Hermite插值多项式插值多项式118n=1,)(1010 xxxxxl ,)(0101xxxxxl )()( )(21)(200000 xlxlxxxh 210101021 xxxxxxxx )()( )(2