插值法与最小二乘法2Zu.ppt

第三章 插值法与 最小二乘法,数学与统计学院,数值计算方法,本章主要内容,插值法 Lagrange插值 插值误差 分段插值法 Newton插值多项式 三次样条插值法 数据拟合 最小二乘法,4 三次样条插值/*Cubic Spline Interpolation*/,许多实际工程技术中一般对精度要求非常高，（1）要求近似曲线在节点连续；（收敛性）；（2）要求近似曲线在节点处导数连续，即充分光滑。分段插值不能保证节点的光滑性，而Hermite插值需要知道节点处的导数值，实际中无法确定。,一、三次样条函数的力学背景,在工程技术和数学应用中经常遇到这样一类数据处理问题：在平面上给定了一组有序的离散点列，要求用一条光滑曲线把这些点按次序连接起来。,形象地称之为样条曲线.,在力学上，通常均匀细木条可以看作弹性细梁，压铁看作是作用在梁上的集中载荷，“样条曲线”就模拟为弹性细梁在外加集中载荷作用下的弯曲变形曲线。,因此，“样条曲线”可近似认为是三次多项式.,二、三次样条插值函数定义及求法,设在区间 上给定一个分割，定义在 上的函数 如果满足下列条件：(1)在每个小区间 内是三次多项式,(2)在整个 区间上，为二阶连续可导函数，即在每个节点 处,假设现在已知函数 在节点处的函数值：,线性插值函数,1、M 连续方程与 的表达式,记,因为 在每一个子区间 上都是线性函数,两边积分,两边再积分一次,？,代入插值条件：,在整个区间 上，的表达式为：,未知数n+1个,的计算方法(利用导数的连续性)：,由,由,由,其中,写成方程组的形式：,三弯矩方程组,3、边界条件/*boundary conditions*/,已知端点的斜率：,已知端点的二阶导数：,设 是以 为周期的周期函数，对 附加周期性条件：,M连续方程在各类边界条件下的求解方法,对于第一类边界条件,从而得到方程组（三对角）：,可用追赶法求解,对于第二类边界条件,类似地可以得到方程组（三对角）：,上述两种情况得到的方程组，可以写成统一形式：,其中,时为第二类边界条件,时为第一类边界条件,对于第三类边界条件,得到方程,其中,第三类边界条件对应的方程组：,对三对角算法经过修改后可以求解上述方程组,不是三对角方程组,注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点处的函数值）；而Hermite插值依赖于f 在许多插值节点的导数值。,f(x),H(x),S(x),性质（误差估计）,设函数，是区间 的一个分割，是关于 的带有型(斜率边界)或型(二阶导数边界)边界条件的插值函数，则有误差估计其中 是分割比，并且系数 与 是最优估计。,性质说明：三次样条插值函数本身连同它的一、二、三阶导数分别收敛到 及其相应导数，具有强收敛性。,例1 已知函数 在的 数据表：,解：,求 在区间 上的三次样条插值函数。,三弯矩方程组,用追赶法求解方程组得,三次样条插值函数,在科学实验中,往往要从一组实验数据(xi,yi)中,寻找自变量 x 与因变量 y 之间的函数关系 y=f(x).在前面,我们学习了通过利用插值法来实现这个目的.,是函数逼近的另一种方法.不要求曲线完全通过所有已知节点,而是从总偏差最小的角度来取近似曲线.即从大量给定数据中找出规律,并构造一条曲线反映数据点的总趋势,以消除其局部波动.属于全局最优.,用插值法近似某个函数时,一个严重的缺点是:对节点测量值的精度要求高.但由于测量数据中往往带有随机误差,在利用这些有误差数据构造插值函数,必将不合理的误差带入,影响对未知函数的近似精度.属于局部最优.,最小二乘法：,实例 考察某种纤维的强度与其拉伸倍数的关系,下表是实际测定的24个纤维样品的强度与相应的拉伸倍数的记录:,5 最小二乘法,结论:纤维强度随拉伸倍数增加而增加,并且24个点大致分布在一条直线附近，因此可以认为强度 S 与拉伸倍数 t的关系近似满足线性关系。,根据上述实例图中测试点的分布情况,可以画出很多条靠近这些点的直线,其方程都可表示为：,5-1 最小二乘法的基本概念,(1),(2),其中:a,b 待定.要从形如(1)式的所有直线中,找出一条用某种度量标准来衡量最靠近所有数据点 的直线.,计算值 S(ti)与测量数据 si 之差为:,其大小依赖于 a,b 的选取.,问:如何衡量直线与数据点偏离程度?,(3),注:(1)式是一条直线，但现实生活中的函数关系并不都是线性关系，因此下面将问题推广到一般情况.,一般使用误差的加权平方和作为误差的度量标准。,用i 表示测量数据(ti,si)的重度,称为权系数,表示在不同点(ti,si)处的数据比重不同.,作为衡量 S(t)与数据点(ti,si)(i=0,1,m)偏离大小的度量标准.,使 最小的 S(t)最接近,以此为依据可确定(1)式中的确定系数 a,b.,问:如何确定直线方程的系数 a 与 b?,(4),(5),(6),定义1 设 为给定一组数据,为各点的权系数,要求在函数类,中,求一函数,使误差的加权平方和最小,即,最小平方误差,其中：为中任意函数，称为拟合函数.,称按条件(6)求函数 s*(x)的方法为数据拟合的最小二乘法,简称最小二乘法.,问：确定拟合函数 s(x)后,如何求拟合系数,使得 满足拟合条件？,5-2 法方程组（正规方程组）,由,可知,为拟合系数 的函数.因此,可设平方误差为:,由多元函数取极值的必要条件,移项整理得：,得：,即,显然(7)式是一个关于 的n+1阶线性方程组.,定义向量：,这是一个系数为,常数项为 的线性方程组.将其表示为矩阵形式：,(11),称为函数系 在离散点 的法方程组.并且其系数矩阵为对称正定矩阵.,坡度矩阵,Hilbert矩阵,由于 为函数类的基,因此它们必然线性无关,所以法方程组的系数矩阵非奇异,即,根据Cramer法则,法方程组有唯一解：,即：,可以证明,是 所对应的 最小二乘解.,为均方差.,可以证明:,平方误差的内积表示形式:,故有,作为一种简单的情况,常使用多项式 Pn(x)作为(xi,yi)(i=0,1,m)的拟合函数,这是最常见的最小二乘拟合.,此时,拟合函数 S(x)的基函数为:,函数类为多项式类时的法方程组,基函数之间的内积为：,此时，法方程组为：,(14),问：如何解决上述问题？,以正交多项式为基函数,简化法方程组.,例2 测得数据如下：试用最小二乘法求最佳数据拟合函数.,解：,1)在坐标平面上描点，,从散点图可以看出函数关系近似线性关系，所以选择线性函数：,其基函数为,作为拟合函数,2)根据散点的分布情况，选择基函数.,（难点）,3)建立法方程组,根据内积公式:,计算下列各值：,取,得法方程组：,4)解法方程组,求拟合函数系数,因此,为所有的最小二乘解.,求得线性函数两系数:,5)求拟合误差,最小二乘拟合的一般步骤:描点(若给定拟合函数形式,这一步骤可以省略);根据数据点的分布情况,确定拟合函数,进一步确定拟合函数的基函数;建立法方程组(涉及到一些内积运算);求解法方程组(推荐使用Gauss列主元消去法),得拟合函数的系数;写出拟合函数;求拟合误差:最小平方误差.,非线性最小二乘问题,当用非多项式函数(例如:指数函数类 或幂函数类 等)拟合给定的一组数据时,拟合函数是关于待定参数的非线性函数.若按最小二乘准则:,用极值原理建立的法方程组将是关于待定参数的非线性方程组.称这类数据拟合问题为非线性最小二乘拟合.,简单的非线性最小二乘拟合问题求解方法:转化为线性最小二乘问题求解.,1786年(9岁),发现1到100自然数之和是5050；1795年(18岁),进入哥廷根大学,发明最小二乘法；1796年,仅用尺规作出正17边形；1879年(22岁),证明代数学基本定理,获博士学位；1801年(24岁),出版算术研究,精确计算谷神星(最大的小行星)的轨迹；1816年左右发现了欧氏几何的原理；1828年出版关于曲面的一般研究,系统地阐述了空间曲面的微分几何学；1833年,和韦伯共同发明了有线电报；,最小二乘法发明者高斯,高斯在数学、天文学、力学、测地学、磁学、光学、水工学和电动学等方面均有杰出贡献.,Gauss(17771855),Lagrange插值法（高次插值多项式数值不稳定，龙格现象；每增加一个插值节点，插值多项式就得重新构造）,分段低次插值法（收敛性和精度能得到保证；具有局部性；在节点处有尖点，不可导）,Newton插值法（增加插值节点时，只需增加部分计算工作量，原来的计算结果仍可用。）,小 结,三次样条插值法（能保证在节点处的连续性和光滑性，收敛性.）,小 结,最小二乘法 总体上偏差最小，不要求：,作业4：教材 P61-62:3-21,3-23，3-26（1）、（2）.第七周星期三晚上7:30-9:30，理科楼312（学习委员）。,上机实验题二,题目：插值法与最小二乘法 教材P62 3-27，3-28，3-29；,要求：1.写出上机报告；2.描述算法步骤；3.写出源程序和计算结果；4.分析计算结果。,时间安排：1.本周星期三晚6：30-10：30，软件01-04，医电01-03；2.本周星期五晚6：30-10：30，力学（硕）01，结构01，钱学森01-02，软件01（部分）,上机实验题二,交报告时间：双面打印后，第7周星期三晚上7：30-9：30（学习委员）,上机报告格式：计算方法实验报告格式.doc,注意：上机签到（各班班长，领签到表）,