数值分析第二章 插值法.

Ch2插值法/*Interpolation*/插值就是利用邻近点上已知函数值的加权平均来估计未知函数值当精确函数y=f(x)非常复杂或未知时，在一系列节点x0…xn处测得函数值y0=f(x0),…yn=f(xn)，由此构造一个简单易算的近似函数P(x)f(x)，满足条件P(xi)=f(xi)(i=0,…n)。这里的P(x)称为f(x)的插值函数。最常用的插值函数是…?多项式x0x1x2x3x4xP(x)f(x)§1拉格朗日多项式/*LagrangePolynomial*/niyxPiin,...,0,)(==求n次多项式使得nnnxaxaaxP=10)(条件：无重合节点，即jixxjin=1已知(x0,y0);(x1,y1)，求xaaxP101)(=使得111001)(,)(yxPyxP==几何意义:P1(x)是过(x0,y0)和(x1,y1)两点的直线。此时为线性插值§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*/§1拉格朗日多项式/*LagrangePolynomial*/)cos()([0.0,1.2]xxfy==上的曲线考虑例1)(2.10.0(a)110xPxx构造线性插值多项式和利用节点==)(0.12.0(b)110xQxx构造线性插值多项式和利用节点==例21.3010,1g201,lg10==已知的近似值利用插值一次多项式求lg12§1拉格朗日多项式/*LagrangePolynomial*/n=2已知(xk-1,yk-1)、(xk,yk)和(xk+1,yk+1)，求22102)(xaxaaxP=使得几何意义:P2(x)是过已知三点(xk-1,yk-1)、(xk,yk)和(xk+1,yk+1)的抛物线P2(xk-1)=yk-1，P2(xk)=yk和P2(xk+1)=yk+1§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§1LagrangePolynomial定理(唯一性)满足的n阶插值多项式是唯一存在的。niyxLii,...,0,)(==证明：反证：若不唯一，则除了Ln(x)外还有另一n阶多项式Pn(x)满足Pn(xi)=yi。考察则Qn的阶数,)()()(xLxPxQnnn-=n而Qn有个不同的根n+1x0…xn一个次数小于等于n的多项式Qn(x)至多有n个根§1LagrangePolynomial定理(唯一性)满足的n阶插值多项式是唯一存在的。niyxLii,...,0,)(==证明：注：若不将多项式次数限制为n，则插值多项式不唯一。例如也是一个插值多项式，其中可以是任意多项式。=-=niinxxxpxLxP0)()()()()(xp推论§1LagrangePolynomial插值余项/*Remainder*/设节点)1(nf在[a,b]内存在,考察截断误差)()()(xLxfxRnn-=上连续在],[)()(baxfnbxxxan10定理,,)(],[)()()(）内存在在（上连续，在设baxfbaxfnn1的是满足条件节点jjnnnyxLxLbxxxa=)()(,10插值余项则对任何插值多项式],,[,bax)()!1()()()()(1)1(xnfxLxfxRnnnn=-=,),(xba且依赖于这里)())(()(101nnxxxxxxx---=§1LagrangePolynomial插值余项/*Remainder*/设节点)1(nf在[a,b]内存在,考察截断误差)()()(xLxfxRnn-=上连续在],[)()(baxfnbxxxan10Rolle’sTheorem:若充分光滑，，则存在使得。)(x0)()(10==xx),(10xx0)(=推广：若0)()()(210===xxx),(),,(211100xxxx使得0)()(10==),(10使得0)(=),(,0)()(baxxn=0)()(0===nxx§1LagrangePolynomialRn(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)(xRn§1LagrangePolynomial例：已知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.010013,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高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿……课堂作业1.的二次插值多项式求时当)(,4,3,0)(2,1,1xfxfx-=-=,2.构造出的和已知由数据)2,2()3,1(),,5.0(),0,0(yyxxP试确定数据的系数是的三次插值多项式6,33)(3.ikikxxninikk==--=00)(:证明牛顿插值§2牛顿插值/*Newton’sInterpolation*/Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。的形式，希望每加一个节点时，将Ln(x)改写成...))(()(102010---xxxxaxxaa))...((10---nnxxxxa只附加一项上去即可。????差商(亦称均差)/*divideddifference*/),()()(],[jijijijixxjixxxfxfxxf--=1阶差商/*the1stdivideddifferenceoffw.r.t.xiandxj*/)(],[],[],,[kixxxxfxxfxxxfkikjjikji--=2阶差商§2Newton’sInterpolation1102001100],...,[],,...,[],,...,[],...,,[],...,[-----=--=kkkkkkkK-1K-1kxxxxfxxxfxxxxxfxxxfxxf(k)阶差商：==kiikikxxfxxf010)()(],...,[事实上其中,)()(01=-=kiikxxx=-=kijjjiikxxx01)()(Warning:myheadisexploding…Whatisthepointofthisformula?差商的值与xi的顺序无关！§2Newton’sInterpolation牛顿插值/*Newton’sInterpolation*/],[)()()(000xxfxxxfxf-=],,[)(],[],[101100xxxfxxxxfxxf-=],...,,[)(],...,[],...,,[0010nnnnxxxfxxxxfxxxf-=-))...((...))(()()(10102010------=nnnxxxxaxxxxaxxaaxN12…………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]§2Newton’sInterpolation注：由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即)(!)1()()(],...,,[1)1(10xnfxxxxfkxnkn=),(,!)(],...,[maxmin)(0xxkfxxfkk=实际计算过程为f(x0)f(x1)f(x2)…f(xn-1)f(xn)f[x0,x1]f[x1,x2]…………f[xn-1,xn]f[x0,x1,x2]…………f[xn-2,xn-1,xn]f[x0,…,xn]f(xn+1)f[xn,xn+1]f[xn-1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]课堂作业1.构造出的和已知由数据)2,2()3,1(),,5.0(),0,0(yyxxP试确定数据的系数是的三次插值多项式6,33)(2.数值表给出xxfln)(=0.40.50.60.70.8-0.916291-0.693147-0.510826-0.356675-0.223144xxln的近似值算线性插值和二次插值计利用54.0lnNewton等距节点插值§2Newton’sInterpolati