计算方法―插值法

2020/3/221第二章插值法（Interpolation）2.1引言2.2拉格朗日插值2.3均差与牛顿插值公式2.5分段低次插值2.6三次样条插值2.4埃尔米特插值Chapter2插值法2020/3/222Chapter2插值法表示两个变量x,y内在关系一般由函数式y=f(x)表达。但在实际问题中的函数是多种多样的,有下面两种情况：（1）由实验观测而得的一组离散数据(函数表)，显然这种函数关系式y=f(x)存在且连续，但未知。（2）函数解析表达式已知，但计算复杂，不便使用。通常也列函数表，如y=sin(x),y=lg(x)2.1引言2020/3/223办法是：根据所给的y=f(x)的函数表，构造一个简单的连续函数P(X)近似替代f(x)。Chapter2插值法2.1引言近似代替即逼近的方法有很多种：插值方法、最佳一致逼近、最佳平方逼近、曲线拟合。由于问题的复杂性,直接研究函数f(x)可能很困难,但为了研究函数的变化规律,有时要求不在表上的函数值，怎么办？简单连续函数P(x)指可用四则运算计算的函数:如有理函数(分式函数),多项式或分段多项式。2020/3/224Chapter2插值法2.1引言插值问题的数学提法：已知函数y=f(x)在n+1个点x0,x1,…,xn上的函数值yi=f(xi)(i=0,1,…,n)，求一个简单函数y=P(x)，使其满足P(xi)=yi,（i=0,1,…,n）。即要求该简单函数曲线要经过y=f(x)上已知的这n+1个点(x0,y0),(x1,y1),…,(xn,yn),同时在其它x∈[a,b]上要估计误差R(x)=f(x)-P(x)。2020/3/225Chapter2插值法2.1引言重要术语对于n+1个基点的插值问题，我们称：f(x)为被插值函数；P(x)为插值函数；x0,x1,…,xn为插值基点或插值节点；P(xk)=f(xk),k=0,1,…,n为插值条件；[a,b]为插值区间。注释：对于早期的插值问题来说，f(x)通常是已知的，比如对数函数，指数函数，三角函数等，这些问题现在已经不用插值法来计算了；对于现在的许多实际问题来说，我们并不知道f(x)的具体形式，所对应的函数值可能是由测量仪器或其他物理设备中直接读出来的，f(x)只是一个概念中的函数。2020/3/226Chapter2插值法2.1引言多项式插值对于n+1个基点的插值问题，如果要求插值函数是次数不超过n的多项式，记为Pn(x)，则相应的问题就是多项式插值，并且把Pn(x)称为插值多项式。实际上，我们所考虑的插值函数通常都是多项式函数或分段多项式函数。由于次数不超过n的多项式的一般形式为：Pn(x)=a0+a1x+a2x2+…+anxn所以只要确定了n+1个系数a0，a1，…，a2，an，我们便确定了一个插值多项式。2020/3/227Chapter2插值法yx2.1引言x0x1x2…xn-1xny0y1y2)(xf)(xP多项式插值的几何意义：多项式Pn(x)，其几何曲线过给定的y=f(x)的n+1个点(xi,yi)i=0,1,2,…,n。ynyn-12020/3/228Chapter2插值法2.2拉格朗日插值2020/3/229Chapter2插值法2.2拉格朗日插值2-1插值多项式的唯一性已知y=f(x)的函数表，且xi(i=0,1,…,n)两两互异，xi∈[a,b]。求次数不超过n的多项式使得Pn(xi)=yi,i=0,1,2…,n此问题中Pn(x)是否存在？存在是否唯一？如何求？显然关键是确定多项式Pn(x)的系数a0,a1,…,an。2020/3/2210Chapter2插值法2.2拉格朗日插值2-1插值多项式的唯一性定理：在n+1个互异的插值节点x0,x1,…,xn上满足插值条件Pn(xi)=yi,i=0,1,2…,n的次数不超过n的代数多项式Pn(x)存在且唯一。分析：为求主要考虑插值条件2020/3/2211Chapter2插值法2.2拉格朗日插值2-1插值多项式的唯一性证明：由插值条件，有nnnnnnnnnnnnnnyxaxaxaaxPyxaxaxaaxPyxaxaxaaxP2210112121101002020100)()()(其系数矩阵的行列式为0)(),,,(11110110212110200jiijninnnnnnnnxxxxxVxxxxxxxxx),jixxji（关于未知量a0,a1,…,an的非齐次线性方程组01,,,naaa方程组的解存在且唯一插值多项式存在且唯一。2020/3/2212Chapter2插值法2.2拉格朗日插值例给定f(x)的函数表，求f(x)的次数不超过3的插值多项式。x-1125y-77-435解：设3322103)(xaxaxaaxP则，3547712525518421111111113210aaaa解方程组得a0=10,a1=5,a2=-10,a3=2即P3(x)=10+5x-10x2+2x3当n=20,在109次/秒的计算机上计算需几万年！2020/3/2213Chapter2插值法2.2拉格朗日插值2-2线性插值与抛物插值问题的提法：已知函数y=f(x)的函数表求次数不超过1的多项式L1(x)=a0+a1x满足插值条件L1(xk)=yk,L1(xk+1)=yk+1。xxkxk+1yykyk+1分析:过两点(xk,yk),(xk+1,yk+1)作直线y=L1(x)——线性插值解:由点斜式方程kkkkkkkkkkkkkkkyxxxxyxxxxyxLyxxxxyyyy111111)()(111()()1111()()kkkkkkkiiikkkklxxklxxxxLxyylxyxxxx1111()()kkkkkkkkxxxxlxlxxxxx称为线性插值基函数,而L1(x)是它们的线性组合。1111()1()0()0()1()()1kkkkkkkkkklxlxlxlxlxlx2020/3/2214Chapter2插值法2.2拉格朗日插值L1(X)L1(X)∴lg2.718≈L1(2.718)=0.434282020/3/22152.2拉格朗日插值Chapter2插值法2-2线性插值与抛物插值利用线性插值法对函数y=f(x)进行逼近时，即用直线y=L1(x)代替曲线y=f(x)。显然当插值区间较大或曲线[x0,x1]凸凹变化大时，线性插值的误差很大。为了减小这种误差，我们用简单的曲线(抛物线)去近似代替复杂曲线y=f(x)。二次多项式函数的曲线为抛物线，所以我们构造插值函数L2(x)，即n=2。2020/3/22162.2拉格朗日插值Chapter2插值法问题的提法：已知y=f(x)的函数表，x0,x1,x2为互异节点，求一个次数不超过2的多项式L2(x)=a0+a1x+a2x2：L2(x0)=y0,L2(x1)=y1,L2(x2)=y2xx0x1x2yy0y1y2几何意义:L2(x)为过三点(x0,y0),(x1,y1),(x2,y2)的抛物线。方法：基函数法，构造基函数l0(x),l1(x),l2(x)(三个二次式)使L2(x)=y0l0(x)+y1l1(x)+y2l2(x)满足插值条件。000102101112202122()1()0()0()0()1()0()0()0()1lxlxlxlxlxlxlxlxlx1()(,0,1,2)0ijijlxijij2020/3/22172.2拉格朗日插值Chapter2插值法求二次多项式l0(x)：l0(x0)=1,l0(x1)=0,l0(x2)=0=l0(x)=C(x-x1)(x-x2)只须求C=?由l0(x0)=1得C(x0-x1)(x0-x2)=1∴C=1/(x0-x1)(x0-x2)1200102()()()()()xxxxlxxxxx同理求得l1(x),l2(x),即抛物插值的插值基函数如下:020112012010210122021()()()()()()(),(),()()()()()()()xxxxxxxxxxxxlxlxlxxxxxxxxxxxxx抛物插值问题的解:0201122012010210122021()()()()()()()()()()()()()xxxxxxxxxxxxLXyyyxxxxxxxxxxxx2020/3/22182.2拉格朗日插值Chapter2插值法2-3拉格朗日插值多项式已知y=f(x)在两两互异节点x0,x1,…,xn的函数值y1,y2,…,yn,求n次多项式Ln(x)=a0+a1x+a2x2+…+anxn,满足插值条件Ln(xi)=yi.i=0,1,2,3,…,n。基函数法：求n+1个n次多项式l0(x),l1(x),…,ln(x)使Ln(x)=y0l0(x)+y1l1(x)+…+ynln(x)。Ln(x)须满足插值条件Ln(xi)=yii=0,1,2,3,…,n即y0l0(xi)+y1l1(xi)+…+yili(xi)…+ynln(xi)=yi1()0ijijijlxij为此，只需这组基函数满足：2020/3/22192.2拉格朗日插值Chapter2插值法∵li(x0)=0,…,li(xi-1)=0,li(xi+1)=0,…,li(xn)=0即li(x)有n个零点，x0,x1,…,xk-1,xk+1,…,xn。011()()()()()iiinlxcxxxxxxxx011011()1()()()()11/()()()()iiiiiiiiniiiiiinlxcxxxxxxxxcxxxxxxxx又011011()()()()()()()()()iiniiiiiiinxxxxxxxxlxxxxxxxxx求插值基函数li(x)与节点有关，而与f无关2020/3/22202.2拉格朗日插值Chapter2插值法于是，满足插值条件Ln(xi)=yi.i=0,1,2,3,…,n的插值多项式为：0,00()()nnnjniiijijiiijxxLxylxyxx上式即为拉格朗日（Lagrange）插值多项式。当n=1，或n=2时分别就是线形插值与抛物插值公式。01(),()()nlxlxlx为拉格朗日插值基函数。1011()()()()()nnnxxxxxxxxH记()()|lim()iixixxiixxxxxxx则()1()()iiixlxxxx基函数的等价形式2020/3/22212.2拉格朗日插值Chapter2插值法2-4插值余项函数y=f(x)与其Lagrange插值多项式Ln(x)：(1)Ln(xi)=f(xi)=yi,i=0,1,2,…,n；(2)而对于插值区间[a,b]内插值节点xi(i=1,2,…,n)以外的点x,一般Ln(x)≠f(x)，存在误差。Def:对于一般的n+1个基点的多项式插值问题，设f(x)为被插值函数,Ln(x)为相应的插值多项式,记Rn(x)为f(x)与Ln(x)的差,即Rn(x)=f(x)-Ln(x)则Rn(x)就是用Ln(x)近似替代f(x)的误差,我们称它为插值余项。显然，由插值多项式的唯一性可以导出插值余项的唯一性。2020/3/22222.2拉格朗日插值Chapter2插值法利用Lagrange插值公式Ln(x)来计算，结果是否可靠，要看余项Rn(x)是否足够小。Rn(x)=？设a≤x0x1…xn≤b，且满足条件f∈cn[a,b],f(n+1)在[a,b]内存在,考察