数值分析-02插值

§1引言一、引例已经测得在某处海洋不同深度处的水温如下：深度（M）46674195014221634水温（oC）7.044.283.402.542.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米…）处的水温.这就是本章要讨论的“插值问题”二、插值问题的定义当精确函数y=f(x)非常复杂或未知时，在区间这个问题称为“插值问题”(2.1.1)近似函数g(x)f(x)，满足条件,由此构造一个简单易算的上一系列节点处测得函数值,ab01,,mxxx00,mmyfxyfx0,1,jjgxyjm这里的g(x)称为f(x)的插值函数。节点x0…xm称为插值节点,条件（2.1.1)称为插值条件，区间称为插值区间。,ab插值函数的类型有很多种最常用的插值函数是…?代数多项式用代数多项式作插值函数的插值称为代数插值，即选取次数不超过n的多项式Pn(x)，使得Pn(xj)=yj(j=0,1…n)(2.1.2)本章主要讨论的内容插值问题插值法插值函数§2代数插值代数插值一、插值问题解的存在唯一性？二、插值多项式的常用构造方法？三、插值函数的误差如何估计？一、插值多项式的存在唯一性：设所要构造的插值多项式为：nnnxaxaxaaxP2210)(由插值条件niyxPiin,,1,0)(得到如下线性代数方程组：nnnnnnnnnyaxaxayaxaxayaxaxa101111000100111此方程组的系数行列式为nnnnnnxxxxxxxxxD212110200111nijjixx0)(当()ijxxij时，D0，因此，Pn(x)由a0,a1,…,an唯一确定。范得蒙行列式！定理(唯一性)满足的n阶插值niyxPii,...,0,)(多项式Pn(x)存在且唯一。注：通过解上述方程组求得插值多项式的方法怎样可以不通过求解方程组而获得插值多项式呢?nPx（可能是病态方程组）,当阶数n越高时，病态越重。并不可取.这是因为当n较大时解方程组的计算量较大，而且方程组系数矩阵的条件数一般较大在n次多项式空间Pn中找一组合适的基函数,使不同的基函数的选取导致不同的插值方法.Lagrange插值Newton插值01,,nxxx0011nnnPxaxaxx二、拉格朗日(Lagrange)插值1．线性插值(n=1)x0x1(x0,y0)(x1,y1)f(x)P1(x)n=1已知x0,x1;y0,y1，求101()Pxaax100111(),()PxyPxy使得l0(x)l1(x)1010010yyPxyxxxx01010011yyxxxxxxxx10iiiylx2．抛物插值(n=2)p2(x)f(x)x0x1x2f(x)因过三点的二次曲线为抛物线，故称为抛物插值。3．n次拉格朗日插值公式设连续函数y=f（x）在[a,b]上对给定n+1个不同结点：x0,x1,…,xn,分别取函数值y0,y1,…,yn其中yi=f(xi)i=0,1,2,…,n试构造一个次数不超过n的插值多项式nnnxaxaaxP10)(使之满足条件i=0,1,2,…,niinyxP)(要求：无重合节点，即jixxji若能求得n次多项式lk(x),k=0,1,…,n，ikikxlik,0,1)(则iinkkkinyxlyxP)()(1i=0,1,2,…,n即Pn(x)满足插值条件（2.1.2）.满足因此，令)())(())(()(1110nkkkxxxxxxxxxxxlnkjjjxx0)(又由lk(xk)=1，得：)())(())((11110nkkkkkkkxxxxxxxxxx的表达式推导：klx根据lk(x)的定义，xk以外所有的结点都是lk(x)的根，)())(())(()())(())(()(11101110nkkkkkkknkkkxxxxxxxxxxxxxxxxxxxxxlnkjjjkjxxxx0从而得n阶拉格朗日（Lagrange）插值公式：knknkjjjkjknkknyxxxxyxlxP000)()(4、插值余项/*Remainder*/定理4.3.1若(1)()nfx在[a,b]内存在,则在[a,b]上的n+1个互异的点，对f（x)所作的n次Lagrange插值多项式有误差估计nLx(1)0()()()()()(1)!nnnniifRxfxLxxxnRolle’sTheorem的推论:若充分光滑，且0)()(0nxx存在),(ba使得0)()(n)(x注：通常不能确定,而是估计,x(a,b)，将作为误差估计上限。1)1()(nnMxfniinxxnM01||)!1(当f(x)为任一个次数n的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。0)(xRn0)()1(xfn例：已知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3,421xx利用计算得：sin500.76008,150.005380.0066018Rsin50=0.7660444…利用x0,x1作为插值节点的实际误差0.01001利用x1,x2作为插值节点的实际误差0.00596n=24363264634643643634()()()()11()()()2()()2()()3()()2xxxxLxxx025sin50()0.7654318L23cos21;)3)(4)(6(!3cos)(2xxxxxxR250.000440.0007718Rsin50=0.7660444…2次插值的实际误差0.00061三、牛顿插值（Newton’sInterpolation）Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需要重新计算。希望每加一个节点时，只附加一项上去即可。1．引入能否重新在中寻找新的基函数？1,,nnPxspanxx01020101()()()()...()...()nnnNxAAxxAxxxxAxxxx利用插值条件代入上式，得关于的线性代数方程组:,0,1,njjNxfxjn0,1,KAkn设0010111000100()10()1()()nninniAfxxxAfxxxxxAfx当互异时，系数矩阵非奇异，且容易求解jx00()Afx10110()()fxfxAxx10212202110()()()()()/()fxfxfxfxAxxxxxxItisnotadifficultthingforamathematician.WecanusenotationHowcomplextheexpressionare!2．差商2.1差商的定义(亦称均差)定义1：设有函数f(x)以及自变量的一系列的值f(xi),称),()()(],[jijijijixxjixxxfxfxxf为f(x)在点xi,xj处的一阶差商，并记作f[xi,xj]，互不相等的（即在时，）01,,,nxxxijijxx又称[,][,][,,]()ikijijkkifxxfxxfxxxikxx为f(x)在点xi,xj,xk处的二阶差商称012011011[,,,,][,,][,,]kkkkkkfxxxxfxxxfxxxxx为f(x)在点x0,x1,…,xk处的k阶差商。利用插值条件和差商的定义,可求出的系数:nNxjA00010101()[][,][,,,]nnAfxfxAfxxAfxxx从而00100011()()[,]()[,,]()()()nnnNxfxfxxxxfxxxxxxxx0010010001010101()()()()[,]()()[,]()()()[,,]()()()kkkkNxfxNxfxfxxxxNxfxxxxNxNxfxxxxxxxx因此，每增加一个结点，Newton插值多项式只增加一项，克服了Lagrange插值的缺点。差商可列表计算：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]xiyi一阶差商二阶差商n阶差商……x0x1x2xn-1xnxn+1f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]由差商定义可知：高阶差商是两个低一阶差商的差商。例:给定的数据表2.202.402.602.803.000.788460.875470.955511.029621.098611.构造差商表2.分别写出二次、四次Newton插值多项式lnfxxjxjfx解:差商表ixifx一阶差商二阶差商三阶差商四阶差商2.202.402.602.803.000.435050.788460.875470.955511.029621.098610.400100.0873750.370550.0738750.344950.064000.022500.016460.0075520.788460.435052.200.0873752.202.40Nxxxx40.788460.435052.200.0873752.202.40Nxxxx0.02252.202.402.60xxx0.007552.202.402.602.80xxxx2.2差商的性质:性质1(差商与函数值的关系):记,则01nxxxxxxx010,,niniifxfxxxx00,,,,,,,,,,,,ijnjinfxxxxfxxxx性质2（对称性）：差商的值与结点排列顺序无关，即性质3(差商与导数的关系):设在上有阶导数,且fx,ab1n01,,,,nxxxxab则存在使得,ab01,,!nnffxxxn性质4(特征定理):101010,,,,nnnnfxxfxxfxxxxx3.牛顿差值余项由插值多项式的唯一性可知，故其余项也相同，即nnNxLx(1)011()[,...,]()()(1)!nnnnffxxxxxn，(1)01(),,...,(1)!nnfxxxxnf，定理：Newton插值多项式的余项为011,,,nnnRxfxxxxx