多项式插值与最小二乘拟合.ppt

2019/6/7,1,在科学与工程等实际问题中，其数据模型（由实验或测量所得到的一批离散数据）容易得到。,那么，能否通过处理这些数据来建立连续模型呢？从而可以对模型有更全面的认识！下面我们以一维的问题来说明，,根据寻找策略的不同，我们有插值问题和最佳平方逼近问题。,为了得到 的更多信息， 我们首先要确定一个函数空间 ，在该函数空间中寻找 的近似函数 。,插值与逼近,引言,2019/6/7,2,若要求 满足,则相应的问题称为插值问题，上述条件称为插值条件，, 插值节点；,则相应的问题称为离散型最佳平方逼近问题（最小二乘问题）。,我们还可以定义对函数 的连续型最佳平方逼近问题！,p(x) 插值函数，,若要求 使得,3,定义1：,设函数组 ，,若向量组,线性无关，,则称 在点集 上线性无关。,定义2：,设函数组 ，在a,b上连续，,若存在不全为零的数 使得,则称 在a,b上线性相关，,否则，称为线性无关。,若 中，任何有限个函数在a,b上线性无关，,则称 为a,b上的线性无关函数系。,预备知识,2019/6/7,4,代数(多项式)插值问题 最小二乘拟合问题,2019/6/7,5,代数(多项式)插值问题,1、概述； 2、拉格朗日插值； 3、分段插值,返回,2019/6/7,6,1 代数插值概述,取函数空间为不超过n阶的多项式集合 ，这样的插值问题称为代数(多项式)插值问题，即求 ，,使得如下插值条件成立, 插值多项式,定理1,插值多项式存在并且唯一。,证：,存在性，,有唯一解！,即 n+1个插值条件可以唯一的确定一个不超过n阶的插值多项式！,唯一性，,（利用n阶多项式在复数域内至多有n个零点可证！）,2019/6/7,7,显然以 作为 在插值点 处的近似值是有误差的，记,证：,不妨设 ，做函数,（多项式插值余项定理）,定理2,设 在 上连续， 在 内存在，则 ，有,其中 且依赖于 ，, 插值余项。,2019/6/7,8,由罗尔定理可知， 在(a,b)内至少有一个零点，记作 ，,即,得证！ #,其中 且依赖于 ，,注：,(1),(2),在实际计算时插值节点应尽量选在插值点x的附近，以使,尽可能小！,(3),对于不超过n次的多项式，其n阶插值多项式就是其本身！,返回,2019/6/7,9,2 拉格朗日(Lagrange)插值,定义：,设n次多项式lj(x) 满足,则称之为拉格朗日插值基函数。,利用待定系数法可得,从而可得满足插值条件的插值多项式, 拉格朗日插值多项式,显然， 在 上线性无关。,2019/6/7,10,线性插值,插值基函数：,插值多项式：,求满足插值条件 的插值多项式，,二次插值（抛物插值）,求满足插值条件 的插值多项式，,插值基函数：,插值多项式：,2019/6/7,11,例1,已知数表,试用抛物插值求 的近似值。,解:,选取最靠近2.05的节点x0, x1 , x2为插值节点，,计算可得,#,问题6：编程实现任意节点的拉格朗日插值多项式的计算，并画出插值节点和插值多项式！,返回,2019/6/7,12,3 分 段 插 值,实例演示：,取等分节点，分别用n=1,2,4,6,8, 10时的多项式插值函数逼近f(x)：,作图如下：,问题7：通过调用编写的拉格朗日插值多项式函数实现本演示实例！,2019/6/7,13,我们看到利用多项式插值函数逼近函数f(x)，n小不行，n大也不行。这种现象我们称为龙格（Runge）现象。,这是为什么呢？,下面分析多项式插值余项的估计式,(1),|f(n+1)(x)|的值，常常随n的增加呈指数级增长，比(n+1)!快得多！,(2),的值，在 的均值附近比较小，而在边界 的附近随n的增加而增加。,(3),当n比较小时，说明在区间a，b内取的节点少，以至于插值多项式不足以反映被插函数f(x)的性态！,通常，,2019/6/7,14,（一）分段线性插值,将a,b n等分，在每个小区间xi , xi+1(i=0,1,n-1)上，作线性插值,(1),(2),在每个小区间xi , xi+1上为一个次数不高于1的多项式;, 分段函数,易见，,(3),可以证明 ，若 则,数值稳定性好,计算简单,光滑性差,从而得,分段线性插值的定义,2019/6/7,15,分别用n=4,10的分段线性差值逼近函数,数值实验,作图演示:,2019/6/7,16,(1),s(x)在每个小区间xi,xi+1 上，是次数不超过三的多项式；,(2),(3),（二）三次样条插值,给定：y=f(x)的数据(xi互异),问题的提法,确定函数s(x),使,满足(1)、(2)的函数s(x)称为三次样条函数； 满足(1)、(2)、(3)的函数s(x)称为三次样条插值函数。,注:,插值条件,2019/6/7,17,确定三次样条插值函数的条件,因为三次样条函数s(x)的确定需要4n个条件，,可以确定了4n-2个条件，所以还需补充二个条件（边界条件）。,由插值条件,及连续性条件,边界条件有以下三种：,(1),(2),(3),周期性条件,自然边条件,2019/6/7,18,故 为xi,xi+1上的线性函数，,确定三次样条插值函数的三弯矩法,设 ，,s(x)在区间xi,xi+1(i=0,1,n-1)内为三次多项式，且 ，,对 进行两次不定积分，并由插值条件可得,(1),由插值条件确定三次样条函数,2019/6/7,19,当 时，,所以,其中,(2),(*),推导三弯矩方程,2019/6/7,20,再由边界条件,可得,从而可以由(*)式求得 ，,代入s(x)的表达式可得三次样条插值函数。,(3),结合边界条件求解三弯矩方程,2019/6/7,21,构成方程组,（1）,综上所述，可得构造三次样条插值函数的算法如下：,由,可得三对角方程组,其中,注：,矩阵A和向量d中元素的计算表达式见前面(*)式！, 三弯矩方程,（2）,用追赶法求解上述三对角方程组，求得M，从而可得三次样条插值函数s(x),2019/6/7,22,注：,设 ，,在小区间xi,xi+1(i=0,1,n-1)上由Hermite插值，可得三次插值函数si(x)，,从而可得三次样条插值函数s(x)，,利用连续性条件,再结合边界条件,可得关于 三对角方程组(三转角方程组)！,（三转角法）,返回,2019/6/7,23,最小二乘拟合,1、问题的提出； 2、线性最小二乘拟合； 3、线性最小二乘拟合的求法。,返回,2019/6/7,24,问题的提出：,在实际问题中，往往会通过实验观测积累了一组数据，(xi,yi),i=1,m，一般来说m比较大，如何从这批实验数据出发，寻求一近似函数 P(x)来逼近这组数据后面隐藏的函数关系 y=f(x)。,事实上，由于观测数据数目较大，又往往带有观测误差，对于这类问题运用插值函数来逼近 y=f(x) 往往是不适当的！,可不可以用插值函数来逼近呢？,返回,2019/6/7,25,线性最小二乘拟合,已知一组离散数据 ，,使得,要求一个函数,显然p*(x)可以表示成,下面考虑如何求系数 ！,返回,2019/6/7,26,线性最小二乘拟合的求法,记,考虑多元函数,为了求得p*(x)，只需求多元函数 的极小值点即可！,由多元函数极值的必要条件,可得,2019/6/7,27,若记,则有,其中,（法方程或正规方程）,容易验证,其中,注：,2019/6/7,28,可以证明法方程存在唯一解 。,称,为最小二乘拟合和的误差平方和。,注：,该值越小，说明拟合效果越好。,非线性最小二乘拟合的线性化,（1）,（2）,2019/6/7,29,例,