数值分析第章插值法

1、2022-7-5第2章 插值法1第第2章章 插值法插值法/* Chapter 2 Interpolation */2.1 引言引言2.2 Lagrange插值插值2.3 差商与差商与 Newton插值插值2.4 带导数条件的带导数条件的Hermite插值插值2.5 分段低次插值分段低次插值2.6 三次样条插值三次样条插值2022-7-5第2章 插值法2&插值法是数值分析中的一个古老的分支。插值法是数值分析中的一个古老的分支。&等距节点内插法等距节点内插法隋朝数学家刘焯隋朝数学家刘焯(公元公元544-610年年)首先提出的首先提出的&不等距节点内插法不等距节点内插法唐朝数

2、学家张遂唐朝数学家张遂(公元公元683-727年年)首先提出的首先提出的&插值法在数值积分、数值微分、微分方程数值解、曲插值法在数值积分、数值微分、微分方程数值解、曲线曲面拟合、函数值近似计算中有着广泛的应用。线曲面拟合、函数值近似计算中有着广泛的应用。2.1 引言引言2.1.1 插值法的提出插值法的提出F以近似计算函数值为例说明插值法的应用。以近似计算函数值为例说明插值法的应用。历史背景历史背景2022-7-5第2章 插值法3插值法就是一种最简单的重要方法插值法就是一种最简单的重要方法函数的插值法的提出背景函数的插值法的提出背景实际问题中经常要涉及到实际问题中经常要涉及到函数值的计算

3、函数值的计算问题：问题：（1）如果如果函数表达式函数表达式本身比较复杂，且需要多次本身比较复杂，且需要多次重复计重复计算算时，计算量会很大；时，计算量会很大； （2）有的函数甚至有的函数甚至没有表达式没有表达式，只是一种，只是一种表格函数表格函数，而，而我们需要的函数值不在该表格中。我们需要的函数值不在该表格中。 对于这两种情况，我们都需要寻找一个对于这两种情况，我们都需要寻找一个计算方便且表计算方便且表达简单达简单的函数来的函数来近似代替近似代替，这就是，这就是数值逼近数值逼近问题。问题。 2022-7-5第2章 插值法4设函数设函数f(x)在区间在区间a,b上有定义，且已知在点上有定义，且

4、已知在点 ax0 x1 xn b 处的函数值处的函数值 y0 = f(x0), y1 = f(x1), yn = f(xn)，若存，若存在一简单的函数在一简单的函数 P(x)，满足条件，满足条件P(xi) = f(xi) (i = 0,1, n)，就称就称P (x) 称为称为f(x) 的的插值函数插值函数。插值法插值法点点x0 , x1 , , xn 称为称为插值节点插值节点，区间，区间a,b称为称为插值区插值区间，间，求插值函数求插值函数P(x)的方法称为的方法称为插值法插值法。几何几何意义：意义：x0 x1x2x3x4xP(x) f(x)2022-7-5第2章 插值法5常用常用插值函数的类

