第1章插值教案

1第1章插值1.1插值插值问题的提出导入：插值法是函数逼近的重要方法之一，有着广泛的应用。在生产和实验中，函数f(x)或者其表达式不便于计算，或者无表达式而只有函数在给定点的函数值(或其导数值)，例如，有很多的物理、化学的实验数据；又例如，温度问题、股票的变化问题等。我们希望建立一个简单的而便于计算的函数g(x)，使其近似的代替f(x)。建立的方法可采用插值法，其中以拉格朗日(Lagrange)插值和牛顿(Newton)插值为代表的多项式插值最有特点,常用的插值还有Hermit插值,分段插值和样条插值。基本概念由实验或测量的方法得到所求函数)(xfy在互异点nxxx10,处的值nyyy,,,10构造一个简单函数)(x作为函数)(xfy的近似表达式)()(xxfy，使得nnyxyxyx)(,)(,)(2211（1）这类问题称为插值问题。)(xf称为被插值函数，)(x称为插值函数，x0,x1,...,xn称为插值节点。(1)式称为插值条件。插值的任务就是由已知的观测点,为物理量(未知量)建立一个简单的、连续的解析模型，以便能根据该模型推测该物理量在非观测点处的特性。我们知道函数的类型很多，用来作插值函数的种类不同，所求得的插值函数P(x)逼近f(x)的效果不同，常用的有代数多项式、三角函数式、和有理函数式等。当选用的是代数多项式，相应的插值问题称为多项式插值。在多项式插值中，最常见、最基本的函数是求一次数不超过n的代数多项式：)1()(2210nnnxaxaxaaxPL这时插值问题变为:求n次多项式Pn(x),使满足插值条件)2(,,2,1,0,)(niyxPiinL2只要求出Pn(x)的系数a0,a1,…,an即可,为此由插值条件(2)知Pn(x)的系数满足下列n+1个代数方程构成的线性方程组nnnnnnnnyxaxaxaayxaxaxaayxaxaxaannLLLL22101212110022010100而ai(i=0,1,2,…,n)的系数行列式是Vandermonde行列式xxxxxxxxxxxxnn2nnn1211n0200n10...1..................1...1),...,,V(niijjixx110)(由于xi互异，所以(4)右端不为零，从而方程组(3)的解a0,a1,…an存在且唯一。解出ai(i=0,1,2,…n),Pn(x)就可构造出来了。但遗憾的是方程组(3)是病态方程组,当阶数n越高时，病态越重。为此我们从另一途径来寻求获得插值多项式Pn(x)的方法----Lagrange插值和Newton插值。1.2拉格郎日插值多项式插值基函数定义：)())(()()())(()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl为插值基函数，满足：kikixlik01)((k=0,1,……,n)显然，这n个基函数)(xlk在对应节点上的函数值为1，其余都为0。并且基函数与所取节点有关。下面我们将看到，由这些基函数的线性组合构成的多项式将满足插值条件，因而也是我们要求的插值函数。拉格朗日插值多项式利用插值基函数立即可以写出满足插值条件的n次插值多项式)()()()(1100xlyxlyxlyxLnnn因为每个插值基函数都是n次多项式，所以它的线性组合必是不高于n次的3多项式；又因为L(x)在每个节点xi的值为yi，（I=0,1,2……n），故L(x)就是待求的n次多项式Pn（x）。特别地010110101)()()(1xxxxyxxxxyxLn为线性插值，在几何上就是用过两点的直线近似代替曲线。))(())(())(())(())(())(()(20212102210120102122102xxxxxxxxyxxxxxxxxyxxxxxxxxyxLn为二次插值。在几何上就是用过三点的抛物线代替曲线。例1已知，,12144,11121,10100分别用线性插值于抛物线插值求115的近似值。解：1001211001112110012110)(1xxxL故用线性插值所求的近似值为714.101001211001151112110012111510)115(1151L仿上723.10)121144)(100144()121115)(100115(12)144121)(100121()144115)(100115(11)144100)(121100()144115)(121115(10)115(1152Lx1x0y=L1(x)4将所得结果与115的精确值10.7238……相比较，可以看出抛物线的精确值较好。从上面几何上我们可以很清楚的看到，L1(x)，L2(x)与实际的函数f(x)有不小的误差，如何计算这些误差呢？插值余项注意到，在插值节点上)()(inixPxf在插值区间[a,b]上用插值多项式Pn(x)近似代替f(x)除了在插值节点上没有误差外，在其它点上一般是存在有误差的，记)()()(xPxfxRnn，则)(xRn就是用)(xPn近似代替)(xf时的截断误差，又称)(xRn为插值多项式)(xPn的余项：定理2：设)(xf在区间[a,b]上有直到n+1阶导数，nxxx,,,10为[a,b]上n个互异的节点，)(xPn为满足条件),,2,1,0)(()(nixfxPiin的n次多项式，那么对于任何],[bax有，xbaxxxnfxRininnnn且依赖于),(),(),()!1()()(011)1(证明：（1）),,2,1,0(,0)(),()(nixRxfxPiniin说明插值节点都是)(xRn的零点，所以设)()()(1xxKxRnn，其中)(xK为待定函数；（2）作辅助函数)()()()()(1txKtPtftFnn可以看出有以下特点)!1()()()(1],[...2),,2,1,0(,0)(...1)1()1(nxKtftFnbanixFnni阶导数，且上有直到在3．由（1）可知，)(tF在[a,b]上至少有n+2个互异的零点，有罗尔（Rolle）定理，在[a,b]上)(tF的两个零点之间)(tF至少有一个零点，所以)(tF在（a,b）内至少有n+1个互异的零点；对)(tF再应用罗尔定理，推得)(tF在（a,b）内有n个互异的零点，继续上述讨论，可推得)()1(tFn在（a,b）内至少有一个零点，若记为，则50)()1(nF，即)!1/()()(0)!1()()()1()1(nfxKnxKfnn这样，即得所求。例2：试讨论例1中的截断误差。解：01125.01061581)121115)(100115(81)115())(()(81)()(21)(32/3]121,100[1102/321maxRxxxxxfxR0017.010)144115)(121115)(100115(161)115())()((161)()(!31)(522102/532RxxxxxxxfxR请注意：插值余项要求函数的n阶导数存在，这个条件很高，不一定总能满足。当插值函数的n阶导数不存在或非常麻烦时，又如何计算它的误差呢？(*补)插值误差的事后估计法在许多情况下，要直接应用余项公式来估计误差是有困难的，因为函数的导数通常不一定知道。下面以线性插值为例，学习误差的事后估计法。设210xxxx且)(ixf已知，若将用10,xx两点做线性插值所求得)(xfy的近似值为1y，用20,xx两点作线性插值所得y的近似值为y2，则由余项公式有],[),)()((21],[),)()((2121220221011011xxxxxxfyyxxxxxxfyy假设],[)(20xxxf在区间上变化不大，将上面两式相除，即得近似式2121xxxxyyyy于是有)(121211yyxxxxyy即)()(1212111yyxxxxyyxR式表明,可以通过两个结果的偏差12yy来估计插值误差1yy.这种直接利用计算结果来估计误差的方法，称为事后估计6法。例3：在例1中，曾用.714.10115,11121,101001y的近似值算得同样，用12144,10100算得另一个近似值为682.102y。又事后估计法可估计出插值结果1y的误差为00835.0)714.10682.10(1211441211151151y请回答：你能说出事后估计的好处吗？你发现拉格朗日插值多项式的不足了吗？拉格朗日多项式算法我们用伪码描述拉格朗日插值多项式的算法。1：输入：插值节点控制数n，插值点序列(xi,yi)，i=1,2,……,n，要计算的函数点x。2：ijijjijijnjiytemfxfxxxxxtemtemxxxxxlniijfortemnifor*:2.2);)((*:)(,,1,1,,1,0:1.2;1:,,2,1,0:0LLL3:输出计算结果。1．3牛顿（Newton）插值问题的提出：在上节课的拉格朗日插值多项式中，我们可能已经发现：当增加一个节点时整个计算工作必须重新开始，这样工作量就比较大，也许大家会问：有没有其他的方法能够避免这种缺陷？由线性代数知道，对于任何一个次数不大于N次的多项式，都可以表示成)())((,),)((,,1110100nxxxxxxxxxxxx的线性组合。也就是说，将满足插值条件),,1,0()(niyxPiin的n次插值多项式不妨设为)())(())(()(110102010nnxxxxxxaxxxxaxxaa其中，),1,0(nkak为待定系数。这种形式的插值多项式为牛顿插值多项式，记7为)())(())(()()(110102010nnnxxxxxxaxxxxaxxaaxN如何求出它的系数呢，让我们先来看以下概念：差商设函数)(xf在一串互异的点nxxx,,,10上的函数值为)(,),(),(10nxfxfxf，一阶差商：121221010110)()(],[,)()(],[xxxfxfxxfxxxfxfxxf二阶差商：132132321021021210],,[],[],,[,],[],[],,[xxxxfxxfxxxfxxxxfxxfxxxfn阶差商：01102110],,,[],,,[],,,[xxxxxfxxxfxxxfnnnn差商的计算通常也使用表格：][],,[],[)(3],,[],[)(2],[)(1)(03210321032132332102122111000xxxxfxxxfxxfxfxxxxfxxfxfxxxfxfxxfxjjjji差商的性质：（1）函数)(xf的m阶差商],,,[10mxxxf可由函数值的线性组合表示：miniiiiiiimxxxxxxxxxfxxxf011010)())(()()(],,,[（2）差商具有对称性，即任意调换节点的次序，不会影响差商的值：例如：],,[],,[],,[012021210xxxfxxxfxxxf（3）!)(],,,[)(10mfxxxfmimii8引进差商后，可利用差商表示牛顿插值多项式的系数；由插值条件，可得到nkxxxfaxfakk,,2,1],,,,[)(1000