第四章 插值方法

第四章插值方法当精确函数y=f(x)非常复杂或未知时，在一系列节点x0…xn处测得函数值y0=f(x0),…yn=f(xn)，由此构造一个简单易算的近似函数g(x)f(x)，满足条件g(xi)=f(xi)(i=0,…n)。这里的g(x)称为f(x)的插值函数。最常用的插值函数是…?多项式。x0x1x2x3x4xg(x)f(x)§4.1多项式插值问题的一般提法§4.2拉格朗日(Lagrange)插值niyxPiin,...,0,)(==求n次多项式使得nnnxaxaaxP=10)(条件：无重合节点，即jixxji.:1()(0,1,2,.....,)()knkknnxPxyknnPx==一插值多项式的存在唯一性在个互异节点处满足插值条件的次数不超过的多项式存在且唯一。定理4.2.1注:一次多项式插值---过两点直线。二次多项式插值---过三点抛物线。若不将多项式次数限制为n，则插值多项式不唯一。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称为拉格朗日插值基函数，满足条件li(xj)=ij/*KroneckerDelta*/二.拉格朗日插值的基函数构造法n1希望找到li(x)，i=0,…,n使得li(xj)=ij；然后令==niiinyxlxP0)()(，则显然有Pn(xi)=yi。=--=njijjijixxxxxl0)()()(0()()nniiiPxlxy==拉格朗日插值多项式，常记为Ln(x)拉格朗日插值基函数与有关，而与无关节点f是n次多项式。li(x)每个li有n个根x0…xi-1…xn，三.插值余项设节点)1(nf在[a,b]内存在,考察截断误差)()()(xLxfxRnn-=],[baCfnbxxxan10，且f满足条件,=-=niixnnxxnfxR0)1()(!)1()()(注：通常不能确定x,而是估计,x(a,b)将作为误差估计上限。1)1()(nnMxf=-niinxxnM01||)!1(当f(x)为任一个次数n的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。0)()1(xfn0)(xRn定义4.3.1差商(亦称均差)),()()(],[jijijijixxjixxxfxfxxf--=称为f关于xi和xj的1阶差商)(],[],[],,[kixxxxfxxfxxxfkikjjikji--=2阶差商§4.3差商与差分及其性质10111010],,...,[],...,,[],...,[--=kkkkkxxxxxfxxxfxxf(k+1)阶差商：==kiikikxxfxxf010)()(],...,[事实上其中,)()(01=-=kiikxxx=-=kijjjiikxxx01)()(差商的值与xi的顺序无关！定义4.3.2差分当节点等距分布时:),...,0(0nihixxi==向前差分iiifff-=1一阶向前差分ikikikikffff1111)(----==k阶向前差分向后差分i-1iifff-=一阶向后差分111----=ikikikfffk阶向后差分中心差分212111----=ikikikfff其中)(221hiixff=k阶中心差分§4.4牛顿插值公式牛顿插值公式：))...((...))(()()(10102010------=nnnxxxxaxxxxaxxaaxN其中ai=f[x0,…,xi]...))(](,,[)](,[)()(102100100---=xxxxxxxfxxxxfxfxf))...(](,...,[100---nnxxxxxxf))()...(](,...,,[100nnnxxxxxxxxxf----Nn(x)Rn(x)注：由唯一性可知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]牛顿公式))...(](,...,[...)](,[)()(1000100----=nnnxxxxxxfxxxxfxfxN牛顿前插公式（一般当x靠近x0时用）牛顿后插公式（一般当x靠近xn时用）将节点顺序倒置：))...(](,...,[...)](,[)()(101xxxxxxfxxxxfxfxNnnnnnnn---=-设htxx=0，则)()()(000xfkthtxNxNknknn===),(,))...(1()!1()()(01)1(nnnnxxhntttnfxR--=设htxxn=，则)()1()()(0nknkknnnxfkthtxNxN--===当节点等距分布时:),...,0(0nihixxi==§4.5分段插值法增加插值多项式的次数并不一定会有更好的插值结果，这是因为高次多项式的振荡是很厉害的.例：在[-5,5]上考察的Ln(x)。取211)(xxf=),...,0(105niinxi=-=-5-4-3-2-1012345-0.500.511.522.5n越大，端点附近抖动越大，称为龙格（Runge）现象Ln(x)f(x)分段低次插值3.63()().nxLxfx事实上，已被证明只有当时，才有一.分段线性插值在每个区间上，用1阶多项式(直线)逼近f(x):],[1iixx11111)()(----=iiiiiiiiyxxxxyxxxxxPxf],[for1iixxx缺点：分段插值函数只能保证连续性，失去了原函数的光滑性。即用折线代替曲线。优点：计算简单；适用于光滑性要求不高的插值问题。记，易证：当时，||max1iixxh-=0h)()(1xfxPh一致设f(x)连续，二.分段三次（Hermite）插值给定000,...,;,...,;,...,,nnnxxyyyy在上利用两端点的y及y'构造3次Hermite函数。],[1iixx不少实际插值问题不仅要求函数值相等，而且还要求导数值也相等。这就导致下面的Hermite插值。31111()()()()()iiiiiiiiSxyxyxyxyx=''并满足3311'3311.(),(),(),()iiiiiiiiSxySxySxySxy===='''从而1111111111111()1,()0,()0,()0,()0,()1,()0,()0,()0,()0,()1,()0,()0,()iiiiiiiiiiiiiiiiiiiiiiiiiiiixxxxxxxxxxxxxx==============''''''1110,()0,()1.iiiixx==''由此条件可求得1111122()12,2()().iiiiiiiiiiiixxxxxxxxxxxxxxxx--=---=--类似可得i+1和i+1的表达式。§4.6三次样条插值定义4.6.1设。三次样条函数,且在每个上为三次多项式。若它同时还满足，则称它为f的三次样条插值函数。bxxxan==...10],[)(2baCxS],[1iixx),...,0(),()(nixfxSii==注：三次样条与分段Hermite插值的根本区别在于S(x)自身光滑，不需要知道f的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f在所有插值点的导数值。f(x)H(x)S(x)§4.7曲线拟合的最小二乘法仍然是已知x1…xm;y1…ym,求一个简单易算的近似函数P(x)f(x)。但是①m很大；②yi本身是测量值，不准确，即yif(xi)。这时没必要取P(xi)=yi,而要使P(xi)-yi总体上尽可能小。常见做法：使最小/*最大最小问题*/|)(|max1iimiyxP-太复杂使最小=-miiiyxP1|)(|不可导，求解困难使最小/*最小二乘法*/=-miiiyxP12|)(|考虑一般的线性无关函数族={0(x),1(x),…,n(x),…}，其有限项的线性组合称为广义多项式。==njjjxxP0)()(常见多项式：{j(x)=xj}对应代数多项式。{j(x)=cosjx}、{j(x)=sinjx}{j(x),j(x)}对应三角多项式。{j(x)=ekjx,kikj}对应指数多项式。对于一组数据(xi,yi)(i=1,2,…,m)使得达到极小，这里nm。=-=miiiyxP12])([实际上是a0,a1,…,an的多元函数，在的极值点应有0,0,...,.kkna==kimiiikaxPyxPa-===)(])([201minjijyj(xi)a==-=10][2k(xi)设：0011()()()().nnPxaxaxax=1(,)()(),miiifgfxgx==记0ka=则n,kyaknjjjk,...,0,),(),(0===12(,,).Tmyyyy=其中即：),(),(),(00yyaabnnjiij===cBa=c存在唯一解0(x),1(x),…,n(x)线性无关。定理4.7.1例4.7.1用来拟合.2210xaxaay=x1234y4101826习题3.14,15,16,4.5,4.6解：0(x)=1，1(x)=x，2(x)=x2622),(182),(581),(354),(301),(30),(101),(100),(411),(241104144122220412411110412412100=======================yyyyxxxxxxiiiiiiiiiiiiii=6221825835410030100301030104210aaa21,1049,23210==-=aaa23104921)(2-==xxxPy本章基本要求：1.熟悉Lagrange插值公式、基函数及其余项公式;2.熟悉差商(分)的定义，会造差商(分)表；3.熟悉Newton插值公式；4.熟悉线性分段插值；5.了解Hermite和三次样条插值法的含义；6.了解曲线拟合的最小二乘法。