插值法与曲线拟合

1第二章插值与曲线拟合§1引言§2拉格朗日插值多项式§3牛顿插值多项式§4分段低次插值§5最小二乘拟合2§1引言1.1插值问题的提法在生产和科研中出现的函数是多种多样的。常遇到这种情况：在某个实际问题中，虽然可以断定所考虑的函数在区间上存在且连续，但却难以找到它的解析表达式，只能通过实验和观测得到在有限个点上的函数值（即一张函数表）。显然，要利用这张函数表来分析函数的性态、甚至直接求出其xfba,3它一些点上的函数值是非常困难的。在有些情况下，虽然可以写出函数的解析表达式，但由于结构相当复杂，使用起来很不方便。面对这些情况，总希望根据所得函数表（或结构复杂的解析表达式），构造某个简单函数P(x)作为的近似。插值法是解决此类问题的一种比较古老的、然而却是目前常用的方法，它不仅直接广泛地应用于生产实际和科学研究中，而且也是进一步学习数值计算方法的基础。xfxf4定义设函数y=f(x)在区间[a,b]上连续，且在n+1个不同的点上分别取值，在一个性质优良、便于计算的函数类φ中，求一简单函数p(x)，使而在其它点上，作为f(x)的近似。称区间为插值区间，点为插值节点，称（1.1）为f(x)的插值条件，称函数类φ为插值函数类，称p(x)为函数在bxxxan,,,10nyyy,,,10niyxPii,1,0(1.1)ixxnxxx,,,105节点处的插值函数。求插值函数p(x)的方法称为插值法。插值函数类φ的取法不同，所求得的插值函数p(x)逼近f(x)的效果就不同它的选择取决于使用上的需要。常用的有代数多项式、三角多项式和有理函数等。当选用代数多项式作为插值函数时，相应的插值问题就称为多项式插值。在多项式插值中，最常见、最基本的问题是：求一次数不超过n的代数多项式nxxx,,,106(1.2)nnnxaxaaxP10使其中为实数。满足插值条件(1.3)的多项式(1.2)，称为函数f(x)在节点处的n次插值值多项式。n次插值多项式的几何意义：过曲线y=f(x)上的n+1个点作一条n次代数曲线，作为曲线y=f(x)的近似，如图2-1。niyxPiin,,,1,0naaa,,,10xPn)(xPyn),,1,0)(,(niyxii(1.3)7xPynxfy0x1xnxXab0y1yny0Y81.2插值多项式存在唯一性由插值条件（1.3）知，插值多项式的系数满足线性方程组（1.4）由线性代数知，线性方程组的系数行列式（记为V）是n+1阶范德蒙（Vandermonde）行列式，且xPnniai,1,0nnnnnnnnnyxaxaayxaxaayxaxaa101111000010niijjinnnnnnxxxxxxxxxxxV1102121102001119因是区间上的不同点，上式右端乘积中的每一个因子，于是，方程组（1.4）的解存在且唯一。故有下面的结论：定理1若节点互不相同，则满足插值条件（1.3）的n次插值多项式（1.2）存在且唯一。0Vnxxx,1,0ba,0jixxnxxx,1,010§2拉格朗日插值多项式在上一节里，我们不仅指出了插值多项式的存在唯一性，而且也提供了它的一种求法，即通过解线性方程组（1.4）来确定其系数，但是，这种作法的计算工作量大，不便于实际应用，下面介绍几种简便的求法。2.1插值基函数先考虑一下简单的插值问题：对节点中任一点,作一n次多项式,使它在该点上取值为1,而在其余点上取值为零,即（2.1）（2.1）表明n个点都是n次多项式的零点，故可设)(xlkianixi,1,0nkxk0nkkixi,,1,1,1,0kikixlik01)()(xlknkkixi,1,1,1,0)())(())(()(1110nkkkkxxxxxxxxxxAxl11其中为待定系数，由条件可得故(2.2)对应于每一节点，都能求出一个满足插值条件（2.1）的n次插值多项式（2.2），这样，由（2.2）式可以求出n+1个n次插插多项式。容易看出，这组多项式仅与节点的取法有关，称它们为在n+1个节点上的n次基本插值多项式或n次插值基函数。kA1)(kkxl)(,),(),(10xlxlxln)())(()(1110nkkkkkkkxxxxxxxxA)())(()()())(()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxlnkxk0122.2拉格朗日插值多项式利用插值基函数立即可以写出满足插值条件（1.3）的n次插值多项式（2.3）事实上，由于每个插值基函数都是n次多项式，故其线性组合（2.3）必是不高于n次的多项式，同时，根据条件（2.1）容易验证多项式（2.3）在节点处的值为，因此，它就是待求的n次插值多项式。形如(2.3)的插值多项式称为拉格朗日插值多项式，记为（2.4)ixxLn)()()(1100xlyxlyxlynn),,1,0)((nkxlkniyi,,1,0xPn)()()(1100xlyxlyxlynnnknkkkkkknkkkxxxxxxxxxxxxxxxxy0110110)())(()()())(()(13作为的特例，令n=1，由（2.4）即得两点插值公式即这是一个线性函数，用线性函数近似代替函数，在几何上就是通过曲线上两点作一直线近似代替曲线(见图2-2)，故两点插值又名线性插值。若令n=2，由（2.4）又可得常用的三点插值公式（2.5）（2.6）（2.7）))(())(())(())(())(())(()(1202102210120120102102xxxxxxxxyxxxxxxxxyxxxxxxxxyxL010110101)(xxxxyxxxxyxL)()(0010101xxxxyyyxL)(1xL),,(00yx),(11yx)(1xyL)(xfy)(xfy)(xf14这是一个二次函数，用二次函数近似代替函数，在几何上就是通过曲线上的三点，作一抛物线近似地代替曲线（图2-3），故三点插值(二次插值)。例1已知分别用线性插值和抛物插值求的值。xLy1xfyx0x0x1),00(yx),11(yxy图2-2)(2xL)(xf)(xfy)(xfy),(),,(),,(221100yxyxyx)(2xLy12144,11121,1010011515解因为115在100和121之间，故取节点x0=100，x1=121相应地有y0=10，y1=11，于是，由线性插值公式（2.5）可得故用线性插值求得的近似值为图2-3xLy2xfy),11(yx),00(yxyxx0x10),22(yx714.10100121100115*11121100121115*10)115(1151L100121100*11121100121*10)(1xxxL16723.10)121144)(100144()121115)(100115(*12)144121)(100121()144115)(100115(*11)144100)(121100()144115)(121115(*10)115(1152L115仿上，用抛物插值公式（2.7）所求得的近似值为将所得结果与的精确值10.7238…相比较，可以看出抛物插值的精确度较好。为了便于上机计算，我们常将拉格朗日插值多项式（2.4）改写成公式（2.8）的对称形式可用二重循环来完成值的计算，先通过内循环，即先固定k，令j从0到，累乘求得nknkjjjkjknxxxxyxL00)(（2.8）)(kjn)(xLn17然后再通过外循环，即令k从0到n，累加得出插值结果。2.3插值余项在插值区间[a,b]上用插值多项式近似代替，除了在插值节点xi上没有误差外，在其它点上一般是存在有误差的。若记则就是用近似代替时所产生的截断误差，称为插值多项式的余项。nkjjjkjkxxxxxl0)()()()(xPxfxRnn)(xLn)(xPn)(xf)(xRn)(xPn)(xPn)(xf18的n次插值多项式，则对于任何，有其中且依赖于。（2.9）b)(a,,)()(01niinxxx)()!1()()(1)1(xnfxRnnn),,1,0)(()(nixfxPiinbax,x关于误差有如下定理2中的估计式。定理2设在区间上有直到n+1阶导数，为区间上n+1个互异的节点，为满足条件:)(xfba,nxxx,,,10)(xPnba,19例2在例1中分别用线性插值和抛物插值计算了的近似值，试估计它们的截断误差。解用线性插值求的近似值，其截断误差由插值余项公式（2.9）知现在x0=100，x1=121，x=115，故115xxf)(xxxxxxxfxR10102/321,))((81)()(''21)(3558.010*6*15*81max)121115)(100115(*81)115(232/3]121,100[1R20当用抛物插值求的近似值时，其截断误差为将代入，即得0178.010*)144115)(121115)(100115(161)115(252RxxxxxRxxxxfx,202102/532),)()((161)()('''!31)(xxf)(115,144,121,100210xxxx§3牛顿插值多项式由线性代数可知，任何一个不高于n次的多项式，都可表示成函数的线性组合，即可将满足插值条件的n次多项式写成形式其中为待定系数。这种形式的插值多项式称为牛顿﹙Newton﹚插值多项式，我们把它记成Νn﹙x﹚,即（3.1)21)())(())(()(110102010nnxxxxxxaxxxxaxxaa11012010nnonxxxxxxaxxxxaxxaaxNnkak,,1,0)())((,),)((,,1110100nxxxxxxxxxxxx),,1,0()(niyxPii22因此，牛顿插值多项式是插值多项式的另一种表示形式,与拉格朗日插值多项式相比较，不仅克服了“增加一个节点时整个计算机工作必须重新开始”﹙见例1﹚的缺点，而且可以节省乘﹑除法运算次数。同时，在牛顿插值多项式中用到的差分与差商等概念，又与数值计算的其它方面有着密切的关系.3.1向前差分与牛顿插值公式设函数ƒ﹙x﹚在等距节点处的函数值为已知，其中h是正常数，称为步长，称两个相邻点和处函数值之差为函数ƒ﹙x﹚在点处以h为步长的一阶向前差分﹙简称一阶差分﹚，记作，即于是，函数ƒ﹙x﹚在各节点处的一阶差分依次为又称一阶差分的差分为二阶差分。xNnxPnnkkhxxk,,1,00kkyxf1kxkkyy1kxkykkkyyy1。11121010,,nnnyyyyyyyyykkkkyyyy12kx23kmkmkmyyy111一般地，定义函数ƒ﹙x﹚在点处的m阶差分为为了便于计算与应用，通常采用表格形式计算差分，如表2-1所示。表2-1xkykykyk2yk3yk4x0x2x3x4x1y0y1y2