33第二章多项式插值

第二章多项式插值引言：本章和下章的内容属于函数逼近论。函数逼近论的基本思想：用一个简单函数)(x去近似(逼近)复杂的函数)(xf。简单函数：如代数多项式nnnxaxaaxp10)(三角多项式)sincos(2)(10nkkknkxbkxaaxf，分段（对高维：分片）多项式有理函数)(),()()()(xQxPxQxPxR为多项式本章主要内容在插值方式（意义）下作函数逼近插值问题：已知)(xfy在离散点ix上的值iy，求简单函数)(x使得：miyxfxiii,,2,1,0,)()(.插值节点:nxxx,,10（彼此相异）（这时)(xf:被插值函数,)(x:插值函数）针对以下两种逼近函数空间：代数多项式空间分段代数多项式空间讨论三类插值（逼近）问题。(1)Lagrange插值仅与函数值有关(2)Hermite插值与函数和导函数值均有关(3)样条（或分段）插值满足一定光滑（连接）条件的分段低次多项式插值每类插值问题所涉及的基本内容问题提法问题的适定性（解的存在、唯一性）误差分析（逼近度刻化）问题解（插值函数）的常用算法§1代数多项式插值1.1插值多项式的存在惟一性给出niyxii,,2,1,0),(求：nnnxaxaaxp10)(，(1)使得：niyxpiin,,1,0,)(.(2)1n，xaaxp101)(2n，22102)(xaxaaxpiinyxp)(可写成一个关于naaa,,,10的线性代数方程组:,2210ininiiyxaxaxaa.,1,0ni定理1多项式插值问题的解是存在惟一的.证明：关于naaa,,,10的线性代数方程组系数行列式为：)(111),,,(021211020010jinijnnnnnnnxxxxxxxxxxxxxxV由于)(,jixxji，所以上式的右端不为零，从而方程组的解存在且惟一.□如：1n，)(11),(011010xxxxxxV2n，))()((111),,(010212222211200210xxxxxxxxxxxxxxxV误差估计:(Rolle中值定理:假设)(xf于],[ba上连续，)(xf在),(ba内存在，又,0)()(bfaf则在),(ba内至少有1个点，使得0)(f.定理2假设)()(xfn于],[ba上连续，)()1(xfn在),(ba存在，又nxxx,,,10是],[ba上互异的数.记插值问题（1），（2）的截断误差为),()()(xpxfxRnn那么当],[bax时有niinnnxxnfxpxfxR0)1()()!1()()()()(.(3)其中),,(ba且依赖于x.证明当x为任何一个插值节点时，(3)的两边为零结论显然成立.现设nixxi,,1,0,，这时niinxxx0)()(不等于零.以下对于固定的x作定义在],[ba上的辅助函数F，)()()()(ttptftFnn，(4)选择，使得：,0)(xF即取,)()()(xxpxfnn（5）于是,0)()()()(10nxFxFxFxF利用Rolle中值定理，在)(tF),(ba内至少有1n个零点.进一步对)(tF应用Rolle中值定理可知在)(tF),(ba内至少有n个零点.继续上述讨论就可推得在插值区间内至少有一个，),,,,max(),,,,min(1010nnxxxxxxxx，使得0)()1(nF即0)!1()()1(nfn，结合（5）式从而得niinnnxxnfxpxfxR0)1()()!1()()()()(.□1.2拉格朗日（Lagrange）插值公式基函数方法：作)(xli（)(xli为n次多项式），使得：,,1,,0)(,kikixlkikii，nk,,1,0这时：nijjjixxAxl0)()(由1)(iixl，得：nijjjixxA0)(/1于是：nijjjinijjjixxxxxl00)(/)()((6)记：njjnxxx0)()(，则：)()(lim)()(lim)('inxxiinnxxinxxxxxxxxiinijjjixx0)(故：)()()()('ininixxxxxlniiinxlyxp0)()()()()('0ininniixxxxy(7)称为n次多项式插值的Lagrange公式.例设xexf)(在30.0,25.0,15.0,10.0x的值顺次为0.904837,0.860708,0.778801,0.740818,利用插值公式求xe在0.20的近似值.令,20.0,30.0,25.0,15.0,10.03210xxxxx依(6)得,61)20.0(,32)20.0(,32)20.0(,61)20.0(3210llll于是由（7）得.818730.0)20.0(3p又由插值多项式的余项估计式（3）有：,!4/)10.0)(05.0)(05.0)(10.0()20.0(3eR由于30.010.0，故e应于0.904837与0.740818之间，于是6361095.01077.0R这个估计说明3R差不多是第六位小数上一个单位，事实上xe在20.0x的值为0.8187308.1.3多项式插值的Neville方法逐次线性插值方法（略）§2差商、牛顿（Newton）插值多项式设nxxx,,,10为任意1n个不同的节点，取：)())((,),(,11100nxxxxxxxx作为多项式空间的基底，作多项式：))(()()(102010xxxxcxxccxpn).())((110nnxxxxxxc将nxxxx,,,10依次代入得：),()()()(),)(()()(),()(,)(1001012022021020110100nnnnnnxxxxcxxccxfxxxxcxxccxfxxccxfcxf算得：)(00xfc,,)()(01011xxxfxfc))(()()()(1202121122xxxxxxcxfxfc0201011212)()()()(xxxxxfxfxxxfxf2.1差商及其性质给出离散变量函数（函数表）ix0x1x…nx)(ixf)(0xf)(1xf…)(nxf我们称：ijijjixxxfxfxxf][][],[为)(xf于点jixx,的一阶差商.注意：由于)(][][lim'iijijxxxfxxxfxfij因此：|)(|)(],['jiijixxOxfxxf.以下归纳法定义高阶差商，特别记：零阶差商：)(][jjxfxf，二阶差商：f[kjixxx,,]ikjikjxxxxfxxf],[],[1n阶差商的差商称为n阶差商：010110],,[],,[],,,[xxxxfxxfxxxfnnnn差商性质类似于微商，例如：1.若)()(xcfxF（线性运算），则：],,,[10nxxxF],,,[10nxxxcf2.若)()()(xgxfxF，则：],,,[10nxxxF],,,[10nxxxf],,,[10nxxxg性质1k阶差商],,,[10kxxxf可表示为函数值)(0xf,)(,),(1kxfxf的线性组合，即,)()(],,,[010kiikikxxfxxxf其中:kijjjiikkjjkxxxxxx00)(,)()(.性质2差商关于所含节点是对称的，即有],,,,[],,,[20110kkxxxxfxxxf],,,[01xxxfkk.性质3如果],,,[0kxxxf是一个依赖于x的m次代数多项式，那么],,,,[10kkxxxxf是一个关于x的1m次代数多项式.事实上，由差商的定义有,],,,[],,,[],,,,[110010kkkkkkxxxxxfxxxfxxxxf性质4设)(xf在含nxxx,,,10的区间上有n阶导数，则在这一区间内至少有一点使得!/)(],,,[)(10nfxxxfnn2.2Newton插值多项式由差商的定义有],,[)()()(000xxfxxxfxf],,,[)(],[],[101100xxxfxxxxfxxf],,,,[)(],,[],,[210221010xxxxfxxxxxfxxxf……………………],,,[)(],,,[],,,[01010nnnnxxxfxxxxxfxxxf.代入有：))(](,,[)](,[)()(102100100xxxxxxxfxxxxfxfxf)()](,,,[1010nnxxxxxxxf)())(](,,,,[1010nnxxxxxxxxxxf)()(xRxNnn其中)](,[)()(0100xxxxfxfxNn)())(](,,,[11010nnxxxxxxxxxf,)())(](,,,[)(100nnnxxxxxxxxxfxR.由于：nixNxRxNxfininini,,1,0),()()()(，因此)(xNn称为Newton插值多项式,)(xRn为插值余项.有：)()(xNxLnn下面证明性质4：)!()(],,[)(0nfxxfnn，max{},,,min{10nxxx},,,10nxxx若：],[)(1baCxfn，则：)())(](,,,,[1010nnxxxxxxxxxxf)!1()()1(nfn)())((10nxxxxxx故：)!1()(],,,[)1(0nfxxxfnn，max{},,,min{10nxxx},,,10nxxx.这就证明了性质4.性质1的证明：由于)()(xNxLnn，即：)](,[)()(0100xxxxfxfxNn)())(](,,,[11010nnxxxxxxxxxfniniininininxxxxxxxxfxL00),()(,)()()()()(比较nx的系数的系数，可得：niininxxfxxf00)()(],,[.差商概念的推广——重节点差商.定义],[lim],[010001xxfxxfxx)()()(lim0010101xfxxxfxfxx，一般地定义],,,,[],,,,,[1010xxxxfdxdxxxxxfnn.又：!./)(],,,[0)(1000nxfxxxfnn个例：求],,,[2110xxxxf],,[],,,[21012110xxxfxxxxxf}],[],[{2021101xxxxfxxfx1010201)()([1{xxxfxfxxx]})()(1021xxxfxf21010101'20)())()(())(({1xxxfxfxxxfxx22121211')())()(())((xxxfxfxxxf2.3差分、等距节点下的Newton插值多项式若niihxxi,,2,1,0,0，h——步长这时：Newton插值多项式中：)()(00xfxf],[10xxf))()((1)()(010101xfxfhxxxfxf],,[210xxxf021021],