李庆扬数值分析-插值法课件.ppt

1、 描述事物之间的数量关系：函数。 有两种情况： 一是表格表格形式一组离散的数据离散的数据来表示函数关系；另一种是函数虽然有明显的有明显的表达式表达式，但很复杂，但很复杂，不便于研究和使用。 从实际需要出发：对于计算结果允许有一定的误差，可以把函数关系用一个简单的便于计算和处理的近似表达式近似表达式来代替，从而使问题得到简化。一般地，构造某种简单函数代替原来函数。插值法就是一种基本方法0 引言引言第二章第二章 插值插值（Interpolation）法法(1)(2)(2) 在在 x 为特殊值为特殊值时时, 是好计算的是好计算的, 则则 (2)可转化为可转化为(1)当精确函数当精确函数 y = f(

2、x) 非常复杂或未知时，在一非常复杂或未知时，在一系列节点系列节点 x0 xn 处测得函数值处测得函数值 y0 = f(x0), yn = f(xn)，由此构造一个简单易算的近似函，由此构造一个简单易算的近似函数数 g(x) f(x)，满足条件，满足条件g(xi) = f(xi) (i = 0, n)。这里的。这里的 g(x) 称为称为f(x) 的的插值函数插值函数。x0 x1x2x3x4xg(x) f(x) 根据实际需要，可以用各种不同的函数来近似原来的函数。最常用的插值函数是最常用的插值函数是 ?多项式：多项式： 代数多项式最简单，计算其值只需用到加、减乘运算，且积分和微分都很方便； 所以

