数值计算方法第四章

58第四章函数插值插值是对函数进行近似的基本方法，本章介绍了代数插值时常用的Lagrange插值法、Newton插值法、Hermite插值法和三次样条插值法，并相应的介绍了差商，差分和插值余项等概念．§4.1引言在科学与工程计算中，常会遇到如下问题：已知)(xfy在区间[,]ab上的一系列点niix0处的函数值niiy0，需要利用这些数据来求某点)(ixxx处的函数值的近似值．若能利用这组数据建立一个近似)(xf的函数)(x，)(xf的值就可以用)(x近似求出．已知函数)(xf在区间],[ba上1n个互异节点niix0处的函数值niiy0．若函数集合中函数()x满足条件()()(0,1,2,,)iixfxin(4.1)则称)(x为)(xf在中关于节点niix0的一个插值函数，并称)(xf为被插值函数，],[ba为插值区间，niix0为插值节点．式(4.1)被称为插值条件．函数集合可以有不同的选择，最常用的是形式简单的多项式函数集合．将多项式作为插值函数进行插值的方法称为代数插值．针对区间],[ba上1n个互异节点，代数插值就是要确定一个不超过n次的多项式nnxaxaax10)((4.2)使其满足插值条件(4.1)，即选取参数0niia，满足线性方程组00001111111nnnnnnnayxxayxxayxx(4.3)59记方程组(4.3)的系数矩阵为A．由于插值节点互异，故0)()det(1)(0njijjixxA．线性方程组(4.3)存在惟一的一组解T),,,(10naaa．若0na，)(x是一个n次多项式，否则)(x的次数低于n．于是有下面的结论．定理4.1满足插值条件(4.1)的不超过n次的多项式存在并且惟一．)(x与)(xf在插值节点niix0处函数值相同，但它们在其它x处的函数值并不一定相同．将()()()nRxfxx(4.4)称为用插值多项式)(x近似)(xf的插值余项．定理4.2)(x是对)(xf关于节点niix0的n次插值多项式，若)()1(xfn在区间],[ba内存在，则对[,]xab，有插值余项(1)1()()()()()(1)!nnnfRxfxxxn(4.5)其中),()(bax，101()()()()nnxxxxxxx．证明由于)(x与)(xf在插值节点上函数值相同，故()()()0(0,1,2,,)niiiRxfxxin因此插值余项可设为)()()(1xxkxRnn(4.6)将x视为区间],[ba上异于niix0的任一固定点，作辅助函数)()()()()(1txkttftgn易于验证01,,,nxxx和x为)(tg在区间],[ba上的2n个零点．由Rolle中值定理知，函数)(tg在区间),(ba上至少有1n个互异零点，这1n个零点形成n个子区间，在这些子区间上对)(tg再次使用Rolle定理，可知函数)(tg在),(ba上至少有n个互异零点．依次类推，函数)()1(tgn在),(ba上至少有1个零点，即存在，使得0)()!1()()()1()1(xknfgnn从而得到)!1()()()1(nfxkn60将上式代入式(4.6)就得到插值余项(4.5)，定理得证．虽然通过1n个点niiiyx0),(的不超过n次的多项式惟一，但可以选用不同的基来表示这个多项式．在本章，将选取两组不同的基函数表示该插值多项式，即Lagrange插值多项式和Newton插值多项式．§4.2Lagrange插值在构造n次插值多项式时，式(4.2)简单地选取了nxxx,,,12作为n次多项式空间的一组基函数．为确定待定系数naaa,,,10，需要求解线性方程组(4.3)．能否选择另外一组基函数来避免求解线性方程组？下面从线性插值来着手分析．线性插值就是构造一条直线使其通过两点),(00yx和),(11yx．此直线的两点式方程为)(001010xxxxyyyy将其等价变形为10100101yxxxxyxxxxy(4.7)式(4.7)满足插值条件，并且右端是关于x的一次多项式，故式(4.7)就是所求的插值多项式．将其记为)(1xL，并引入记号,)(1010xxxxxl0101)(xxxxxl式(4.7)就可以写成11001)()()(yxlyxlxL(4.8)容易验证)()(10xlxl和线性无关，它们被称为线性插值的Lagrange插值基函数．观察两个基函数，发现它们具有如下性质0)(1)(1000xlxl1011()0()1lxlx对于三点),(00yx、),(11yx及),(22yx的插值可以类似地写出一个二次多项式612211002)()()()(yxlyxlyxlxL为了满足插值条件，上式中基函数)()(10xlxl、、)(2xl需分别满足下面的关系式0)(0)(1)(201000xlxlxl0)(1)(0)(211101xlxlxl1)(0)(0)(221202xlxlxl将以上思路推广到1n个节点的情形，将经过1n个点niiiyx0),(的n次插值多项式表示为niiinnnyxlyxlyxlyxlyxlxL0221100)()()()()()((4.9))(xLn被称为关于节点niix0的Lagrange插值多项式，式中()(0,1,,)ilxin被称为基于节点niix0的Lagrange插值基函数．当每个基函数()(0,1,,)ilxin分别满足条件ijnjijxlji,0,0,1)((4.10)时，可以验证)(xLn满足插值条件．对于某一个特定的ni,2,1,0，)(xli为不超过n次的多项式．根据式(4.10)，)(xli在除节点ix外的其余n个节点处函数值为零,故)(xli可表示为)())(())(()(1110niiiixxxxxxxxxxkxl由1)(iixl解出)())(())((11110niiiiiiiixxxxxxxxxxk这样就得到插值基函数)(xli的具体表达式)())(())(()())(())(()(11101110niiiiiiiniiixxxxxxxxxxxxxxxxxxxxxl(4.11)式(4.11)也可写为)()()()(11ininixxxxxl62依据公式(4.11)，前面提到的三点插值的Lagrange插值基函数为))(())(()(2010210xxxxxxxxxl))(())(()(2101201xxxxxxxxxl))(())(()(1202102xxxxxxxxxl例4.1对于xy，已知14)196(,13)169(,12)144(fff，用Lagrange线性和二次插值多项式求165的近似值，并给出插值误差估计．解记196169144210xxx，，；141312210yyy，，．由于165x处在0x和1x之间，以它们为插值节点的Lagrange线性插值多项式为011010110()xxxxLxyyxxxx代入已知数据得25144132516912)(1xxxL所以4.1225144165132516916512)165()165(1Lf以210,,xxx为插值节点的二次Lagrange插值多项式为0201122012010210122021()()()()()()()()()()()()()xxxxxxxxxxxxLxyyyxxxxxxxxxxxx代入已知数据得2(169)(196)(144)(196)(144)(169)()12131413006751404xxxxxxLx所以8448.12)165()165(2Lf由于xxf21)(，2341)(xxf，2583)(xxf．故由式(4.5)可知，在165x处线性插值多项式的余项6311(165)()(165144)(165169)max()4812!214416912(144)484.1667102Rffxxf同理在165x处二次插值多项式的余项241441961(165)()(165144)(165169)(165196)3!11max()1488(144)14886.54061066xRffxf§4.3Newton插值当插值节点逐个增加时，考察插值多项式之间的联系．只有一个节点0x时，插值多项式为0yy．当增加一个节点1x时，由点),(00yx和),(11yx确定的线性多项式为1010001010()()()yypxyxxycxxxx(4.12)进一步考察三个节点012,,xxx上建立的二次插值多项式2()px．由于2()px与1()px在01,xx处函数值分别相等，故01,xx是方程21()()0pxpx的根，则21201()()()()pxpxcxxxx即21201()()()()pxpxcxxxx(4.13)同理，当节点由k个增加到1k个，分别由它们所确定的1k次和k次多项式之间的关系为1011()()()()()kkkkpxpxcxxxxxx(4.14)从上面的关系式可以看出，新增加一个节点，新的k次多项式只需要在原来1k次多项式的基础上增加一项即可，而且增加的这一项只需要确定系数kc．将式(4.12)、(4.13)等前面1k个式子依次代入(4.14)就得到()kpx的具体形式为010011()()()()()kkkpxycxxcxxxxxx(4.15)64可将式(4.15)看成是以0010111,,()(),,()()()kxxxxxxxxxxxx为基函数的插值多项式的表达形式，这种插值方法被称为Newton插值法．一、差商的定义给定1k个节点，求出k次Newton插值多项式(4.15)的关键是求出系数12,,,kccc．将插值条件111()pxy代入(4.12)可以求出10110yycxx(4.16)同理将插值条件222()pxy代入(4.13)，并结合1()px的表达式有2012022122202120211021201101212110202120[()]()()()()()()[()]()()()yycxxpxpxcxxxxxxxxyyyyyycxxcxxxxxxxxxxxx(4.17)可见1c是在两点处函数值增量与自变量增量的商，数学上将它形象的称为差商．系数2c可以看成是差商的增量与自变量的增量的商．下面给出差商的一般定义：已知()yfx在互异节点012,,,xxx处的函数值分别为012,,,yyy，定义[,]jiijjiyyfxxxx(4.18)为()fx在节点,ijxx处的一阶差商．定义[,][,][,,]jkijijkkifxxfxxfxxxxx(4.19)为()fx在节点,,ijkxxx处的二阶差商．更一般的，对于任意的正整数k，当定义了两个1k阶差商11[,,,]iiikfxxx和12[,,,]iiikfxxx后就可以定义()fx在节点1,,,iiikxxx处的k阶差商6512111[,,,][,,,][,,,]i