北航计算方法复习题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算方法,复习课,2011-12-29,教学内容,引论,第一章 插值方法,第二章 数值积分,第三章 常微分方程的差分方法,第四章 方程求根的迭代法,第五章 线性方程组的迭代法,第六章 线性方程组的直接法,（但精度、误差等概念要贯穿于考题中）,考题形式,填空题,主要考察基本概念，对方法的理解,共,8,题，共,40,分,五章的内容基本平均分配,大题,计算、证明等,5-6,道题，共,60,分,五章的内容基本平均分配,其中有,1-2,道题为作业题或书上的例题（可能改数）,第一章 插值方法,拉格朗日插值（插值余项）埃特金算法,牛顿插值,埃尔米特插值,分段插值,样条插值,曲线拟合的最小二乘法,第一章 插值方法,计算函数值,需要计算函数值，但函数关系复杂，没有解析表达式。,常见的有：由观测数据计算未观测到的点的函数值。,由观测数据构造一个适当的简单函数近似的代替要寻求的函数,插值法。,第一章 插值方法,几个典型问题：,问题,1,：,设函数,y,=,f,(,x,),定义域为,a,，,b,，,x,0,，,x,1,，,，,x,n,是,a,，,b,上的,n,+1,个互异点，且,y,i,=,f,(,x,i,),已知，要构造一个函数,g(,x,),，使得,g,(,x,i,)=,y,i,(,i,=0,1,n,),。,问题,2,：,求做,n,次多项式,p,n,(,x,),，使满足条件：,为一组已给数据。,问题,3,：,=,问题,1+,问题,2,：即过给定点，也要求导数相同。,第一章 插值方法,问题,1,：,设函数,y,=,f,(,x,),定义域为,a,，,b,，,x,0,，,x,1,，,，,x,n,是,a,，,b,上的,n,+1,个互异点，且,y,i,=,f,(,x,i,),已知，要构造一个函数,g(,x,),，使得,g,(,x,i,)=,y,i,(,i,=0,1,n,),。,几何,意义：,x,0,x,1,x,2,x,3,x,4,x,g,(,x,),f,(,x,),代数插值：为多项式函数集,第一章 插值方法,问题,1,：,设函数,y,=,f,(,x,),定义域为,a,，,b,，,x,0,，,x,1,，,，,x,n,是,a,，,b,上的,n,+1,个互异点，且,y,i,=,f,(,x,i,),已知，要构造一个函数,g(,x,),，使得,g,(,x,i,)=,y,i,(,i,=0,1,n,),。,代数插值：为多项式函数集,Lagrange,插值公式,Aitken,插值公式,Newton,插值公式,第一章 插值方法,Lagrange,插值公式,Lagrange,多项式,Lagrange,基函数,满足,与,节点,有关，而与,f,无关,给定,x,i,=i,+1,i,=0,1,2,3,4,5.,下面哪个是,l2,(,x,),的图像？,y,0,-,-,-,1,0.5,-,0.5,1,2,3,4,5,6,x,y,0,-,-,-,1,0.5,-,0.5,1,2,3,4,5,6,x,y,0,-,-,-,1,0.5,-,0.5,1,2,3,4,5,6,x,A,B,C,第一章 插值方法,Lagrange,插值公式,Lagrange,多项式,Lagrange,基函数,思考,1,：,令,R,x,n,+1,表示所有的不高于,n,次的实系数多项式和零多项式构成的集合，假设函数,y,=,f,(,x,),的已知值,(,x,i,，,y,i,)(,y,i,=,f,(,x,i,),，,i,=0,，,1,，,，,n,),，寻找一个多项式,P,n,(,x,)R,x,n,+1,，满足：,P,n,(,x,i,)=,f,(,x,i,)(,i,=0,，,1,，,，,n,)(*),唯一性？,思考,2,：,f,(,x,)=,x,k,(,k,=0,1,n,),关于互异节点,x,i,(,i,=0,1,n,),的拉格朗日插值公式,第一章 插值方法,Lagrange,插值公式,Lagrange,多项式,Lagrange,基函数,1.2,0.4,-0.8,-2.0,y,i,=f,(,x,i,),2.0,1.8,1.4,1.0,x,i,求 的值,求方程 在,1,，,2,内根的近似值,。,反插值问题,例：,已知单调连续函数 在如下采样点的函数值：,第一章 插值方法,Lagrange,插值公式,Lagrange,多项式,Lagrange,基函数,（,2,）,Lagrange,插值多项式结构,对称,，形式简单,.,注,：,（,1,）,若不将多项式次数限制为,n,，则插值多项式,不唯一,。,（,4,）,当插值,节点增加,时，,拉氏基函数需要,重新,计算，,n,较大时，计算量非常大,故,常用于理论分析。,（,3,）,误差估计,第一章 插值方法,Aitken,插值公式,(,效率，或临时增加一个节点,),利用两个,k,-1,次插值,f,k,-1,(,x,k,-1,),，,f,k,-1,(,x,i,),再做线性插值，结果得到,k,次插值,f,kx,i,),的结果,特点：,高次插值过程归结为线性插值的多次重复；,数据的一致程度可判断插值结果的精度。,给定,3,个节点及节点上的函数值,(,x,i,，,f,(,x,i,)(,i,=0,，,，,2),，按,Aitken,插值方法构造插值函数，试在下图中画出任意给定,x,对应的,f,2,(,x,2,),第一章 插值方法,Newton,插值公式,具有承袭性的显示插值公式,差商具有对称性,余项？,第一章 插值方法,问题,2,：,求做,n,次多项式,p,n,(,x,),，使满足条件：,为一组已给数据。,Taylor,插值,第一章 插值方法,问题,3,：,=,问题,1+,问题,2,：即过给定点，也要求导数相同。,Hermite,插值,求函数,f,(,x,),的二次近似式,P,2,(,x,),，满足：,P,2,(,x,0,)=,f,(,x,0,)=,y,0,P,2,(,x,0,)=,f,(,x,0,)=,y,0,P,2,(,x,1,)=,f,(,x,1,)=,y,1,。,求函数,f,(,x,),的三次近似式,p,3,(,x,),，满足：,P,3,(,x,0,)=,f,(,x,0,)=,y,0,P,3,(,x,0,)=,f,(,x,0,)=,y,0,P,3,(,x,1,)=,f,(,x,1,)=,y,1,，,P,3,(,x,1,)=,f,(,x,1,)=,y,1,基函数法,余项？,第一章 插值方法,分段插值,高次插值可能会产生龙格现象,-,5,-,4,-,3,-,2,-,1,0,1,2,3,4,5,-,0.5,0,0.5,1,1.5,2,2.5,第一章 插值方法,高次插值可能会产生龙格现象,分段插值,光滑性问题,样条插值,第二章 数值积分,机械求积,牛顿,-,柯特斯公式,龙贝格算法,高斯公式,数值微分,第二章 数值积分,为什么研究数值积分：,(1),有些函数的原函数不能用初等函数表现为有限的形式；,(2),原函数的形式复杂；,(3),原函数没有具体的表达式，只有离散点。,定积分的数值解法,(,效率,+,精度,),。,第二章 数值积分,机械求积,用被积函数,f,(,x,),的若干节点,x,i,(,a,x,0,x,1,x,n,b,),处的函数值,f,(,x,i,),的线性组合,(,数值积分公式，求积公式,),作为,I,(,f,),的近似值。,求积节点：,x,i,(,i,=0,，,1,，,，,n,),求积系数：,A,i,(,i,=0,，,1,，,，,n,),与,f,(,x,),无关,；,一般形式,第二章 数值积分,机械求积,一般形式,一般性问题：,求积公式的,收敛性,:,求积系数的,特征,:,求积公式的,稳定性,:,求积系数全为正时，公式是稳定的,第二章 数值积分,机械求积,一般形式,一般性问题：,求积公式的,精度：,如果求积公式,对一切不高于,m,次的多项式都恒成立，而对于某个,m+1,次多项式不能精确成立，则称该求积公式具有,m,次,代数精度,。,求积公式 具有次,m,代数精,度的充要条件是 为,时求积公式,精确成立,，而 为 时求积公式,不能成为等式。,第二章 数值积分,机械求积,一般形式,Q1,、节点已知，系数,A,i,如何选取,Q2,、节点自由选取，怎么选,第二章 数值积分,求积节点固定的情况,一般思想：取简单的、便于积分且又逼近于被积函数,f,(,x,),的函数,(,x,),代替,f,(,x,),来构造求积公式；,典型,插值多项式,p,n,(,x,),dx,插值型求积公式,插值型,求积公式余项：,插值型,求积公式的代数精度：,插值型求积公式至少具有,n,次代数精度,具有,n,次代数精度的求积公式必是插值型的,第二章 数值积分,求积节点固定的情况,第二章 数值积分,求积节点固定的情况,设,a,，,b,为有限区间，取,h,=(,b,-,a,)/,n,，,等距节点,x,i,=,a+i,h,(,i,=0,，,1,，,，,n,),。,记,x,=,a,+,th,(0,t,n,),，则：,牛顿,-,柯特斯公式,第二章 数值积分,求积节点固定的情况,梯形公式,Simpson,公式,Cotes,公式,阶数越高越好？,精度？,稳定性？,n,为,偶数,时，,Newton,Cotes,求积公式,至少具有,n+1,次代数精度。,n,为,奇数,时，,NewtonCotes,求积公式,至少具有,n,次代数精度。,复化求积公式,第二章 数值积分,求积节点可选择的情况,高斯求积公式,提高精度,当求积,节点个数,确定后，不管这些求积节点如何选 取，,求积公式的,代数精度,最高,能达到多少？,具有,最高,代数精度,的求积公式,中求积节点如何选取？,第二章 数值积分,求积节点可选择的情况,高斯求积公式,提高精度,不失一般性，由代数精度构造插值型数值求积公式,求积节点,x,i,(,i,=1,，,2,，,，,n,)(,a,x,1,x,2,x,n,b,),。,适当的,选取求积节点,x,i,和求积系数,A,i,，可以使得该插值公式具有,2,n,-1,次代数精度。,高斯求积公式和高斯求积点。,第二章 数值积分,求积节点可选择的情况,高斯求积公式,提高精度,n,=1,：,中点公式,n,=2,：具有,3,次代数精度。,对于任意区间,a,b,，,第二章 数值积分,求积节点可选择的情况,高斯求积公式,提高精度,高斯点的特点,节点,x,i,(,i,=1,，,2,，,，,n,),是高斯点的充要条件是：多项式 与一切次数,n,-1,的多项式,p,(,x,),正交，即成立：,高次的高斯公式不便于应用，一般可借鉴复合求积方法,第二章 数值积分,求积节点可选择的情况,高斯求积公式,提高精度,高斯求积公式的余项,Gauss,型,求积公式总是稳定的。,设,f,在,a,b,上连续，则Gauss,型求积公式是收敛的,高斯求积公式的稳定性,高斯求积公式的收敛性,第三章 常微分方程的差分方法,欧拉方法,改进的欧拉方法,龙格,-,库塔方法,亚当姆斯方法,收敛性与稳定性,方程组与高阶方程的情形,边值问题,重点：,构造某种格式,格式的收敛性和稳定性,格式的精度,第三章 常微分方程的差分方法,典型的微分方程,(,一阶方程的初值问题,),求解的核心,消除导数,离散化方法,差分方法是一类重要的数值解法,初值问题 的解表示过点 的一条,曲线,初值问题 的数值解表示一组,离散点列,第三章 常微分方程的差分方法,局部截断误差,整体截断误差,设 是,准确,的，用某种方法计算 时产生的截,断误差，称为该方法的,局部截断,误差,称 为某方法在点 的,整体截断,误差,去掉,准确,的前提,如果其局部截断误差为,O(,h,p,+1,),，称该数值方法的精度是,p,阶的,定义精度,判断收敛性,第三章 常微分方程的差分方法,Euler,方法,差商代替导数,隐式,Euler,方法,向后差商,两步,Euler,格式,中心差商公式,第三章 常微分方程的差分方法,微分方程转化为积分方程,选取不同的数值积分公式,不同的离散方法,(,差分格式,),矩形格式,梯形格式,第三章 常微分方程的差分方法,改进的欧拉方法：预报,-,校正系统,第三章 常微分方程的差分方法,龙格,-,库塔方法,高精度,(,构造！,),思想核心,是如何确定,区间,x,n,x,n,+1,上的平均斜率,第三章 常微分方程的差分方法,龙格,-,库塔方法,高精度,(,构造！,),思想,核心,是如何确定,区间,x,n,x,n,+1,上的平均斜率,第三章 常微分方程的差分方法,龙格,-,库塔方法,二阶龙格,-,库塔：取,x,n,和,x,n+p,=,x,n,+ph,，,0,p,1,。合理的确定,、,p,，以提高精度。,有：,p=,1/2,。,二阶,Runge-Kutta,格式（二阶精度）,=,1/2,，,p=,1,，改进的,Euler,公式；,=,1,，,p=,1/2,，变形的,Euler,公式,中点公式,；,类似可得,三,阶,Runge-Kutta,格式（三阶精度）,第三章 常微分方程的差分方法,龙格库塔方法的基本思想,亚当姆斯方法的基本思想,第三章 常微分方程的差分方法,亚当姆斯方法,基本思想：利用,x,n,，,x,n,-1,，,x,n,-2,上的斜率值减少计算,y,n,+1,的计算量或提高精度。,取合理的,，使上述格式具有二阶精度,二阶,Adams,格式（,=-1/2,）,第三章 常微分方程的差分方法,亚当姆斯方法,斜率外推变成内插（改善精度）,隐式亚当姆斯格式,三阶,四阶,二阶隐式,Adams,格式,第三章 常微分方程的差分方法,收敛性与稳定性,收敛性问题,若 ，则称该方法收敛。,欧拉格式：,如果初值准确，则有,h,0,e,n,0,，,Euler,格式收敛。,第三章 常微分方程的差分方法,收敛性与稳定性,稳定性问题,每一步的计算并不严格准确，存在计算误差的传播问题,扰动。若则称为稳定的。,第四章 方程根的迭代法,迭代过程的收敛性,迭代过程的加速,牛顿法,弦截法,重点：,不动点理论,写出有收敛性的格式，用于解题,第四章 方程根的迭代法,迭代法基本思想,从给定的一个或几个初始近似值,(,初始值,),x,0,、,x,1,、,x,2,、,、,x,r,出发，按某种方法产生的一个序列,x,0,，,x,1,，,x,2,，,，,x,r,，,x,r+,1,，,，,x,k,，,称为迭代序列，使得此序列,收敛,于方程,f,(,x,)=0,的一个根,x,*,。,当,k,足够大时，取,x,k,作为,x,*,的近似值。,需要讨论的问题 迭代法的构造,(,迭代格式,),；迭代序列的收敛性和收敛速度；误差估计。,第四章 方程根的迭代法,迭代格式,如何构造序列,x,0,，,x,1,，,x,2,，,，,x,k,如何判断迭代格式的好坏,收敛性及收敛速度,误差估计,第四章 方程根的迭代法,收敛性,解的收敛与初值选取范围有关。,大范围收敛,：从任何可取的初始值出发都能保证收敛；,局部收敛,：初始值充分接近于所要求的根，如果存在邻域,：，使迭代过程对于任何初值,x,0,均收敛。,收敛速度,收敛阶数,令 若存在实数,和非零常数,C,，使得 则称该迭代法为,阶收敛，或者说收敛阶数为,。,第四章 方程根的迭代法,将非线性方程,f,(,x,)=0,化为等价方程,x,=,g,(,x,),f,(,x,)=0,x,=,g,(,x,),（迭代函数）,等价变换,f,(,x,),的根,g,(,x,),的不动点,第四章 方程根的迭代法,假设,g,(,x,),为定义在有限区间,a,，,b,上的一个实函数，满足下列条件：,(1)(2),存在,0,L,1,，对于任意,x,a,，,b,，成立,则对任意的初始值,x,0,a,，,b,，由,Picard,迭代产生的序列都收敛于,g,(,x,),的唯一不动点,x*,，并有误差估计式,不动点迭代,不动点理论（压缩映像原理）,定理,1,第四章 方程根的迭代法,封闭性条件,压缩性条件,判断结果的精度,速度,迭代步数估计,1,）两个条件：,(1),(2),存在,0,L,2),阶连续导数，,x*,是方程,f(x,)=0,的单根，则当,x,0,充分接近,x*,时，,Newton,法收敛，且至少为二阶收敛。,Newton,法的收敛性与,x,0,的选取有关,牛顿迭代法的优缺点,优点：在单根附近,牛顿迭代法具有平方收敛,(,至少,),的 速度，所以在迭代过程中只要迭代几次就会得 到很精确解,。,缺点,:,1.,重根情形下为局部线性收敛,;,2.,牛顿迭代法计算量比较大,:,因每次迭代除计算 函数值外还要计算导数值,;,3选定的初值要接近方程的解，否则有可能得不 到收敛的结果,;,第四章 方程根的迭代法,第四章 方程根的迭代法,弦截法,导数计算比较复杂，采用差商公式替换,Newton,公式中的导数，有：,当,x,0,充分接近,x*,，,0|,g,(,x,)|1,，从而线性收敛,提高收敛速度？,第五章 线性方程组的迭代法,迭代公式的建立,迭代过程的收敛性,迭代法的基本原理,Jacobi,迭代,Gauss-Seidel,迭代,SOR,法,第五章 线性方程组的迭代法,迭代公式的建立,与解,f,(,x,)=0,的,不动点迭代,相似,，,将方程组,等价改写成 形式，从而建立,迭代格式,，从 出发，生成迭代序列,第五章 线性方程组的迭代法,迭代过程的收敛性,定理,1,迭代法 收敛的充要条件是,定理,2,若,|M|1,，则迭代格式 收敛。,定理,3,误差估计式,若,|M|1,，则近似解,x,(,k,),满足,第五章 线性方程组的迭代法,雅可比迭代,设线性方程组,Ax,=,b,的系数矩阵,A=,a,ij,n,n,非奇异，且主对角元素,a,ii,0,，,i,=1,，,2,，,，,n,。将,A,分解为,从而有：,Dx=b-(L+U)x,或,x=-D,-1,(L+U)x+D,-1,b,对角占优,对角占优方程组的,Jacobi,迭代收敛,M,g,第五章 线性方程组的迭代法,高斯,-,塞德尔迭代,x,(,k,),=-(,D,+,L,),-1,Ux,(,k-,1),+(,D,+,L,),-1,b,x,(,k,),=D,-1,(b-Lx,(,k,),-Ux,(,k-,1),),x=-D,-1,(L+U)x+D,-1,b,M,g,M,g,x,(,k,),=D,-1,(b-Lx,(,k-,1),-Ux,(,k-,1),),第五章 线性方程组的迭代法,松弛法,(Gauss-Seidel,的加速方法,),为松弛因子，,0,2,。,取,x,(,k,),=,D,-1,(,b,-,Lx,(,k,),-,Ux,(,k,-1),),，则有,:,x,(,k,),=,(,D,-1,(,b,-,Lx,(,k,),-,Ux,(,k,-1),),+(1-,),x,(,k,-1),超松弛法（,SOR,法）,1,2,。,注意,准确性、精度、有效数字的概念贯穿于各个求解过程当中,考试中没有特别复杂的计算,要把解题思想写清楚,低阶的公式应该记住,