3、常用它来近似表示表格函数(或复杂函数),这样的插值方法叫做代数插值法代数插值法，简称插值法。1 拉格朗日多项式拉格朗日多项式 niyxPiin,., 0,)(= = =求求 n 次多项式次多项式 使得使得nnnxaxaaxP = =10)(条件：条件：无重合节点，即无重合节点，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( = =使得使得111001)(,)(yxPyxP= = =可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)(1xP101xxxx- - -010 xxxx-

4、 - -= y0 + y11.1 线性插值线性插值两点式两点式)()(0010101xxxxyyyxP- - - - = =点斜式点斜式)(001010 xxxxxxy- - - - = =()ff1.2 二次插值二次插值n = 2已知已知 x0 , x1 , x2; y0 , y1 ,y2 , 求求22102)(xaxaaxP = =使得使得002,)(yxP112)(yxP= = =222)(yxP= =, 为求为求P2(x),将三点代入其表达式将三点代入其表达式,即可得到三个方程式即可得到三个方程式,从而联立方程组解出系数从而联立方程组解出系数a0, a1, a2即可即可:2020100

5、 xaxaay = =2121101xaxaay = =2222102xaxaay = =方程组的方程组的解是否存在解是否存在? 若存在解若存在解,是否是否唯一唯一?!当当 x0 , x1 , x2互异时互异时,方程组的解存在且唯一方程组的解存在且唯一.注：注：显然有显然有, 求求n 次插值时次插值时, 由由n +1个点可有个点可有n +1个方程个方程, 联立方程组即可求出插值多项式的联立方程组即可求出插值多项式的n +1个系数个系数. 然而然而,方程组的求解也并不是一件容易的事方程组的求解也并不是一件容易的事。1.2.1 待定系数法待定系数法 对于线性插值的对于线性插值的两种形式两种形式解解

6、进行适当的分析进行适当的分析, , 从中寻求规律而得到启发从中寻求规律而得到启发, ,就有了所谓的就有了所谓的拉格朗日拉格朗日插值法插值法( (公式公式) )和和牛顿插值牛顿插值( (公式公式). ). 我们先来看看如何得到二次二次拉格朗日插值公式拉格朗日插值公式（和和牛顿插值公式牛顿插值公式（为讨论方便，留待后述为讨论方便，留待后述）. . 首先, 线性插值的两点式可看作是两个特殊的一次式可看作是两个特殊的一次式的一种线性组合的一种线性组合.101xxxx- - -010 xxxx- - -)(1xP= y0 + y1 = = =10)(iiiyxl两点式两点式l0(x)l1(x)实质上实质

7、上0l（x）和）和1l（x）即是满足函数表）即是满足函数表 的一次插值多项式的一次插值多项式 ,称称l0(x)和和l1(x)为以为以x0,x1为节点的基本插为节点的基本插值多项式，也称为值多项式，也称为线性插值的线性插值的插值基函数插值基函数 。 于是，线性插值即是用于是，线性插值即是用基函数的线性组合基函数的线性组合来构造的来构造的. 1.2.2 基函数法基函数法称为称为拉氏基函数拉氏基函数 ，满足，满足 li(xj)= ij 显然有显然有l0(x)+ l0(x)1.这里，这里， l0(x)和和l1(x)具有如下性质：具有如下性质：l0(x0)=1, l0(x1)=0, l1(x0)=0,

8、l1(x1)=1, 由此启发，我们希望二次插值也能由一些二次插值基由此启发，我们希望二次插值也能由一些二次插值基函数来线性组合函数来线性组合:这时，这时，l0(x), l1(x), l2(x)都是二次多项式，且应满足都是二次多项式，且应满足满足满足(2.1)式的式的 l i(x) 是否存在是否存在?若存在，具有什么形式呢若存在，具有什么形式呢?（2.1）同理可得同理可得 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)

9、, l2(x)是满足是满足(2.1)的特殊的特殊(基本基本)二次插值多项式二次插值多项式;称为称为二次插值基函数二次插值基函数.P2(x)= y0+ y1+ y2(x - -x0)(x - -x2)(x1- -x0)(x1- -x2)(x - -x1)(x - -x2)(x0- -x1)(x0- -x2)(x - -x0)(x - -x1)(x2- -x0)(x2- -x1) 先考虑先考虑 l0(x)。因。因 l0(x)是以是以 x1, x2 为零点的二次多项式为零点的二次多项式,所以它可写成所以它可写成 l0(x) 0(x x1)(x x2), 其中其中 0 是待定系是待定系数。数。 又因为

10、又因为 l0( x0)=1，所以，所以 0(x0 x1)(x0 x2)1，则可有，则可有0(x0 x1)(x0 x2)1 l0(x) 0(x x1)(x x2), n 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 = = =niiinyxlxP0)()(，则显然有，则显然有Pn(xi) = yi 。li(x)每个每个 li 有有 n 个根个根 x0 xi xn = =- -= =- - - -= =njj i jiniiixxCxxxxxxCxl00)().().()( - -= = =j i jiiiixxCxl)(11)(= = -

11、- -= =njijjijixxxxxl0)()()( = = =niiinyxlxL0)()( 拉格朗日拉格朗日 多项式多项式与与 有关，而与有关，而与 无关无关节点节点f1.3 n 次插值次插值定理定理 (唯一性唯一性) 满足满足 的的 n 阶插值多阶插值多项式是唯一存在的。【项式是唯一存在的。【P14】niyxPii,., 0,)(= = =证明：证明： ( 存在性存在性可利用可利用Vandermonde 行列式行列式论证论证)反证：若不唯一，则除了反证：若不唯一，则除了Ln(x) 外还有另一外还有另一 n 阶多项阶多项式式 Pn(x) 满足满足 Pn(xi) = yi 。考察考察 则则

12、 Qn 的阶数的阶数, )()()(xLxPxQnnn- -= = n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注：注：若不将多项式次数限制为若不将多项式次数限制为 n ，则插值多项式，则插值多项式不唯一不唯一。例如例如 也是一个插值也是一个插值多项式，其中多项式，其中 可以是任意多项式。可以是任意多项式。= =- - = =niinxxxpxLxP0)()()()()(xp = = =niiinyxlxL0)()(设节点设节点)1( nf在在a , b内存在内存在, 考察截断误差考察截断误差)()()(xLxfxRnn- -= =, baCfn bxxxan 10，且，且 f

13、 满足条件满足条件 ,Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。)(x 0)()(10= = =xx ),(10 xx 0)(= = 推广：推广：若若0)()()(210= = = =xxx ),(),(211100 xxxx 使得使得0)()(10= = = = ),(10 使得使得0)(= = 0)()(0= = = =nxx 存在存在),(ba 使得使得0)()(= = nRn(x) 至少有至少有 个根个根n+1 = =- -= =niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 = =-

14、- -= =niixtxKtRnt0)()()()( (t)有有 n+2 个不同的根个不同的根 x0 xn x),(, 0)()1(baxxn = = !)1()()()1(-nxKRxnn 注意这里是对注意这里是对 t 求导求导= = - - - !)1)()()()1()1(nxKLfxnnxn !)1()()()1( = = nfxKxn = = - - = =niixnnxxnfxR0)1()(! ) 1()()( 1.4 插值余项插值余项 (Remainder) 注：注： 通常不能确定通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限

15、。1)1()( nnMxf= = - - niinxxnM01|)!1(当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项多项式是式是精确精确的。的。0)()1( xfn0)( xRn.)(应应用用的的高高阶阶导导数数存存在在时时才才能能余余项项表表达达式式只只有有在在xf,)()( )(61)(2,)( )(21)()(21)(1202102101021xxxxxxxxfxRnxxxxxxfxfxRn - - - - = = = - - - = = = = = ，时时，抛抛物物插插值值的的余余项项为

16、为当当，时时，线线性性插插值值余余项项为为当当例例1 求经过求经过A(0,1)，B(1,2)，C(2,3)三个插值点的插值多项式三个插值点的插值多项式.解：解：三个插值节点及对应的函数值为三个插值节点及对应的函数值为.322110221100= = = = = = =yxyxyx，；，；，13)12)(02()1)(0(2)21)(01()2)(0(1)20)(10()2)(1()()()()()()()(2120210121012002010212 = = - - - - - - - - - - - - - - -= =- - - - - - - - - - - - - - -= =xxxx

17、xxxyxxxxxxxxyxxxxxxxxyxxxxxxxxxL由抛物插值公式得由抛物插值公式得例例2：已知已知233sin,214sin,216sin= = = = 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 =n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 =xx利用利用216/4/6/214/6/4/)(1 - - - - - -= = xxxL这里这里)3,6(,sin)(,sin)()2( - -= = =xxxfxxf而而)4)

