《数值算法总结》PPT课件.ppt

《《数值算法总结》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数值算法总结》PPT课件.ppt（55页珍藏版）》请在三一办公上搜索。

1、拉格朗日插值,线性插值（一次插值）,1.插值：就是定义一个在特定点取给定值的函数的过程。2.问题的提法 已知函数 在区间 的端点上的函数，求一个一次函数 使得。其几何意义是已知平面上两点,求一条直线过该已知两点。,线性插值（一次插值）,2.插值函数和插值基函数由直线的点斜式公式可知：把此式按照 和 写成两项：记，并称它们为一次插值基函数。,线性插值（一次插值）,该基函数的特点如右表：从而,此形式称之为拉格朗日型插值多项式。其中,插值基函数与、无关，而由插值结点、所决定。一次插值多项式是插值基函数的线性组合,相应的组合系数是该点的函数值、。,二次插值多项式,2.插值基本多项式 有三个插值结点,构

2、造三个插值基本多项式，要求满足：(1)基本多项式为二次多项式；(2)它们的函数值满足下表：,二次插值多项式,2.插值基本多项式 有三个插值结点,构造三个插值基本多项式，要求满足：(1)基本多项式为二次多项式；(2)它们的函数值满足下表：,二次插值多项式,3.拉格朗日型二次插值多项式由前述，拉格朗日型二次插值多项式 是三个二次插值多项式的线性组合,因而其是次数不超过二次的多项式,且满足：,拉格朗日型n次插值多项式,1.问题的提出：已知函数 在n+1个不同的点 上的函数值分别为,求一个次数不超过n的多项式,使其满足,即n+1个不同的点可以唯一决定一个n次多项式。2.插值基函数 过n+1个不同的点分

3、别决定n+1个n次插值基函数 每个插值基本多项式 满足：(1).是n次多项式;(2).，而在其它n个。,拉格朗日型n次插值多项式,由于，故 有因子 因其已经是n次多项式，故而仅相差一个常数因子。令:由，可以定出a，进而得到：3.n次拉格朗日型插值多项式 是n+1个n次插值基本多项式 的线性组合，相应的组合系数是。即从而，是一个次数不超过n的多项式,且满足,。,拉格朗日型n次插值多项式,例3求过点(2,0)(4,3)(6,5)(8,4)(10,1)的拉格朗日型插值多项式。解：用4次插值多项式对5个点插值。所以,牛顿插值,均差,设函数f(x)在n+1个相异的点 上的函数值分别为,或者记为。1.一阶

4、均差：称 为f(x)关于节点 的一阶均差，记为。2.二阶均差：一阶均差，的均差 称为f(x)关于节点 的二阶均差，记为。3.n阶均差：递归地用n-1阶均差来定义n阶均差，称为f(x)关于n+1个节点 的均差。,均差,牛顿插值公式,例2：已知求满足以上插值条件的牛顿型插值多项式。解：在例1中，我们已计算出则牛顿三次插值多项式为,牛顿插值公式,例3：已知 在六个点的函数值如下表，运用牛顿型插值多项式求 的近似值。欲求，只需在 之后再加一项：故,最小二乘法,最小二乘法,通过观测、测量或试验得到某一函数在的函数值。我们可以用插值的方法对这一函数进行近似,而插值方法要求所得到的插值多项式经过已知的这n个

5、插值结点;在n比较大的情况下,插值多项式往往是高次多项式,这也就容易出现振荡现象:虽然在插值结点上没有误差,但在插值结点之外插值误差变得很大,从“整体”上看,插值逼近效果将变得“很差”。于是,我们采用数据拟合的方法。所谓数据拟合是求一个简单的函数,不要求通过已知的这n个点,而是要求在整体上“尽量好”的逼近原函数。这时,在每个已知点上就会有误差,数据拟合就是从整体上使误差,尽量的小一些。,求一个低次多项式,使得 达到最小,此问题便是一个数据拟合的最小二乘问题。,直线拟合（一次函数）,已知数据,求一个一次多项式,（实际上，就是求a,b）,使得,达到最小。,利用高等数学中求二元函数极小值(最小值)的

6、方法，上述问题转化为求解下列方程组,因为,得到如下的正则方程组,已知10对数据如下表,利用最小二乘法求拟合曲线,解：先列表来计算四个,：,形成方程组,解得,，,于是，最小二乘拟合一次函数为,方程求根,方程求根,如果f(x)是多项式,称此方程为代数方程,若f(x)是超越函数,就称f(x)=0为超越方程。一般一次方程称为线性方程,而二次以上的代数方程或超越方程称为非线性方程。对于一次、二次代数方程,我们可以求出精确解,而对于三次以上的代数方程和超越方程,我们没有通用的技术来求出精确解,这就需要数值方法来求出方程的近似解。分离区间 许多方程往往有两个以上的根,在某个区间a,b上,如果方程在此区间内只