5、型插值函数的类型代数代数插值：多项式插值插值：多项式插值, 0,)(0111 nnnnnaaxaxaxaxP有理有理插值：有理分式函数插值：有理分式函数三角三角插值：三角函数插值：三角函数)()()(xQxPxPnm 2.1.2 多项式插值多项式插值/* Polynomial Interpolation */ ), 1 , 0()(niyxPii （1.3）bxxxan 10 设在区间设在区间 上给定上给定 个点个点,ba1 n上的函数值上的函数值 , ,求次数不超过求次数不超过 的多项式的多项式 ，使，使), 1 , 0)(nixfyii n)(xP多项式插值问题多项式插值问题 2022-7

6、-5第2章 插值法6由由插值条件插值条件得关于系数得关于系数 的的 元线性方程组元线性方程组naaa,101 n ,101111000010nnnnnnnnnyxaxaayxaxaayxaxaa（1.4） 问题：问题： P(x)是否存在？若存在，是否唯一？如何求？是否存在？若存在，是否唯一？如何求？nnxaxaaxP 10)(系数矩阵为系数矩阵为,1111100 nnnnnxxxxxxA（1.5）nnnnnxxxxxxA1010111 2022-7-5第2章 插值法7称为称为范德蒙德（范德蒙德（Vandermonde）矩阵）矩阵, ,由由 互异，故互异，故),1 ,0(nixi .0)(det

7、1, njiojijixxA因此线性方程组因此线性方程组（1.4）的解的解 存在且唯一存在且唯一. .naaa,10 结论结论定理定理1 设设x0 ,x1,xn 是是n+1个互异节点个互异节点,函数函数f(x)在这组节在这组节点的值点的值yk=f(xk)(k=0,1,n)是给定的，那么存在唯一的次是给定的，那么存在唯一的次数数n的的多项式多项式P (x)满足满足 P (xk)= yk, k=0,1,n。?P(x) 但遗憾的是但遗憾的是方程组方程组(1.4)是病态方程组是病态方程组,阶数阶数n越高，病态越高，病态越严重越严重。为此我们从另一途径寻求获得。为此我们从另一途径寻求获得P(x) 的方法

8、的方法-Lagrange插值和插值和Newton插值。（这两种方法称为基函数法）插值。（这两种方法称为基函数法）2022-7-5第2章 插值法8Interpolation polynomial 2022-7-5第2章 插值法92.2 拉格朗日多项式拉格朗日多项式 niyxPiin,., 0,)( 求求 n 次多项式次多项式 使得使得nnnxaxaaxP 10)(条件：条件：无重合节点，即无重合节点，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( 使得使得111001)(,)(yxPyxP P1(x) 是过是过 ( x0 , y0 ) 和和

9、 ( x1, y1 ) 两点的直线。两点的直线。)(1xP101xxxx 010 xxxx = y0 + y12.1.1 线性插值与抛物插值线性插值与抛物插值两点式两点式)()(0010101xxxxyyyxP 点斜式点斜式)(001010 xxxxxxy ()ff线性插值线性插值2022-7-5第2章 插值法10二次插值二次插值n = 2已知已知 x0 , x1 , x2; y0 , y1 ,y2 , 求求22102)(xaxaaxP 使得使得002,)(yxP112)(yxP 222)(yxP ,2020100 xaxaay 2121101xaxaay 2222102xaxaay 方程组求

10、解麻烦方程组求解麻烦抛物插值抛物插值 思路：思路：对于线性插值的对于线性插值的两种形式解两种形式解进行适当的分析进行适当的分析, 从从中寻求规律得到中寻求规律得到拉格朗日插值拉格朗日插值(公式公式)和和牛顿插值牛顿插值(公式公式).我们先来看看如何得到我们先来看看如何得到二次拉格朗日插值公式二次拉格朗日插值公式.)(1xP101xxxx 010 xxxx = y0 + y1两点式两点式)()(0010101xxxxyyyxP 点斜式点斜式)(001010 xxxxxxy ()ff2022-7-5第2章 插值法11 首先首先, 线性插值的两点式可看作是两个特殊的一次线性插值的两点式可看作是两个特

11、殊的一次式的一种线性组合式的一种线性组合.101xxxx 010 xxxx )(1xP= y0 + y1 10)(iiiyxl对称式对称式l0(x)l1(x)实质上实质上0l（x）和）和1l（x）即是满足函数表）即是满足函数表 的一次插值多项式的一次插值多项式 ,称称l0(x)和和l1(x)为以为以x0,x1为节点的基本插为节点的基本插值多项式，也称为值多项式，也称为线性插值线性插值的的插值基函数插值基函数 。基函数的线性组合基函数的线性组合基函数法基函数法满足满足 li(xj)= ij 显然有显然有l0(x)+ l1(x)1.其中，其中， l0(x)和和l1(x)满足：满足： l0(x0)=

12、1, l0(x1)=0, l1(x0)=0, l1(x1)=1, L1(x) L1(xj) 10)(iiiyxjl =yj2022-7-5第2章 插值法12启发启发: :其中，其中，l0(x), l1(x), l2(x)都是都是二次多项式二次多项式，且应满足，且应满足满足满足(2.1) 的的 l i(x) 是否存在是否存在?若存在，具有什么形式呢若存在，具有什么形式呢?（2.1）二次二次Lagrange插值多项式为插值多项式为 L(x)= y0l0(x) + y1l1(x) + y2l2(x) 二次插值是否能由一些二次插值是否能由一些二次插值基函数二次插值基函数来线性组合？来线性组合？先考虑先

13、考虑 l0(x)。 l0(x) 0(x x1)(x x2), 其中其中 0 是待定系数。是待定系数。2022-7-5第2章 插值法13同理同理 l1(x) 1(x x0)(x x2), l2(x) 2(x x0)(x x1),1(x1x0)(x1x2)12(x2x0)(x2x1)1此即此即二次拉格朗日插值公式二次拉格朗日插值公式, 其中其中, l0(x), l1(x), l2(x)是满足是满足(2.1)的特殊的特殊(基本基本)二次插值多项式二次插值多项式;称为称为二次插值基函数二次插值基函数.L2(x)= y0+ y1+ y2(x - -x0)(x - -x2)(x1- -x0)(x1- -x

14、2)(x - -x1)(x - -x2)(x0- -x1)(x0- -x2)(x - -x0)(x - -x1)(x2- -x0)(x2- -x1)0(x0 x1)(x0 x2)1 l0(x) 0(x x1)(x x2), 由由 l0( x0)=1，所以，所以 0(x0 x1)(x0 x2)1，则，则 L2(xj) 20)(iiiyxjl =yj2022-7-5第2章 插值法14n 1li(x)每个每个 li 有有 n 个根个根 x0 xi xn njj i jiniiixxCxxxxxxCxl00)().().()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)