18、(6(!2)()(,23sin21)2(1 - - -= = xxfxRxx00762. 0)185(01319. 01- - - - Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 (extrapolation ) 的实际误差的实际误差 - -0.010010.010013,421 = = =xx利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插 (interpolation ) 的实际误差的实际误差 0.00596 0.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的

19、所在的区间的端点，插值效果较好。端点，插值效果较好。n = 223)()(21)()(21)()()(4363463464363646342 - - - - - - - - - - - - - - -= = xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 - - - - -= =xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.00061 0.00061高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好，嘿高就

20、越好，嘿嘿嘿 例例3 考虑下述的插值法问题：求二次多项式考虑下述的插值法问题：求二次多项式P(x)，满足，满足P(x0) = y0, 其中其中 是已给的数据并给出使这一问题的解存在且唯一的条件是已给的数据并给出使这一问题的解存在且唯一的条件.，2211)()(yxPyxP=21020yyyxx、，解解：设：设 则则 由已知条件有由已知条件有，cbxaxxP=2)(.2)(baxxP=11222200202ybaxycbxaxycbxax0012111222020 xxxxx0)()(22220201-xxxxx)0(220201-xxxxx即即 所以所以故原问题的唯一可解性就归结为上述方程组的

21、唯一可解性而后故原问题的唯一可解性就归结为上述方程组的唯一可解性而后者唯一可解的充要条件为者唯一可解的充要条件为这就是这就是P（x）存在且唯一的条件。）存在且唯一的条件。 回顾回顾 拉格朗日插值公式拉格朗日插值公式 .)10(.出有牛顿插值公式出有牛顿插值公式形式，从而导形式，从而导项式变形为便于计算的项式变形为便于计算的这一缺点，可把插值多这一缺点，可把插值多为了克服为了克服的的实际计算中是很不方便实际计算中是很不方便式也要发生变化，这在式也要发生变化，这在均要随之变化，整个公均要随之变化，整个公，时，全部插值基函数时，全部插值基函数但是，当插值节点增加但是，当插值节点增加中非常方便中非常方

22、便结构紧凑，在理论分析结构紧凑，在理论分析式，公式式，公式得到拉格朗日插值多项得到拉格朗日插值多项利用插值基函数很容易利用插值基函数很容易nklk= =1.5 拉格朗日插值公式的优缺点拉格朗日插值公式的优缺点n 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 = = =niiinyxlxP0)()(，则显然有，则显然有Pn(xi) = yi 。li(x)每个每个 li 有有 n 个根个根 x0 xi xn = =- -= =- - - -= =njj i jiniiixxCxxxxxxCxl00)().().()( - -= = =j i

23、jiiiixxCxl)(11)(= = - - -= =njijjijixxxxxl0)()()( = = =niiinyxlxL0)()( 拉格朗日拉格朗日 多项式多项式与与 有关，而与有关，而与 无关无关节点节点f拉格朗日插值公式拉格朗日插值公式 Lab 1. Lagrange Polynomial Given a set of sample points of a certain function f , use Lagrange polynomial to approximate function values at some given points . InputThere are

24、 several sets of inputs. For each set:The 1st line contains an integer 20 n 0 which is the degree of Lagrange polynomial. n = - -1 signals the end of file.The 2nd line contains n+1 distinct real numbers .The 3rd line contains n+1 real numbers .The last line of a test case consists of an integer m 0

25、and m real numbers .The numbers are separated by spaces and new lines. )(,(.,),(,(),(,(1100nnxfxxfxxfxmaa,.,1nxxx,.,10)(,.),(),(10nxfxfxfmaa,.,1Output ( ( represents a space) represents a space)For each ai , you are supposed to print the function value at this point in the following format: fprintf(

26、outfile, f(%6.3f)=%12.8en, a, f );The outputs of two test cases must be seperated by a blank line. Sample Input Sample Input 70.50.70.91.11.31.51.71.90.480.640.780.890.961.000.990.9550.741.60.551.21.8510.01.00.01.010.51Sample OutputSample Outputf(0.740) =6.68735821e001f(1.600) =1.00341309e+000f(0.55

27、0) =5.26938820e001f(1.200) =9.29135742e001f(1.850) =9.52078056e001 f(0.500) =5.00000000e001 Lagrange插值插值公式公式(利用利用插值基函数插值基函数很容易得到很容易得到): 含义直观含义直观,结构紧凑结构紧凑,在理论分析中非常方便在理论分析中非常方便; 计算机上计算机上实现实现也很也很容易容易. 也有一些也有一些缺点缺点： 一是一是计算量大计算量大，这是显然的；另外，还有一个更严重的，这是显然的；另外，还有一个更严重的缺点，当插值节点增加时，缺点，当插值节点增加时，全部插值基函数全部插值基函数均要

28、随之均要随之变化变化，整个计算工作必须从头开始：不仅原来的每一项都要改变，整个计算工作必须从头开始：不仅原来的每一项都要改变，还要还要增加一项增加一项计算。计算。 为克服上述两个缺点为克服上述两个缺点, 努力：把插值多项式变形为努力：把插值多项式变形为便于计算便于计算的形式。的形式。 希望：希望：计算改变的过程中计算改变的过程中,尽可能能利用已有的计算结果尽可能能利用已有的计算结果. 下面我们将看到下面我们将看到,这是可能的。我们可以有具有这是可能的。我们可以有具有“承袭性承袭性”的所谓牛顿公式。的所谓牛顿公式。差 商)()(0010101xxxxyyyxP- - - - = =)(00101

29、0 xxxxxxy- - - - = =()fffx0,x1 二次牛顿插值多项式二次牛顿插值多项式 我们再看线性插值线性插值的点斜式点斜式: )(00 xxy- - = =fx0,x1常数常数(差商差商) 由此启发，我们希望二次插值也能类似地有有规律的由此启发，我们希望二次插值也能类似地有有规律的组合表达式组合表达式:P2(x)= 0 + 1(x- -x0) + 2(x- -x0)(x- -x1)利用利用P2(x0)=y0有有: 0 = y0 ,利用利用P2(x1)=y1有有: 1 = 0101xxxx- - -()ff= fx0,x1 ,利用利用P2(x2)=y2有有: 2 = fx0,x1

30、 (x2- -x0)(x2- -x1) (x2- -x0)(x2- -x1)0 xx2- -()ff (x2- -x0)-fx0,x2fx0,x1 x2 - - x1 =-= fx0,x1,x2 ;P2(x)=f(x0) + (x- -x0) + (x- -x0)(x- -x1) fx0,x1 fx0,x1,x2 fx0,x2 x=x0时0注注: 1. 事实上事实上,从上述可看出二次牛顿插值公式是用从上述可看出二次牛顿插值公式是用待待定系数法定系数法求得的求得的; 2. 它也可看作是三个特殊函数的一种线性组合它也可看作是三个特殊函数的一种线性组合:P2(x)=f(x0) + (x- -x0)

31、+ (x- -x0)(x- -x1) fx0,x1 fx0,x1,x2 fx0,x1 , fx0,x1,x2 f(x0), 1 , (x- -x0) , (x- -x0)(x- -x1)即函数 的线性组合,组合系数为 本质上还是本质上还是基函数法基函数法. 更一般地，更一般地，n+1个节点的插值多项式，我们希望由上个节点的插值多项式，我们希望由上述类似的一组特殊函数：述类似的一组特殊函数：来线性组合为：来线性组合为： 1 , (x- -x0) , (x- -x0)(x- -x1)，(x- -x0)(x- -x1)(x- -xn).(.)()()(10102010- - - - - - - -

32、- = =nnnxxxxaxxxxaxxaaxN那么其组合系数是什么样的呢？怎么求呢？那么其组合系数是什么样的呢？怎么求呢？我们同样可用待定系数法我们同样可用待定系数法. 容易发现容易发现,计算计算a0, a1, a2 , an 是很有规律的是很有规律的.一、均差及其性质一、均差及其性质2 牛顿插值牛顿插值当当x=x0时，时，Pn(x0)=a0=f0.当当x=x1时，时，Pn(x1)=a0+a1(x1- -x0)=f1, 推得推得a1=f1- -f0 x1- -x0当当x=x2时，时，Pn(x2)=a0+a1(x2- -x0)+a2(x2- -x0)(x2- -x1)= f2,推得推得f1-

33、-f0 x1- -x0- -f1- -f0 x1- -x0a2=x2- -x1 依次递推可得到依次递推可得到a3, , an. 为写出系数为写出系数 ak的一般表达式的一般表达式,先引进如下均差定义先引进如下均差定义. 定义定义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- - fx

34、0,x1, ,xk-1xk- -xk-1均差有如下的基本性质均差有如下的基本性质: 1 k 阶均差可表示为函数值阶均差可表示为函数值f(x0), f(x1), f(xk)的线性组合的线性组合,即即 fx0,x1,xk=f(xj)(xj- -xj+1)(xj- -xk)(xj- -xj+1)(xj- -x0) kj=0这个性质可用归纳法证明这个性质可用归纳法证明. 这个性质也表明均差与节点的排列这个性质也表明均差与节点的排列次序无关次序无关,称为均差的对称性称为均差的对称性,即即 fx0,x1,xk= fx1,x0,x2,xk= = fx1, , xk ,x0 fx0,x1,xk=fx1, xk

35、-1,xk- - fx0,x1, ,xk-1xk- -x02 由性质由性质1可得可得: fx0, x1,xk =f(n)()n!,ba 3 若若f(x)在在a,b上存在上存在n阶导数阶导数, 且节点且节点x0,x1,xn a,b,则则n阶均差与导数关系如下阶均差与导数关系如下: 这个公式可直接用罗尔定理证明这个公式可直接用罗尔定理证明.，0!)()(0)()(= =- -= =nnnxxfnfq .!)()(0nfxxfnn = =， 所以所以，使使记记为为个个零零点点内内至至少少有有在在理理，可可知知零零点点；反反复复应应用用罗罗尔尔定定个个内内至至少少有有在在个个零零点点，故故的的两两个个

36、零零点点间间至至少少有有一一在在，个个零零点点，根根据据罗罗尔尔定定理理上上有有在在处处均均为为零零，所所以以，在在，证证明明：设设, , 1 ,)(,)()()(1,)()( ),()()( )(0100babaxqnbaxqxqxqnbaxqxxxqxxxxxxxxxfxqnnnn - - - -= = ,)()()(000 xxfxxxfxf- - = =,)(,101100 xxxfxxxxfxxf- - = =,.,)(,.,.,0010nnnnxxxfxxxxfxxxf- - = =- -).(.)()()(10102010- - - - - - - - - = =nnnxxxxa

37、xxxxaxxaaxN12 n- -11+ (x - - x0) 2+ + (x - - x0)(x - - xn- -1) n- -1.)(,)(,)()(102100100 - - - - - = =xxxxxxxfxxxxfxfxf).(,.,100- - - - nnxxxxxxf)().(,.,100nnnxxxxxxxxxf- - - - - -Nn(x)Rn(x)ai = f x0, , xi 二、牛顿插值公式二、牛顿插值公式)().(,.,100nnnxxxxxxxxxf- - - -= =- -Rn(x).)(,)(,)(102100100 - - - - - = =xxxx

38、xxxfxxxxfxf).(,.,100- - - - nnxxxxxxfNn(x)n+1(x)10(0nkxxfakk，= = = 多项式多项式Nn(x)显然满足插值条件显然满足插值条件,即即Nn(xj)=f(xj),(j=1, n),且次数不超过且次数不超过n,由唯一性定理它就是前述的由唯一性定理它就是前述的Ln(x),其系数为其系数为 Nn(x)称为牛顿均差插值多项式称为牛顿均差插值多项式,它比拉格朗日插值多项式它比拉格朗日插值多项式计算量省计算量省,且便于程序设计且便于程序设计.注：注： 由由唯一性可知唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其只是算法不同，故其余项也相同

39、，即余项也相同，即)(!)1()()(,.,1)1(10 xnfxxxxfkxnkn = = ),(,!)(,.,maxmin)(0 xxkfxxfkk = = 实际计算过程为实际计算过程为f (x0)f (x1)f (x2)f (xn- -1)f (xn)f x0, x1f x1, x2 f xn- -1, 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均差计算可列均差表如下：均差计算可列均差表如下：, 2, 1 ,

40、1, 0 ,11 = = =- - -= =- - iikixxxxfxxfxxfikkikiki 例例1 依据如下函数值表建立不超过依据如下函数值表建立不超过3次的拉格朗日插值多次的拉格朗日插值多项式及牛顿插值多项式项式及牛顿插值多项式Nn(x),并验证插值多项式的唯一性并验证插值多项式的唯一性. 解解: (1)拉格朗日插值多项式拉格朗日插值多项式Ln(x).插值基函数插值基函数xk0124f (xk)19233拉格朗日插值多项式为拉格朗日插值多项式为:121445411 )(3)(23)(9)()()(233210303-=xxxxlxlxlxlyxlxLiii,12181241)24)(

41、14)(04()2)(1)(0()(,4541)42)(12)(02()4)(1)(0()(,38231)41)(21)(01()4)(2)(0()(, 1478781)40)(20)(10()4)(2)(1()(233232231230 xxxxxxxlxxxxxxxlxxxxxxxlxxxxxxxl-=-=-=-=-=-=-=-=xkf (xk) 一阶均差一阶均差二阶均差二阶均差三阶均差三阶均差0119822314343- -10- -8(2) 牛顿插值多项式牛顿插值多项式Nn(x).建立如下差商表建立如下差商表牛顿插值多项式为牛顿插值多项式为:121445411 )2)(1)(0(411

42、) 1)(0(3)0(81)(233-=-=xxxxxxxxxxN411-(3) 唯一性验证唯一性验证.通过比较牛顿插值多项式和拉格朗日插值多项式通过比较牛顿插值多项式和拉格朗日插值多项式,知知: Nn(x) = Ln(x)这一事实与插值多项式的唯一性一致这一事实与插值多项式的唯一性一致. 2 等距节点插值公式等距节点插值公式 向前差分向前差分 iiifff- -= = 1ikikikikffff1111)(- - - - - - - = = = = 向后差分向后差分 111- - - - - - = = ikikikfffi- -1iifff- -= = 中心差分中心差分 212111- -

43、 - - - -= =ikikikfff 其中其中)(221hiixff = = 当节点当节点等距等距分布时分布时:),.,0(0nihixxi= = = = 差分的重要性质：差分的重要性质： 线性：例如线性：例如gbfaxgbxfa = = )()( 若若 f (x)是是 m 次多项式，则次多项式，则 是是 次多项次多项式，而式，而 )0()(mkxfk km -)(0)(mkxfk = = 差分值可由函数值算出：差分值可由函数值算出： = =- - - -= = njjknjknfjnf0)1( = =- - - - -= = njnjkjnknfjnf0) 1(!)1).(1(jjnnn

44、jn - - -= = 其中其中 函数值可由差分值算出：函数值可由差分值算出：kjnjknfjnf =0kkkhkfxxf!,.,00 = =knkknnnhkfxxxf!,.,1 = =- - -kkkhff0)()( = = 由由 Rn 表达式表达式牛顿公式牛顿公式).(,.,.)(,)()(1000100- - - - - - = =nnnxxxxxxfxxxxfxfxN 牛顿前差公式牛顿前差公式 牛顿后差公式牛顿后差公式 将节点顺序倒置：将节点顺序倒置：).(,.,.)(,)()(101xxxxxxfxxxxfxfxNnnnnnnn- - - - - = =- -设设htxx = =0

45、，则，则)()()(000 xfkthtxNxNknknn = = = = = =),(,).(1()!1()()(01)1(nnnnxxhntttnfxR - - - = = 设设htxxn = =，则，则)() 1()()(0nknkknnnxfkthtxNxN - - -= = = = = =注：注：一般当一般当 x 靠近靠近 x0 时用前插，靠近时用前插，靠近 xn 时用后插，故两时用后插，故两种公式亦称为种公式亦称为表初公式表初公式和和表末公式表末公式。3 厄尔米特插值厄尔米特插值 不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数也重合。也重合。即：要求插

46、值函数即：要求插值函数 (x) 满足满足 (xi) = f (xi), (xi) = f (xi), (mi) (xi) = f (mi) (xi).注：注： N 个条件可以确定个条件可以确定 阶多项式。阶多项式。N - - 1要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插值多项式即为值多项式即为Taylor多项式多项式00)(!)(.)()()(000)(000mmxxmxfxxxfxfx- - - - = = 其余项为其余项为)1(00)1(00)()!1()()()()(-=-=mmxxmfxxfxR 一般只考虑一般只考虑 f 与与f 的值。的值。例

47、：例：设设 x0 x1 x2, 已知已知 f(x0)、 f(x1)、 f(x2) 和和 f (x1), 求多项式求多项式 P(x) 满足满足 P(xi) = f (xi)，i = 0, 1, 2，且且 P(x1) = f (x1), 并估计误差。并估计误差。模仿模仿 Lagrange 多项式的思想，设多项式的思想，设解：解：首先，首先，P 的阶数的阶数 = 3=213)()()()()(=0iiixhx1f xhxfxP h0(x)有根有根x1, x2，且且 h0(x1) = 0 x1 是重根。是重根。)()()(22100 xxxxCxh- - -= =又又: h0(x0) = 1 C0 )

48、()()()()(202102210 xxxxxxxxxh- - - - -= =h2(x)h1(x)有根有根 x0, x2 )()()(201xxxxBAxxh- - - = =由余下条件由余下条件 h1(x1) = 1 和和 h1(x1) = 0 可解。可解。与与h0(x) 完全类似。完全类似。 (x) h1有根有根 x0, x1, x2 h1)()()(2101xxxxxxCx- - - -= = h1又又: (x1) = 1 C1 可解。可解。其中其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x1) = 1 h1 h1),()()()()()(2210

49、33xxxxxxxKxPxfxR- - - -= =- -= =!4)()()4(xfxK = =与与 Lagrange 分析分析完全类似完全类似一般地，已知一般地，已知 x0 , , xn 处有处有 y0 , , yn 和和 y0 , , yn ，求，求 H2n+1(x) 满足满足 H2n+1(xi) = yi ， H2n+1(xi) = yi。解：解：设设=ni)()()(=0iixhxhyixH2n+1 n=0iyi其中其中 hi(xj) = ij , hi(xj) = 0, (xj) = 0, (xj) = ij hi hihi(x)有根有根 x0 , , xi , , xn且都是且都

50、是2重根重根 )()()(2xlBxAxhiiii = = - - -= =ijjijixxxxxl)()()(由余下条件由余下条件 hi(xi) = 1 和和 hi(xi) = 0 可解可解Ai 和和 Bi )()(21 )(2xlxxxlxhiiiii- - - -= = (x) hi有根有根 x0 , , xn, 除了除了xi 外都是外都是2重根重根 hi)()(iili2(x)xxCx- -= = hi又又: (xi) = 1 Ci = 1 hi)(x)(ili2(x)xx- -= =设设,.210baCfbxxxann = = = =则则20)22()()!22()()( - - =