拉格朗日插值法总结

1、拉格朗日插值法总结拉格朗日插值法2008-05-12 16 : 44一、问题的背景在实际问题中常遇到这样的函数 y=f(x),其在某个区间a,b上是存在的。 但是,通过观察或测量或试验只能得到在区间a,b上有限个离散点x0,x1,xn上的函数值yi=f(xi),(i=0,1,n)。或者f(x)的函数f(x)表达式是已知的，但却很复杂而不便于计算；希望用一个既能反映函数 f(x)的特性, 又便于计算的简单函数来描述它。二、插值问题的数学提法：已知函数在n+1个点x0,x1,xn上的函数值yi=f(xi),(i=0,1,n)求一个简单函数y=P(x),使其满足：P(xi)=yi,(i=0,1,n)

2、。即要求该简单函数的曲线要经过 y=f(x)上已知的这个n+1个点：(x0,y0),(x1,y1),(xn,yn),同时在其它x a,b上要估计误差：R(x)=f(x)-P(x)其中P(x)为f(x)的插值函数，x0,x1,xn称为插值节点，包含插值节点 的区间a,b称为插值区间，求插值函数P(x)的方法称为插值法。若P(x)是次数不超过n的代数多项式，就称P(x)为插值多项式，相应的插值法称为多项式插值。若P(x)是分段的多项式，就是分段插值。若P(x)是三角多项式，就称三角插值。三、插值方法面临的几个问题第一个问题：根据实际问题选择恰当的函数类。本章我们选择代数多项式类，其原因有两个：(1

3、)代数多项式类简单；微分、积分运算易于实行；(2)根 据著名的Weierstrass逼近定理，任何连续的函数都可以用代数多项式作任意 精确的逼近。第二个问题：构造插值函数 P(x),使其满足：P(xi)=yi,(i=0,1,n)与此相关的问题是：插值问题是否可解(存在性的问题)，如果有解，是否唯一 ?(唯一 性的问题)第三个问题：插值误差R(x)=f(x)-P(x) 的估计问题。与此相关的问题是插 值过程的收敛性的问题。第一节拉格朗日插值公式一. 线性插值(一次插值)已知函数f(x)在区间xk,xk+1的端点上的函数值yk=f(xk),yk+仁f(xk+1), 求一个一次函数y=P1(x)使得

4、yk=f(xk),yk+仁f(xk+1), 其几何意义是已知平面 上两点(xk,yk),(xk+1,yk+1), 求一条直线过该已知两点。1.插值函数和插值基函数由直线的点斜式公式可知：把此式按照yk和yk+1写成两项：记并称它们为一次插值基函数。该基函数的特点如下表：从而P1(x)=yk lk(x)+yk+1 lk+1(x)此形式称之为拉格朗日型插值多项式。其中,插值基函数与yk、yk+1无关, 而由插值结点xk、xk+1所决定。一次插值多项式是插值基函数的线性组合,相应的组合系数是该点的函数值 yk、yk+1.例1:已知lg10=1,lg20=1.3010,利用插值一次多项式求Ig12的近

5、似值。解：f(x)=lgx,f(10)=1,f(20)=1.3010, 设x0=10,x1=20,y0=1,y1=1.3010则插值基函数为：于是,拉格朗日型一次插值多项式为：故：即Ig12由lg10和Ig20两个值的线性插值得到，且具有两位有效数字(精确 值 Ig12=1.0792).二. 二次插值多项式已知函数y=f(x)在点xk-1,xk,xk+1 上的函数值yk-仁f(xk- 1),yk=f(xk),yk+1=f(xk+1),求一个次数不超过二次的多项式 P2(x),使其满足，P2(xk-1)=yk-1,P2(xk)=yk,P2(xk+1)=yk+1.其几何意义为：已知平面上的三个点(

6、xk-1,yk-1),(xk,yk),(xk+1,yk+1),求一个二次抛物线，使得该抛物线经过这三点。1.插值基本多项式有三个插值结点xk-1,xk,xk+1构造三个插值基本多项式，要求满足:(1)基本多项式为二次多项式；(2)它们的函数值满足下表：因为 lk-1(xk)=0,lk-1(xk+1)=0,故有因子(x-xk)(x-xk+1),而其已经是一个二次多项式，仅相差一个常数倍，可设lk-1(x)=a(x-xk)(x-xk+1),又因为lk-1(xk-1)=1=a(xk-1-xk)(xk-1-xk+1)=1得从而同理得基本二次多项式见右上图(点击按钮显示Li)。2.拉格朗日型二次插值多项

