Ch2_1Lagrange插值

第二章插值/*Interpolation*/问题提出—函数逼近/*problemformulation-----functionapproximation*/用已经测得在某处海洋不同深度处的水温如下：深度（M）46674195014221634水温（oC）7.044.283.402.542.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米…）处的水温举例这就是本章要讨论的“插值问题”函数逼近的方法有很多，例如Taylor级数，Fourier级数，有限元方法、边界元方法，小波分析等，大学科叫逼近论。插值节点插值条件---插值问题多项式插值是数值分析的基本工具，常用来计算被插函数的近似函数值，零、极点，导数、积分，解微分方程、积分方程插值x0x1x2x3x4xf(x)g(x)注意：1、插值函数是简单易算的2、所取节点是互异的，即：g(x)ix,ijxxij3、多项式插值是比较常用的插值方法，这是因为多项式函数本身的特殊性（易求导，易积分），但除此之外，也有其他的插值法：三角插值（三角函数）；分段插值（分段函数），等等最常用的插值函数是…?代数多项式用代数多项式作插值函数的插值称为代数插值本章主要讨论的内容插值函数的类型有很多种插值问题插值法插值函数•一、插值问题解的存在唯一性？•二、插值多项式的常用构造方法？•三、插值函数的误差如何估计？代数插值多项式插值----polynomialinterpolationProblemI.给定y=f(x)的函数表,xi[a,b]niyxPiin,...,0,)(==求次数不超过n的多项式使得nnnxaxaaxP=10)(条件：无重合节点，即jixxjiInterpolationintervalInterpolationconditionInterpolationpolynomialInterpolationpoints(2.1)(2.2)代数插值问题解的存在惟一性给定区间［a,b］上互异的n+1个点｛xj｝nj=0的一组函数值f(xj)，j=0，…,n，求一个n次多项式pn(x)∈Pn，使得pn(xj)=f(xj)，j=0,1,…，n.…...(1)令pn(x)=a0+a1x+…+anxn,…...(2)只要证明Pn(x)的系数a0,a1,…,an存在唯一即可为此由插值条件(1)知Pn(x)的系数满足下列n+1个代数方程构成的线性方程组a0+a1x0+…+anx0n=f(x0)a0+a1x1+…+anx1n=f(x1)…………………….a0+a1xn+…+anxnn=f(xn)……(3)200021110121...1...V(,,...,)...............1...nnnnnnnxxxxxxxxxxxx=110()niijijxx===而ai(i=0,1,2,…,n)的系数行列式是Vandermonde行列式由于xi互异，所以上式右端不为零，从而方程组(3)的解a0,a1,…an存在且唯一。通过解上述方程组(3)求得插值多项式pn(x)的方法并不可取.这是因为当n较大时解方程组的计算量较大，而且方程组系数矩阵的条件数一般较大（可能是病态方程组）,当阶数n越高时，病态越重。为此我们必须从其它途径来求Pn(x)：不通过求解方程组而获得插值多项式§1拉格朗日多项式/*LagrangePolynomial*/niyxPiin,...,0,)(==求n次多项式使得nnnxaxaaxP=10)(条件：无重合节点，即jixxjin=1已知x0,x1;y0,y1，求xaaxP101)(=使得111001)(,)(yxPyxP==可见P1(x)是过(x0,y0)和(x1,y1)两点的直线。)()(0010101xxxxyyyxP=101xxxx010xxxx=y0+y1l0(x)l1(x)==10)(iiiyxl称为拉氏基函数/*LagrangeBasis*/，满足条件li(xj)=ij/*KroneckerDelta*/§1LagrangePolynomialn1希望找到li(x)，i=0,…,n使得li(xj)=ij；然后令==niiinyxlxP0)()(，则显然有Pn(xi)=yi。li(x)每个li有n个根x0…xi…xn===njjijiniiixxCxxxxxxCxl00)())...()...(()(==jijiiiixxCxl)(11)(==njijjijixxxxxl0)()()(==niiinyxlxL0)()(LagrangePolynomial与有关，而与无关节点f当n=1时,为线性插值当n=2时,为二次多项式插值(抛物线插值)1．线性插值(n=1)x0x1(x0,y0)(x1,y1)L1(x)f(x)可见L1(x)是过(x0,y0)和(x1,y1)两点的直线。x0x1x2L2(x)f(x)f(x)2．抛物插值（n=2）因过三点的二次曲线为抛物线，故称为抛物插值。§1LagrangePolynomial定理(唯一性)满足的n阶插值多项式是唯一存在的。niyxPii,...,0,)(==证明：(利用Vandermonde行列式论证)反证：若不唯一，则除了Ln(x)外还有另一n阶多项式Pn(x)满足Pn(xi)=yi。考察则Qn的阶数,)()()(xLxPxQnnn=n而Qn有个不同的根n+1x0…xn注：若不将多项式次数限制为n，则插值多项式不唯一。例如也是一个插值多项式，其中可以是任意多项式。==niinxxxpxLxP0)()()()()(xp§1LagrangePolynomial插值余项/*Remainder*/设节点)1(nf在[a,b]内存在,考察截断误差)()()(xLxfxRnn=],[baCfnbxxxan10，且f满足条件,Rolle’sTheorem:若充分光滑，，则存在使得。)(x0)()(10==xx),(10xx0)(=推广：若0)()()(210===xxx),(),,(211100xxxx使得0)()(10==),(10使得0)(=0)()(0===nxx存在),(ba使得0)()(=nRn(x)至少有个根n+1==niinxxxKxR0)()()(任意固定xxi(i=0,…,n),考察==niixtxKtRnt0)()()()((x)有n+2个不同的根x0…xnx),(,0)()1(baxxn=!)1()()()1(nxKRxnn注意这里是对t求导=!)1)(()()()1()1(nxKLfxnnxn!)1()()()1(=nfxKxn==niixnnxxnfxR0)1()(!)1()()(§1LagrangePolynomial注：通常不能确定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)的图像？y0---10.5-0.5123456xy0---10.5-0.5123456xy0---10.5-0.5123456xABC§1LagrangePolynomial例1：已知233sin,214sin,216sin===分别利用sinx的1次、2次Lagrange插值计算sin50并估计误差。解：0x1x2x185500=n=1分别利用x0,x1以及x1,x2计算4,610==xx利用216/4/6/214/6/4/)(1=xxxL这里)3,6(,sin)(,sin)()2(==xxxfxxf而)4)(6(!2)()(,23sin21)2(1=xxfxRxx00762.0)185(01319.01Rsin50=0.7660444…)185(50sin10L0.77614外推/*extrapolation*/的实际误差0.01013,421==xx利用sin500.76008,00660.0185~00538.01R内插/*interpolation*/的实际误差0.00596内插通常优于外推。选择要计算的x所在的区间的端点，插值效果较好。§1LagrangePolynomialn=223))(())((21))(())((21))(())(()(4363463464363646342=xxxxxxxL)185(50sin20L0.7654323cos21;)3)(4)(6(!3cos)(2=xxxxxxR00077.018500044.02Rsin50=0.7660444…2次插值的实际误差0.00061高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿……例2:已知y=f(x)=ln(1+x)的值如下xi123yi0.71.11.42001122()()()()Lxylxylxylx=(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(12)(13)(21)(23)(31)(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()4xfx21()(1)(2)(3)24Rxxxx例3:证明拉格朗日插值基函数具有如下性质设01()()()1nlxlxlx0101()()()()1()1()1()nnnLxlxlxlxlxlxlx==即y0=1，y1=1，…，yn=1，因此Ln(x)可看成f(x)1的n次多项式.由于f(n+1)(x)0，所以(1)1()()()()()0(1)!nnnnfRxfxLxxn==证：所以Ln(x)f(x)，即Ln(x)1.Whenyoustartwritingtheprogram,youwillfindhoweasyitistocalculatetheLagrangepolynomial.Ohyeah?WhatifIfindthecurrentinterpolationnotaccurateenough?Thenyoumightwanttotakemoreinterpolatingpointsintoaccount.Right.ThenalltheLagrangebasis,li(x),willhavetobere-calculated.Excellentpoint!Wewillcometodiscussthisproblemsoon.