科学计算（计算方法）课件.ppt

第4章 函数的插值,4.1 引 言,背景：实际问题中，函数 f(x)多样、复杂，通常只能观测到一些离散数据；或者 f(x)过于复杂而难以进行一些运算，例如求导。希望用简单函数 g(x)近似 f(x)。,最简单的办法：在所有的离散点(节点)处，让 g(x)=f(x)；在其它点处,让 g(x)f(x).,定义4.1.1 设 f(x)是定义在区间a,b上的函数，为区间a,b中n+1个互异的点（称为节点），是给定的函数类。插值问题就是在 求函数 g(x)，使得,问题：(1)函数类的选取：多项式，样条函数，有理函数，？(2)插值问题是否有解？如果存在解，解是否唯一？(3)如何构造问题的解？(4)截断误差多大？(5)随着节点增加，g(x)是否收敛于f(x)？,设 是函数类子空间 的一组基，则对，则,其中,定理4.1.1 设 f(x)是定义在区间a,b上的函数，为区间a,b中n+1个互异的节点，。则插值问题存在惟一解当且仅当如下矩阵非奇异,如果取，即,则,4.2 Lagrange插值,定理4.2.1 设 f(x)是定义在区间a,b上的函数，为区间a,b中n+1个互异的节点。则存在惟一次数不超过 n 的多项式,使得,1.Lagrange插值,定义4.2.1 设 为区间a,b中n+1个互异的节点。如果存在次数不超过 n 的多项式,使得则称 为Lagrange插值基函数。,容易求得Lagrange插值基函数,则插值问题的解为,线性插值,二次插值,例.,定理4.2.2 设函数 f(x)在区间a,b上具有n 阶连续导数，并且在(a,b)内n+1阶导数存在，为区间a,b中n+1个互异的节点，是代数插值问题的解。则,用插值多项式 近似 f(x)的截断误差为,2.误差估计,其中,解.,n=1,分别利用x0,x1 以及 x1,x2 计算,利用,这里,而,sin 50=0.7660444,外推(extrapolation)的实际误差 0.01001,利用,内插(interpolation)的实际误差 0.00596,n=2,sin 50=0.7660444,2次插值的实际误差 0.00061,Lagrange插值的缺点,无承袭性：增加一个节点，所有的基函数都要重新计算,1.差分,4.3 Newton插值,设 f(x)是定义在区间a,b上的函数，n为正整数。记,称h为步长。,称 为等距节点。,记,称 为f(x)在节点 处的1阶向前差分。,记,依次称为f(x)在节点 处的2阶，k 阶向前差分。,记,依次称为f(x)在节点 处的1阶，2阶，k 阶向后差分。,记,称,为f(x)在节点 处的1阶，2阶，k 阶中心差分。,分别称为向前差分算子，向后差分算子和中心差分算子，用 表示恒等算子和位移算子，即,则,从而,利用差分和差分算子的定义，容易证明如下结论。,定理4.3.1(1)设,c,d 是常数，则(2)设,则(3)如果f(x)是m次多项式，则f(x)的一阶差分是m-1次多项式。(4)f(x)的各阶差分均可用函数值表示，即(5)f(x)的函数值也可用各阶差分表示，即,2.差商,为f(x)在节点 处的1阶差商。称,设 f(x)是给定的函数，为n+1个互异的节点。称,为f(x)在节点 处的2阶差商。称,为f(x)在节点 处的k阶差商。,差商表,利用差商的定义和数学归纳法，容易证明如下结论。,定理4.3.2(1)设,c,d 是常数，则(2)设,则(3)如果f(x)是m次多项式，则f(x)的一阶差商是m-1次多项式。(4)f(x)的各阶差商均可用函数值表示，即(5)f(x)的各阶差商具有对称性，即(6)如果，则,3.Newton插值,设 f(x)是给定的函数，为n+1个互异的节点，则,上面各式两边依次乘,然后左右两边全部等式相加，得,记,则,并且,即 是满足插值条件的n次插值多项式，称为n次Newton插值多项式。,事实上.设 表示在节点 处的k次Lagrange插值多项式，则,对，因为,并且 是k 次多项式,则 是的全部根。因此,将 代入上式，得,得,从而,于是,利用,例.2点Newton插值多项式,利用差商表，容易构造Newton插值多项式,设函数 f(x)在区间a,b上具有n 阶连续导数，并且在(a,b)内n+1阶导数存在，为区间a,b中n+1个互异的节点.因为，则由定理4.2.2，有,用Newton插值多项式 近似 f(x)的截断误差为,其中，从而,4.4 Hermite插值,背景：实际问题中，构造函数f(x)的插值多项式除利用函数值的条件外，还可以利用函数的导数值，这样的插值问题称为Hermite插值问题。,Hermite插值问题的提法,设 f(x)是定义在区间a,b上的可微函数，为区间a,b中n+1个互异的节点，给定的函数f(x)在节点处的函数值和导数值。求次数不超过2n+1的多项式,使得,定理4.4.1 设 f(x)是定义在区间a,b上的可微函数，为区间a,b中n+1个互异的节点。则存在惟一次数不超过 2n+1 的多项式,使得,Hermite插值问题的解,构造一个次数不超过 2n+1 的多项式,使得,因为 是 的二重零点，则,由，可得,记,则,由，可得,再构造一个次数不超过 2n+1 的多项式,使得,因为 是 的二重零点，而 是 的单零点，则,由，可得,从而,和 称为Hermite插值基函数，则Hermite插值问题的解为,容易证明：Hermite插值问题的解是惟一的。,定理4.4.2 设函数 f(x)在区间a,b上具有2n+1 阶连续导数，并在(a,b)内2n+2阶导数存在，为区间a,b中n+1个互异的节点，是Hermite插值问题的解。则,用插值多项式 近似 f(x)的截断误差为,误差估计,其中,一般Hermite插值问题,设 f(x)是定义在区间a,b上的可微函数，为区间a,b中n+1个互异的节点，给定的函数f(x)在节点处的函数值和导数值，求次数不超过m-1的多项式,使得其中,例.设f(x)是区间a,b上4次可微函数，给定函数及导数表,构造一个次数不超过3 的多项式,使得,并估计误差。,例.设f(x)是区间a,b上4次可微函数，给定函数及导数表,构造一个次数不超过3 的多项式,使得,并估计误差。,Hermite插值问题的解为,截断误差为,4.5 分段低阶插值,Runge现象,例：,等距节点构造10次Lagrange插值多项式,例：在5,5上考察 的Ln(x)。取,n 越大，端点附近抖动越大，称为Runge 现象,是否次数越高越好呢？,分段线性插值,每个小区间上，作线性插值,(1),误差估计,可以看出,分段Hermite插值 每个小区间上，作Hermite插值,构造一个次数不超过3 的多项式,使得,子区间 上Hermite插值多项式为,在区间a,b上分段Hermite插值问题的解为,误差估计,可以看出,分段低阶插值 优点：收敛 缺点：不够光滑。,4.6 样条插值,1.背景：实际问题中，构造函数f(x)的近似除利用节点处函数值的条件外，还希望近似函数具有较好的光滑性、保凸性和流线型。,2.样条函数,对区间a,b的一个分划,如果函数 满足如下条件：(1)在每个子区间 内是次多项式；(2)及其 阶导数在a,b上连续，则称 是对应于分划 的k 次多项式样条函数，称为样条节点，称为内节点，称为边界节点。这样k 次样条函数的全体记为,3.二次样条插值,给定区间a,b的一个分划,并给定函数 f(x)在节点 处的函数值，求2次样条函数 满足如下条件：,问题的提法,称 为函数 f(x)关于分划 的2次样条插值函数。,由于 在 上是2次多项式，即,其中共有3n个待定参数。确定 也就是要确定3n个待定参数。,因为 满足如下条件：,共有3n-1个条件。要唯一确定2次样条插值函数，还需要增加一个插值条件。通常利用边界节点处的导数作为补充条件。,第1边界条件：给定函数 f(x)在 处的导数值，即要求 还满足如下条件：,第2边界条件：给定函数 f(x)在 处的导数值，即要求 还满足如下条件：,定理4.6.1 二次样条插值问题的解存在且唯一。,设待求 的分段表达式为,二次样条插值问题的解,由插值条件可得,记,由第1边界条件可得,因为S(x)在a,b上连续可微，则在内部节点处有从而,于是,因此，对第1边界条件，2次样条插值问题的解存在且唯一。类似可证明：对第2边界条件，2次样条插值问题的解存在且唯一。,定理4.6.2 设函数 f(x)在区间a,b上具有4阶连续导数，为a,b中n+1个等距节点，是2次样条插值问题的解。则,对等距节点，即，可以证明如下结论。,误差估计,其中,4.三次样条插值,给定区间a,b的一个分划,并给定函数 f(x)在节点 处的函数值，求3次样条函数 满足如下条件：,问题的提法,称 为函数 f(x)关于分划 的3次样条插值函数。,由于 在 上是3次多项式，即,其中共有4n个待定参数。确定 也就是要确定4n个待定参数。,因为 满足如下条件：,共有4n-2个条件。要唯一确定3次样条插值函数，还需要增加两个插值条件。,第1边界条件：给定函数 f(x)在 处的一阶导数值，即要求 还满足如下条件：,第2边界条件：给定函数 f(x)在 处的二阶导数值，即要求 还满足如下条件：,第3边界条件（周期边界条件）：如果给定函数 f(x)为周期b-a的周期函数，则要求S(x)也是周期函数，即要求S(x)还满足如下条件：,定理4.6.3 在第1,2,3边界条件下，三次样条插值问题的解存在且唯一。,三次样条插值问题的解,m关系式,设,这是Hermite插值问题，记,由,两个边界条件,即,第1边界条件,第2边值条件,周期边界条件,M关系式,设,记,3次多项式求导2次后为线性函数,则,积分2次,由 可确定。,由 可得,再加上边界条件，利用严格对角占优矩阵的性质，可导出三次样条插值问题有唯一解。,