7、含一个根,我们称此区间为方程的分离区间。,方程求根,如果f(x)在区间a,b上连续,满足f(a).f(b)0,即两个端点值异号,且f(x)在区间a,b上严格单调,则利用闭区间上连续函数的性质,可知f(x)在区间a,b上存在唯一的零点,其几何意义如下图:,二分法,计算过程:寻找一个分离区间,要求,取中点,计算,如,则:,;否则:,得一个区间序列,误差估计:,中间要转出循环的可能是,如,时,此时转出循环,二分法迭代次数:,特点:简便、易掌握、对,的要求不高,但收敛较慢,二分法,求方程,的实根,精确到0.001。,解:,则:,误差为:,迭代法,迭代法的构造:将方程,等解的转化为:,收敛要求:,因此构

8、造,迭代格式:,当,时,迭代中止。,时要适当选取。,已知方程,在,内只有一个根,求此根,精确到:0.01,解:,故用简单迭代时收敛的。,注意:这儿 只能用弧度不能用角度。,取,(如取,则,),精确解为:,因,已满足要求了,牛顿迭代法,1)迭代公式:,2)初始值的选取:,内满足,要使选取,使得:,3)收敛条件:选取,使,在,内有根。,不为零,不变号,例：用牛顿法求方程,在,上的近似根,解:,迭代公式为:,在,内,故选取,达到精度要求。,弦截法,方法的构造:求解方程,设,在,两端点,且,在,上,不变号,选取,使,另一个端点为,用,的连线,与x轴的焦点,来作为,的一次近似。,迭代公式:通过以上,的选

9、取,我们有,。如果,未经选取,在第次之前,弦,与x轴的焦点为,计算,找出,使,满足该式的,作为,从而计算,的公式为:,每一步均加以判断,例:(自我练习4)用弦截法求方程,的根,精确到0.01,解:,故选取,所有弦,均为端点,1),2),3),4),5),6),解线性方程组,高斯消去法,例1.解方程组,解:方程组的矩阵形式为,其中,第一步,消元过程:对增广矩阵进行消元,即得方程组:,第二步,回代过程:,此方法就是高斯消去法,高斯消去法的计算流程,高斯消去法能进行到底的充要条件是 系数矩阵A的各阶顺序主子式不为零,列主元消去法,例:用列主元消去法求解方程组,解:,消元得,消元得,回代过程:,列主元

10、消去法计算流程,三角分解,三角分解流程,雅可比(Jacobi)迭代法,设方程组,满足,雅可比(Jacobi)迭代法,A=D+L+U。于是,Ax=b可以转化为(D+L+U)x=b,Dx=b-(L+U)x,x=-D-1(L+U)x+D-1b。雅可比迭代的矩阵形式为:,对应于,有,高斯赛德尔迭代,设方程组,满足,高斯赛德尔迭代,矩阵表示G-S迭代:,转化为,于是我们得到:,则G-S迭代的矩阵形式为,其中,为G-S迭代的迭代矩阵,超松驰迭代,数值积分,数值积分,数值积分,数值积分,数值积分,性质1:归一公式：,性质2:对称性：,在柯特斯系数表中：(1).n表示n阶NC 公式的系数,（共有n+1个）。(

11、2).从表中可以看到各行和等于1,且各系数与积分区间无关。(3).当n8时，柯特斯系数出现负数，这意味着,这就会产生数值不稳定性，因此高阶NC公式的效果并不理想,数值积分,梯形公式,数值积分,抛物线公式（辛普森公式）,数值积分,柯特斯公式,龙贝格求积公式,龙贝格积分法是在计算梯形和序列的基础上应用了线性外推的加速方法，由此构成的一种具有超线性收敛的自动积分法,方法思路:,1.按照区间逐次分半的方法，计算梯形和序列,由此生成序列,T0,T1,Tn,当 时，就可以结束计算。,设Tn为梯形和，I为积分真值，由复化梯形公式,龙贝格求积公式,2.加速,由解析几何,柯特斯序列,龙贝格序列,梯 形序列,用类似方法可推得：,由此法，可得如下三角形数表,计算步骤：,1取，计算,2对k=1,2,计算下列各步,3对n=0,1,2,k=n 1,n 2,4收敛控制,则输出积分值，否则转3。,龙贝格求积公式,例：用龙贝格算法计算定积分（计算一个龙贝格过程即可）。,解：,常微分方程初值问题的数值解法,欧拉法,步长,改进欧拉方法,例：初值问题,用四阶古典RungeKutta方法，,龙格库塔法,