7、式由前述,拉格朗日型二次插值多项式：P2(x)=yk-1 lk-1(x)+yk lk(x)+yk+1 lk+1(x),P2(x)是三个二次插值多项式的线性组合,因而其是次数不超过二次的多项式，且 满足：P2(xi)=yi,(i=k-1,k,k+1)。例2已知：xi 10 15 20 yi=lgxi 11.1761 1.3010利用此三值的二次插值多项式求lg12的近似值。解：设 x0=10,x1=15,x2=20,则:故:所以7利用三个点进行抛物插值得到Ig12的值,与精确值lg12=1.0792相比,具 有3位有效数字，精度提高了。三、拉格朗日型n次插值多项式已知函数y=f(x)在n+1个不

8、同的点x0,x1,x2上的函数值分别为y0,y1,yn,求一个次数不超过n的多项式Pn(x),使其满足：Pn (xi)=yi,(i=0,1,n),即n+1个不同的点可以唯一决定一个n次多项式。1.插值基函数过n+1个不同的点分别决定n+1个n次插值基函数I0(x),I1(x),In(X)每个插值基本多项式li(x)满足：(1) li(x)是n次多项式；(2) li(xi)=1,而在其它 n 个 li(xk)=0,(k 工 i)。由于li(xk)=0,(k 工i),故有因子：(x-x0)(x-xi-1)(x-xi+1)(x-xn)因其已经是n次多项式，故而仅相差一个常数因子。令：li(x)=a(

9、x-x0)(x-xi-1)(x-xi+1)(x-x n)由li(xi)=1,可以定出a,进而得到:2.n次拉格朗日型插值多项式 Pn(x)Pn(x)是n+1个n次插值基本多项式IO(x),l1(x),ln(X)的线性组合,相应的组合系数是yO,y1,yn。即：Pn (x)=yO I0(x)+y1 I1(x)+yn In (x),从而Pn(x)是一个次数不超过n的多项式,且满足Pn( xi)=yi,(i=0,1,2,n).例3求过点(2,0),(4,3),(6,5),(8,4),(10,1)的拉格朗日型插值多项式。解用4次插值多项式对5个点插值。所以四、拉格朗日插值多项式的截断误差我们在a,b上

10、用多项式Pn(x)来近似代替函数f(x),其截断误差记作Rn (x)=f(x)-P n(x)当x在插值结点xi上时Rn(xi)=f(xi)-P n(xi)=0, 下面来估计截断误差：定理1:设函数y=f(x)的n阶导数y(n)=f(n)(x)在a,b上连续，y( n+1)=f( n+1)(x)在(a,b)上存在；插值结点为：a x0 x1 xnw b,Pn(x)是n次拉格朗日插值多项式；则对任意 x a,b有：其中 E (a,b), E 依赖于 x： 3 n+1(x)=(x-x0)(x-x1)(x-xn)证明：由插值多项式的要求:Rn(xi)=f(xi)-Pn(xi)=O, (i=0,1,2,

11、n)；设Rn(x)=K(x)(x-xO)(x-x1)(x-xn)=K(x)3 n+1(x)其中K(x)是待定系数；固定x a,b且x工xk, k=0,1,2,n ;作函数H(t)=f(t)-P n( t)-K(x)(t-xO)(t-x1)(t-x n)则 H(xk)=O, (k=0,1,2,n),且 H(x)=f(x)-Pn(x)-Rn(x)=O, 所以，H(t)在a,b上有n+2个零点，反复使用罗尔中值定理：存在E (a,b),使；因Pn(x)是n次多项式，故P(n+1)( E )=O,而3 n+1(t)=(t-xO)(t-x1)(t-xn)是首项系数为1的n+1次多项式，故有于是H(n+1

12、)( E )=f(n+1)( E)-(n+1) ! K(x)得：所以设,则：易知，线性插值的截断误差为：二次插值的截断误差为：下面来分析前面两个例子(例1,例2)中计算Ig12的截断误差：在例1中，用lg10和lg20计算Ig12,P1(12)=1.0602,lg12=1.0792 e=|1.0792-1.0602|=0.0190估计误差：f(x)=lgx,当 x 10,20时，在例2中，用Ig10,lg15 和lg20计算Ig12.P2(12)=1.0766,e=|1.0792-1.0766|=0.0026估计误差：对应的C+S序：#in elude iostream using n ame

13、space std double fun c(double X,i nt k,double x,i nt n) int mai n()double Sn=0 ；int n ；cout请输入点的个数n：;cin n ；double*x=(double*)malloc( n*sizeof(double) double*y=(double*)malloc( n*sizeof(double) double X ；int ifor(i=0 ； i n ； i+)cout请输入 xi+1,yi+1: endl ;cin xiyi ;cout请输入x;cin X ；for(i=0 ； i n ； i+)Sn=S n+fu nc(X,i,x,