Lagrange插值

第二章插值法(InterpolationMethod)已经测得在某处海洋不同深度处的水温如下：深度（M）46674195014221634水温（oC）7.044.283.402.542.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米…）处的水温。这就是本章要讨论的“插值问题”例当精确函数y=f(x)非常复杂或未知时，在区间[a,b]上一系列节点x0…xm处测得函数值y0=f(x0),…,ym=f(xm)，由此构造一个简单易算的近似函数g(x)f(x)，满足条件g(xj)=f(xj)(j=0,…,m)(*)这个问题称为“插值问题”。一、插值问题这里的g(x)称为f(x)的插值函数。节点x0…xm称为插值节点,条件(*)称为插值条件，区间[a,b]称为插值区间。定义1x0x1x2x3x4xf(x)g(x)最常用的插值函数是…?代数多项式用代数多项式作插值函数的插值称为代数插值本章主要讨论的内容插值函数的类型有很多种插值问题插值法插值函数一、插值问题解的存在唯一性？二、插值多项式的常用构造方法？三、插值函数的误差如何估计？代数插值二、代数插值问题解的存在惟一性nnnxaxaaxp10)(令只要证明pn(x)的系数a0,a1,…,an存在唯一即可,给定区间[a,b]上互异的n+1个点的一组函数值f(xj)，j=0,…,n,求一个n次多项式pn(x)∈Pn,使得njjx0}{.,,1,0,)()(njjjnxfxp为此由插值条件知pn(x)的系数满足下列n+1个代数方程构成的线性方程组:)()()(101111000010nnnnnnnnnxfxaxaaxfxaxaaxfxaxaa而ai(i=0,1,2,…,n)的系数行列式是Vandermonde行列式由于xi互异，所以上式右端不为零，从而方程组的解a0,a1,…an存在且唯一。nnnnnnnxxxxxxxxxxxxV21211020010111),,,(niijjixx110)(为此我们必须从其它途径来求pn(x)：不通过求解方程组而获得插值多项式。通过解上述方程组求得插值多项式pn(x)的方法并不可取。这是因为当n较大时解方程组的计算量较大，而且方程组系数矩阵的条件数一般较大（可能是病态方程组）,当阶数n越高时，病态越重。基本思想：在n次多项式空间Pn中找一组合适的基函数0(x),1(x),…,3(x),使不同的基函数的选取导致不同的插值方法Lagrange插值Newton插值)()()()(1100xaxaxaxpnnn三、插值多项式的构造方法知识点一n=1可见P1(x)是过(x0,y0)和(x1,y1)两点的直线。)()(0010101xxxxyyyxP101xxxx010xxxx=y0+y1l0(x)l1(x)10)(iiiyxl§2Lagrange插值求n次多项式使得nnnxaxaaxP10)((),0,1,,niiPxyin已知x0,x1;y0,y1，求101()Pxaax100111(),()PxyPxy使得一、构造基函数011101110()()()()()()()()()()()jjnjjjjjjjjnniijiijxxxxxxxxxxlxxxxxxxxxxxxxxx与节点有关，而与f无关这里每个lj(x)都是n次多项式，且容易验证lj(x)满足j=0,1,…，njijixlij,1,0)(知识点二插值基函数图形x0x11l0(x)x0x11l1(x)x0x21l0(x)x1n=1n=2x0x21l1(x)x1x0x21l2(x)x1对任意的Ln(x)∈Pn，Ln(x)=c0l0(x)+c1l1(x)+…+cnln(x)其中c0,c1,…,cn为组合系数0010000011111101()()()()()()()()()()()()nnnnnnnnlxlxlxcfxlxlxlxcfxlxlxlxcfx可以证明函数组l0(x)，l1(x)，…,ln(x)在插值区间［a,b］上线性无关，所以这n+1个函数可作为Pn的一组基函数，称为Lagrange插值基函数0011()100()010()001nncfxcfxcfx由Lagrange插值基函数满足，方程组变成因此得到插值多项式Ln(x)=f(x0)l0(x)+f(x1)l1(x)+…+f(xn)ln(x)记为Ln(x)＝f(xj)lj(x)称Ln(x)为n次Lagrange插值多项式jijixlij,1,0)(知识点三二、插值余项/*Remainder*/(1)0()()()()()(1)!nnnniifRxfxLxxxnRolle’sTheorem的推论:若充分光滑，且0)()(0nxx存在),(ba使得0)()(n)(x定理1若在[a,b]内存在,则在[a,b]上的n+1个互异的点，对f（x)所作的n次Lagrange插值多项式Ln(x)有误差估计)()1(xfn由于Rn(xi)＝0，i=0,1,…，n()())(0nRxxuxxnii任意固定xxi(i=0,…,n),考察(t)有n+2个不同的根x0…xnx(1)()()(1)!nfuxnniinxtxutRt0)()()()(niinxtxutLtf0)()()()(),(,0)()1(baxxn证明已知233sin,214sin,216sin分别利用sinx的1次、2次Lagrange插值计算sin50，并估计误差。n=1分别利用x0,x1以及x1,x2计算4,610xx利用216/4/6/214/6/4/)(1xxxL015sin50()0.7761418L(2)1()13()()(),sin2!6422xxfRxxx150.01319()0.0076218R例1解sin50=0.7660444…利用x0,x1作为插值节点的实际误差0.010013,421xx利用计算得：sin500.76008,150.005380.0066018R利用x1,x2作为插值节点的实际误差0.00596n=24363264634643643634()()()()11()()()2()()2()()3()()2xxxxLxxx23cos21;)3)(4)(6(!3cos)(2xxxxxxR250.000440.0007718Rsin50=0.7660444…2次插值的实际误差0.00061025sin50()0.7654318L0)(xRn特殊地:有kxxf)(1)(0njjxlknjjkjxxlx0)(关于Langrange插值的几点说明仅与已知数据有关，与的原来形式无关，但余式与密切相关。)(xLn),,1,0(),(niyxii)(xf)(xf(1))()(xfxLn即若本身是一个不超过n次的多项式，则)(xf(2)从角度观察，内插误差要小些，即x位于x0,x1,…,xn之间。而外插有可能误差变大，因此要慎用。)())(()(10nxxxxxxx(3)Langrange插值也有其不足为了提高精度有时需增加结点，但这时原来求的全改变,也就是原来的数据不能利用,浪费资源；)(xlj(4)§3逐次线性插值用拉格朗日插值多项式Ln(x)计算函数近似值，如精度不满足要求需增加插值节点时，原来算出的数据均不能利用，必须重新计算。为克服这缺点，通常可用逐次线性插值方法求得高次插值。对已给sin0.32=0.314567,sin0.34=0.333487,sin0.36=0.352274,用线性插值及抛物线插值计算sin0.3367的值并估计截断误差。①取sin0.32=0.314567,sin0.34=0.333487，用线性插值计算：)3367.0()3367.0(3367.0sin0010101xxxyyyL330365.00167.002.001892.0314567.0其截断误差为：51092.00033.00167.03335.021|2))((||)(|max|)3367.0(|10101xxxxxfRxxx例2解②取sin0.34=0.333487，sin0.36=0.352274,用线性插值计算：其截断误差为：)3367.0()3367.0(~3367.0sin1121211xxxyyyL330387.0)0033.0(02.0018787.0333487.0|2))((||)(|max|)3367.0(~|21201xxxxxfRxxx51036.10233.00033.03523.021③取sin0.32=0.314567,sin0.34=0.333487，sin0.36=0.352274,用抛物线插值计算：其截断误差为：)3367.0(3367.0sin2L0201021))(())((yxxxxxxxx1210120))(())((yxxxxxxxx2120210))(())((yxxxxxxxx=0.330374|6))()((||)(|max|)3367.0(|210202xxxxxxxfRxxx610178.0埃特金（Aitken）逐次线性插值方法)3367.0(2L)32.03367.0(32.036.0)3367.0()3367.0(~)3367.0(111LLL)3367.0(1L)3367.0(~1L)3367.0(2L是三节点抛物线插值计算的，它也可由和按类似线性插值的方法计算，即一般情况，两个k次插值多项式可通过线性插值得到(k+1)次插值多项式)(,,1,0xIk是关于节点x0,x1,…,xk的插值多项式)(,,,1,0xIlk)()()()(,,1,0,1,,1,0,,1,0kklklkkxxxxxIxIxI首先:为k+1次插值多项式。)(,,,1,0xIlk其次：对i=0,1,…,k−1，有)()()()(,1,,1,0,,1,0,,,1,0iilkikilkxfxIxIxI当x=xk时，有)()()(,,1,0,,,1,0kkkklkxfxIxI当x=xl时，有)()()()()(,,1,0,,1,0,,,1,0klkllkllkllkxxxxxIxfxIxI)(lxf公式也可改为)()()()()(001,,1,01,,1,,1,01,,1,0xxxxxIxIxIxIkkkkk列维尔（Neville）算法已知f(x)=shx的值，用埃特金插值求f(0.23)的近似值。表中右端是各次插值的计算结果，由于三次插值的两个结果相同，因而不需要再计算四次插值，故求得f(0.23)=0.232034。例3解