插值与拟合方法

2.插值法在生产和实验中，常常需要根据一张表格表示的函数推算该表中没有的函数值.解决此类问题的简单途径之一利用插值法。插值在数学发展史上是一个老问题，它是和Gauss,Lagrange,Newton等在著名数学家连在一起的。它最初来源于天体计算——由若干观测值计算人一时刻星球的位置。现在，插值法在工程技术和数据处理有许多直接应用，而且也是数值积分、数值微分的基础。2.1插值概念与基础理论2.1.1插值问题的提法对于给定的函数表xx0x1…….xnY=f(x)y0y1……..yn(其中在[a,b]上连续，x0，x1，…，xn是[a,b]上的n+1个互异的点)，在某函数类{(x)}中求一个函数(x)，使()yfx(xi)=yi,(i=0,1,2,…,n)(2)（1）并用函数(x)作为函数y=f(x)的近似函数，即y=f(x)(x),(x∈[a,b])这类问题称为插值问题。[a,b]称为插值区间，x0,x1,...,xn称为插值节点，（2）称为插值条件，插值条件是选择近似函数的标准，满足此条件的近似函数(x)称为插值函数，f(x)称为被插值函数。函数类{(x)}有多种取法，常用的有代数多项式、三角函数和有理函数。最简单的插值函数是代数多项式，相应的插值问题称为多项式插值。最简单的插值函数是代数多项式，相应的插值问题称为多项式插值。根据所给函数表（1），求一个次数不高于n的多项式Pn(x)=a0+a1x+…+anxn,(3)使pn(xi)=yi,,（i=0,1,2,…，n）(4)满足插值条件（4）的多项式（3），称为函数y=f(x)在节点x0，x1，…，xn处的n次插值多项式。2.2.2多项式插值的理论基础求)(xf的n次插值多项式()nypx的几何意义，就是)(xfy上的若干个节点，作一条代数曲线()nypx来近似代替曲线)(xfy。如图所示。通过曲线a0+a1x0+…+anx0n=y0a0+a1x1+…+anx1n=y1…………………….(5)a0+a1xn+…+anxnn=yn插值多项式的存在唯一性由插值条件（4）知，插值多项式Pn(x)的系数a0,a1,…,an满足下列线性方程组由于xi互异，所以(6)右端不为零，从而方程组(5)的解a0,a1,…an存在且唯一。于是有2n0002n1112nnnn1...1...D...............1...xxxxxxxxx0()ijjinxx而ai(i=0,1,2,…,n)的系数行列式是Vandermonde行列式(6)定理1满足插值条件（4）的n次次插值多项式是存在且唯一的。n2.1.3误差估计()nypx)(xfy从前面的分析知道，用代数多项式来近似代替曲线。除了在节点处没有误差外，在其它点上一般都有误差。若记xpxfxRnnxpnxf的截断误差（插值余项）则nRx就是用代替定理2设[,],nfxCab0,x1,x2,xnxxpnxf则对任意],[bax为在n+1个节点，有余项xnfxpxfxRnnnn1)1(!1)()()()(ba,其中niinnxxxxxxxxx0101任意的[,],xab1nfx存在。上的n次插值多项式，（7）应当指出，余项表达式只有在f(x)的高阶导数存在时才能应用。在（a，b）内的具体位置通常不可能给出，如果我们可以求出，那么插值多项式Ln(x)逼近f(x)的截断误差是…(11)Mfnnbxax1)1)((max)()!1(11)(xnnMxRnn§2.2插值多项式的求法在前面讨论插值多项式的存在唯一性时，实际上已提供了它的一种求法，即通过求解线性方程组来确定其系数ai(i=0,1,2,…,n)但是这种方法不仅计算量大，而且因不能获得简明的表达式而给理论和应用研究带来不便。在这里我们学习两种简便而实用的求答。2.2.1拉格朗日插值多项式在线性代数中知道，所有次数不超过n次的多项式构成一个n+1维线性空间。其基有各种不同的取法。因此尽管满足条件（4）的n次插值多项式是唯一的，然而它的表达式可以有多种不同的形式。如果取满足条件：0,()1,kiikiklx的一组n次多项式xlxlxlxln,,,,210作为上述线性空间的基，则容易看出10010()()()()nnnkkklxylxylxyylxn是一个次数不超过的多项式。且满足插值条件（4）。因此，由n+1个代数多项式xlxlxlxln,,,,210线性生成的多项式（10）就是满足插值条件的n次插值多项式。（10）（9）满足条件（9）的多项式称为n+1个节点的n次基本插值多项式（或n次基函数）xlxlxlxln,,,,210显然，求拉格朗日多项式的关键是求n次插值基函数。0,()1,kiikiklx因此，可设0111()()...()()...()kkkknlxAxxxxxxxxxx因为xlk为n次多项式，且n011011()()()()()()()()()nkkkkkkknkkxxxxxxxxlxxxxxxxxx两种特殊的Lagrange插值多项式1.线性插值(两点插值)最简单的插值是线性插值(此时n=1),这时插值问题就是求一次多项式P1(x)=a0+a1x使它满足条件P1(x0)=y0,P1(x1)=y1,这时1001()xxlxxx0110()xxlxxx于是线性插值多项式为011010110()xxxxLxyyxxxx即100010()()nyyLxyxxxx它就是通过M0(x0,y0)和M1(x1,y1)两点的线段.2.抛物插值线性插值仅仅用两个节点以上的信息，精确度较差。为了提高精确度，我们进一步考察以下三点的插值问题(n=2)：这时1200102()()()()()xxxxlxxxxx0211012()()()()()xxxxlxxxxx0122021()()()()()xxxxlxxxxx由此得到抛物插值多项式2001122()()()()Lxylxylxylx抛物插值又称三点插值.xyln例2已知的函数表x1011121314y2.30262.39792.48492.56492.63915.11ln并估计误差。分别用拉格朗日线性和抛物线插值求的近似值，2.3分段低次插值插值的目的是数值逼近的一种手段，而数值逼近，为了得到一个数学问题的精确解或足够精确的解。那么，是否插值多项式的次数越高，越能够达到这个目的呢？现在，我们来讨论一下这个问题。我们已经知道：f(x)在n+1个节点xi(i=0，1，2，…，n)上的n次插值多项式Pn(x)的余项niinnxxnfxPxfxR011)()!()()()()()(设想当节点数增多时会出现什么情况。由插值余项可知，当f(x)充分光滑时时，余项随n增大而减少，这说明可用增加节点的方法达到这个目的，那么实际是这样吗？1901年龙格(Runge)给出一个例子:定义在区间[-1，1]上，这是一个光滑函数，它的任意阶导数都存在，对它在[-1，1]上作等距节点插值时，插值多项式情况，见图:从图中，可见，在靠近-1或1时，余项会随n值增大而增大，如P12(0.96)=3×6!但f(0.96)=0.2521()1fxx-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)从图中，还可发现，在0附近插值效果是好的，即余项较小，另一种现象是插值多项式随节点增多而振动更多。这种插值多项式当节点增加时反而不能更好地接近被插之数的现象，称为龙格现象。上述现象和定理，告诉我们用高次插值多项式是不妥当的，从数值计算上可解释为高次插值多项式的计算会带来舍入误差的增大，从而引起计算失真。那么如何提高插值精度呢？采用分段插值是一种办法。实践上作插值时一般只用一次、二次最多用三次插值多项式。分段线性插值的构造：设f(x)是定义在[a,b]上的函数，在[a,b]上节点a=x0x1x2…xn-1xn=b,的函数值为y0,y1,y2,…yn-1,yn。(x)在每个子区间[xi,xi+1](i=0,1,2,,n-1)上是一次插值多项式;11111iiiiiiiiiixxxxxxxyxxxxyx,)(这种分段低次插值称为分段线性插值.在几何上就是用折线段带代替曲线,故分段线性插值又称为折线插值.(,),0,1,,kkxyin实际上是连接点的一条折线分段线性插值曲线图：-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81曲线的光滑性较差在节点处有尖点但如果增加节点的数量减小步长,会改善插值效果分段二次插值即：选取跟节点x最近的三个节点xi-1,xi,xi+1进行二次插值，即在区间[xi-1,xi+1]，取：这种分段的低次插值叫分段二次插值，在几何上就是用分段抛物线代替y=f(x)，故分段二次插值又和分段抛物插值。11112iikikjijikjikxxxxyxLxf)()()()(什么是样条:是指飞机或轮船等的制造过程中为描绘出光滑的外形曲线(放样)所用的工具样条本质上是一段一段的三次多项式拼合而成的曲线在拼接处,不仅函数是连续的,且一阶和二阶导数也是连续的1946年,Schoenberg将样条引入数学,即所谓的样条函数2.4三次样条插值],[)(,],[)(),(),()1(2baCxSbaxSxSxS即上连续都在区间上都是三次多项式在每个小区间],[)()2(1kkxxxS处的函数值为在节点如果函数nxxxxf,,,)()3(10njyxfjj,,1,0,)(()Sx而满足njyxSjj,,1,0,)(上的三次样条插值函数在为则称],[)()(baxfxS------(1)定义1.的一个分割为区间],[,,,10babxxxan:],[)(上满足条件在区间如果函数baxS2.4.1、三次样条插值函数2()sx由条件（），不妨将记为1[,],1,2,...,iiisxsxxxxin()={(),}32()(1)iiiixaxbxcxdisiiiiabcd其中，，，为待定系数，共4n个。1由条件（），有()()()()(1,2,...,1)(2)()()iiiiiixxxxinxxii+1ii+1ii+1ssssss3由条件（），有()(0,1,2,...,)(3)iiisxyin2342n容易看出，（）和（）共有个方程，为确定s(x)的4n个待定参数，尚需再给出两个条件，即所谓边界条件。通常使用的边界条件有以下三类：000,nnnxfxfff第一类边界条件是s()=s()=为给定的值。00000()nnnnnfxx-xsxx-xsxsxsxsxsxsx第三类边界条件是周期条件。设()是周期函数，不妨设以为一个周期，这时也应以为周期的周期函数，于是s(x)在端点处满足条件：(+0)=(-0);(+0)=(-0);(+0)=(-0).000nnnxfxfff第二类边界条件是s()=s()=，为给定的值。0=0nxx当s()=s()时，样条函数在两端点不受力，呈自然状态，故称之为自然边界条件。4()4().nsxnsx利用个条件求出三次样条函数的个待定常数，直接求解计算量很大，通常利用Matlab软件求例１　设f(x)为定义在[0,3]上的函数，有下列函数值表xi0123yi00.521.503()0.2