第四章 多项式插值与数值逼近

实际问题中经常要涉及到函数值的计算问题：（1）如果函数表达式本身比较复杂，且需要多次重复计算时，计算量会很大；（2）有的函数甚至没有表达式，只是一种表格函数，而我们需要的函数值可能不在该表格中。对于这两种情况，我们都需要寻找一个计算方便且表达简单的函数来近似代替，这就是数值逼近问题。问题背景§1插值问题/*InterpolationProblem*/（插值的定义）411..Def1n已知定义于区间上的实值函数在个互异节点处的函数值，若函数集合中的函数满足[,]ab()fx0[,]niixab0()niifx()x012()(),,,,()iixfxin则称为在函数集合中关于节点的一个插值函数，并称为被插值函数,[a,b]为插值区间，为插值节点，（*）式为插值条件。()x0niix()fx()fx0niix设00max,minnniiiiMxmx外插法：内插法：用计算被插值函数在点处的近似值()x(,)xmM()fx用计算被插值函数在点处的近似值()x[,],(,)xabxmM()fx插值类型代数插值：集合为多项式函数集x0x1x2x3x4xg(x)f(x)几何意义：()ygx()yfx有理插值：集合为有理分式函数集三角插值：集合为三角函数集代数插值的存在唯一性21,,,,nnHspanxxx设20120()(),,nnixxaaxaxaxaRin即代入插值条件：012()(),,,,iixfxin200102000210112111212()()()()()()nnnnnnnnnnnnxaaxaxaxfxxaaxaxaxfxxaaxaxaxfx方程组的系数矩阵是Vandermonde矩阵20002111021101()nnijjinnnnnxxxxxxxxxxx方程组存在唯一解，因此满足插值条件(*)的不超过n次的插值多项式是唯一存在的.411..Th截断误差插值余项设在区间[a,b]上连续，在区间[a,b]上存在,是满足插值条件（*）的不超过n次的插值多项式，则对存在，满足其中。且当在区间[a,b]有上界时，有()()nfx1()()nfx()x[,]xab()[,]xab111()()()()()()()!nnnfRxfxxxn10()()nniixxx1()()nfx1nM111()()()!nnnMRxxn代数插值的插值余项412..Th/*Remainder*/注意这里是对t求导证明：设1()()()nnRxkxxixx结论显然成立01(,,,)ixxin时构造辅助函数1()()()()()ngtfttkxt则有个互异零点、()gt2n01(,,,)ixinx由罗尔(Roll)定理()gt在区间（a,b）上至少有n+1个互异零点在区间（a,b）上至少有n个互异零点()gt以此类推，反复利用Roll定理在区间（a,b）上至少有1个零点1()()ngt111()()()()()!()nngtftnkx而11()()()()!nfkxn111()()()()()!nnnfRxxn注：（1）插值误差与节点和之间的距离有关；（2）如果本身为多项式，其插值函数为本身。（3）通常不能确定,而是估计,x(a,b)将作为误差估计上限。0niixx()fx11()()nnfxM101||()!nniiMxxn§2代数插值多项式的构造方法一、拉格朗日多项式/*LagrangePolynomial*/niyxPiin,...,0,)(求n次多项式使得nnnxaxaaxP10)(条件：无重合节点，即jixxjin=1已知x0,x1;y0,y1，求xaaxP101)(使得111001)(,)(yxPyxP可见P1(x)是过(x0,y0)和(x1,y1)两点的直线。)()(0010101xxxxyyyxP101xxxx010xxxx=y0+y1l0(x)l1(x)10)(iiiyxl10()ijijijlxij称为拉氏基函数/*LagrangeBasis*/，满足条件li(xj)=ijnjijjijixxxxxl0)()()(与有关，而与无关n1希望找到li(x)，i=0,…,n使得li(xj)=ij；然后令niiinyxlxP0)()(，则显然有Pn(xi)=yi。li(x)每个li(x)有n个根x0…xi-1、xi+1…xnjijiiiixxCxl)(11)(niiinyxlxL0)()(LagrangePolynomial节点f0110()()()()()()niiiinijjjilxCxxxxxxxxCxx01110111()()()()()()()()()()()iiniiiiiiiinxxxxxxxxxxlxxxxxxxxxxx10100()()()()()()()nnnniijjjjixxxxxxxxxxxxx若记100()()()()nnnjijjjjijidxxxxxxxdx10()()nniijjjixxx11()()()()niinixlxxxx01110111()()()()()()()()()()()iiniiiiiiiinxxxxxxxxxxlxxxxxxxxxxx例如也是一个插值多项式，其中可以是任意多项式。0()()()()nniiPxLxqxxx()qx（2）Lagrange插值多项式结构对称，形式简单.111()()()()()()()!nnnnfRxfxLxxn（3）误差估计注：（1）若不将多项式次数限制为n，则插值多项式不唯一。（4）当插值节点增加时，拉氏基函数需要重新计算，n较大时，计算量非常大,故常用于理论分析。Quiz:给定xi=i+1,i=0,1,2,3,4,5.下面哪个是l2(x)的图像？y0---10.5-0.5123456xy0---10.5-0.5123456xy0---10.5-0.5123456xABC2124563132343536()()()()()()()()()()()xxxxxlx例1：已知233sin,214sin,216sin分别利用sinx的1次、2次Lagrange插值计算sin50并估计误差。解：0x1x2x185500n=1分别利用x0,x1以及x1,x2计算4,610xx利用216/4/6/214/6/4/)(1xxxL这里263()()sin,()sin,(,)fxxf而211322264()()sin,()()()!fRxxx00762.0)185(01319.01Rsin50=0.7660444…)185(50sin10L0.776143,421xx利用sin500.76008,00660.0185~00538.01R1/31/43()/4/3/3/422xxLx选择要计算的x在区间的内部，插值效果较好。高次插值通常优于低次插值n=223))(())((21))(())((21))(())(()(4363463464363646342xxxxxxxL)185(50sin20L0.76543213364322cos()()()();cos!Rxxxx00077.018500044.02Rsin50=0.7660444…但绝对不是次数越高就越好，嘿嘿……反插值问题1n已知定义于区间上的单调连续函数在个互异节点处的函数值，若函数值已知，如何求？[,]ab()fx0[,]niixab0()niifxx()yfx1()xfy即求因此可以看作如下插值问题：1n已知定义于区间上的连续函数在个互异节点处的函数值，求函数值[,]ab1()xfy10()niiixfy0()niiiyfx1()xfyxi1.01.41.82.0yi=f(xi)-2.0-0.80.41.2例2：已知单调连续函数在如下采样点的函数值：()yfx求方程在[1，2]内根的近似值。x0()fx解：1308041210200820042012(.)(.)(.)()().(..)(..)(..)yyyfyLy20041214082008040812(.)(.)(.).(..)(..)(..)yyy20081218042004080412(.)(.)(.).(..)(..)(..)yyy20080420122012081204(.)(.)(.).(..)(..)(..)yyy10()xf301675().L二、牛顿插值/*Newton’sInterpolation*/Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。将Ln(x)改写成...))(()(102010xxxxaxxaa))...((10nnxxxxa的形式，希望每加一个节点，只附加一项上去即可。????差商(亦称均差)/*divideddifference*/),()()(],[jijijijixxjixxxfxfxxf1阶差商/*the1stdivideddifferenceoffw.r.t.xiandxj*/)(],[],[],,[kixxxxfxxfxxxfkikjjikji2阶差商11101010111010],,...,[],,...,[],,...,[],...,,[],...,[kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)阶差商：kiikikxxfxxf010)()(],...,[事实上其中,)()(01kiikxxxkijjjiikxxx01)()(差商的值与xi的顺序无关！差商性质/*Propertyofdivideddifference*/性质1010011()[,,...,]()()()()niniiiiiiinfxfxxxxxxxxxxx001()[,...,]()nininifxfxxx即其中10()(),nniixxx10()()nniijjjixxx证明：数学归纳法100101100110()()()()[,]fxfxfxfxfxxxxxxxxn=1n=2120101220[,][,][,,]fxxfxxfxxxxx012010210122021()()()()()()()()()fxfxfxxxxxxxxxxxxx120101220[,][,][,,]fxxfxxfxxxxx012120122101101()()()()()fxfxfxfxxxxxxxxxxx同理归纳，结论成立性质2差商具有对称性，即的值与节点的顺序无关。01[,,,]nfxxx