第4章 插值逼近

第四章插值方法三、Newton插值五、分段低次插值一、插值多项式及存在唯一性二、Lagrange插值四、Hermite插值本章要求•1．熟练掌握拉格朗日插值、牛顿插值的基本思想与误差估计；•2．掌握分段低次插值的概念算法；•3．掌握三次样条插值及其算法的计算机实现；•重点：多项式插值与误差估计、三次样条算法的计算机实现。插值问题的背景且不利于在计算机上其函数形式可能很复杂对函数,),(xf012...naxxxxb能否存在一个性能优良、便于计算的函数满足比如多项式函数),(xP()0,1,2,...,iiPxyin)()(xfxP近似代替并且用------(1)个不同的点上的一组在区间可以获得量假如可以通过实验或测运算1],[)(,,nbaxf(),0,1,2,...,iiyfxin上的函数值这就是插值问题,(1)式为插值条件,()()Pxfx称函数为函数的插值函数(),Px如果为多项式函数插则称之为值多项式,0,1,2,...,,ixin点称为插值节点[,]ab区间称为插值区间个等分点上若给定如函数5],0[,sinxy其插值函数的图象如图00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy)()(xPxf和插值函数对于被插函数处的函数值必然相等在节点ix)()(xfxP的值可能就会偏离但在节点外必然存在着误差近似代替因此)()(xfxP整体误差的大小反映了插值函数的好坏为了使插值函数更方便在计算机上运算,一般插值函数都使用代数多项式和有理函数本章讨论的就是代数插值多项式插值多项式存在唯一性定理.)()1(,,,21存在且唯一的插值多项式中，满足条件的多项式集合互异，则在次数不超过设节点xPHnxxxnnn证明：得代入将)1()(2210nnnxaxaxaaxP.,,101111000010nnnnnnnnnyxaxaayxaxaayxaxaa元线性方程组，的这是一个关于1,,,10naaan其系数行列式nnnnnnxxxxxxxxxV111),,,(110010是Vandermonde行列式,故niijjinxxxxxV11010)(),,,(.0于是方程组有唯一解，即满足(1)式的多项式存在且唯一。（一）线性插值给定两个点(x0，y0),(x1，y1),x0≠x1，确定一个一次多项式插值函数，简称线性插值。待定系数法设L1(x)=a0+a1x,代入插值点01000111aaxyaaxy当x0≠x1时，方程组的解存在唯一。即插值条件：L1(xi)=f(xi)=yi,i=0,1Lagrange插值就是选用节点上的函数值作为插值条件，选用代数多项式作为插值函数。Lagrange插值解之得，011001010101,.xyxyyyaaxxxx因此，0110011010101010110()xyxyyyLxxxxxxxxxxyyxxxx　　　　　　（2）式称为一次Lagrange插值。注：由求解过程知，用待定系数法，需要求解线性方程组，当已知节点较多时，即方程的未知数多，计算量较大，不便向高阶插值推广。------(2)插值基函数法分别构造两个节点上的一次函数，使其在本节点上的函数值为1，而在其他节点上的函数值为0。设l0(x),l1(x)分别为满足上述条件的一次函数，即00100111()1,()0()0,()1lxlxlxlx　　　或简单地记为1,,()0,.ijijijlxij　　　　　　对于过两个节点x0,x1的线性插值（2）式，令01010110(),()xxxxlxlxxxxx011010110()xxxxLxyyxxxx　　(2)显然，l0(x),l1(x)满足：线性插值函数可以写成节点上函数值的线性组合，即L1(x)=l0(x)y0+l1(x)y1．称l0(x),l1(x)分别为x0,x1的插值基函数。(),,0,1.ijijlxij　011010110()xxxxLxyyxxxx　　(2)满足插值条件：L1(xi)=yi,i=0,1线性插值的误差定理4.1.1设L1(x)为一次Lagrange插值函数,若f(x)一阶连续可导，f(x)在(a,b)上存在，则对任意给定的x∈(a,b),至少存在一点ζ∈(a,b),使得证明因为L(xi)=f(xi),i=0,1,所以，R1(x0)=R1(x1)=0,即x0,x1为R1(x)的两个根。因此，可设R1(x)为1101()()()()()()2!fRxfxLxxxxx101()()()()()(),tftLtkxtxtx固定任一x，作辅助函数，令R1(x)=k(x)(x-x0)(x-x1).则Ψ(xi)=0,i=0,1,Ψ(x)=0,即Ψ(t)有3个零点x0,x1,x假定，x0xx1,分别在[x0，x]和[x，x1]上应用洛尔(Rolle）定理，可知，Ψ′(t)在每个区间上至少存在一个零点，ζ1，ζ2，使Ψ′(ζ1)=0，Ψ′(ζ2)=0(此即Ψ′(t)有2个零点)。再利用洛尔定理知，Ψ′(t)在[ζ1,ζ2]上至少有一个零点ζ，使Ψ″(ζ)=0.对Ψ(t)求2阶导数得，Ψ″(t)=f″(t)-2!k(x),因为Ψ″(ζ)=0，所以，有k(x)=f″(ζ)/2!.证毕。给定3个互异插值点(xi,f(xi)),i=0,1,2，确定一个二次插值多项式函数，即抛物线插值（如图）。待定系数法设L2(x)=a0+a1x+a2x2,代入3个插值条件：L2(xi)=f(xi),i=0,1,2，解线性方程组可得a0,a1,a2.（二）二次插值插值基函数法构造3个节点上2次插值基函数l0(x),l1(x),l2(x),使满足li(xj)=δij，i,j=0,1,2。因为l0(x)为2次插值基函数,且l0(x1)=l0(x2)=0,所以可设l0(x)=A(x-x1)(x-x2)由条件：l0(x0)=1，得01021,()()Axxxx1200102()()().()()xxxxlxxxxx同理可得，02011210122021()()()()(),().()()()()xxxxxxxxlxlxxxxxxxxx　　二次Lagrange插值多项式为220011220()()()()()()()()()iiiLxlxfxlxfxlxfxlxfx容易验证满足插值条件二次插值的误差定理4.1.2设L2(x)为二次Lagrange插值函数,若f(x)∈C3[a，b],则任给x∈(a,b),至少存在一点ζ=ζ(x)∈(a,b),使22012()()()()()()()3!fRxfxLxxxxxxx提示：因为R2(x0)=R2(x1)=R2(x2)=0,可设2012()()()()().Rxkxxxxxxx作辅助函数2012()()()()()()(),tftLtkxtxtxtx易知，x0,x1,x2,x为Ψ(t)的4个零点，在4个点两两组成的区间上，应用Rolle定理，然后再反复应用Rolle定理即得证。例4.1.1给定sin11°=0.190809,sin12°=0.207912,求线性插值，并计算sin11°30'和sin10°30'。解x0=11°,x1=12°,y0=0.190809,y1=0.207912，10101(12)(11)()(12)(11).11121211xxLxyyxyxysin11°30'≈L1(11.5)=0.199361,sin10°30'≈L1(10.5)=0.182258准确值为：sin11°30’=0.199368sin10°30’=0.182236由定理知，误差为101()sin()()()()(11)(12).2!2fRxxxxxxx11()(11)(12)21(11.511)(11.512)0.125.2Rxxx　　　　　　01111211.522xxx例4.1.2给定sin11°=0.190809,sin12°=0.207912,sin13°=0.224951,构造二次插值，并计算sin11°30′。解x0=11,x1=12,x2=13,y0=0.190809,y1=0.207912,y2=0.224951，2(12)(13)(11)(13)()0.1908090.207912(1112)(1113)(1211)(1213)(11)(12)0.224951(1312)(1312)xxxxLxxx　　　sin11°30′≈L2(11.5)=0.199369,sin11°30′=0.199368.例4.1.3要制作三角函数sinx的值表，已知表值有四位小数，要求用线性插值引起的截断误差不超过表值的舍入误差，试确定其最大允许的步长。解f(x)=sinx,设xi-1,xi为任意两个插值节点，最大允许步长记为h=hi=xi－xi-1，111111121124()sin()()()()()2!211()()()()22221()(),88110,0.02.82iiiiiiiiiiiiiiiifRxxxxxxxxxxxxxxxxxxxhxxxxhh　　　　　　　　　　　　（三）n次插值已知n+1个互异插值节点(xi,f(xi)),i=0,1,2,…,n,研究n次插值多项式的存在性及其表示形式。存在性：待定系数法设n次多项式为2012()...,nnnLxaaxaxax------(3)代入插值点，即插值条件：Ln(xi)=f(xi),i=0,1,2,…,n,得20102000201121112012...()...().........()nnnnnnnnnnaaxaxaxfxaaxaxaxfxaaxaxaxfx　------(4)其范德蒙德(Vandermonde)行列式为：2000211101201...1...(,,...,).........1...()0,nnnnnnnijjinxxxxxxVxxxxxxxx　　　　　　　所以，(4)的解存在唯一。解出(4)的解a0,a1,…,an，代入(3)即得n次插值多项式Ln(x)。n次插值多项式的构造：插值基函数法虽然方程组(4)的解存在唯一，但用待定系数法求插值多项式却不是好方法，其计算量大，实际中不可取。维的间是的多项式构成的线性空所有次数不超过1nn根据线性空间的理论个多项式组成维线性空间的基底也由这个11nn并且形式不是唯一的表示次多项式可由基底线性而任意一个n且在不同的基底下有不同的形式01(),(),...,()1nlxlxlxn设为上述维线性空间的一组基底01(),(),...,()nlxlxlx显然线性无关01()(),(),...,()nnnLxlxlxlx且任意次多项式可由线性表示0011()()()...()nnnLxclxclxclx分别构造x0,x1,…,xn上的n次插值基函数l0(x),l1(x),…,ln(x),满足性质：1,0,1,2,...,()0ijijijnlx