计算方法第三章r.

第三章插值法第一节插值多项式的基本概念假设已经获得若干点上的函数值即提供了一张数据表如何利用这张表求某个给定点上的函数值呢?插值方法所要研究的就是这个课题。,0,1,,,iifxyinx0x1x2xnxyfx0y1y2yny通常用多项式来作为近似函数，称为插值多项式。2012()nnnPxaaxaxax数据表中的函数值为已知的节点称为插值节点，插值节点上所给的函数值称为样本值。函数值待求的点称为插值点。插值节点所界定的范围称为插值区间。如果所给插值点位于插值区间之内，这种插值过程称为内插，否则称为外插。如果插值条件只是给出节点的函数值，称为拉格朗日插值，如果既有函数值也有节点处函数的导数值，称为埃尔米特插值。因式定理：多项式P(x)具有r次因式(x-a)r的充要条件是P(a)=P‘(a)=……=P(a)(r-1)=0最一般的插值条件：是重根，(1)(1)(),(),,()iirriiiiiixyxyxy定理：一旦插值条件给定，则插值多项式是唯一的。irix011mrrrn设函数y=f(x)在闭区间[a,b]上有n+1阶导数，满足前面的一般插值条件，且插值节点各不相同，则插值截断误差为01(1)011()()()()()(1)!()()()()mnnnnrrrnmRxfxPxfxnxxxxxxx01011,,,mmrrrnxxxx在之间，与有关证明思路：构造辅助函数，用罗尔定理。33(4)2012()()()1()()()()4!RxfxPxfxxxxxx300300311322(),(),(),()PxyPxyPxyPxy2301223012()()()()()()[()()]/()()()gtftPtxxxxxxftPtxxxxxx值得注意的是在较大区间上进行插值时，误差可能会很大！另外，一般情况下，外推不如内插好！第二节Lagrange插值公式插值条件是0011(,),(,),,(,)nnxyxyxyLagrange插值实质上是求通过上面n+1个点的n次多项式。一次插值：问题为求一次多项式，即一次函数，过以下两点：容易求出，该函数为：0011(,),(,)xyxy01010110xxxxyyyxxxx二次插值：问题为求二次多项式，即二次函数，过以下三点：容易求出，该函数为：001122(,),(,),(,)xyxyxy120010202110120122021()()()()()()()()()()()()xxxxyyxxxxxxxxyxxxxxxxxyxxxx一般插值问题：求过n+1个点的不超过n次多项式。称为Lagrange插值基函数，满足：0011(,),(,),,(,)nnxyxyxy()nLx0()()nniiiLxylx()ilx1,(),0,ijijijijlxij011011()()()()()()()()()iiniiiiiiinxxxxxxxxlxxxxxxxxx问题:过n+1个点的Lagrange插值多项式是否唯一？满足n+1个插值条件的n次多项式是唯一的；满足n+1个插值条件的多项式不是唯一的；插值公式的误差为：(1)01()()()()()()()(1)!nnnxnRxfxLxfxxxxxxn(1)1[,]101max()()()()()(1)!nnxabnnnMfxMRxxxxxxxn计算程序框图始终输入数据x及,,0,1,,iixyin0,0yi计算权系数i存单元中?iniyyy=1iiLagrange公式的计算流程第三节逐次线性插值函数y=f(x)在节点上的插值多项式记为，则有,,,ijkxxx,,,()ijkNx,,,,,,,,,,,,,,,,,()()()()()()ijkpqijkpijkqijkppqpNxLxNxNxNxxxxxAitken（埃特肯）算法Neville（列维尔）算法0,1,,,0,1,,0,1,,1,0,1,,()()()()()()kpkkpkkpkNxLxNxNxNxxxxx,1,,,1,,11,2,,1,,1()()()()()()iikiikiikiikikiNxLxNxNxNxxxxxAitken（埃特肯）算法0x0N1x1N0,1()Nx2x2N0,2()Nx0,1,2()Nx3x3N0,3()Nx0,1,3()Nx0,1,2,3()NxNeville（列维尔）算法0x0N1x1N0,1()Nx2x2N1,2()Nx0,1,2()Nx3x3N2,3()Nx1,2,3()Nx0,1,2,3()Nx例子：求方程在(2,3)内的根思路，用反函数3250xxyx163-122.058823-0.392.058232.0965892.0956590.0121.51E-52.0956592.0945532.0945292.0945542.094553第四节牛顿插值001122(,),(,),(,),,(,)nnxfxfxfxf010201011()()()()()()()nnnNxccxxcxxxxxxxxxxc差商设函数f(x)，定义函数在两个不同点的一阶差商为三个不同点的二阶差商为：在点处K+1阶差商为：()()(,),(,)ijijijijfxfxfxxxxijxx(,)(,)(,,)ijjkijkikfxxfxxfxxxxx011,,,,kkxxxx011101101(,,,)(,,,)(,,,,)kkkkkkfxxxfxxxfxxxxxx给定n+1个点的函数值，则牛顿插值公式为：00100120101011101011,(),0,1,2,,()()(,)()(,,)()()(,,,)()()()()(,,,)()()()iiinnnnnnnxffxinNxfxfxxxxfxxxxxxxfxxxxxxxxxNxNfxxxxxxxxx差商的计算简表：0011012212012332312301234434234123401234()()(,)()(,)(,,)()(,)(,,)(,,,)()(,)(,,)(,,,)(,,,,)xfxxfxfxxxfxfxxfxxxxfxfxxfxxxfxxxxxfxfxxfxxxfxxxxfxxxxx例子：用0、30、45、60、90五个点作出sinx牛顿插值多项式。做差商表00300.50.016667450.70710.013807-0.000063556600.8660.010595-0.00010707-0.00000079010.0044658-0.0001362-0.00000049牛顿插值的截断误差：101101()(,,,)()()()nnnnNxNfxxxxxxxxx111101110111()()()(,,,)()()()nnnnnnnnnnfxNxNxfxxxxxxxxx101101()()()(,,,)()()()nnnnfxNxNxfxxxxxxxxx01101()()()(,,,)()()()nnnnRxfxNxfxxxxxxxxx例子：用0、30、45、60、90五个点作出sinx牛顿插值多项式。做差商表009010.011111800-0.01111-1.235e-4270-1-0.0111104.572e-736000.011111.235e-44.572e-70差商的计算公式：差商的对称性：差商的线性011000()(,,,,)()()(),()()kjkkjkjkkkikjjiiiijfxfxxxxxxxxxxx()()()()(,)ijjiijijjifxfxfxfxfxxxxxx(,,)(,,)(,,)ijkjikikjfxxxfxxxfxxx010101()()()(,,,)(,,,)(,,,)nnnfxuxvxfxxxuxxxvxxx由于n次插值多项式是唯一的，所以牛顿插值公式与Lagrange插值多项式一样，这意味着余项也一样，Lagrange余项为：所以牛顿余项也一样，(1)01()()()()()(1)!nxnnfRxxxxxxxn01101(1)01()01()()()()(,,,,)()()()()(1)!()(,,,)!nnnnxnkxkxxxxxxxxfxxxxfxxxxxxnffxxxk差商与导数的关系重节点差商推论：当n个节点全为同一个点，牛顿插值变成泰勒多项式。()011(,,,)()!nnfxxxfn()00001(,,,)()!nfxxxfxn差商的导数n次多项式的的1阶差商是n-1次多项式。(1)*011011()(,,,,)(,,,,,)(1)!nnndffxxxxfxxxxxdxn推论：设p(x)是n次多项式，kn时k阶差商是n-k次多项式，kn时k阶差商为零。00000000()()()()0()()()()()()()()()(,)()gxpxpxgxgxxxqxpxpxxxqxpxpxpxxqxxx差分设函数，定义为该函数在i点的一阶差分，记为类似地，定义二阶差分为：K阶差分为：此差分称为向前差分。()iifxxf在的函数值为1iiff,(0,1,2,,)ifin21,(0,1,2,)iiifffi111,(0,1,2,)kkkiiifffi类似地，向后差分定义为：中心差分定义为：1,(0,1,2,)iiifffin111,(0,1,2,)kkkiiifffi1/21,(0,1,2,)iiifffin1/21/2,(0,1,2,)iiifffin111/21,(0,1,2,)kkkiiifffi差商与差分的关系：等距节点时0/201()()()(,,,)!!!nnnnnnnnnfxfxfxfxxxnhnhnh0ixxih第五节带导数的插值问题的提出：如果在已知节点处不仅知道函数值，同时还指导导数值，这样，插值多项式就要求在已知节点处与函数值和导数值都相等。这就是所谓埃尔米特插值，记为H(x)1、牛顿插值如果已知某个点i的，则插值节点应视为个相同节点，并注意到k+1重节点的差商(1),,,,iriiiiyyyyirix()1()(,,,,)!kiiiiikfxfxxxxk例子：已知关于函数y=f(x)的函数值、导数值0011112211,00,4,0,61,2,5xyxyyyxyy-100-4-40-4040-403-11-222-101-253121(0,0)(0)0(0,0,0)(0)/2!3(1,1)(1)5fyfyfy已知函数在n个不同的节点处的函数值和导数值：求次数不超过2n-1次的多项式设想该多项式具有形式：,,(1,2,,)iiixyyin2121(),(),(1,2,,)niiniiHxyHxyin2111()()()nnnjjjjjjHxyhxyhx(),()0,1,2,,()0,(),1,2,,jiijjijijiijhxhxjinhxhxjin由条件可得：此外，由得：2()()()jjhxAxBWx111111()()()()()()()()()jjnjjjjjjjnxxxxxxx