《拉格朗日插值》PPT课件.ppt

1,Lagrange插值,2,主要知识点,插值的基本概念，插值多项式的存在唯一性；Lagrange插值(含线性插值、抛物插值、n次Lagrange插值公式）；插值余项；插值方法：（1）解方程组、（2）基函数法。,3,插值问题描述,设已知某个函数关系 在某些离散点上的函数值：插值问题：根据这些已知数据来构造函数 的一种简单的近似表达式,以便于计算点 的函数值，或计算函数的一阶、二阶导数值。,4,多项式插值定义,在众多函数中,多项式最简单、最易计算，已知函数 个互不相同的点处的函数值，为求 的近似式，自然应当选 次多项式,使 满足条件,5,插值的几何意义,插值多项式的几何意义,6,插值唯一性定理,定理：(唯一性)满足 的 n 阶插值,多项式是唯一存在的。,7,存在唯一性定理证明,设所要构造的插值多项式为：,由插值条件,得到如下线性代数方程组：,8,存在唯一性定理证明(续),此方程组的系数行列式为,范得蒙行列式！,D 0，,因此，Pn(x)由a0,a1,an唯一确定。,9,插值方法,一、解方程组法：类似插值唯一性定理证明过程，先设插值多项式函数为，将 个节点的函数值代入多项式里，便得到 个等式，得到一个关于多项式里系数的线性方程组，解此线性方程组，便得到所要求的插值多项式。二、基函数法：一种既能避免解方程组，又能适合于计算机求解的方法，下面将具体介绍。,10,拉格朗日插值公式,拉格朗日（Lagrange）插值公式的基本思想是，把pn(x)的构造问题转化为n+1个插值基函数li(x)(i=0,1,n)的构造。,11,线性插值函数,x0,x1,(x0，y0),(x1，y1),P1(x),f(x),可见 是过 和 两点的直线。,12,抛物插值函数,x0,x1,x2,p2(x)f(x),f(x),因过三点的二次曲线为抛物线，故称为抛物插值。,13,N次插值函数,设连续函数 在a,b上对给定n+1个不同结点：,分别取函数值,其中,试构造一个次数不超过n的插值多项式,使之满足条件,i=0,1,2,n,14,一次Lagrange插值多项式(1),已知函数 在点 上的值为，要求多项式，使，。其几何意义，就是通过两点 的一条直线，如图所示。,15,一次Lagrange插值多项式(2),一次插值多项式,16,一次Lagrange插值多项式(3),由直线两点式可知，通过A，B的直线方程为 它也可变形为 显然有：,17,一次Lagrange插值多项式(4),记,可以看出,的线性组合得到，其系数分别为，,称 为节点,的线性插值基函数,18,一次Lagrange插值多项式(5),线性插值基函数,满足下述条件,并且他们都是一次函数。,注意他们的特点对下面的推广很重要,19,一次Lagrange插值多项式(6),我们称 为点 的一次插值基函数，为点 的一次插值基函数。它们在对应的插值点上取值为1，而在另外的插值点上取值为0。插值函数 是这两个插值基函数的线性组合，其组合系数就是对应点上的函数值。这种形式的插值称作为拉格朗日（Lagrange）插值。,20,二次Lagrange插值多项式1,线性插值只利用两对值及求得的 近似值，误差较大。p2(x)是x的二次函数，称为二次插值多项式。通过三点的插值问题称为二次插值或抛物插值。,21,二次Lagrange插值多项式2,以过节点 的二次函数,为插值函数。,用基函数的方法获得,其中,设被插函数在插值节点,处的函数值为,22,N次插值函数1,我们看到，两个插值点可求出一次插值多项式，而三个插值点可求出二次插值多项式。当插值点增加到n+1个时，我们可以利用Lagrange插值方法写出n次插值多项式，如下所示：,23,N次插值多项式问题2,已知n+1个节点处的函数值,求一个n次插值函数,满足,24,N次插值多项式3,构造各个插值节点上的基函数 满足如下条件,25,N次插值多项式4,求n次多项式，k=0,1,n,则,i=0,1,2,n,即 满足插值条件,根据 的表达式，以外所有的结点都是 的根，,26,N次插值多项式5,又由，得：,因此令,27,N次插值多项式6,从而得n 阶拉格朗日（Lagrange）插值公式：,28,N次插值多项式7,在a,b内存在,考察截断误差,推广：若,使得,罗尔定理:若 在 连续，在 充分光滑，,29,N次插值多项式8,注：通常不能确定 x,而是估计,x(a,b)将 作为误差估计上限。,当 f(x)为任一个次数 n 的多项式时，,可知，即插值多项式对于次数 n 的多项式是精确的。,30,例题分析1,例：已知特殊角 处的正弦函数值,分别为,求正弦函数的一次、二次插值多项式，并用,插值函数近似计算，并估计误差,解：一次插值函数为,31,例题分析2,误差为,在所求点的函数值为,误差为,知,32,例题分析3,33,例题分析4,误差为,右图中红色曲线为 图形,绿色曲线为插值函数的图形。,34,Newton插值,35,第三讲主要知识点,牛顿（Newton）插值及余项、差商的定义与性质；埃尔米特(Hermite)插值公式及余项；等距节点的多项式插值、分段低次多项式插值、三次样条插值*。,36,函数插值问题描述,设已知某个函数关系 在某些离散点上的函数值：插值问题：根据这些已知数据来构造函数 的一种简单的近似表达式,以便于计算点 的函数值，或计算函数的一阶、二阶导数值。,37,Newton插值,求作n次多项式 使得：,38,插值问题讨论,Lagrange 插值虽然易算，但若要增加一个节点时，,全部基函数 li(x)都需重新算过。,39,Newton插值的承袭性,40,Newton插值,41,具有承袭性的插值公式,线性插值公式可以写成如下形式：其中，其修正项的系数 再修正 可以进一步得到拋物插值公式其中以上讨论说明，为建立具有承袭性的插值公式，需要引进差商概念并研究其性质。,42,差商的概念,1差商的定义,定义1：设有函数f(x)以及自变量的一系列互不相等,的x0,x1,xn（即在i j时，x i xj）的值 f(xi),称,为f(x)在点xi,xi处的一阶差商，并记作f xi,xj，,43,差商的概念(续),又称,为在点 处的二阶差商,称,为f(x)在点处的n阶差商。,44,差商表,由差商定义可知：高阶差商是两个低一阶差商的差商。,45,差商形式的插值公式,再考虑拉格朗日插值问题：问题 求作次数 多项式，使满足条件，利用差商其解亦可表达为如下形式：这种差商形式的插值公式称为牛顿插值公式。,46,Newton插值,容易证明牛顿插值多项式满足插值条件。由插值多项式的唯一性，得,牛顿插值多项式的误差估计,47,Newton插值(续),牛顿插值公式的优点是：当增加一个节点时，,只要再增加一项就行了，即有递推式:,48,例题分析,49,例题分析（续1）,50,例题分析（续2）,51,Hermite插值多项式,要求函数值重合，而且要求若干阶导数也重合。,在实际问题中，对所构造的插值多项式，不仅,把此类插值多项式称为埃米尔特（Hermite）,插值多项式或称带导数的插值多项式，记为H(x)。,52,Hermite插值多项式（续1）,N 1,N 个条件可以确定 阶多项式。,53,已知函数 在区间a,b上n个互异点 处的函数值，,以及导数值，求,使得满足插值条件,Hermite插值多项式（续2）,54,简化问题描述,使得满足插值条件,55,Hermite插值多项式,构造各个节点的插值基函数,Hermit插值函数可表成,构造方法：（类似Lagrange 插值基函数）,56,两点三次Hermit插值,使得满足插值条件,已知：,57,两点三次Hermit插值（续1）,直接设,待定系数将使计算复杂，且不易推广到高次。回忆Lagrange插值基函数的方法，引入四个基函数,使之满足,58,两点三次Hermit插值（续2）,为方便起见，先考虑,的情形。,，,，,，,在一般情形下，只需作变换,59,两点三次Hermit插值（续3）,相应的基函数为：,，,，,，,60,两点三次Hermit插值（续4）,从而Hermite插值多项式为,61,算例：已知对数函数在两点处的值及导数值,用三次Hermit多项式求 的近似值,ln,1.5,=,0.409074,两点三次Hermit插值（续5）,62,一般的Hermit插值,设在n+1个节点,给出函数值和导数值,要求插值多项式 满足,满足这些条件的插值多项式就是Hermit插值多项式。其构造方法和两点情况类似，不再重复。,63,高次插值的龙格现象,对于代数插值来说，插值多项式的次数很高时，逼近效果往往很不理想。例如，考察函数,设将区间 分为 等份，表取 个等分点作节点的插值多项式，如下图所示，当 增大时，在两端会发出激烈的振荡，这就是所谓龙格现象。,64,龙格现象,65,分段插值的概念,所谓分段插值，就是将被插值函数逐段多项式化。一般来说，分段插值方法的处理过程分两步，先将所考察的区间作一分划 并在每个 子段上构造插值多项式，然后把它们装配在一起，作为整个区间 上的插值函数，即称为分段多项式。如果函数 在分划 的每个子段上都是 次式，则称为具有分划 的分段 次式。,66,分段插值,1.分段线性插值；2.分段抛物插值；3.分段低次多项式插值；原因：高次插值会发生Runge现象。逼近效果并不算太好！,67,分段线性插值,满足条件 具有分划 的分段一次式 在每个子段 上都具有如下表达式：,68,分段三次埃尔米特插值,问题 求作具有分划 的分段三次式，使成立 解 由于每个子段 上的 都是三次式，且满足埃尔米特插值条件：所以 其中，且有,69,样条函数的概念,所谓样条函数，从数学上讲，就是按一定光滑性要求“装配”起来的分段多项式，具体的说，称具有分划的分段 次式 为 次样条函数，如果它在每个内节点 上具有直到 阶连续导数。点 称为样条函数的节点。特别地，零次样条 就是人们熟知的阶梯函数，一次样条 则为折线函数。,70,样条函数插值,插值曲线即要简单，又要在曲线的连接处比较光滑。,这样的分段插值函数在分段上要求多项式次数低，而在节点上不仅连续，还存在连续的低阶导数，我们把满足这样条件的插值函数，称为样条插值函数，它所对应的曲线称为样条曲线，其节点称为样点，这种插值方法称为样条插值。,71,样条函数插值（续1）,插值函数。,72,样条函数插值（续2）,f(x),H(x),S(x),注：三次样条与分段 Hermite 插值的根本区别 在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点可能需要）；而Hermite 插值依赖于f 在所有插值点的导数值。,73,曲线拟和,74,第四讲主要知识点,1、曲线拟合的概念2、曲线拟和的方法3、解矛盾方程组,75,函数插值问题回忆,设已知某个函数关系 在某些离散点上的函数值：插值问题：根据这些已知数据来构造函数 的一种简单的近似表达式,以便于计算点 的函数值，或计算函数的一阶、二阶导数值。,76,曲线拟和的概念,在前面所讨论的各种插值方法中，始假设数据点是精确的，准确的，不可修改的，所要求出的插值曲线必须通过每一个数据点。但在实际工作中由于各随机因素的干扰，所得到的数据往往不同程度存在着误差。因此，插值方法只能适用那些误差可以忽略不记的情况，当误差较大而不能忽略时，又如何通过这些观测数据确定其内在的变化规律呢？本节所介绍的曲线拟合就是解决这一问题的主要方法之一。,77,曲线拟合的概念(续),如图所示，常常需要从一组获得的数据点中，寻找变量与变量之间的变化规律用几何方法来解释，就是用已知平面内的一组点，来确定一条曲线，使该曲线能在整体上刻画这组点的变化趋势而不需通过每个点，我们称这种方法为曲线拟合，所求出的曲线称为拟合曲线。,78,曲线拟合的方法,将上述问题抽象为数学问题为：设有一组数据对，求连续变量的一个函数，它在 处误差为，使总体误差按某种算法达到最小常用的三种准则是:,79,曲线拟合的方法(续),（）使得误差的最大的绝对值为最小，即（）使误差的绝对值和最小，即（）使误差的平方和为最小，即 由于准测（）、（）含有绝对值不便于处理，通常采用准测（），并称基于准则（）来选取拟合曲线的方法，为曲线拟合的最小二乘法。,80,多项式拟合,一般而言，所求得的拟合函数可以是不同的函数类，其中最简单的是多项式，此时称为多项式拟合，具体定义如下：,81,多项式拟合(续1),定义2.5设有给定的数据，假设其拟合函数形式为，求系数，使得 取最小值称 次多项式为 次最小二乘拟合多项式(或 次最小平方逼近多项式)。特别地，当 时，称 为线性最小二乘拟合。,82,多项式拟合（续2）,容易看出 是系数 的 元二次多项式(二次型)，所以可以用多元函数求极值的方法求其最小值点和最小值。将 对 求偏导数得到驻点方程组：，即,83,直线拟和,问题 对于给定的数据点,，求作一次式,，使总误差为最小，即在二元函数式中,为最小。这里Q是关于未知数a和b的二元函数，这一问题就是要确定a和b取何值时，二元函数,的值最小?,84,直线拟和（续1）,由微积分的知识可知，这一问题的求解，可归结为求二元函数,的极值问题，即,和,应满足：,85,直线拟和（续2）,86,拟合例题,例1已知观测数据如下所示，求它的拟合曲线。解：根据所给数据，在直角坐标下画出数据点，从图中可以看出，各点在一条直线附近，故可取线性函数作为拟合曲线,87,拟合例题（续1）,令 将数据带入公式得，解得。因此而得所求拟合曲线为。,88,拟合例题（续2）,例2 有一滑轮组，要举起W公斤的重物需要用F公斤的力，实验所得的数据如下表。,求适合上述关系的近似公式。,89,拟合例题（续3）,解 首先，将这些数据画在直角坐标系中，从图形上 看，数据点的分布大致呈一条直线，所以设所求 的拟合直线为，,则由式(2.28)得关于a和b的线性方程组,90,其他类拟和问题,正如本节开头所指出的最小二乘法并不只限于多项式，也可用于任何具体给出的函数形式。特别重要的是有些非线性最小二乘拟合问题通过适当的变换可以转化为线性最小二乘问题求解。,91,拟合例题（续4）,例2 已知数据表,求一形如,解：所求拟合函数是一个指数函数，对它两边取自然对数，得,的经验公式与已知数据拟合,92,拟合例题（续5）,于是对应于上述数据表得到一个以应数据表：,若记,则,从而将原问题转化为由新数据表所给出的线性拟合问题易知其求解方程组为：,93,拟合例题（续6）,解之得,，于是,，故所求经验公式为,94,拟合例题分析,通过上述两例可知，用多项式作曲线拟合的计算步骤可分为如下几步：（）根据已给的数据,作草图，由草图估计出多项式的次数(m次)并令,，其中,（）求解由最小二乘原理得到的方程组；（）将所得的解作为拟合多项式的相关项的系数，则此多项式即为所求。,为待定系数；,95,矛盾方程组,试求下列矛盾方程组的解：,很显然，直接求解是不行的，因为满足方程组的精确解是不存在的！只能求出尽量满足方程组的近似解。,96,矛盾方程组（续1）,运用最小二乘法，要求满足方程组的解，,即求使下列值 最小的解，就是方程组的近似解：,97,矛盾方程组（续2）,得解：,98,本讲结束!谢谢大家!再见!20090411,