第五章插值方法

第5章插值方法/*MethodsofInterpolation*/5.1插值多项式及存在唯一性012naxxxxb的函数值01(),(),,(),nfxfxfx若存在一个简单函数P(x),使其经过y=f(x)上的n+1个已知x0x1x2x3x4xp(x)f(x)图5.1插值函数的几何描述如图5.10011(,),,,,,,nnxyxyxy点5.1已知函数y=f(x)在区间[a,b]上n+1个不同点定义5.1.1插值多项式的一般提法x0x1x2x3x4xg(x)f(x)成立,则称p(x)是f(x)的插值函数,点为插值节点,0,,nxx(),(0,1,,)(5.1)iiiPxyfxin包含插值节点的区间[a,b]称为插值区间,求插值函数P(x)的方法称为插值方法.若P(x)是次数不超过n的多项式,即2012()(5.2)nnnPxaaxaxax其中是实数,则称P(x)为插值多项式,相应的插值方法称为ia多项式插值.若P(x)为分段多项式,则称为分段插值.若P(x)为三角多项式,则称为三角插值.本章主要讨论多项式插值和分段插值5.1.2插值多项式存在唯一性定理5.1设节点互异,则在次数不超过n的多12,,,nxxx项式集合中,满足条件5.1的插值多项式存在且唯一.nH()nPx证明将代入5.1式得2012()nnnPxaaxaxax20102000201121112012(5.3)nnnnnnnnnnaaxaxaxyaaxaxaxyaaxaxaxy0011111nnnnnxxxxVxx关于的系数行列式是V,而,于是上述方01,,,naaa0V程组有唯一的一组解,即多项式存在且唯一.证毕.()nPx注：若不将多项式次数限制为n，则插值多项式不唯一。例如也是一个插值多项式，其中可以是任意多项式。niinxxxpxLxP0)()()()()(xp反证：若不唯一，则除了Ln(x)外还有另一n阶多项式Pn(x)满足Pn(xi)=yi。考察则Qn的阶数,)()()(xLxPxQnnnn而Qn有个不同的根n+1x0…xn还可以用反证法证明:5.2Lagrange插值/*LagrangePolynomial*/5.2.1Lagrange插值多项式为Lagrange插值多项式,为Lagrange插值基函数.()ilx称满足5.1的n次插值多项式0()()()(5.15)nniiiLxfxlx011101110()()()()()()()()()()()iiniiiiiiiinnjjijjixxxxxxxxxxlxxxxxxxxxxxxxxx其中与节点有关，而与f无关5.2.2线性插值与抛物插值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线性插值在式5.15中当n=1时,有以下内容li(x)已知函数y=f(x)在点处的函数值分别为,012,,xxx012,,yyy在式5.15中当n=2时,Lagrange插值多项式为2001122020112012010210122021()()()()()()()()()()()()()()()()()()()Lxfxlxfxlxfxlxxxxxxxxxxxxxyyyxxxxxxxxxxxx因此这种插值是二次函数,是经过的抛物线,2()Lx001122(,),(,),(,)xyxyxyxyy=2()Lxy=f(x)00x1x2x图5.3抛物线插值图示方法被称为抛物线插值.5.2.4Lagrange插值余项与误差估计1)Lagrange插值余项/*LagrangeRemainder*/设节点)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()()(其中[,],(,)xxabab2)Lagrange插值误差估计定理5.3注：通常不能确定x,而是估计,x(a,b)将作为误差估计上限。1)1()(nnMxfniinxxnM01||)!1(当f(x)为任一个次数n的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。0)()1(xfn0)(xRn推论5.3设节点,在上连续,记01xx()fx01[,]xx2[,]max()xabMfx则过点的线性插值余项为0011(,()),(,())xfxxfx10101()()()(),(,)2xfRxxxxxxx由于在上,在达到最大值01[,]xx01()()xxxx012xxx,可得余项的一个上界估计:对于有210()4xx01[,]xxx22110()()4MRxxx§5.4差商与牛顿插值/*DivededDifferdnceandNewton’sInterpolation*/Lagrange插值方法的优点是容易建立多项式形式整齐直观具有对称性,缺点是增加节点时原有已计算的插值多项式不能利用,这是因为在插值基函数的表达式中,包含了所有的插值节点,因此在进行节点修改时,必须全部重新计算,而Newton插值方法,在增加节点时具有”继承性”这要用到差商的概念。希望将Ln(x)改写成...))(()(102010xxxxaxxaa))...((10nnxxxxa的形式，希望每加一个节点时，只附加一项上去即可。????牛顿插值的思想是：5.4.1差商（亦称均差）及其性质/*divideddifference*/定义5.4),()()(],[jijijijixxjixxxfxfxxf1阶差商：2阶差商:)(],[],[],,[kixxxxfxxfxxxfkikjjikjik+1阶差商:11101010111010],,...,[],,...,[],,...,[],...,,[],...,[kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxfWarning:myheadisexploding…Whatisthepointofthisformula?差商的值与xi的顺序无关！性质5.1性质5.2n阶差商可以表示成n+1个函数值的线性组合,即010011()[,,]()()()()niniiiiiiinfxfxxxxxxxxxxx0110[,][,]fxxfxx012102021[,,][,,][,,]fxxxfxxxfxxx性质5.3实际计算过程为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阶差商5.4.2Newton插值多项式],[)()()(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](1)011()()[,,...,]()()(1)!nxnnkkfRxfxxxxxn注：由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即()0()[,...,],(,)!nnffxxabn性质5.4等距节点公式/*FormulaewithEqualSpacing*/向前差分/*forwarddifference*/iiifff1ikikikikffff1111)(向后差分/*backwarddifference*/111ikikikfffi1iifff中心差分/*centereddifference*/212111ikikikfff其中)(221hiixff当节点等距分布时:),...,0(0nihixxiMoregivenonp.163-164.5.5差分与等距节点的Newton插值5.5.1差分及其性质差分的性质常数的差分等于零00()(1)(1)nnnnjjnjjjkknknnkjjjfEIfCEfCf函数值可以表示各阶差分(5.42)100()(1)(1)nnnnnjjjnnjjkknknkjnjjfIEfCEfCf各阶差分可以表示函数值0()()nnnjjnkkknkjfEfIfCf于是0(5.44)nnjjnkknkjfEfCf差商与差分的关系11121211222[,][,][,]1[,,]2kkkkkkkkkkkkkkkkkffffxxxxhfxxfxxfxxxfxxh一般地有11[,,,](5.45)!mkkkmkmfxxxfmh同理对向后差分有11[,,,](5.46)!mkkkmkmfxxxfmh利用5.45和5.38得()(),((,))nnnkkknfhfxx计算差分可用向前差分表5.6和向后差分表5.7表5.6向前差分表234()()()()()kkkkkkxfxfxfxfxfx0011223344()()()()()xfxxfxxfxxfxxfx0123()()()()fxfxfxfx202122()()()fxfxfx3031()()fxfx40()fx表5.7向后差分表234()()()()()kkkkkkxfxfxfxfxfx4433221100()()()()()xfxxfxxfxxfxxfx4321()()()()fxfxfxfx242322()()()fxfxfx3433(