多项式插值与样条插值

1、1汪远征汪远征 实践中常有这样的问题：实践中常有这样的问题： (1) 由实验得到某一函数由实验得到某一函数f(x)在一系列点在一系列点x0, x1, , xn处的值处的值y0, y1, , yn, 其函数的解析表达式是未知的其函数的解析表达式是未知的 (2) 或者或者f(x)虽有解析式虽有解析式, 但计算复杂但计算复杂, 不便于使用不便于使用 需要构造一个简单函数需要构造一个简单函数p(x)近似地代替近似地代替f(x) 这就是函这就是函数逼近问题数逼近问题汪远征汪远征 设已知被逼近函数设已知被逼近函数f (x)在离散点在离散点xi a, b上的值上的值 f (xi) = yi, i = 0,

2、1, 2, , n (1) 要求要求p(x)满足满足 （甚至（甚至 ）的问题称为函数插值。）的问题称为函数插值。 (2) 要求要求p(x)满足满足 为最小的问题称为数据拟为最小的问题称为数据拟合（曲线拟合）合（曲线拟合）0| )()(|max0 iinixpxf0| )()(|max0 iinixpxf niiixpxf02| )()(|汪远征汪远征 设设 0, 1, , n线性无关线性无关, 令令 = span 0, 1, , n为简单函数类为简单函数类, 其中其中 0, 1, , n称为称为 的基函数。的基函数。 逼近问题即用逼近问题即用p(x) = a0 0(x) + a1 1(x) +

3、 an n(x)来做逼近来做逼近, 问题归结为求其中的待定系数问题归结为求其中的待定系数a0, a1, , an。汪远征汪远征 【定义定义1】设区间设区间a, b上定义的函数上定义的函数f(x)在在n+1个互异点个互异点a x0 x1 . xn b的函数值为的函数值为y0, y1, ., yn, 若存在一个次若存在一个次数不超过数不超过n的多项式的多项式pn(x)满足条件：满足条件：pn(xi) = yii = 0, 1, 2, , n(3.1)则称则称pn(x)为函数为函数f(x)的的n次插值多项式次插值多项式 按条件按条件(3.1)求函数求函数f(x)近似表达式近似表达式pn(x)的方法称

4、为插值法的方法称为插值法, 条件条件(3.1)称为插值条件称为插值条件 点点xi (i = 0, 1, 2, , n)称为插值节点称为插值节点 区间区间a, b称为插值区间称为插值区间汪远征汪远征 【定义定义1】设区间设区间a, b上定义的函数上定义的函数f(x)在在n+1个互异点个互异点a x0 x1 . xn b的函数值为的函数值为y0, y1, ., yn, 若存在一个次若存在一个次数不超过数不超过n的多项式的多项式pn(x)满足条件：满足条件：pn(xi) = yii = 0, 1, 2, , n(3.1)则称则称pn(x)为函数为函数f(x)的的n次插值多项式次插值多项式 几何意义：

5、曲线几何意义：曲线y = pn(x)与曲线与曲线y = f(x)在平面上相交于在平面上相交于n+1个互异的点个互异的点(xi, yi) (i = 0, 1, 2, , n).汪远征汪远征 【定理定理1】存在唯一存在唯一pn(x) Pnx满足插值条件满足插值条件(3.1)证明：设证明：设pn(x) = a0 + a1x + anxn 满足插值条件满足插值条件pn(xi) = yii = 0, 1, 2, , n 从而只需求解线性方程组从而只需求解线性方程组pn(xi) = a0 + a1xi + anxin = yi (i = 0, 1, 2, , n) (3.2)(3.2)的系数行列式为范德蒙

6、行列式：的系数行列式为范德蒙行列式：nnnnnnnxxxxxxxxxV111),.,(110010 niijjixx110)(汪远征汪远征 【定理定理1】存在唯一存在唯一pn(x) Pnx满足插值条件满足插值条件(3.1)证明：证明：只需求解线性方程组只需求解线性方程组pn(xi) = a0 + a1xi + anxin = yi (i = 0, 1, 2, , n) (3.2)(3.2)的系数行列式为范德蒙行列式：的系数行列式为范德蒙行列式：因为因为x0, x1, , xn互异互异, 所以所以Vn 0。即。即(3.2)存在唯一解存在唯一解, 从而从而存在唯一的存在唯一的pn(x) Pnx 满

7、足插值条件满足插值条件(3.1)。 niijjinnnnnnnxxxxxxxxxxxV110110010)(111),.,(汪远征汪远征 【例例1 】给定数据给定数据求次数不大于求次数不大于3的插值多项式的插值多项式p3(x)解：设解：设p3(x) = a0 + a1x + a2x2 + a3x3依题意有依题意有解之得：解之得：a0 = 10, a1 = 5, a2 = 5, a3 = 2即有即有 p3(x) = 10 + 5x 5x2 +2x3 35)5()5()5(4)2()2()2(7)1()1()1(7)1()1()1(332210332210332210332210aaaaaaaaa

8、aaaaaaa汪远征汪远征 【例例1 】给定数据给定数据求次数不大于求次数不大于3的插值多项式的插值多项式p3(x)注：注：(1) 范德蒙矩阵的条件数很大范德蒙矩阵的条件数很大 误差大计算量大误差大计算量大(2) 选择适当基函数使插值多项式具特殊形式选择适当基函数使插值多项式具特殊形式汪远征汪远征 所求的插值多项式所求的插值多项式pn(x)是线性空间是线性空间Pnx中的一个点中的一个点, 而而Pnx的基是不唯一的。因此的基是不唯一的。因此, n次代数插值多项式次代数插值多项式pn(x)可以写可以写成多种形式成多种形式. 由线性空间的不同基底出发由线性空间的不同基底出发, 构造满足插值条件的多项

9、式构造满足插值条件的多项式的方法称为基函数法。的方法称为基函数法。汪远征汪远征 由线性空间的不同基底出发由线性空间的不同基底出发, 构造满足插值条件的多项式构造满足插值条件的多项式的方法称为基函数法。的方法称为基函数法。 基函数法求插值多项式的步骤：基函数法求插值多项式的步骤： 1) 定义定义n+1个线性无关的特殊多项式个线性无关的特殊多项式插值基函数：插值基函数： 2) 根据插值条件确定插值多项式的系数根据插值条件确定插值多项式的系数a0, ., an)(,),(),(10 xxxn )()()()(1100 xaxaxaxpnnn 汪远征汪远征 (1) n = 1时时. 设设yi = f(

10、xi) i = 0, 1.作直线方程：作直线方程： 令：令：称称L1为两点式插值或线性插值。为两点式插值或线性插值。)(001010 xxxxyyyy )()()(1000101001xxyxxyxxyxx )()(1011001xxyxxyxx .)(101001011yxxxxyxxxxxL 汪远征汪远征 (1) n = 1时时. 设设yi = f(xi) i = 0, 1.令：令：称称L1为两点式插值或线性插值。为两点式插值或线性插值。 【例例1】设设 的函数表的函数表求求f(175)的近似值。的近似值。解：解：x0 = 169, x1 = 225, y0 = 13, y1 = 15。.

11、)(101001011yxxxxyxxxxxL xxf )(151312225169144xx1516922516913225169225)(1 xxxL汪远征汪远征 (1) n = 1时时. 设设yi = f(xi) i = 0, 1.令：令：称称L1为两点式插值或线性插值。为两点式插值或线性插值。 【例例1】设设 的函数表的函数表求求f(175)的近似值。的近似值。解：解：.)(101001011yxxxxyxxxxxL .214285.131751751 Lxxf )(151312225169144xx1516922516913225169225)(1 xxxL汪远征汪远征 (2) n

12、= 2时时. 设设yi = f(xi) i = 0, 1, 2. 令：令：称称L2为三点式插值或抛物插值。为三点式插值或抛物插值。 【例例1】计算计算 。解解：x0 = 144, x1 = 169, x2 = 225, y0 = 12, y1 = 13, y2 = 15 13.23158 2120210121012002010212)()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxL 175 15)169225)(144225()169175)(144175(13)225169)(144169()225175)(144175(12)225144)(169144()

13、225175)(169175(1751752 L汪远征汪远征 【定义定义2】满足满足 (3.3)次数不大于次数不大于n的多项式的多项式li(x)称为以称为以x0, ., xi-1, xi+1, ., xn为节点为节点的的Lagrange插值基函数。插值基函数。注：因为注：因为n个节点个节点x0, ., xi-1, xi+1, ., xn是是li(x)的零点的零点所以可设所以可设 li(x) = bi(xx0).(xxi-1)(xxi+1).(xxn)又由又由li(xi) = 1, 得得即即 ijijxlijji01)( ).()().(1110niiiiiiixxxxxxxxb nijjjij

14、niiiiiiniiixxxxxxxxxxxxxxxxxxxxxl0110110).()().().()().()(汪远征汪远征 【定义定义2】满足满足 (3.3)次数不大于次数不大于n的多项式的多项式li(x)称为以称为以x0, ., xi-1, xi+1, ., xn为节点为节点的的Lagrange插值基函数。插值基函数。注：即注：即(j = 0, 1, ., n) nijjjijniiiiiiniiixxxxxxxxxxxxxxxxxxxxxl0110110).()().().()().()( ijijxlijji01)( 汪远征汪远征 【定义定义3】令令 (3.4)则易知则易知(3.4

15、)所示的所示的pn(x)为次数不大于为次数不大于n的多项式的多项式, 且满足插值且满足插值条件条件(3.1): (j = 0, 1, ., n)称称Ln(x)为为Lagrange插值多项式。插值多项式。注：注：n = 1时称为线性插值：时称为线性插值：L1(x) = l0(x)y0 + l1(x)y1 ninijjjijiniiinxxxxyxlyxL000)()(jnijiijnyxlyxL 0)()(1010)(xxxxxl 0101)(xxxxxl 汪远征汪远征 【定义定义3】令令 (3.4)则易知则易知(3.4)所示的所示的pn(x)为次数不大于为次数不大于n的多项式的多项式, 且满足

16、插值且满足插值条件条件(3.1): (j = 0, 1, ., n)称称Ln(x)为为Lagrange插值多项式。插值多项式。注：注：n = 2时称为抛物插值：时称为抛物插值：L2(x) = l0(x)y0 + l1(x)y1 + l2(x)y2)()()(2010210 xxxxxxxxxl )()()(2101201xxxxxxxxxl )()()(1202102xxxxxxxxxl ninijjjijiniiinxxxxyxlyxL000)()(jnijiijnyxlyxL 0)()(汪远征汪远征 【例例3】已知离散数据如下：已知离散数据如下： (1) 求以求以x2 =0, x3 =1为

17、节点的线性插值多项式为节点的线性插值多项式, 并预测并预测x =0.3时时f 的近似值。的近似值。 (2) 求以求以x1 = -1, x2 = 0, x3 = 1为节点的二次插值多项式为节点的二次插值多项式, 并预并预测测x = 0.3时时f 的近似值。的近似值。汪远征汪远征 【例例3】已知离散数据如下：已知离散数据如下： (1) 求以求以x2 =0, x3 =1为节点的线性插值多项式为节点的线性插值多项式, 并预测并预测x =0.3时时f 的近似值。的近似值。解解:(1) 线性插值多项式是：线性插值多项式是：由于由于L1(0.3) = 0.3+1 = 1.3, 所以当所以当x=0.3时时f

18、的近似值为的近似值为1.3。232332321)(xxxxyxxxxyxL 01021011 xx汪远征汪远征 【例例3】已知离散数据如下：已知离散数据如下： (2) 求以求以x1 = -1, x2 = 0, x3 = 1为节点的二次插值多项式为节点的二次插值多项式, 并预并预测测x = 0.3时时f 的近似值。的近似值。由于由于L2(0.3)=1.2475, 所以当所以当x = 0.3时时f 的近似值为的近似值为1.2475。)01)(1(1()0)(1(2)10)(1(0()1)(1(1)11)(01()1)(0(5 . 0)(2 xxxxxxxL)1()1()1(25. 02 xxxxx

19、175. 025. 02 xx汪远征汪远征 Matlab代码代码function s=lagrange1(x0, y0)syms xn = length(x0); s = 0;for k = 1:n xp = x0(1:k-1 k+1:n); yp = prod(x-xp)./(x0(k)-xp); s = s + yp*y0(k);ends = vpa(s, 2)s = sym(s)s = simple(s);汪远征汪远征 Matlab代码代码function yh=lagrange2(x0, y0, xh)n = length(x0); m = length(xh);yh=zeros(1,

20、 m);for k = 1:m for i = 1:n xp = x0(1:i-1 i+1:n); yp = prod(xh(k)-xp)./(x0(i)-xp); yh(k) = yh(k) + yp*y0(i); endend汪远征汪远征 设设pn(x)为函数为函数f(x)关于给定节点关于给定节点x0, x1, ., xn上的上的n次插值多次插值多项式。项式。 称称Rn(x) = f(x) pn(x)为插值余项为插值余项 【定理定理2】设设f(x)在插值区间在插值区间a, b上存在上存在n + 1阶导数阶导数, 则对则对于任意于任意x a, b, 存在存在 = (x) (a, b), 使使

21、 (3.5)()!1()()()()(1)1(xnfxpxfxRnnnn 汪远征汪远征 【定理定理2】设设f(x)在插值区间在插值区间a, b上存在上存在n + 1阶导数阶导数, 则对则对于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)证明：显然证明：显然Rn(xi) = 0, (i = 0, 1, 2, , n), 所以所以Rn(xi)至少有至少有n + 1个零点个零点, 故可设故可设作辅助函数作辅助函数)()!1()()()()(1)1(xnfxpxfxRnnnn )()()()()(10 xxKxxxKxRnniin niinxtxKtptft0)()(

22、)()()( 汪远征汪远征 【定理定理2】设设f(x)在插值区间在插值区间a, b上存在上存在n + 1阶导数阶导数, 则对则对于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)证明：设证明：设作辅助函数作辅助函数则则 (t)在在a, b上具有上具有n+1阶导数阶导数, 且有且有n+2个互异的零点：个互异的零点：x0, x1, ., xn, x)()!1()()()()(1)1(xnfxpxfxRnnnn )()()()()(10 xxKxxxKxRnniin niinxtxKtptft0)()()()()( )()()()()(10 xxKxxxKxRnnii

23、n 汪远征汪远征 【定理定理2】设设f(x)在插值区间在插值区间a, b上存在上存在n + 1阶导数阶导数, 则对则对于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)证明：作辅助函数证明：作辅助函数则则 (t)在在a, b上具有上具有n+1阶导数阶导数, 且有且有n+2个互异的零点：个互异的零点：x0, x1, ., xn, x由罗尔定理由罗尔定理, 存在存在 (a, b)使使)()!1()()()()(1)1(xnfxpxfxRnnnn niinxtxKtptft0)()()()()( )()()()()1(1)1()1( nnnnnxKpf)(0)1( n

24、)()()()()(10 xxKxxxKxRnniin 汪远征汪远征 【定理定理2】设设f(x)在插值区间在插值区间a, b上存在上存在n + 1阶导数阶导数, 则对则对于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)证明：由证明：由罗尔定理罗尔定理, 存在存在 (a, b)使使 f (n+1)( ) K(x)(n + 1)! = 0 )()!1()()()()(1)1(xnfxpxfxRnnnn )()()()()1(1)1()1( nnnnnxKpf)(0)1( n)!1()()()1( nfxKn )()()()()(10 xxKxxxKxRnniin

25、汪远征汪远征 【定理定理2】设设f(x)在插值区间在插值区间a, b上存在上存在n + 1阶导数阶导数, 则对则对于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)注：注：(1) 通常余项估计：通常余项估计：(3.6)其中其中 (3.7)| )(|)!1(| )(|11xnMxRnnn | )(|max)1(,1xfMnbaxn | )(|max)!1(| )(|max1,1xnMxRnbaxnn )()!1()()()()(1)1(xnfxpxfxRnnnn 汪远征汪远征 【定理定理2】设设f(x)在插值区间在插值区间a, b上存在上存在n + 1阶导数阶导数

26、, 则对则对于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)注：注：(2) 对于指定对于指定x, 应取靠近应取靠近x的的n+1个节点作插值个节点作插值, 以使以使| n+1(x)|较小较小)()!1()()()()(1)1(xnfxpxfxRnnnn 汪远征汪远征 【例例4】利用余项公式估计例利用余项公式估计例1中的中的L1(175)和例和例2中的中的L2(175)的误差的误差, 并做比较。并做比较。解解 因为因为 所以所以于是于是,83)(,41)()(2523 xxfxxxf422516921014. 1| )169(| )(|max fxfMx62251

27、4431051. 1| )144(| )(|max fxfMx2211071. 1)225175)(169175(! 2)( MxR3321034. 2)225175)(169175)(144175(! 3)( MxR. )()!1()(11xnMxRnnn 13.21428513.230158汪远征汪远征 L插值的缺点：每增加一个新节点插值的缺点：每增加一个新节点, 其插值基函数其插值基函数li(x)要重要重新计算新计算, 能否充分利用已有结果呢？能否充分利用已有结果呢？ 为此作基函数：为此作基函数：即将即将pn(x)表示为：表示为： (3.8)这样这样, 当增加一个新节点时当增加一个新节点

28、时, 只需增加一个新项只需增加一个新项 1,.,2 , 1 , 0)()()(1)(10nixxxxxiii 10102010)(.)()(1)(-niinnxxcxxxxcxxccxp 10)(-niinxxc汪远征汪远征作基函数：作基函数：即将即将pn(x)表示为：表示为： (3.8) 例如例如N1(x) = c0 + c1(x x0)N2(x) = c0 + c1(x x0) + c2(x x0)(x x1) 1,.,2 , 1 , 0)()()(1)(10nixxxxxiii 10102010)(.)()(1)(-niinnxxcxxxxcxxccxp汪远征汪远征即将即将pn(x)表示

29、为：表示为： (3.8) 利用插值条件利用插值条件(5.1-1)可得可得 c0 = f0 称为一阶差商称为一阶差商称为二阶差商称为二阶差商 10102010)(.)()(1)(-niinnxxcxxxxcxxccxppn(xi) = f(xi) = fi,10010101011xxfxxffxxcfc 121020121002021202021022,)()(xxxxfxxfxxxxfxxffxxxxxxccfc ,210 xxxf 汪远征汪远征即将即将pn(x)表示为：表示为： (3.8) c0 = f0称为一阶差商称为一阶差商称为二阶差商称为二阶差商称为称为i阶差商阶差商 (i = 1,

30、2, , n),.,.,.,1011210210iiiiiiiixxxfxxxxxxfxxxxfc ,2101210202xxxfxxxxfxxfc ,10010101011xxfxxffxxcfc 10102010)(.)()(1)(-niinnxxcxxxxcxxccxp汪远征汪远征 注：差商的基本性质如下：注：差商的基本性质如下： (1) i阶差商阶差商f x0, x1, , xi可表为可表为f(x0), f(x1), , f(xi)的线性的线性组合组合 (2) 差商具有对称性差商具有对称性, 即差商与它所含节点的排列顺序无关即差商与它所含节点的排列顺序无关 iknkkkkkkkixxx

31、xxxxxxfxxxf011010).()().()(,.,.,.,.,.,.,.,00kijkjixxxxfxxxxf ,.,.,.,1011210210iiiiiiiixxxfxxxxxxfxxxxfc 汪远征汪远征 注：差商的基本性质如下：注：差商的基本性质如下： (2) 差商具有对称性差商具有对称性, 即差商与它所含节点的排列顺序无关即差商与它所含节点的排列顺序无关从而从而,.,.,.,.,.,.,00kijkjixxxxfxxxxf 1121021010,.,.,., iiiiiiixxxxxxfxxxxfxxxf,.,0211iiixxxxxf 00211211,.,.,xxxxx

32、xfxxxxfiiiiii 011011,.,.,xxxxxfxxxfiiii ,.,.,.,1011210210iiiiiiiixxxfxxxxxxfxxxxfc 汪远征汪远征 注：差商的基本性质如下：注：差商的基本性质如下： (2) 差商具有对称性差商具有对称性, 即差商与它所含节点的排列顺序无关即差商与它所含节点的排列顺序无关从而从而差商表差商表01101110,.,.,.,xxxxxfxxxfxxxfiiiii ,.,.,.,.,.,.,00kijkjixxxxfxxxxf 汪远征汪远征 注：差商的基本性质如下：注：差商的基本性质如下： (2) 差商具有对称性差商具有对称性, 即差商与

33、它所含节点的排列顺序无关即差商与它所含节点的排列顺序无关差商表差商表例例汪远征汪远征 有了差商的定义有了差商的定义, 可以证明可以证明表为表为 pn(x) = f0 +f x0, x1(x x0) + +f x0, x1, , xn(xx0)(xx1)(xxn-1) (3.9)称称(3.9)为为Newton插值多项式插值多项式, 记为记为 Nn(x) = f0 +f x0, x1(x x0) + +f x0, x1, , xn(xx0)(xx1)(xxn-1) 10102010)(.)()(1)(niinnxxcxxxxcxxccxp汪远征汪远征 【例例5】已知函数已知函数y = f(x)的数

34、据表如下的数据表如下求求(1) 次数不大于次数不大于3的插值多项式的插值多项式p3(x)通过前通过前4个数据点个数据点 (2) 次数不大于次数不大于4的插值多项式的插值多项式p4(x)通过所给通过所给5个数据点个数据点, 并并计算计算f (4.0)的近似值。的近似值。解：计算差商表如下：解：计算差商表如下：xif i一阶差商一阶差商二阶差商二阶差商三阶差商三阶差商四阶差商四阶差商1.014.22.717.82.1183.222.08.4002.8554.838.210.1250.821-0.5355.651.716.8752.8130.6870.266汪远征汪远征 【例例5】已知函数已知函数y

35、 = f(x)的数据表如下的数据表如下求求(1) 次数不大于次数不大于3的插值多项式的插值多项式p3(x)通过前通过前4个数据点个数据点 (2) 次数不大于次数不大于4的插值多项式的插值多项式p4(x)通过所给通过所给5个数据点个数据点, 并并计算计算f (4.0)的近似值。的近似值。解：解：(1) N3(x)=14.2+2.118(x1.0)+2.855(x1.0)(x2.7) 0.535(x 1.0)(x 2.7)(x 3.2)汪远征汪远征 【例例5】已知函数已知函数y = f(x)的数据表如下的数据表如下求求(1) 次数不大于次数不大于3的插值多项式的插值多项式p3(x)通过前通过前4个

36、数据点个数据点 (2) 次数不大于次数不大于4的插值多项式的插值多项式p4(x)通过所给通过所给5个数据点个数据点, 并并计算计算f (4.0)的近似值。的近似值。解：解：(2) N4(x)=14.2+2.118(x1.0)+2.855(x1.0)(x2.7) 0.535(x 1.0)(x 2.7)(x 3.2) + 0.266(x1.0)(x2.7)(x3.2)(x4.8)汪远征汪远征 将将x看成与看成与x0, x1, ., xn互异的节点互异的节点, 则按则按Newton插值公式得插值公式得上式令上式令t = x, 则因为则因为f(x) = Nn+1(x) (插值条件插值条件) niinn

37、iinnxtxxxxfxtxxxfxtxxfftN010101001001)(,.,)(,.,.)(,)( niinniinxxxxxxfxxxxxfxxxxffxf01010100100)(,.,)(,.,.)(,)(汪远征汪远征 由余项公式由余项公式(3.5)知知 niinniinxxxxxxfxxxxxfxxxxffxf01010100100)(,.,)(,.,.)(,)( niinnxxxxxxfxN010)(,.,)()(,.,)(,.,)()()(110010 xxxxxfxxxxxxfxNxfxRnnniinnn )!1()(,.,)1(10 nfxxxxfnn 汪远征汪远征(3

38、.10)!)(,.,)(10kfxxxfkk )!1()(,.,)1(10 nfxxxxfnn 汪远征汪远征 【例例6】设设f(x)=ex, 给出给出f(x)在在0, 1上上n+1个等距节点处的函个等距节点处的函数值数值 (1) 若按所给的函数值表用线性插值求若按所给的函数值表用线性插值求f (x) = ex, （0 x 1）的近似值的近似值, 使其绝对误差限不大于使其绝对误差限不大于 , 问问n应取多大应取多大 (2) 每个表值每个表值f(xi)应取几位有效数字应取几位有效数字),.,2 , 1 , 0(ninixi 61021 汪远征汪远征 【例例6】设设f(x)=ex, 给出给出f(x)

39、在在0, 1上上n+1个等距节点处的函个等距节点处的函数值数值 (1) 若按所给的函数值表用线性插值求若按所给的函数值表用线性插值求f (x) = ex, （0 x 1）的近似值的近似值, 使其绝对误差限不大于使其绝对误差限不大于 , 问问n应取多大应取多大解：解：(1) 由于由于x 0, 1, 故必有一个故必有一个i, 使得使得xi-1 x xi若若p1(x)是是f(x)在在xi-1, xi上的线性插值多项式上的线性插值多项式, 且用且用p1(x)的值的值作为作为f(x) = ex的近似值的近似值, 则由则由(3.7)及及| )(|max)!1(| )(|max1,1xnMxRnbaxnn

40、eexfxxx 1010max| )(|max211)(41| )( |max1 iiiixxxxxxxxxii),.,2 , 1 , 0(ninixi 61021 汪远征汪远征 【例例6】设设f(x)=ex, 给出给出f(x)在在0, 1上上n+1个等距节点处的函个等距节点处的函数值数值 (1) 若按所给的函数值表用线性插值求若按所给的函数值表用线性插值求f (x) = ex, （0 x 1）的近似值的近似值, 使其绝对误差限不大于使其绝对误差限不大于 , 问问n应取多大应取多大解：解：(1) 由由(3.7)及及有有由此解得由此解得n 824。| )(|max)!1(| )(|max1,1x

41、nMxRnbaxnn eexfxxx 1010max| )(|max6221110218)(41! 21| )(| neexxxRii211)(41| )( |max1 iiiixxxxxxxxxii),.,2 , 1 , 0(ninixi 61021 汪远征汪远征 【例例6】设设f(x)=ex, 给出给出f(x)在在0, 1上上n+1个等距节点处的函个等距节点处的函数值数值 (1) 若按所给的函数值表用线性插值求若按所给的函数值表用线性插值求f (x) = ex, （0 x 1）的近似值的近似值, 使其绝对误差限不大于使其绝对误差限不大于 , 问问n应取多大应取多大解：解：(1) 由此解得由

42、此解得n 824。造表时一个合适的选取是造表时一个合适的选取是n = 1000。此时步长为。此时步长为0.001。6221110218)(41! 21| )(| neexxxRii),.,2 , 1 , 0(ninixi 61021 汪远征汪远征 【例例6】设设f(x)=ex, 给出给出f(x)在在0, 1上上n+1个等距节点处的函个等距节点处的函数数值值 (2) 每个表值每个表值f(xi)应取几位有效数字应取几位有效数字解：解：(2) 因因0 x 1, 有有1 ex e, 即个位数非零即个位数非零, 由有效数位由有效数位的概念知的概念知, 每个表值至少应有每个表值至少应有7位有效数字。位有效

43、数字。61021 ),.,2 , 1 , 0(ninixi 汪远征汪远征 当节点等距时当节点等距时, 称为等距插值节点。称为等距插值节点。 此时差商此时差商 的分母为一个常数的分母为一个常数 可以期望可以期望Newton插值公式可以简单一些插值公式可以简单一些 设有设有n+1个等距插值节点个等距插值节点, 为步长。为步长。ikikkixxffxxf ,),.,2 , 1 , 0( ,0nkkhxxk nxxhn0 汪远征汪远征 设有设有n+1个等距插值节点个等距插值节点, 为步长。为步长。 【定义定义4】设设fk = f(xk), 则则 称称 为为f在在x=xk处的一阶向前差分处的一阶向前差分

44、, 称为向前差称为向前差分算子。分算子。 称称 为为f在在x=xk处的一阶向后差分处的一阶向后差分, 称为向后差称为向后差分算子。分算子。),.,2 , 1 , 0( ,0nkkhxxk nxxhn0 kkkfff 1 1 kkkfff汪远征汪远征 【定义定义4】设设fk = f(xk), 则则 称称 为为f 在在x=xk处的一阶处的一阶向前差分向前差分 称称 为为f 在在x=xk处的一阶处的一阶向后差分向后差分 称称 为为f在在x=xk处的处的m阶向前差分阶向前差分 称称 为为f在在x=xk处的处的m阶阶向后差分向后差分注：注： 由归纳法由归纳法, 可证：可证：kmkmkmfff111 11

45、1 kmkmkmfffmkmkmff kkkfff 122212 kkkfff)()(112kkkkffff kkkfff 1 1 kkkfff汪远征汪远征注：注： 差商与差分有如下关系：差商与差分有如下关系： (3.11)事实上：事实上： k = 1成立成立, 设设 （k时成立）时成立）, 则当则当k + 1时时kmkmkmfff111 kkkhkfxxxf!,010 kkkkkhkfxxxf!,01 ,0010110hfxxffxxf kkkhkfxxxf!,010 011011110,.,.,.,xxxxxfxxxfxxxxfkkkkkk hkhkfhkfkkkk)1(!01 101)!

46、1( kkkhkff 101)!1( kkhkf 汪远征汪远征注：注： 差商与差分有如下关系：差商与差分有如下关系： (3.11)事实上：事实上： k = 1成立成立, 设设 （k时成立）时成立）, 则当则当k + 1时时由归纳法原理由归纳法原理, 对所有自然数对所有自然数k成立。成立。kmkmkmfff111 101)!1( kkhkf ,.,110 kkxxxxfkkkhkfxxxf!,010 kkkhkfxxxf!,010 kkkkkhkfxxxf!,01 ,0010110hfxxffxxf kkkhkfxxxf!,010 汪远征汪远征注：注： 差分与导数的关系：差分与导数的关系：事实上

47、：事实上：).()(0 kkkfhf .,0kxx ,!100kkkxxxfhkf kkkhkfxxxf!,010 ).(!)(!)()( kkkkfhkfhk 汪远征汪远征注：注： 差分表差分表44332214433422232243133212211440433032202100432 iiiiiiiiiffffffffffffffffffffffffffffffffff 汪远征汪远征 设设 插值点插值点( ).则则 牛顿插值公式中的一般项化为：牛顿插值公式中的一般项化为：).,.,2 , 1 , 0( ,0nkkhxxk ).0( ,0 tthxx0,00 hxxtnxxhn).,.,2

48、 , 1 , 0( ,)(nkhktxxk kkjkkkjjkhjthkfxxxxxf 1001010)(!)(, 100)(!kjkjtkf 20nxxx 汪远征汪远征 设设 插值点插值点( ).则则 牛顿插值公式中的一般项化为：牛顿插值公式中的一般项化为：从而从而(3.9)表示为表示为 (3.12)20nxxx 1001010)(!)(,kjkkjjkjtkfxxxxxf 101000)(!)()(kjnkknnjtkffthxNxN 101100)(,)()(kjjnkknxxxxxfxfxN).,.,2 , 1 , 0( ,0nkkhxxk ).0( ,0 tthxx0,00 hxxt

49、nxxhn).,.,2 , 1 , 0( ,)(nkhktxxk 汪远征汪远征从而从而(3.9)表示为表示为 (3.12)称称(3.12)为牛顿前插公式。其余项：为牛顿前插公式。其余项：以差分近似表示导数。以差分近似表示导数。 101000)(!)()(kjnkknnjtkffthxNxN njnnjjnnjtnfxxnfthxR0010)1(0)()!1()()!1()()( 汪远征汪远征 设设 记记( )则则 (3.12)称称(3.12)为牛顿后插公式。为牛顿后插公式。).,.,2 , 1 , 0( ,nkkhxxnkn ).0( , tthxxn0,0 hxxtnxxhnn.)(hktx

50、xkn ).,.,2 , 1 , 0(nk . )(!)(101 kjnknknnnjtkffthxNnnxxx 2汪远征汪远征 仅满足条件仅满足条件(3.1)的插值多项式还不能全面反映被插值函数的插值多项式还不能全面反映被插值函数f(x)的性态的性态, 许多实际问题不但要求插值函数在某些节点或全许多实际问题不但要求插值函数在某些节点或全部节点上与部节点上与f(x)的导函数值也相等的导函数值也相等, 甚至要求高阶导数也相等甚至要求高阶导数也相等. 这种插值问题就是厄米特插值问题这种插值问题就是厄米特插值问题 只讨论较为简单的情形只讨论较为简单的情形汪远征汪远征 【定义定义5】已知已知 i =

51、0, 1, , n, 求插值多项式求插值多项式H(x)满足：满足： i = 0, 1, , n (3.13)则称则称H(x)为厄米特为厄米特(Hermite)插值多项式。插值多项式。注：注： 1) H(x)与与f(x)的图形在的图形在n+1个节点处相切个节点处相切.2) 插值条件有插值条件有2(n+1)个。故个。故H(x)的次数的次数2n+1.特别特别: n=1时有时有2个节点个节点, 3次多项式次多项式 )()(iiiixfyxfy iiiiyxHyxH)()(两点三次两点三次Hermite插值插值汪远征汪远征 设设令令其中其中 为三次多项式为三次多项式, 满足：满足： 101010)()(

52、yyxfyyxfxxx ).()()()()(11110000 xyxyxyxyxH )(),(xxii jijixji01)( 0)()( iijixx jijixji01)( . 0)()( jiiixx x0 x1汪远征汪远征令令其中其中 为三次多项式为三次多项式, 满足：满足：则易知则易知H(x)满足厄米特插值条件。满足厄米特插值条件。 101010)()(yyxfyyxfxxx ).()()()()(11110000 xyxyxyxyxH )(),(xxii 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 0)(1)(0)(0)(

53、10001000 xxxx 1)(0)(0)(0)(11011101xxxx 汪远征汪远征 由由 , 考虑考虑li(x) 二重零点二重零点, 考虑考虑li2(x) .又又 三次多项式三次多项式, 考虑考虑其中其中a, b待定。待定。 jijixji01)( 22)()()()( jijiixxxxbaxxlbaxx 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 汪远征汪远征考虑考虑其中其中a, b待定。待定。因为因为1= i(xi) = axi+b, 22)()()()( jijiixxxxbaxxlbaxx jijijjijixxxxx

54、xbaxxxxxax 1)(2)(2 jiiixxax 2)(0 ijxxa 2 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 汪远征汪远征考虑考虑其中其中a, b待定。待定。因为因为1= i(xi) = axi+b, 22)()()()( jijiixxxxbaxxlbaxx ijxxa 2ijiixxxaxb 211jiixxx 21 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 汪远征汪远征考虑考虑其中其中a, b待定。待定。22)()()()( jijiixxxxbaxxlb

55、axx ijxxa 2jiixxxb 21)1 , 0()21()(2 ixxxxxxxxxjijjiii 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 汪远征汪远征同理可得同理可得)1 , 0()21()(2 ixxxxxxxxxjijjiii ).1 , 0()(2 ixxxxxxxjijii .2121)(20101121010020100111210110003 xxxxxxyxxxxxxyxxxxxxxxyxxxxxxxxyxH).()()()()(11110000 xyxyxyxyxH 汪远征汪远征注：注： 一般地一般地, n

56、+1个节点个节点2n+1次厄米特插值公式：次厄米特插值公式： .2121)(20101121010020100111210110003 xxxxxxyxxxxxxyxxxxxxxxyxxxxxxxxyxH).()()()()(11110000 xyxyxyxyxH 103)()(iiiiixyxyH niiiiinxyxyxH012)()()( 汪远征汪远征注：注： 一般地一般地, n+1个节点个节点2n+1次厄米特插值公式：次厄米特插值公式：其中其中 （i=0, 1, , n）. niiiiinxyxyxH012)()()( nikkkikiiiinijjijiiixxxxxlxlxxxxl

57、xxxxx0202)()()()()(1)(21()( 103)()(iiiiixyxyH 汪远征汪远征 【例例1】设设 , 求求H3(x).解：解：x0=1, x1=2, y0=2, y1=3, y0 = 0, y1 = -1, 103221iiffx221011000)2)(12()21()( xxxxxxxxxxx 220100111)1)(25()21()( xxxxxxxxxxx 2210100)2)(1()()( xxxxxxxxx 2201011)1)(2()()( xxxxxxxxx ).()()()()(11110000 xyxyxyxyxH 汪远征汪远征 【例例1】设设 ,

58、 求求H3(x).解：解：x0=1, x1=2, y0=2, y1=3, y0 = 0, y1 = -1, H(x)=2 0(x)+3 1(x) - 1(x)= -3x3+13x2-17x+920)2)(12()( xxx 21)1)(25()( xxx 20)2)(1()( xxx 21)1)(2()( xxx ).()()()()(11110000 xyxyxyxyxH 103221iiffx汪远征汪远征 设设R3(x) = f(x) - H3(x) 【定理定理5.1】设设f(4)在在x0, x1上连续上连续, 则则 x x0, x1有有 (x0, x1)证明：证明：R3(xi) = R3

59、(xi) = 0 (i = 0, 1)可设可设R3(x) = K(x)(x x0)2(x x1)2令令 (t) = f(t) H3(t) K(x)(t x0)2(t x1)2 五个零点五个零点由罗尔定理由罗尔定理, (x0, x1) 使使 (4)( ) = 0即即 f(4)( ) K(x)4! = 0 2120)4(3)()(! 4)()(xxxxfxR ! 4)()()4( fxK 汪远征汪远征 n+1个节点个节点2n+1次厄米特插值公式：次厄米特插值公式：其中其中 （i = 0, 1, , n） n+1个节点个节点2n+1次厄米特插值公式的余项表达式为：次厄米特插值公式的余项表达式为： (

60、a, b) niiiiniiiiiinyxlxxyxlxxxlxH020212)()()()(21()( nikkkikixxxxxl0)( njjnnnxxnfxHxfxR02)22(1212)()!22()()()()( 汪远征汪远征 为使插值更准确为使插值更准确, 插值节点之间间距应较小插值节点之间间距应较小, 即增加节点即增加节点, 此时插值多项式的次数增高此时插值多项式的次数增高高次插值。高次插值。function f=runge(n)p=10.0/nx=-5:p:5;y=1./(1+x.2);xh=-5:0.25:5;yh=lagrange2(x, y, xh);x1=-5:0.2