拉格朗日插值

1、第五章第五章 插值插值 /* Interpolation */ 问题提出问题提出函数逼近函数逼近 / /* *problem formulation-function approximationproblem formulation-function approximation* */ /用用已经测得在某处海洋不同深度处的水温如下：深度（M） 466 741 950 1422 1634水温（oC）7.04 4.28 3.40 2.54 2.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米）处的水温举例这就是本章要讨论的“插值问题”函数逼近的方法有很多，例如函数逼近的

2、方法有很多，例如Taylor级数，级数，Fourier级数，有限元方法、边界元方法，小级数，有限元方法、边界元方法，小波分析等，大学科叫波分析等，大学科叫逼近论逼近论。插值节点插值节点插值条件插值条件-插值问题插值问题多项式插值是数值分析的基本工具，常用来计算被插函数多项式插值是数值分析的基本工具，常用来计算被插函数的近似的近似函数值函数值，零、极点零、极点，导数、积分导数、积分，解微分方程解微分方程、积积分方程分方程插值插值x0 x1x2x3x4 xf(x)g(x)多项式插值多项式插值-polynomial interpolationProblem I. 给定给定y=f(x)的函数表的函数表

3、, xi a,bniyxPiin,., 0,)(= = =求求 次数不超过次数不超过 n 的多项式的多项式 使得使得nnnxaxaaxP = =10)(条件：条件：无重合节点无重合节点，即，即jixx ji Interpolation intervalInterpolation conditionInterpolation polynomialInterpolation points(2.1)(2.2)当精确函数当精确函数 y = f(x) 非常复杂或未知时，在一非常复杂或未知时，在一系列节点系列节点 x0 xn 处测得函数值处测得函数值 y0 = f(x0), yn = f(xn)，由此构造

4、一个简单易算的近似函，由此构造一个简单易算的近似函数数 g(x) f(x)，满足条件，满足条件g(xi) = f(xi) (i = 0, n)。这里的。这里的 g(x) 称为称为f(x) 的的插值函数插值函数。最常。最常用的插值函数是用的插值函数是 ? 多项式多项式x0 x1x2x3x4xg(x) f(x)最常用的插值函数是最常用的插值函数是 ?代数多项式用代数多项式作插值函数的插值称为代数插值本章主要讨论的内容插值函数的类型有很多种插值问题插值法插值函数 一、插值问题解的存在唯一性？ 二、插值多项式的常用构造方法？ 三、插值函数的误差如何估计？代数插值 代数插值问题解的存在惟一性代数插值问题

5、解的存在惟一性 给定区间给定区间a,ba,b上互异的上互异的n+1n+1个点个点x xj jn nj=0j=0的一的一 组函数值组函数值f(xf(xj j) )，j =0j =0，, n, n，求一个求一个n n次多项式次多项式p pn n(x)(x)P Pn n，使得使得 p pn n(x(xj j)=f(x)=f(xj j) )，j=0,1,j=0,1,，n. n. . (1) 令令 pn(x)=a0+a1x+anxn, . (2) 只要证明只要证明Pn(x)的系数的系数a0 ,a1, an存在唯一即可存在唯一即可为此由插值条件(1)知Pn(x)的系数满足下列n+1个代数方程构成的线性方程

6、组 a0+a1x0+anx0n=f(x0) a0+a1x1+anx1n= f(x1) .a0+a1xn+anxnn= f(xn) (3)200021110121.1.V(,.,).1.nnnnnnnxxxxxxx xxxxx=110()niijijxx=而ai(i=0,1,2,n)的系数行列式是Vandermonde行列式由于xi互异，所以上式右端不为零，从而方程组(3)的解 a0 ,a1 ,an 存在且唯一。 通过解上述方程组通过解上述方程组(3)求得插值多项式求得插值多项式pn(x)的方法并的方法并不可取不可取.这是因为当这是因为当n较大时解方程组的计算量较大，较大时解方程组的计算量较大，

7、而且方程组系数矩阵的条件数一般较大（可能而且方程组系数矩阵的条件数一般较大（可能是是病态方程组）病态方程组）,当阶数当阶数n越越高时，病态越重高时，病态越重。为此我们必须从其它途径来求Pn(x)：不通过求解方程组而获得插值多项式1 拉格朗日多项式拉格朗日多项式 /* Lagrange Polynomial */niyxPiin,., 0,)(= = =求求 n 次多项式次多项式 使得使得nnnxaxaaxP = =10)(条件：条件：无重合节点，即无重合节点，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( = =使得使得111001)(,

8、)(yxPyxP= = =可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)()(0010101xxxxyyyxP = =101xxxx 010 xxxx = y0 + y1l0(x)l1(x) = = =10)(iiiyxl称为称为拉氏基函数拉氏基函数 /* Lagrange Basis */，满足条件满足条件 li(xj)= ij /* Kronecker Delta */1 Lagrange Polynomialn 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 = = =n

9、iiinyxlxP0)()(，则显然有，则显然有Pn(xi) = yi 。li(x)每个每个 li 有有 n 个根个根 x0 xi xn = = = = = =njj i jiniiixxCxxxxxxCxl00)().().()( = = =j i jiiiixxCxl)(11)(= = = =njijjijixxxxxl0)()()( = = =niiinyxlxL0)()(Lagrange Polynomial与与 有关，而与有关，而与 无关无关节点节点f当n=1时,为线性插值当n=2时,为二次多项式插值(抛物线插值)1线性插值线性插值 (n=1) x0 x1(x0 ,y0)(x1 ,y

10、1)L1(x)f(x)可见可见 L1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。x0 x1x2L2(x) f(x)f(x)2抛物插值（抛物插值（n=2）因过三点的二次曲线为抛物线，故称为抛物插值。因过三点的二次曲线为抛物线，故称为抛物插值。 1 Lagrange Polynomial定理定理 (唯一性唯一性) 满足满足 的的 n 阶插值多阶插值多项式是唯一存在的。项式是唯一存在的。niyxPii,., 0,)(= = =证明：证明： (利用利用Vandermonde 行列式行列式论证论证)反证：若不唯一，则除了反证：若不唯一，则除了Ln(x)

11、外还有另一外还有另一 n 阶多项阶多项式式 Pn(x) 满足满足 Pn(xi) = yi 。考察考察 则则 Qn 的阶数的阶数, )()()(xLxPxQnnn = = n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注：注：若不将多项式次数限制为若不将多项式次数限制为 n ，则插值多项式，则插值多项式不唯一不唯一。例如例如 也是一个插值也是一个插值多项式，其中多项式，其中 可以是任意多项式。可以是任意多项式。= = = =niinxxxpxLxP0)()()()()(xp1 Lagrange Polynomial 插值余项插值余项 /* Remainder */设节点设节点)1(

12、 nf在在a , b内存在内存在, 考察截断误差考察截断误差)()()(xLxfxRnn = =, baCfn bxxxan 10，且，且 f 满足条件满足条件 ,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) 至少有至少有 个

13、根个根n+1 = = = =niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 = = = =niixtxKtRnt0)()()()( (x)有有 n+2 个不同的根个不同的根 x0 xn x),(, 0)()1(baxxn = = !)1()()()1(nxKRxnn 注意这里是对注意这里是对 t 求导求导= = !)1)()()()1()1(nxKLfxnnxn !)1()()()1( = = nfxKxn = = = =niixnnxxnfxR0)1()(! ) 1()()( 1 Lagrange Polynomial注：注： 通常不能确定

14、通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。1)1()( nnMxf= = niinxxnM01|)!1(当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项多项式是式是精确精确的。的。0)()1( xfn0)( xRnQuiz: 给定给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是下面哪个是 l2(x)的图像？的图像？ y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1

15、 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 1 Lagrange Polynomial例例1：已知已知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)

16、()2( = = =xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 = = xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的实际误差的实际误差 0.01010.01013,421 = = =xx利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插 /* interpolation */ 的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算

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

18、:已知 y = f(x) = ln(1+x) 的值如下xi123yi0.71.11.420 01 12 2( )( )( )( )L xy lxy l xy lx=(1) 求Lagrange插值多项式L2(x)(2) 求L2(2.5). (3)求插值余项R2(x) ，并估计R2(x)。 (1) .由公式得2(2)(3)(1)(3)(1)(2)0.71.11.4(1 2)(1 3)(2 1)(23)(3 1)(32)0.050.550.2xxxxxxxx= (2)因为 所以2( )( )(1)(2)(3),(1,3)3!fRxxxx=而32( ) ln(1)(1)fxxx=(3)因为：2(2.5)1.2625,L=2(2.5)(2.5)1.2625.fL=从而进而131max( )4xfx21( )(1)(2)(3)