计算方法-插值与拟合

考试地点：建环151-2：1F-319安全151：1F-214油159:1F-313考试时间：第16周周3第4大节15:25-16:55唯一有效证件学生证，无证不能参加考试第16周建环151-2的实验课调至第16周周3第2大节1C206第4章插值与拟合设已知某个函数关系y=f(x)在某些离散点处的函数值：插值拟合根据这些已知数据来构造函数y=f(x)的一个简单的近似函数要求近似函数经过所有已知的数据点根据已知数据点所反映的趋势，构造一个近似的函数表达式，不要求经过所有的点nxxxxx210nyyyyy210求x=t点处的函数值f(t)插值与拟合的区别第4章插值与拟合插值曲线经过所有节点拟合Lagrange插值Newton插值等距节点插值多项式拟合幂函数指数函数曲线只要反映趋势即可解决的问题：求近似函数以及这个函数在某点的近似值我们的选择：代数插值求一个多项式解决问题的原则：已知的点都在曲线上4.1插值法概述选取多项式Pn(x)，使得niyxPiin,,2,1,0,)(（4.2）作为f(x)的近似函数表达式。满足关系（4.2）的函数Pn(x)为f(x)的一个插值函数，x0,x1,…,xn为插值节点，关系（4.2）为插值条件。设x0x1…xn记a=x0,b=xn，则[a,b]为插值区间。代数插值代数插值的唯一性由n+1个互异节点构造一个次数不超过n的多项式是唯一的。插值多项式存在唯一性设所要构造的插值多项式为：nnnxaxaxaaxP2210)(由插值条件niyxPiin,,1,0)(得到如下线性代数方程组：nnnnnnnnnyaxaxayaxaxayaxaxa101111000100111插值多项式的存在唯一性：由n+1个互异节点构造的n次插值多项式是唯一的。此方程组的系数行列式为nnnnnnxxxxxxxxxD212110200111nijjixx0)(范得蒙行列式！当jixx时，;,2,1ninj,2,1D0，因此，Pn(x)由a0,a1,…,an唯一确定。定理(唯一性)满足的n阶插值niyxPii,...,0,)(多项式是唯一存在的。插值多项式的唯一性注意：当由n+1个节点构造的多项式次数超过n时，插值多项式将会有无穷多个。4.2线性插值和二次插值1．线性插值x0x1(x0,y0)(x1,y1)P1(x)y=f(x)可见P1(x)是过(x0,y0)和(x1,y1)两点的直线。线性插值的两种形式10100101yxxxxyxxxxy)()(0010101xxxxyyyxP100,0,1)(xxxxxl101,1,0)(xxxxxl11001)()()(yxlyxlxL于是P1(x)可以表示为插值基函数的线性组合x0x1x2p2(x)f(x)f(x)2．二次（抛物）插值因过三点的二次曲线为抛物线，故称为抛物插值。Lagrange二次插值多项式的表示形式2120210121012002010212))(())(())(())(())(())(()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxPnnnxaxaaxP10)(要求：互异节点，即jixxji设连续函数y=f（x）在[a,b]上对给定n+1个互异结点：x0,x1,…,xn分别取函数值y0,y1,…,yn其中yi=f(xi)i=0,1,2,…,n试构造一个次数不超过n的插值多项式使之满足条件i=0,1,2,…,niinyxP)(4.3拉格朗日插值求n次多项式lk(x)k=0,1,…,nikikxlik,0,1)(iinkkkinyxlyxP)()(0则i=0,1,2,…,n即Pn(x)满足插值条件（4.2）根据lk(x)的表达式，xk以外所有的结点都是lk(x)的根，1.构造插值基函数)())(())(()(1110nkkkxxxxxxxxxxxlnkjjjxx0)(又由lk(xk)=1，得：)())(())((11110nkkkkkkkxxxxxxxxxx因此令knknkjjjkjknkknyxxxxyxlxP000)()()())(())(()())(())(()(11101110nkkkkkkknkkkxxxxxxxxxxxxxxxxxxxxxlnkjjjkjxxxx0从而得n阶拉格朗日（Lagrange）插值公式：例4.1已知函数y=f(x)的观测数据如下表试求其Lagrange插值多项式。k012xk012yk135解由题知，共有3个结点，所以n=2，于是所求Lagrange插值多项式为：例4.2已知函数y=f(x)的观测数据如下表k0123xk1234yk451437试求其Lagrange插值多项式。解由题知，共有4个结点，所以n=3，于是所求Lagrange插值多项式为：2.Lagrange全程插值算法jipxxxtpjijspysi(1)输入插值节点(xi,yi)(i=0,1,2,…,n)及插值点t；(2)赋初值s=0；(3)当i=0,1,2,…,n时做①p=1②对j=0,1,2,…,n当时，③(4)输出s。)1(nf在(a,b)内存在,考察截断误差)()()(xLxfxRnn设节点bxxxan10，且f满足条件0)(0)()(10xx),(10xx存在使得。且推广：若0)()()(210xxx),(),,(211100xxxx使得0)()(10),(10使得0)()(x10,xx),(10xx罗尔定理:若在［］连续，若充分光滑，)(nf在[a,b]连续,3.插值余项余项定理，Ln(x)是插值多项式，则对任意)()(xfn)()1(xfnbxxxan10],[bax)()!1()()(1)1(xnfxRnxnn),(bax)())(()(101nnxxxxxxx定理4.1设在[a,b]上连续，在(a,b)内存在，节点满足，插值余项(4.10)其中))()(()()()()()(11xLxfxttLtftFnnnn证(1)当x=xi(i=0,1,2,…,n)时，由插值条件知Ln(xi)=yi,，结论成立。F(t)有n+2个零点，反复应用Rolle定理，得0)()1(xnF0)()()!1()(1)1(xRxnfnnxn)()!1()()(1)1(xnfxRnxnn且],[baxixx(i=0,1,2,…,n)，固定x，考虑函数(2)任取注意：通常不能确定x,而是估计,x(a,b)将作为误差估计上限。1)1()(nnMxfniinxxnM01||)!1(当f(x)为任一个次数n的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。0)()1(xfn0)(xRn如何使余项减小？1、增加n能否保证Rn(x)减小？2、设法使减小。使用内插，少用外推。)())(()(101nnxxxxxxxLagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新计算。4.4均差与牛顿基本插值公式4.4均差与牛顿基本插值公式)(jixxyyjiji],[ijxxf)(],[jixxyyxxfjijiij1．均差（差商）的定义设连续函数y=f(x)在n+1个互异节点x0,x1,x2,…,xn上对应的函数值为y0,y1,y2,…,yn，为函数f(x)关于xi,xj的一阶均差，记为即4.4.1均差一般称均差的定义)(],[],[kiikjikjxxxxxxfxxf],,[kjixxxfikjikjkjixxxxfxxfxxxf],[],[],,[],,,[110kxxxf],,,[21kxxxf011021],,,[],,,[xxxxxfxxxfkkk011021210],,,[],,,[],,,,[xxxxxfxxxfxxxxfkkkk称为函数f(x)关于xi,xj,xk的二阶均差，记为，即同理，可以依次定义下去。设与分别为函数f(x)关于x0,x1,…,xk-1及关于x1,x2,…,xk的k-1阶均差，则称为函数f(x)关于x0,x1,x2,…,xk的k阶均差，即均差具有对称性，即均差与节点的排列次序无关2.均差表y0y1y2…yn1ynf[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]……………f[xn2,xn1,xn]…f[x0,…,xn]xn+1yn+1f[xn,xn+1]f[xn1,xn,xn+1]…f[x1,…,xn+1]f[x0,…,xn+1]xiyi一阶均差二阶均差n阶均差……由均差定义可知：高阶均差是两个低一阶均差的均差（差商）。x0x1x2xn-1xn例4.3根据已知数据构造均差表i012345xi023561yi08271252161均差表914.4.2牛顿基本插值公式)](,[)()(01001xxxxfxfxP))(](,,[)](,[)()(1021001002xxxxxxxfxxxxfxfxP)())(](,,,[)](,[)()(110100100nnnxxxxxxxxxfxxxxfxfxP设已知函数y=f(x)在n+1个互异结点x0,x1,x2,…,xn上的函数值为y0,y1,y2,…,yn。当n=1或2时，可分别有如下形式的插值多项式和由此可以推测，插值多项式可能有如下的一般形式1.牛顿插值公式任取ixx,(i=0,1,2,…,n)，由一阶均差的定义有000)()(],[xxxfxfxxf于是)](,[)()(000xxxxfxfxf110010],[],[],,[xxxxfxxfxxxf],,[)(],[],[101100xxxfxxxxfxxf],,,[)(],,[],,[210221010xxxxfxxxxxfxxxf],,,,[)(],,[],,,,[1010110nnnnxxxxfxxxxxfxxxxf由二阶均差的定义有于是这样依次做下去就有……)())(](,,,[)())((],,,[))(](,,[)](,[)()(101011010102100100nnnnxxxxxxxxxxfxxxxxxxxxfxxxxxxxfxxxxfxfxf)())(](,,,,[)(1010nnnxxxxxxxxxxfxR)()()(xRxPxfnn将以上各式依次代入，可得记于是其中)())(](,,,[)](,[)()(110100100nnnxxxxxxxxxfxxxxfxfxP只要验证Pn(x)满足插值条件f(xi)=pn(xi)即可当x=xi时，Rn(xi)=0)(!)1()()(],...,,[1)1(10xnfxxxxfkxnkn),(,!)(],...,[maxmin)(0xxkfxxfkk牛顿插值公式的优点是：当增加一个节点时，只要再增加一项就行了，即有递推式:],,,[)())(()()(10101kkkkkxxxfxxxxxxxPxP由插值的唯一性可知Pn(x)Ln(x)，故其余项也相同，即均差与导数的关系公式2.牛顿插值举例例4.3根据已知数据i012345xi023561yi08271252161构造均差插值多项式。均差表91牛顿基本插值