《计算方法》第四章插值方法

1计算方法华中科技大学数学与统计学院第四章插值方法计算方法课程组2§4插值方法§4.1多项式插值问题的一般提法§4.2拉格朗日(Lagrange)插值§4.3差商与差分及其性质§4.4牛顿插值公式§4.5分段插值法§4.6曲线拟合的最小二乘法3§4.0引言插值法是广泛应用于理论研究和生产实践的重要数值方法,它是用简单函数(特别是多项式或分段多项式)为各种离散数组建立连续模型；为各种非有理函数提供好的逼近方法。众所周知，反映自然规律的数量关系的函数有三种表示方法：•解析表达式52)(3xxxfyyxsin•图象法•表格法4§4.0引言许多数据都是用表格法给出的(如观测和实验而得到的函数数据表格)，可是，从一个只提供离散的函数值去进行理论分析和进行设计，是极不方便的,甚至是不可能的。因此需要设法去寻找与已知函数值相符，并且形式简单的插值函数(或近似函数)。另外一种情况是，函数表达式完全给定，但其形式不适宜计算机使用，因为计算机只能执行算术和逻辑操作，因此涉及连续变量问题的计算都需要经过离散化以后才能进行。如数值积分方法、数值微分方法、差分方程以及有限元法等，都必须直接或间接地应用到插值理论和方法。5§4.1多项式插值问题的一般提法当精确函数y=f(x)非常复杂或未知时，在一系列节点x0…xn处测得函数值y0=f(x0),…,yn=f(xn)，由此构造一个简单易算的近似函数p(x)f(x)，满足条件:p(xi)=f(xi)(i=0,…n)。这里的p(x)称为f(x)的插值函数。最常用的插值函数是…?代数多项式、三角多项式、有理分式…6插值函数p(x)作为f(x)的近似，可以选自不同类型的函数,如p(x)为代数多项式、三角多项式、有理分式；其函数性态可以是光滑的、亦可以是分段光滑的。其中，代数多项式类的插值函数占有重要地位：(a)结构简单、计算机容易处理、任何多项式的导数和积分也易确定，并且仍是多项式。(b)著名的Weierstrass逼近定理(定义在闭区间上的任何连续函数f(x),存在代数多项式p(x)一致逼近f(x),并达到所要求的精度)。因此，我们主要考虑代数多项式的插值问题。7x0,x1,…,xn插值节点,函数P(x)称为函数y=f(x)的插值函数，区间[a,b]称为插值区间。8例题:已知函数f(x)有如下数据:求f(x)的插值多项式p(x)，并求f(x)在x=0.5处的近似值。910插值的几何意义从几何上看，插值就是求一条曲线使其通过给定的个点，并且与已知曲线有一定的近似度。()yPx1n(,)iixy(0,1,,)in()yfxx0yy=p(x)a=x0x1x2x3xn=b•(xi,yi)y=f(x)曲线P(x)近似f(x)11插值方法的研究问题（1）满足插值条件的P(x)是否存在唯一？（2）若满足插值条件的P(x)存在，如何构造P(x)？（3）如何估计用P(x)近似替代f(x)产生的误差？x0yy=p(x)a=x0x1x2x3xn=b•(xi,yi)y=f(x)曲线P(x)近似f(x)12求n次多项式使得:nnnxaxaaxP10)(条件：无重合节点，即jixxji§4.2拉格朗日多项式/*LagrangePolynomial*/根据插值条件，有：nnnnnnnnnnyxaxaaxPyxaxaaxPyxaxaaxP10111101000100)()()(其系数矩阵的行列式为nnnnnnnxxxxxxxxxV111),,,(110010(),0,1,,niipxyinVandermonde行列式13),,2,1(nixi0)(),,,(010nijjinnxxxxxVnaaa,,10注意到插值节点两两相异，而故方程组(1)有惟一解于是满足插值条件的多项式存在且惟一。nxxx,,,10nnnxaxaaxP10)(iinyxP)(由n+1个不同插值节点可以惟一确定一个n次多项式满足插值条件(唯一性)Return14n=1已知x0,x1;y0,y1，求101()Lxaax=+使得111001)(,)(y1x1Ly0x0L可见L1(x)是过(x0,y0)和(x1,y1)两点的直线。l0(x)l1(x)§4.2拉格朗日多项式/*LagrangePolynomial*/线性插值基函数1.构造线性插值基函数的方法:iiiyxlyxxxxyxxxxxxxxyyyxL)()()(1010100101001010115线性插值与其基函数示意图xy00()yylx11()yylx0x1xO10011()()()Lxylxylx0x1xxy0y1y()yfx1()yLxO16显然,是过、、三点的一条抛物线。),(11yx),(22yx已知,求，n=2)(2xL使得200211222()()()LxyLxyLxy===2()Lx00(,)xy210210,,,,yyyxxx17显然,是过、、三点的一条抛物线。),(11yx),(22yx已知,求，n=2210210,,,,yyyxxx)(2xL使得200211222()()()LxyLxyLxy===仿照线性插值基函数的构造方法，令))(())(()())(())(()())(())(()(120210221012012010210xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl抛物线基函数2()Lx称其为抛物线插值基函数(如上右图所示)。2()Lx00(,)xy18))(())(()())(())(()())(())(()(120210221012012010210xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl抛物线插值基函数于是抛物线基函数020112201201021012202120()()()()()()()()()()()()()()iiixxxxxxxxxxxxLxyyyxxxxxxxxxxxxlxy=------=++------=å19希望找到li(x)，i=0,…,n使得li(xj)=ij；然后令，则显然有Pn(xi)=yi。每个li有n个根x0,…xi,…xn一般情形)()()()()()()()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl，k=0,1,⋯,n.,)()()()()(110nkkkxxxxxxxxAxl令k=0,1,⋯,n.0111()()()()knkkkkkAxxxxxxxx()1,kklx由得:0(()()）nnkkkLxfxlx0(()()）nnkkkLxfxlx20设函数表则满足插值条件的多项式（Lagrange）插值多项式nkkknxlxfxL0)()((）()yfx,,,(,(,())(01...)),ijiixxxfxinij()()(0,1...)，niiLxfxin其中,.0()(0,1,...)njkjkjjkxxlxknxx21以下的问题：如何分析插值的余项？(1)先求插值基函数.(2)构造插值多项式.构造插值多项式的方法：22x-1012f(x)-2-212已知连续函数f(x)的函数表如下：求方程f(x)=0在(-1,2)内的近似根。例题23解：利用Lagrange插值法有取初值x=0.5，利用牛顿法求解可得f(x)在(-1,2)内的近似根为0.67433。325914120xxx解方程x-1012f(x)-2-212已知连续函数f(x)的函数表如下：求方程f(x)=0在(-1,2)内的近似根。例题301211222101112010102121112211212021xxxxxxLxxxxxxx()()()()()()()()()()()()()()()()()()()()()()()---+--=-+-------+--+-+-+???+--3215914126xxx[]=-++-24，且f满足条件,Lagrange插值法插值余项设节点)1(nf在[a,b]内存在,考察截断误差:)()()(xLxfxRnn],[baCfnbxxxan1025Lagrange插值法的插值余项，且f满足条件,设节点)1(nf在[a,b]内存在,截断误差(或插值余项):],[baCfnbxxxan10(1)1()()()()()(1)!nnnnfRxfxLxxn,(,)ab26Lagrange插值法的插值余项，且f满足条件,设节点)1(nf在[a,b]内存在,截断误差(或插值余项):],[baCfnbxxxan10(1)1()()()()()(1)!nnnnfRxfxLxxn,(,)ab证明：由已知条件得到：()0,0,1,,nkRxkn于是有：011()()()()()()()nnnRxkxxxxxxxkxx其中是与x有关的待定函数。()kx27任意固定xxi(i=0,…,n),考察01()()()()()()()nntftLtkxtxtxtx根据插值条件及余项定义，可知()t在点01,,,,nxxxx故处均为零，在()t[,]ab上有n+2个个零点，根据Roll定理在的每两个零点间至少有一个零点，故在内至少有一个零点，对再用Roll定理，可知在内至少有n个零点，依此类推，在内至少有一个零点，记为()t()t()t[,]ab()t()t[,]ab(1)()nt[,]ab(,)ab使得:(1)(1)()()(1)!()0nnfnkx(1)()(),(,)(1)!nfkxabn28由于是不能确定，因此我们并不能确定误差的大小但如能求出，那么用逼近的截断误差限是：当时，当时()nLx()fx1n12010111()''()()''()()(),[,]22Rxfxfxxxxxx2n230120211()'''()()'''()()()(),66[,]Rxfxfxxxxxxxx(1)1()nnaxbmaxfxM11()()(1)!nnnMRxxn29当f(x)为任一个次数n的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。0)()1(xfn0)(xRn注意30给定xi=i+1,i=0,1,2,3,4,5.下面哪个是l2(x)的图像？问题31算例1Lagrange插值法已知，，用线性插值及抛物线插值计算的值并估计截断误差。sin0.320.314567sin0.340.333487sin0.360.352274sin0.336732算例1Lagrange插值法已知，，用线性插值及抛物线插值计算的值并估计截断误差。sin0.320.314567sin0.340.333487sin0.360.352274sin0.33670120.320.340.36xxx0120.3145670.3334870.352274yyy线性插值时取解:010.32,0.34xx1sin0.3367(0.3367)0.33670.320.33670.340.3145670.3334870.340.320.320.340.330365L33其截断误差为：其中,因为可取于是：2101()()(),2MRxxxxx012max''()xxxMf()sin,''()sinfxxfxx0121maxsinsin0.3335xxxMxx115sin0.3367(0.3367)