15、()()( niiinyxlxL0)()( Lagrange Polynomial与与 有关，而与有关，而与 无关无关节点节点f2.2.2 拉格朗日插值多项式拉格朗日插值多项式)()()()()()()(110110niiiiiiniiixxxxxxxxxxxxxxxxxl )., 1 , 0(ni 展开展开n 次插值多项式次插值多项式 :求次数求次数n的多项式的多项式Ln(x), 使其满足使其满足 Ln(x0)=y0 , Ln(x1)=y1 , . , Ln(xn)=yn 令令 Ln(x)=l0(x)y0 + l1(x)y1 + +ln(x)yn ., 0;, 1)(jijixlji2022

16、-7-5第2章 插值法15例例1 已知已知 ， ，用线性插值求，用线性插值求 的近似值的近似值.解：解：xy 9, 410 xx73, 210 yy基函数分别为基函数分别为949)(0 xxl494)(1 xxl)9(51 x)4(51 x插值多项式为插值多项式为L1(x)=l0(x)y0 + l1(x)y1)4(513)9(512 xx)4(513)9(512 xx)6(51 x7)7(1L 6 . 2 2022-7-5第2章 插值法16其中其中满足条件满足条件 nkkknxlyxL0)()( ), 1 , 0,(., 0;, 1)(nkjjkjkxljk)()()()()()()(1101

17、10nkkkkkknkkkxxxxxxxxxxxxxxxxxl )., 1 , 0()()(0njyxlyxLjnkjkkjn （2.9）易求得易求得 ),()()()(1101nkkkkkkknxxxxxxxxx ),()()(101nnxxxxxxx（2.10）记记.)()()()(011 nkknknknxxxxyxL （2.11）2022-7-5第2章 插值法17 注意注意: : 次插值多项式次插值多项式 通常是次数为通常是次数为 的多项式，的多项式，n)(xLnn特殊情况下次数可能小于特殊情况下次数可能小于 . .n注：注：若不将多项式次数限制为若不将多项式次数限制为 n ，则插值多

18、项式，则插值多项式不唯一不唯一。例如例如 也是一个插值也是一个插值多项式，其中多项式，其中 可以是任意多项式。可以是任意多项式。 niinxxxpxLxP0)()()()()(xp例例2 求经过求经过A(0,1)，B(1,2)，C(2,3)三个点的二次三个点的二次Lagrange插值多项式插值多项式.解：解：.322110221100 yxyxyx，；，；，2120210121012002010212)()()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxL 13)12)(02()1)(0(2)21)(01()2)(0(1)20)(10()2)(1( xxxxxxx

19、插值条件插值条件2022-7-5第2章 插值法18设节点设节点)1( nf在在(a , b)内存在内存在, 考察考察截断误差截断误差)()()(xLxfxRnn , baCfn bxxxan 10，且，且 f 满足条件满足条件 , 2.2.3 插值余项插值余项 (Remainder)罗尔定理罗尔定理 设设f(x)在在a,b内连续，在内连续，在(a,b)内可导，且有内可导，且有 f(a)=f(b)；则在；则在(a,b)内一定存在一点内一定存在一点，使得，使得 。0)( f显然显然 Rn(xi ) =f(xi)-Ln(xi)=0 , i=0,1,n, 设设Rn(x)=K(x) n+1(x), 现在

20、任意固定一点现在任意固定一点 x a,b, xxi (i=0,1,n),引进辅助函数引进辅助函数 g(t)=f(t)- Ln(t)-K(x) n+1(t), 则则g(t)在在(a,b)上具有上具有n+1阶导数，在阶导数，在 t= x0, x1, xn, x 诸点诸点处函数值皆等于零。处函数值皆等于零。即即g(t)在在a,b中有中有n+2个零点。个零点。由由罗尔定理罗尔定理知知g(t)在在a,b中有中有n+1个零点。个零点。2022-7-5第2章 插值法19如此反复，最后可推知如此反复，最后可推知g(n+1)(t)在在a,b中有中有1个零点个零点 ，即有，即有 g(n+1)( )=0, a b.

21、)()()()()()1(1)1()1()1(txKtLtftgnnnnnn )!1)()()1( nxKtfn则有则有0)()!1()()()1()1( xKnfgnn)!1()()()1( nfxKn从而从而)()()!1()()()()(10)1(nnnxxxxxxnfxLxfxR 截断误差截断误差存存在在时时成成立立)()1(xfn n = 1n = 2,)( )(21)()(21)(101021xxxxxxfxfxR ，,)()( )(61)(202102xxxxxxxxfxR ，（2.12）2022-7-5第2章 插值法20注：注：FF 通常不能确定通常不能确定 x , 而是估计而

22、是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。1)1()( nnMxf niinxxnM01|)!1(FF当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项多项式是式是精确精确的。的。0)()1( xfn0)( xRn当当 时，时，)()(nkxxfk, 0)()(0 xlxxxRniikikn0)()1(xfn, ,于是于是由此得由此得., 1 , 0,)(0nkxxlxkniiki （2.17）特别当特别当 时，时，0k. 1)(0 xlnii（2.18）)()(0 xlx

23、xLniikin 2022-7-5第2章 插值法21 例例3 证明证明 ，其中其中 是关于点是关于点 的插值基函数的插值基函数. . 0)()(502xlxxiii)(xli510,xxx证明证明)()2()()(5022502xlxxxxxlxxiiiiiii )()(2)(50250502xlxxlxxxlxiiiiiiii . 02222 xxx2022-7-5第2章 插值法22例例4 已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x18

24、5500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL这里这里)4,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)()(,22sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.776143,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R选择要计算的选择要计算的 x 所在的区所在的区间的端点，插值效果较好。间的端点，插值效果

25、较好。2022-7-5第2章 插值法23n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.7660444高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好，嘿高就越好，嘿嘿嘿2022-7-5第2章 插值法24Quiz: 给定给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是下面哪个是 l2(x)的

26、图像？的图像？ y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x ABC 2124563 1 32 34 3 5 36()()()()()( )()()()()()xxxxxlx 2022-7-5第2章 插值法25 Lagrange插值插值公式公式(利用利用插值基函数插值基函数很容易得到很容易得到): 含义直观含义直观,结构紧凑结构紧凑,在理论分析中非常方便在理论分析中非常方便; 计算机上实现也很容易计算机上实现也很容易. 也有一些也有

27、一些缺点缺点： 一是一是计算量大计算量大，这是显然的；另外，还有一个更严重的，这是显然的；另外，还有一个更严重的缺点，当插值节点增加时，缺点，当插值节点增加时，全部插值基函数全部插值基函数均要随之均要随之变化变化，整个计算工作必须从头开始：不仅原来的每一项都要改变，整个计算工作必须从头开始：不仅原来的每一项都要改变，还要还要增加一项增加一项计算。计算。 为克服上述两个缺点为克服上述两个缺点, 努力：把插值多项式变形为努力：把插值多项式变形为便于计算便于计算的形式。的形式。 希望：希望：计算改变的过程中计算改变的过程中,尽可能能利用已有的计算结果尽可能能利用已有的计算结果. 下面我们将看到下面我

28、们将看到,这是可能的。我们可以有具有这是可能的。我们可以有具有“承袭性承袭性”的所谓牛顿公式。的所谓牛顿公式。2022-7-5第2章 插值法26拉格朗日插值拉格朗日插值Ln(x)还可以写成什么样的表达式？还可以写成什么样的表达式？)(xLk记记 是关于节点是关于节点 的的k 次拉格朗日插值多项次拉格朗日插值多项式，则有式，则有kxxx,10)()()()(1101 kkkxxxxxxAxLxL2.3 均差与牛顿插值多项式均差与牛顿插值多项式 kjkjkjjjjjjjjxxxxxxxxxxxxxfA011110)()()()()()()()()()()()(112010 xLxLxLxLxLxL

29、xLxLnnn nkkknxLxLxLxL110)()()()( nkkkjjkjxxxxxxxxfxf1110010)()()()()()( 2022-7-5第2章 插值法27记记,210kxxxxf kjjkjxxf01)()( kjkjkjjjjjjjjxxxxxxxxxxxxxf011110)()()()()()(,)(,)(,)()(11010102100100 nnnxxxxxxxxxfxxxxxxxfxxxxfxfxL,)()()()(101101kkkkxxxfxxxxxxxLxL )(xNn 2022-7-5第2章 插值法28均差定义均差定义2.3.1 均差及其性质均差及其性

30、质/* divided difference */ 定义定义2 称称 为函数为函数f(x)关于点关于点x0,xk的的一阶均差一阶均差.称称 为为f(x) 的的二阶均差二阶均差.一般地一般地, 称称 为为 f(x) 的的k 阶均差阶均差(差商差商). fx0,xk =f(xk)- -f(x0)xk- -x0 fx0,x1,xk=fx0,xk- - fx0,x1xk- -x1 fx0,x1,xk=fx0, xk-2,xk- - fx0,x1, ,xk-1xk- -xk-1均差的基本性质均差的基本性质 1 n 阶均差可表示为函数值阶均差可表示为函数值f(x0), f(x1), f(xn)的线性组合的

31、线性组合,即即 fx0,x1,xn=f(xj)(xj- -xj+1)(xj- -xn)(xj- -xj-1)(xj- -x0) nj=0注：注：均差与节点的排列次序无关均差与节点的排列次序无关均差的对称性均差的对称性 fx0,x1,xn= fx1,x0,x2,xn= = fx1, , xn ,x02022-7-5第2章 插值法29 fx0,x1,xk=fx1, xk-1,xk- - fx0,x1, ,xk-1xk- -x02 由性质由性质1可得可得:FF 实际计算过程为实际计算过程为f (x0)f (x1)f (x2)f (xn 1)f (xn)f x0, x1f x1, x2 f xn 1,

32、 xnf x0, x1 , x2 f xn 2, xn 1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn 1, xn, xn+1 f x1, , xn+1 f x0, , xn+1均差计算可列均差表如下：均差计算可列均差表如下：2022-7-5第2章 插值法30证明：证明：上式右端的分子是上式右端的分子是 的的m次多项式次多项式 ，记为，记为x则则( )h x为为m-1次多项式次多项式3 若若 是一个依赖于是一个依赖于 的的 次多项式，次多项式，则则 是关于是关于 的的 次多项式。次多项式。 ,.,0kxxxfx,.,10 kxxxfmx1 m1100,.,.,

33、 kkkxxxxfxxxf,.,10 kxxxf,.,.,)(100 kkxxfxxxfxg,.,.,)(10011 kkkkxxfxxxfxg0 )()()(1xhxxxgk ,.,)(,.,.,101100 kkkkkxxxxfxxxxfxxxf2022-7-5第2章 插值法31,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf ).(.)()()(10102010 nnnxxxxaxxxxaxxaaxP12 n+11+ (x x0) 2+ + (x x0)(x xn 1) n+1.)(,

34、)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)2.3.2 牛顿插值多项式牛顿插值多项式/* Newtons Interpolation */Nn(x)牛顿均差插值多项式牛顿均差插值多项式,显然有显然有Nn(xi)=f(xi)(i=0,1,2,n),)(,210221010 xxxxfxxxxxfxxxf 32022-7-5第2章 插值法32 fx0, x1,xn =f(n)()n!,ba 4 若若f(x)在在a,b上存在上存在n阶导数阶导数, 且节点且节点x0,x1

35、,xn a,b,则则n阶均差与导数关系如下阶均差与导数关系如下: 析析nnnxxxnxNxfxR,1)()()(10个零点个零点有有 应用应用n次罗尔定理有次罗尔定理有 fx0, x1,xn =f(n)()n!,ba .)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfNn(x)余项形式余项形式)().(,.,100nnnxxxxxxxxxf Rn(x)注：注： 由由n(x) Ln(x)， 只是算法不同，故其余项也相同，只是算法不同，故其余项也相同，)(!)1()()(,.,1)1(10 xnfxxxxfnxnnn 2022-7-5第2章

36、插值法33 例例5 依据如下函数值表建立不超过依据如下函数值表建立不超过3次的拉格朗日插值次的拉格朗日插值多项式及牛顿插值多项式多项式及牛顿插值多项式Nn(x),并验证插值多项式的唯一性并验证插值多项式的唯一性. 解解: (1)拉格朗日插值多项式拉格朗日插值多项式Ln(x).插值基函数插值基函数xk0124f (xk)19233拉格朗日插值多项式为拉格朗日插值多项式为:121445411 )(3)(23)(9)()()(233210303xxxxlxlxlxlyxlxLiii,12181241)24)(14)(04()2)(1)(0()(,4541)42)(12)(02()4)(1)(0()(

37、,38231)41)(21)(01()4)(2)(0()(, 1478781)40)(20)(10()4)(2)(1()(233232231230 xxxxxxxlxxxxxxxlxxxxxxxlxxxxxxxl2022-7-5第2章 插值法34xkf (xk) 一阶均差一阶均差二阶均差二阶均差三阶均差三阶均差011922343(2) 牛顿插值多项式牛顿插值多项式Nn(x). 建立如下差商表建立如下差商表牛顿插值多项式为牛顿插值多项式为:121445411 )2)(1)(0(411) 1)(0(3)0(81)(233xxxxxxxxxxN411(3) 唯一性验证唯一性验证.通过比较牛顿插值多项

38、式和拉格朗日插值多项式通过比较牛顿插值多项式和拉格朗日插值多项式,知知: Nn(x) = Ln(x)这一事实与插值多项式的唯一性一致这一事实与插值多项式的唯一性一致. 814-103-82022-7-5第2章 插值法35注：注： 当题目中没有指明用哪一种方法建立插值多项式时，原则上拉格当题目中没有指明用哪一种方法建立插值多项式时，原则上拉格朗日插值方法和牛顿插值方法都可行，做题目时选较为方便的一种方法。朗日插值方法和牛顿插值方法都可行，做题目时选较为方便的一种方法。近似计算时，由于牛顿插值多项式的非整理形式可以直接写成秦九韶算近似计算时，由于牛顿插值多项式的非整理形式可以直接写成秦九韶算法的形

39、式，计算量小，且当节点增加时只需增加一项，前面的工作依然法的形式，计算量小，且当节点增加时只需增加一项，前面的工作依然有效，因而通常情况下牛顿插值比较方便，拉格朗日插值则没有该优点，有效，因而通常情况下牛顿插值比较方便，拉格朗日插值则没有该优点，但在理论证明上因其基函数的特点广泛应用。但在理论证明上因其基函数的特点广泛应用。.)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfNn(x).)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfNn+1(x)().(,.,1010nnnnxxxx

40、xxxxxf 2022-7-5第2章 插值法36差商表差商表i0123xi-2-112 (xi)531721练习练习 给出函数给出函数y= (x)的的函数表函数表写出函数写出函数y= (x)的的差商表，并求节点为差商表，并求节点为x0,x1的一次插值的一次插值x0,x1, x2的二次的二次插值和插值和x0,x1,x2,x3的三次插值多的三次插值多项式项式.ixi(xi)一阶一阶差商差商二阶二阶差商差商三阶三阶差商差商0123-2-112531721-2743-1-1N1(x)=5-2(x+2)=1-2x解解N2(x)=1-2x+3(x+2)(x+1) =3x2+7x+7N3(x)=3x2+7x

41、+7-(x+2)(x+1)(x-1)=-x3+x2+8x+92022-7-5第2章 插值法372.3.4 差分形式的牛顿插值公式差分形式的牛顿插值公式 设有等距节点，设有等距节点，其中称为其中称为步长步长。), 1 , 0(0nkkhxxkh 设设 点的函数值为点的函数值为 ，称，称 为为 处以处以 为步长的为步长的一一阶（阶（向前）差分向前）差分. .kx), 1 , 0)(nkxffkk,1kkkfffkxh 类似地称类似地称 为为 处的处的二二阶差分阶差分. .kkkfff12kx 一般地，一般地，knknknfff111 为为 处的处的 阶差分阶差分. .kxn（3.8）差分差分例例

42、f(x)=x2 , xi=i (i=1,2,n), 求求nf(xi),(i=1,n-1) n3解：解：f(xi)=f(xi+1)-f(xi)=(i+1)2-i2=2i+1 2f(xi )= f(xi+1)- f(xi)=2(i+1)+1-(2i+1)=23f(xi )= 2f(xi+1)- 2f(xi )= 2-2=0nf(xi)=0 n32022-7-5第2章 插值法38两个常用算子符号两个常用算子符号,kkff I,1 kkffEI 称为称为不变算子不变算子Eh称为步长为称为步长为 的的移位算子移位算子,)(1kkkkkkffffffIEIE 差分与函数值差分与函数值knknff) IE(

43、 kjnnjjfjn E)1(0（3.9）,)1(0jknnjjfjn 其中其中 为二项式展开系数为二项式展开系数!)1()1(jjnnnjn 反之反之可得可得 .0kjnjknfjnf （3.10）knf)I ( ,0kjnjfjn knknffE 2022-7-5第2章 插值法39,111hfxxffxxfkkkkkkk kkkkkkkkkxxxxfxxfxxxf 212121,2122kfh 均差与差分的关系均差与差分的关系,1!1,kmmmkkfhmxxf ).,2,1(nm （3.11）),()(fhfnnkn （3.12）其中其中 . .),(nkkxx差分表差分表差分与导数的关系

44、差分与导数的关系xi fi 2 3 n x0 f0 x1 f1x2 f2x3 f3xn-3 fn-3xn-2 fn-2xn-1 fn-1xn fnf0f1f2fn-3fn-2fn-12f02f12fn-32fn-23f03fn-3nf02022-7-5第2章 插值法40令令 ，用差分代替差商，用差分代替差商thxx002000! 2) 1()(fttftfthxPn,!) 1() 1(0fnntttn（3.13）),()!1()() 1()()1(1nnnfhnntttxR).,(0nxx（3.14）牛顿向前插值公式牛顿向前插值公式/* Newtons forward-difference f

45、ormula */给出给出 在在 xxfcos)( 1 .0,5 ,1 ,0, hkkhxk处的函数值，试用处的函数值，试用4次牛顿前插公式计算次牛顿前插公式计算 的近似值的近似值并估计误差并估计误差.)048. 0(f例例7解解 为使用牛顿插值公式，先构造差分表为使用牛顿插值公式，先构造差分表. . .)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfn(x)牛顿向前插值公式的余项牛顿向前插值公式的余项2022-7-5第2章 插值法4187758.050.04348.000920.092106.040.000035.003428.0000

