《第4章插值与拟合详解》由会员分享，可在线阅读，更多相关《第4章插值与拟合详解（111页珍藏版）》请在金锄头文库上搜索。
1、数值计算方法,第4章 插值法,插值法,插值法是一种古老的数学方法，早在一千多年前的隋唐时期定制历法时就广泛应用了二次插值。刘焯将等距节点的二次插值应用于天文计算。 插值理论却是在17世纪微积分产生后才逐步发展起来的，Newton插值公式理论是当时的重要成果。 由于计算机的使用以及航空、造船、精密仪器的加工，插值法在理论和实践上都得到进一步发展，获得了广泛的应用。,引言 拉格朗日插值 均差与牛顿插值公式 差分与等距节点插值 埃尔米特插值 分段低次插值 三次样条插值,插值法,一、插值问题,-(1),这就是插值问题, (1)式为插值条件,其插值函数的图象如图,整体误差的大小反映了插值函数的好坏,为了
2、使插值函数更方便在计算机上运算,一般插值函 数都使用代数多项式和有理函数。,P(x) f(x),Lagrange插值多项式 为了求得便于使用的简单的插值多项式P(x), 我们先讨论n=1的情形,要求线性插值多项式L1(x),使它满足：,L1(x)的几何意义就是通过这两点的直线；,由两点式可以看出， L1(x)是由两个线性函数,也是线性插值多项式,称为线性插值基函数,n=2的情况，假定插值节点为,为了求出L2(x)的表达式，可采用基函数方法,同理,线性无关，作为二次插值基函数,得到二次插值多项式,考虑通过n+1个节点,？,n+1次多项式,且,(请同学们思考),从而,n 1,Lagrange Po
3、lynomial,与 有关，而与 无关,节点,f,例1:,解:,且,在例1中,如果只给出两个节点169和225,也可以作插值 多项式,即1次Lagrange插值多项式,有两个插值基函数, 这种插值方法称为Lagrange线性插值,也可以在n+1个 节点中取相邻的两个节点作线性插值,例2.,解:,Lagrange插值基函数为,Lagrange线性插值多项式为,所以,Lagrange插值多项式的缺点：,插值基函数计算复杂,高次插值的精度不一定高,高次插值通常优于低次插值,但绝对不是次数越高就越好，嘿嘿,三、插值余项Remainder,满足,不会完全成立,因此,插值多项式存在着截断误差,那么我们怎样
4、估 计这个截断误差呢？,令,设,其中,近似函数,误差,根据Rolle定理,再由Rolle定理,依此类推,由于,因此,所以,定理2.,Lagrange型余项,余项表达式只有在f(x)的高阶导数存在时才能应用。,设,则,例3:,解:,练习1：,练习2：,Lagrange插值多项式的缺点,我们知道,Lagrange插值多项式的插值基函数为,理论分析中很方便，但是当插值节点增减时全部插值基函数就要随之变化，整个公式也将发生变化，这在实际计算中是很不方便的；,解决,由线性代数的知识可知,任何一个n次多项式都可以表示成,共n+1个多项式的线性组合,那么，是否可以将这n+1个多项式作为插值基函数呢？,显然，
5、多项式组,线性无关，,因此，可以作为插值基函数,基函数,有,再继续下去待定系数的形式将更复杂 。,为此引入差商和差分的概念,差商(亦称均差)/* divided difference */,1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */,2阶差商,定义2.,(k+1) 阶 差 商,差商的计算方法(表格法):,规定函数值为零阶差商,差商表,差商具有如下性质:,Warning: my head is exploding What is the point of this formula?,差商的值与 xi 的顺序无关！,New
6、ton插值公式及其余项, ,Nn(x),Rn(x),ai =,f x0, , xi ,Newton插值公式及其余项,Newton插值公式及其余项,例： 已知x=1,4,9的平方根为1,2,3，利用牛顿基本差商 公式求 的近似值。,解：,从而得二阶牛顿基本差商公式为,因此计算得 的近似值为,二、代数插值多项式的存在唯一性,且满足,-(2),-(3),-(4),上述方程组的系数行列式为n+1阶范德蒙行列式,由Cramer法则,线性方程组(4)有唯一解,定理1.,则满足插值条件,的插值多项式,存在且唯一.,注：若不将多项式次数限制为 n ，则插值多项式不唯一。,例如 也是一个插值多项式，其中 可以是
7、任意多项式。,练习,4.3 埃尔米特插值 /* Hermite Interpolation */,不仅要求函数值重合，而且要求若干阶导数也重合。 即：要求插值函数 (x) 满足 (xi) = f (xi), (xi) = f (xi), , (mi) (xi) = f (mi) (xi).,注： N 个条件可以确定 阶多项式。,N 1,一般只考虑 f 与f 的值。,3 Hermite Interpolation,例：设 x0 x1 x2, 已知 f(x0)、 f(x1)、 f(x2) 和 f (x1), 求多项式 P(x) 满足 P(xi) = f (xi)，i = 0, 1, 2，且 P(x
8、1) = f (x1), 并估计误差。,模仿 Lagrange 多项式的思想，设,解：首先，P 的阶数 =,3,h0(x),有根,x1, x2，且 h0(x1) = 0 x1 是重根。,又: h0(x0) = 1 C0,h2(x),h1(x),有根 x0, x2 ,由余下条件 h1(x1) = 1 和 h1(x1) = 0 可解。,与h0(x) 完全类似。,有根 x0, x1, x2 ,与 Lagrange 分析完全类似,3 Hermite Interpolation,一般地，已知 x0 , , xn 处有 y0 , , yn 和 y0 , , yn ，求 H2n+1(x) 满足 H2n+1(
9、xi) = yi ， H2n+1(xi) = yi。,解：设,hi(x),由余下条件 hi(xi) = 1 和 hi(xi) = 0 可解Ai 和 Bi ,有根 x0 , , xn, 除了xi 外都是2重根 ,这样的Hermite 插值唯一,3 Hermite Interpolation,斜率=1, 求Hermite多项式的基本步骤：, 根据多项式的总阶数和根的个数写出表达式；, 根据尚未利用的条件解出表达式中的待定系数；, 最后完整写出H(x)。,4 分段低次插值 /* piecewise polynomial approximation */,Remember what I have sa
10、id? Increasing the degree of interpolating polynomial will NOT guarantee a good result, since high-degree polynomials are oscillating.,例：在5, 5上考察 的Ln(x)。取,n 越大， 端点附近抖动 越大，称为 Runge 现象,4 Piecewise Polynomial Approximation, 分段线性插值 /* piecewise linear interpolation */,在每个区间 上，用1阶多项式 (直线) 逼近 f (x):, 分段He
11、rmite插值 /* Hermite piecewise polynomials */,How can we make a smooth interpolation without asking too much from f ? Headache ,三次样条 插值,早期工程师制图时，把富有弹性的细长木条（所谓样条）用压铁固定在样点上，在其它地方让它自由弯曲，然后画下长条的曲线，称为样条曲线。它实际上是由分段三次曲线并接而成，在连接点即样点上要求二阶导数连续，从数学上加以概括就得到数学样条这一概念。,三次样条插值,样条本质上是一段一段的三次多项式拼合而成的曲线,在拼接处,不仅函数是连续的,且一
12、阶和二阶导数也是连续的,一、三次样条插值函数,定义1.,-(1),注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f 在所有插值点的导数值。,f(x),H(x),S(x),要求出S(x)，则在每个小区间上 要确定4个待定系数，共有n个小区间，所以应确定4n个参数。,共(n+1)+(3n-3)=4n-2个条件，因此还需要两个条件才能确定S(x),可在区间端点a,b上各加一个条件（边界条件），具体要根据实际问题要求给定；,已知两端的一阶导数值,2. 两端的二阶导数已知,其特殊情况为,3. 当f(x
13、)是 为周期的周期函数时，则要求S(x)也是周期函数，这时边界条件应满足：,这样确定的样条函数S(x)称为周期样条函数；,加上任何一类边界条件(至少两个)后,一般使用第一、二类边界条件,常用第二类边界条件,样条插值函数的建立,即,或,可直接利用分段三次Hermit插值，只要假定,可得,加以整理后可得,-(10),由条件,-(11),由于以上两式相等,得,基本方程组,如果问题要求满足第一类(一阶)边界条件:,即,-(12),基本方程组化为n-1阶方程组,将上式化为矩阵形式,-(13),-(14),这是一个三对角方程组,如果问题要求满足第二类(二阶自然)边界条件:,由(11)式,可知,-(15),
14、-(16),与基本方程组(12)联合,并化为矩阵形式,得,(19)式与(14)一样,都是三对角方程组,解是唯一的；,例1. 对于给定的节点及函数值,解:,由(12)式可得,由(19)式得基本方程组,将上述结果代入(10)式,定理 .,最后，介绍一个有用的结果,小结,曲线拟合,当函数只在有限点集上给定函数值，要在包含该点击的区间上用公式给出函数的简单表达式，这些都涉及到在区间a,b上用简单函数逼近已知复杂函数的问题，这就是函数逼近问题。,插值法就是函数逼近问题的一种,拟解决的问题： 计算复杂的函数值 已知有限点集上的函数值，给出在包含该点集的区间上函数的简单表达式,函数逼近对函数类A中给定的函数
15、f(x)，记作 要求在另一类简单的便于计算的函数类B中求函数 使p(x)与f(x)的误差在某种度量意义下最小。,逼近问题,函数逼近,曲线拟合,实例：考察某种纤维的强度与其拉伸倍数的关系,下表 是实际测定的24个纤维样品的强度与相应的拉伸倍数 是记录:,纤维强度随拉伸 倍数增加而增加,并且24个点大致分 布在一条直线附近,必须找到一种度量标准来衡量什么曲线最接近所有数据点,(1),仍然是已知 x1 xm ; y1 ym, 求一个简单易算的近似函数 P(x) f(x)。,但是, m 很大；, yi 本身是测量值，不准确，即 yi f (xi),这时没必要取 P(xi) = yi , 而要使 P(xi) yi 总体上尽可能小。,使误差在某种度量意义下最小,最小二乘法的基本概念,一般使用,在回归分析中称为残差,称为平方误差,在回归分析中称为残差平方和,从而确定(1)中的待定系数,注意(1)式是一条直线,因此将问题一般化,仍然定义平方误差,我们选取的度量标准是,-(2),-(3),法方程组,由,可知,因此可假设,因此求最小二乘解转化为,二次函数,由多元函数取极值的必要条件,得,即,-(4),即,引入记号,则由内积的概念可知,-(5),-
