研究生数值分析PPT7.ppt

第四章插值法（interpolation）,4.1问题提出,对原函数，其本身表达式过于复杂，我们只知道有限个点的函数值,需要寻找一个简单的函数近似地表示原函数，且满足这些给定的数值点。,4.1.1插值概念,定义：设函数f(x)在区间a,b上有意义,且已知,的值为,若存在一个简单,(1),成立，则称为f(x)的插值函数。其中为插值节点，a,b为插值区间，f(x)为被插值函数，式(1)为插值条件.,函数,使得,几何意义：用线性、抛物线等简单函数近似表示原函数。,插值函数类的选取:代数多项式(多次式插值)，三角多项式，有理多项式等,最简单的插值多项式:,使得:,有n+1个未知数，n+1个方程求解。,4.1.2插值多项式的存在唯一性,求未知数：,其系数行列式为,范德蒙行列式(Vandermonde),例如n=2时，,有唯一解。,利用,(克莱姆法则求解),特殊情况：,n=0时，即过一点可知,插值函数为过,的直线.,n=1时,即为过两点的直线。,4.2拉格朗日插值（Lagrange）,使用线性方程组求系数构造插值公式相对复杂，可改用构造方法来插值。,对节点,中任一点,作一n次多项式,，使它在该点上取值为1，,上为0，即,则插值多项式为:,而在其余点,构造过程：,上式表明：n个点,都是,其中为待定系数。,(i=k时),n次拉格朗日插值多项式为：,的零点。,常用的拉格朗日插值多项式：,n=1时，称为线性插值，,n=2时，称为二次插值或抛物线插值，,例题：已知,用线性插值,的近似值。,和抛物线插值计算,解：首先是线性插值：,节点为:,抛物线插值：,精确值为,抛物线精度相对高些.,4.3插值余项,区间a,b上使用插值多项式,近似f(x),节点,上没有误差，其它点上一般存在误差，记,称,为,近似代替,的截断误差，也称为,的插值余项.,可由下面定理来估计,定理：设f(x)在区间a,b上有直到n+1阶导数，,为互不相同的节点，为满足,的n次插值,其中,，且与x有关。,除了在,多项式，则对任何有:,证明：考虑插值节点上有,这些节点是的零点,可设,其中,为待定函数（与x有关），需确定.,对分析知：,当时，式左边=右边=0，此时,可为任意函数。,当时，,为,为了计算，引入辅导函数(并且变量用t表示),可使式成立.,可知至少有n+2个零点：.,由罗尔定理知:,在的两个相邻零点间至少有一个零点。,至少有n+1个零点，以此类推，,至少有一个零点,，即,对关于t求n+1阶导数：,(为n次多项式），,因为,所以,注意：,，即使得,2.该定理中，当f(x)具有（n+1）阶导数才可使用且在求误差时，利用,求得，即,例：前面例子中，求线性插值和抛物线插值在处的误差限。,1.若f(x)本身为不超过n次多项式，则一定可构造出,即,解：,线性插值：,抛物线插值：,4.4带导数插值条件的插值,利用拉格朗日插值和待定系数法求导数插值条件的插值，一阶导数在几何图形中具有几何意义，（例如参数曲线中的切矢量，包括切线方向和模长）,如何构造，通过下例说明：,例：已知节点上函数值,和处的导数值,构造一个次数不超过3的多项式,要求满足：,且,解：对,三节点，可先构造二次拉格朗日插值,令,其中为不超过3次的多项式,因为,是和,的零点,即,也是的3个零点,可设,A为待定系数,（1）,通过计算知，,且,利用(1)式可求出A,从而得到,所以,注意：（1）也可直接设,A为待定系数，利用导数条件,，求出A，,一般情况下也有可能为二次多项式，,原来方法更加准确。,（2）求余项:R(x)=f(x)P3(x),易知:x0,x2是R(x)的一重零点，x1为R(x)的二重零点,R(x)可写为,R(x)=K(x)(xx0)(xx1)2(xx2),其中K(x)待定函数,可知：当x=x0,x1,x2时，K(x)可取任意数，式都成立（此时左=右=0）,但求出的通常为3次多项式或为0，,当xx0,x1,x2时，,引入辅助函数,K(x)(xx0)(xx1)2(xx2),可知,在插值区间内有5个零点：,x0,x1(二重),x2,x,反复应用罗尔定理知：,在区间内至少有一个零点，,(),插值余项为R(x)=,在插值区间内与x有关.,所以,若K(x)为R(x)/(xx0)(xx1)2(xx2)式也成立。,记为,4.5埃尔米特插值（Hermite）,有时插值函数不仅要求在节点上与原函数相同，还要求其导数的值与原函数的值相同，即要求,H2n1(xi)=f(xi)，H2n1(xi)=f(xi),i=0、1、n,H2n1(x)为次数不超过2n1的插值多项式,该问题即为埃尔米特插值.这里只讨论如何构造三次Hermite插值.,4.5.1Hermite插值,问题：在x0,x1上寻找一个次数不多于3的多项式H(x)，满足,H(x0)=f(x0);H(x0)=f(x0);,H(x1)=f(x1);H(x1)=f(x1),(1),根据条件可知：,具体构造：,可设,由第一列知x1是,的二重根；,为三次多项式,可设,由,求出a，b后化简得,(其中h=x1x0),同理可求出：,4.6牛顿插值多项式,问题提出：拉格朗日插值方法中，若增加一个节点数据，其插值的多项式需重新计算。,现设构造一个插值多项式Nn(x)，只需对Nn-1(x)作简单修正(如增加某项)即可得到，这样计算方便。,由线性代数知，对任何一个不高n次的多项式P(x)=b0b1xb2x2bnxn(幂基),也可将其写成P(x)=a0a1(xx0)a2(xx0)(xx1)an(xx0)(xxn-1),其中,为系数，,为给定节点，可由求出,对牛顿插值多项式,可将其写成：,只需求出系数,，即可得到插值多项式。,先讨论等距节点下插值公式：,4.6.1差分等距节点下插值公式,对等距节点可写成,h称为步长。,定义：设Y(x)在,处的函数值分别为,称,为f(x)在处以步长为h的一阶向前差分,类似的称：,为f(x),在处步长为h的m阶向前差分。,有了差分定义,可用来计算系数,对一般的n次插值多项式,可设,通过节点,可得,通过对节点,一般的，