46、10.000955.095534.030.000002.000025.002473.000012.000980.098007.020.000013.001493.000993.099500.010.000500.000000.100.0)(325432 fffffxfxkk差差分分表表表取取, 1 . 0,048. 0hx则则,48. 01 . 00048. 00hxxt得得 )048. 0(4P048. 0cos)048. 0(f)00500. 0(48. 000000. 1)00993. 0(2) 148. 0)(48. 0()00013. 0)(248. 0)(148. 0)(48. 0

47、(! 31)00012. 0)(348. 0)(248. 0)(148. 0)(48. 0(! 4199885. 02022-7-5第2章 插值法42误差估计误差估计554)4)(3)(2)(1(! 5)048.0(htttttMR,105845.17其中 .565.06 .0sin5M48.0 t2022-7-5第2章 插值法432022-7-5第2章 插值法442.4 埃尔米特插值埃尔米特插值 假设函数假设函数y=f(x)是是 在在a,b上有一定光滑性的函数上有一定光滑性的函数,在在a,b 上有上有n+1个互异点个互异点xoxn, f(x)在这些点上取值在这些点上取值yo.yn.求一个求一

48、个确定的函数确定的函数p(x)在上面在上面n+1个点上满足个点上满足p(xi)=yi i=0,1,n.这是这是最简单的插值问题最简单的插值问题,如果除了知道如果除了知道f(x)在插值节点上的取值外在插值节点上的取值外,还知道还知道f(x)在插值节点在插值节点xi上的上的 1min阶导数，如何来构造插阶导数，如何来构造插值函数呢值函数呢? Hermite插值就是既满足插值节点插值就是既满足插值节点xi的函数值条件的函数值条件又满足微商条件的插值函数。又满足微商条件的插值函数。 Hermite插值也叫带指定微商值的插值插值也叫带指定微商值的插值,它要构造一个插它要构造一个插值函数值函数,不但在给定

49、节点上取函数值不但在给定节点上取函数值,而且取已知微商值，使而且取已知微商值，使插值函数和被插函数的密和程度更好插值函数和被插函数的密和程度更好 。2022-7-5第2章 插值法452.4.1 重节点均差与泰勒插值重节点均差与泰勒插值 定理定理3 设设 为为 上的相异上的相异节点，则节点，则 是其变量的连续函数是其变量的连续函数. .nnxxxbaCf,10,ba,10nxxxf)()()(lim,lim000000 xfxxxfxfxxfxxxx 重节点的一阶均差重节点的一阶均差)(,lim,0100001xfxxfxxfxx 重节点均差重节点均差),(,!)(,0)(10nnnxxnfxx

50、xf )(! 1)(lim,0000 xffxxfx 重节点的二阶均差重节点的二阶均差)(21! 2)(lim,lim,021000000201xffxxxfxxxfxxxxx 2022-7-5第2章 插值法46).(!1,lim,0)(100000 xfnxxxfxxxfnnxxi （4.1）令令),2, 1(0nixxi.)(!)()()()(00)(000nnnxxnxfxxxfxfxP （4.2）这实际上是在点这实际上是在点 附近逼近附近逼近 的一个带导数的插值多项的一个带导数的插值多项式，它满足条件式，它满足条件0 x)(xf., 1 ,0),()(0)(0)(nkxfxPkkn （

51、4.3）重节点的重节点的n阶均差阶均差泰勒插值泰勒插值泰勒多项式泰勒多项式.)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfPn(x)泰勒插值多项式泰勒插值多项式2022-7-5第2章 插值法47一个埃尔米特插值多项式，余项为一个埃尔米特插值多项式，余项为,)()!1()()(10)1( nnnxxnfxR ),(ba（4.4）泰勒插值是牛顿插值的极限形式，是只在一点泰勒插值是牛顿插值的极限形式，是只在一点 给出给出 个插值条件所得到的个插值条件所得到的 次埃尔米特插值多项式次埃尔米特插值多项式. . 0 xn1n2.4.2 两个典型的埃

52、尔米特插值两个典型的埃尔米特插值不完全导数的不完全导数的Hermite插值插值 考虑满足条件考虑满足条件 及及 的插值多项式及其余项表达式的插值多项式及其余项表达式. . )2, 1 ,0()()(ixfxPii)()(11xfxP多项式的曲线通过多项式的曲线通过),(,(),(,(),(,(221100 xfxxfxxfx)(,)()(0100 xxxxfxfxP )(,10210 xxxxxxxf 故故),)()(210 xxxxxxA 2022-7-5第2章 插值法48.)(,)(,)(210121001101xxxxxxxfxxxxfxfA 可由条件可由条件 确定确定)()(11xfx

53、P A通过计算通过计算余项余项可设可设),()()()(2210 xxxxxxxkxR 其中其中 为待定函数为待定函数. . )(xk).()()()()()(2210 xtxtxtxktPtftg 构造构造a, b上有四个零点上有四个零点x， x0，x1，x2 ；其中；其中x1为为 二重零点二重零点. 利利用用Rolly定理，知定理，知g(t)在在x0，x1，x2 ，x组成的三个小区间内组成的三个小区间内至少各有一个零点，记为至少各有一个零点，记为 1, 2, 3 ，加上，加上x1 ，在，在a, b上至上至少有少有4个零点个零点., 0)(!4)()()4()4( xkfg 反复应用罗尔定理

54、，得反复应用罗尔定理，得 在在 内至少有一个内至少有一个零点零点，)()4(tg),(ba故有故有),()()(! 41)(2210)4(xxxxxxfxR (4.5)余项表达式为余项表达式为 2022-7-5第2章 插值法49 例例8 给定给定 试求试求 在在 上的三次埃尔米特插值多项式上的三次埃尔米特插值多项式 ，使它满足，使它满足并写出余项表达式并写出余项表达式. .,49, 1,41,)(2102/3xxxxxf)(xf49,41)(xP),2, 1 ,0()()(ixfxPii),()(11xfxP由题意可求出由题意可求出,827)49(, 1)1(,81)41(210 ffffff

55、.23)1(,23)(2/1 fxxf构造均差表构造均差表 解解 101982749301167814111iifx均差表4-表2.3011,67,21010 xxxfxxf令令).49)(1)(41()1)(41(3011)41(6781)( xxxAxxxxP2022-7-5第2章 插值法50可得可得.22514)40116723(1516A故故,25145023345026322514)49)(1)(41(22514)1)(41(3011)41(6781)(23xxxxxxxxxxP余项余项).49,41()49()1)(41(169! 41)49()1)(41(! 4)()()()(2

56、2/52)4( xxxxxxfxPxfxR 由条件由条件 ，可得，可得23)1()1(fP,23)45(4343301167)1(AP2022-7-5第2章 插值法51,)()()()()(11113 kkkkkkkkmxmxyxyxxH (4.7)基函数法基函数法 插值节点取为插值节点取为 及及 ，插值多项式为，插值多项式为 ，插值条，插值条件为件为kx1kx)(3xH其中其中 是关于节点是关于节点 及及 的三次的三次埃尔米特插值基函数，分别满足埃尔米特插值基函数，分别满足)(),(),(),(11xxxxkkkkkx1kx,)(3kkyxH ,)(3kkmxH .)(;)(113113kk

57、kkmxHyxH(4.6)完全导数完全导数两点三次埃尔米特插值两点三次埃尔米特插值插值多项式插值多项式, 1)( kkx , 0)(1 kkx , 0)(1 kkx ,0)( kkx ,0)( kkx , 1)( kkx , 0)(1 kkx , 0)(1 kkx , 0)(1 kkx , 1)(11 kkx , 0)(1 kkx . 1)(11 kkx ,0)(1 kkx ,0)(1 kkx , 0)(1 kkx , 0)(11 kkx 2022-7-5第2章 插值法52 ,)(211 kkkkxxxxbaxx根据给定条件可令根据给定条件可令显然显然, 0)(1 kkx , 0)(1 kkx

58、 再利用再利用, 1)( baxxkkk 及及, 02)(1 axxbaxxkkkkk , 1)( kkx , 0)()(1 kkkkxx , 0)(1 kkx 解得解得,21,211 kkkkkxxxbxxa于是求得于是求得.21)(2111 kkkkkkkxxxxxxxxx 同理可得同理可得2111121)( kkkkkkkxxxxxxxxx (4.8)(4.9)2022-7-5第2章 插值法53 ,)(211 kkkkkxxxxxxax 为求为求 ，由给定条件可令，由给定条件可令)(xk直接由直接由 ，得到，得到1)(axkk ,)(211 kkkkkxxxxxxx (4.10) .)(

59、2111 kkkkkxxxxxxx (4.11),0)()(1 kkkkxx , 1)( kkx , 0)(1 kkx 同理同理2022-7-5第2章 插值法54最后代入，得最后代入，得12112111211121113)()(2121)( kkkkkkkkkkkkkkkkkkkkkkkkmxxxxxxmxxxxxxyxxxxxxxxyxxxxxxxxxH(4.12).,(,)()(! 41)(1212)4(3kkkkxxxxxxfxR(4.13)余项余项 ，)()()(33xHxfxR2022-7-5第2章 插值法55重节点均差构造重节点均差构造Hermite插值插值Newton形式的形式的

60、Hermite插值插值求一个四次插值多项式求一个四次插值多项式 ，满足，满足)(xH40)1(,10)1(,0)1(;2)0(,1)0( HHHHH例例9并写出插值余项的表达式。并写出插值余项的表达式。解：解：构造差商表构造差商表2022-7-5第2章 插值法56根据根据Newton插值公式插值公式 )(xH2222)1(5)1(6321 xxxxxx插值余项插值余项32)5()1(!5)()( xxfxR10 2022-7-5第2章 插值法57 ., 1 , 0 ,)( ,)( )(12 , 1 , 0,)()(1112121210njyxHyxHxHnnjyxfyxfbxxxannjjnjjnnjjjjn 满满足足次次