西工大计算方法4

第四章函数插值§4.1引言§4.2Lagrange插值§4.3Newton插值§4.4等距节点插值§4.5Hermite插值§4.6分段插值§4.7三次样条插值1函数表达式过于复杂不便于计算,而又需要计算许多点处的函数值2仅有几个采样点处的函数值,而又需要知道非采样点处的函数值……上述问题的一种解决思路：建立复杂函数或者未知函数的一个便于计算的近似表达式.解决方法－插值法§4.1引言一、问题提出已知定义于],[ba上的函数)(xf在1n个互异节点],[0baxnii处的函数值niixf0)(。若函数族中的函数)(x满足条件nixfxii,,1,0),()(（1）则称)(x为)(xf在中关于节点niix0的一个插值函数。)(xf——被插值函数；],[ba——插值区间；niix0——插值节点；式（1）——插值条件.二、插值问题定义求插值函数(x)的问题称为插值问题。三、几何意义、内插法、外插法内插外插niixM0}max{~niixm0}min{~]~,~[Mmx]~,~[],[Mmxbutbax四、多项式插值问题对于不同的函数族Φ的选择，得到不同的插值问题–当Φ为一些三角函数的多项式集合时:三角插值;–当Φ为一些有理分式集合时：有理插值；–当Φ为一些多项式集合时：多项式插值（代数插值）特别的取=nnxxx,,,,1span2P,即niRaxaxaxaaxxinnn0,,)()(2210P五、插值多项式的存在唯一性分析对于多项式插值问题，插值条件（1）等价于确定多项式的系数，使得满足如下的线性方程组)()()()(111210210212110200nnnnnnnnxfxfxfxfaaaaxxxxxxxxx•定理4.1(存在唯一性)满足插值条件(1)的不超过n次的插值多项式是存在唯一的。定理证明：多项式插值问题满足的线性方程组是关于多项式的系数a0，a1，a2，…，an的n＋1阶线性方程组，其系数矩阵的行列式Vn(x0,x1,…,xn)称为范德蒙(Vandermonde)行列式。利用行列式的性质可以求得nijjinnxxxxxV010)(),,,(由于假设ij时，xixj，故所有因子xi-xj0，于是Vn(x0,x1,…,xn)0。因此方程组的解存在且唯一，从而插值多项式是存在唯一的。证毕六、插值余项引理已知函数f(x)在[a,b]上具有m-1阶连续导函数，且在（a,b）上存在m阶导数。若它在该区间上有m+1个零点，则它的m阶导函数在(a,b)内至少存在一个零点。)()()()()(23012101210xfxfxfxxxxxxfmmmmmmm插值余项：)()()(xxfxRn定理4.2(误差估计)设)()(xfn在],[ba上连续,)()1(xfn在),(ba内存在.)(x是满足插值条件(1)的不超过n次的插值多项式.则对任意],[bax,存在),()(bax,使得)()!1()()()()(1)1(xnfxxfxRnnn成立,式中)()(01ininxxx.进而当)()1(xfn在区间),(ba有上界1nM时,有)(!)1()(11xnMxRnnn.分析：nixxfxRiii,,2,1,0,0)()()()())(()()()()()()(1011nnnxxxxxxxxxkxxfxR)()()()()(1txkttftgn当x为某一插值节点时,对函数)(xk无约束；当点x与插值节点niix0}{互不相同时，构造以t为新自变量的函数)(tg在区间],[ba上的2n个互异零点：x、niix0}{当)(tg充分光滑时，)()1(tgn在开区间),(ba内至少存在一个零点ξ)!1()()(0)()()!1()()()1()1()1()1(nfxkgxkntftgnnnnRemark1插值误差与节点niix0和点x之间的距离有关,节点距离x越近,插值误差一般情况下越小。Remark2若被插值函数)(xf本身就是不超过n次的多项式,则有)()(xxf。Remark3可以通过求解线性方程组得到插值多项式。七、插值方法由于插值多项式的存在唯一性，无论是用何种方法构造出的插值多项式，它们均恒等，进而截断误差也都相同。本章我们要讨论的插值方法有：Lagrange插值法Newton插值法等距节点插值公式带导数的插值问题线性插值x0x1(x0,y0)(x1,y1)P1(x)f(x)可见P1(x)是过(x0,y0)和(x1,y1)两点的直线。)(001010xxxxyyyy直线方程为:§4.2Lagrange插值等价变形为:10100101yxxxxyxxxxy记为:)(1xL一、插值基函数引入记号:,)(1010xxxxxl0101)(xxxxxl则:11001)()()(yxlyxlxL分析两个基函数有:0)(1)(1000xlxl1011()0()1lxlx对于三个点,类似有:2211002)()()()(yxlyxlyxlxL称为插值基函数0)(0)(1)(201000xlxlxl0)(1)(0)(211101xlxlxl1)(0)(0)(221202xlxlxlx0x1x2p2(x)f(x)f(x)二次插值将以上思路推广到n+1个节点情形，即可得到类似的插值基函数和插值多项式表示形式。1.插值基函数定义：若n次多项式lk(x)(k=0,1,…,n)在n+1个插值节点x0x1…xn上满足插值条件：),,1,0,()(0)(1)(nkikikixlikik则称这n＋1个n次多项式l0(x),l1(x),…,ln(x)为插值节点x0,x1,…,xn上的n次插值基函数。Remark：容易验证，n次插值基函数的线性组合在插值节点x0,x1,…,xn上满足插值条件，从而可以利用插值基函数来构造插值多项式。),,1,0()())(())(()())(())(()(11101110nkxxxxxxxxxxxxxxxxxxxxxlnkkkkkkknkkk)()()()('11knknkxxxxxl2.插值基函数的构造由于ik时，lk(xi)=0，故x0,x1,…,xk-1,xk+1,…,xn为lk(x)的零点，从而可以设)())(())(()(1110nkkkkxxxxxxxxxxAxl由lk(xk)＝1可得)())(())((11110nkkkkkkkkxxxxxxxxxxA故若记，则有，从而niinxxx01)()(nkiiikknxxx,01)()(二、Lagrange型插值公式niinininiiinxxxxxfxlxfxL0'110)()()()()()()(上式是不超过n次的多项式，且满足所有的插值条件，因而就是我们所需构造的插值多项式，称之为Lagrange插值多项式。当n＝1时，有101001011)(yxxxxyxxxxxL当n＝2时，有2120210121012002010212))(())(())(())(())(())(()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxL)()!1()()()()(1)1(xnfxLxfxRnnnn三、Lagrange插值多项式的余项设f(x)为定义在[a,b]上的被插值函数，Ln(x)为f(x)的n次Lagrange插值多项式，其插值余项为：Rn(x)=f(x)-Ln(x)定理：如果f(n)(x)在区间[a,b]上连续，f(n＋1)(x)在(a,b)内存在，Ln(x)为在节点ax0x1…xnb上满足插值条件的n次Lagrange插值多项式，则对任一x(a,b),其插值余项为：其中(a,b)且依赖于x。上式给出的余项通常称为Lagrange型余项。)(max)!1()()()(11xnMxLxfxRnbxannnRemark一般情况下，余项表达式中的(a,b)的具体数值无法知道。但是，如果能够求出，则可以得出插值多项式的截断误差限为：1)1()(maxnnbxaMxf由此可以看出，误差大小除了与Mn+1有关外，还与插值节点有密切关系。当给定m个点处的函数值，但仅选用其中n＋1（n＋1m）个作为插值条件而求某个点处函数值时，n＋1个节点的选取应尽可能接近，以使使得所计算的函数值的误差限尽可能小。xx例题已知3)5.0(,2)0(,1)1(,2)2(ffff,试选用合适的插值节点，通过二次插值多项式计算)5.0(f的近似值,使之精度尽可能高。解依据误差估计式,选5.0,0,1210xxx为插值节点拉格朗日插值基函数为:)5.0(32)5.01)(01()5.0)(0()(0xxxxxl)5.0)(1(2)5.00)(10()5.0)(1()(1xxxxxl)1(34)05.0)(15.0()0)(1()(2xxxxxl二次插值多项式为)()()()()()()(2211002xlxfxlxfxlxfxL)(3)(2)(210xlxlxl3/4)5.0(3)5.0(2)5.0(1)5.0()5.0(2102lllLf#四、反插值法已知单调连续函数)(xfy在如下采样点处的函数值ix1.01.41.82.0)(iixfy-2.0-0.80.41.2求方程0)(xf在]2,1[内根的近似值*x,使误差尽可能小iy2.00.80.41.20iixyf)(11.01.41.82.0？分析问题求解))()(())()(()()(302010321013yyyyyyyyyyyyyfyL))()(())()(()(31210132011yyyyyyyyyyyyyf))()(())()(()(32120231021yyyyyyyyyyyyyf))()(())()(()(23130321031yyyyyyyyyyyyyf3201302.003125.03271.0675.1yyy于是有675.1)0()0(31*Lfx解对)(xfy的反函数)(1yfx进行三次插值,插值多项式为#Lagrange插值公式的特点：–形式对称–通常用于理论分析–当增加插值节点时，在计算实践中不方便§4.3Newton插值问题：想要构造一个更加方便灵活的插值格式，当增加插值节点时，只需在原有格式的基础上再增加一些即可。解决方法：Newton插值（考虑多项式之间的关系）Lagrange插值多项式间的关系10)()(0)()(1kixfxLkixfxLiikiik)()(1xLxLkk)())((110kxxxxxxA)())(())(()())(())(()()()()(111011100kiiiiiiikiiikiiikxxxxxxxxxxxxxxxxxxxxxlxlxfxL)())(()()(1100kiiiiiiikixxxxxxxxxfA