数值分析计算方法复习(典型例题)ppt课件.ppt
计算方法复习,典型概念例题,Final Exam Review,零 绪论,误差及算法,误差,算法,分类,度量,传播,舍入,截断,绝对,相对,有效数字,一元函数,n元函数,一 插值与逼近,例1,观测物体过原点的直线运动,得到所示数据,求运动方程.,解,作直线模型: at+s=0,n为观测点数,定义残差向量:,所以:,令:,所求运动方程为:,二 数值积分,数值积分,基本概念,Gauss求积公式,代数精度,插值型求积公式,收敛及稳定性,数值求积思想,N-C公式,Romberg求积公式及外推加速,梯形公式,辛普森公式,例2,试确定常数A,B,C及,使求积公式:,解,代数精确度尽可能高，并确定上述公式的代数精确度。是否为高斯型求积公式.,令:,整理得:,所以代数精确度为5次.,因为代数精确度为23=5次,是高斯型求积公式.,标准Simpson公式:,复化 Simpson 公式,将区间0,1划分为8等分,应用复化梯形法求得,=0.9456909,例1,解,应用复化Simpson法计算,得,比较上面两个结果T8和S4,它们都需要提供9个点上的函数值工作量基本相同,然而精度却差别很大.,同积分的准确值I(f)=0.9460831比较,复化梯形法的结果T8=0.9456909只有两位有效数字, 而复化,Simpson法的结果S4=0.9460832却有六位有效数字.,=0.9456909,三 线性方程组,直接法,Gauss消去法,矩阵三角分解法,向量和矩阵范数,追赶法,矩阵条件数,三 线性方程组,迭代法,基本概念,雅可比迭代,迭代收敛速度,高斯-塞德尔迭代,迭代格式,收敛条件,SOR迭代,常用的算子范数：,（行范数）,（列范数）,（谱范数(spectral norm)）,定义7,设ARnn的特征值为i: (i=1,n),称为A的谱半径.,特殊地：,Hamilton-Cayley定理,设 A 是一个n阶方阵，特征多项式为,则,（的n次多项式）,当k 时，Bk 0 ( B ) 1,设线性方程组x=Bx+g有惟一解，那么逐次逼近法对任意初始向量x收敛的充分必要条件是迭代矩阵B的谱半径 ( B ) 1,因此,一、逐次逼近法收敛的条件,定理2,定理3,证明,例3,解,设线性方程组 的系数矩阵为:,(1)写出Jacobi 迭代法的迭代格式,(2)确定a的取值范围，使方程组对应的Gauss-Seidel迭代收敛。,(1) 线性方程组,Jacobi 迭代,(2) 线性方程组,Gauss-Seidel迭代矩阵:,令,得,四 非线性方程求根,求根法,二分法,不动点迭代法及收敛性理论,牛顿迭代法,插值型迭代,弦截法,抛物线法,f (x) = 0,x = g (x),f (x) 的根,g (x) 的不动点,2 单个方程的迭代法,f(x)=0化为等价方程x=g(x)的方式是不唯一的,有的收敛,有的发散 For example：2x3-x-1=0,一、不动点迭代,由此可见，这种迭代格式是发散的,则迭代格式为,(1) 如果将原方程化为等价方程,取初值,(2) 如果将原方程化为等价方程,仍取初值,x3 = 0.9940 x4 = 0.9990 x5 = 0.9998x6 = 1.0000 x7 = 1.0000,已经收敛,故原方程的解为 x = 1.0000,同样的方程 不同的迭代格式 有不同的结果,什么形式的迭代法能够收敛呢?,依此类推,得,局部收敛性定理,设x*为g的不动点, g(x)与g(x)在包含x*的某邻域U(x*) (即开区间)内连续, 且|g(x*)|0,当x0 x*- , x*+ 时, 迭代法产生的序列xkx*- , x*+ 且收敛于x*.,定理2,用一般迭代法求x3-x-1=0的正实根x*,容易得到: g(x)在包含x*的某邻域U(x*) 内连续，且|g(x*)|1,将方程变形成等价形式：,则迭代函数为:,因此迭代格式 在x*附近收敛,例4,解,用一般迭代法求方程x-lnx2在区间(2, )内的根，要求|xk-xk-1|/|xk|=10-8,令f(x)=x-lnx-2,f(2)0,故方程在(2,4)内至少有一个根,因此f(x)=0在(2, )内仅有一个根x*,将方程化为等价方程：x2lnx,x (2, 4),例5,解,因此， x0(2, ), xk+12lnxk产生的序列 xk 收敛于x*,取初值x03.0,计算结果如下：,k xi 0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781,5 3.1457022096 3.1460371437 3.1461436118 3.1461774529 3.146188209,10 3.14619162811 3.14619271412 3.14619306013 3.14619316914 3.146193204,另一种迭代格式,0 3.000000000 1 3.147918433,2 3.1461934413 3.146193221,五 常微分方程数值解,数值解法,单步法,线性多步法,方程组与高阶方程,重要概念,重要构造方法,局部截断误差,方法精度,差分构造,泰勒展式构造,积分构造,例5,解,给定求解常微分方程初值问题,的线性多步公式,试确定系数,并推导其局部截断误差主项。,使它具有尽可能高的精度，,线性多步公式局部截断误差,此时:,令:,得:,所以当:,为三阶多步公式.,局部截断误差主项为:,六 特征值特征向量,特征值及特征向量解法,迭代法,变换法,重要概念,特征值特征向量,QR分解,变换,正交相似,反射,平面旋转,幂法,反幂法,雅可比法,QR法,(1)QR算法的基本思想,记 AA1且有A1Q1R1.,将等号右边两个矩阵因子的次序交换，得 A2R1Q1,不难证明:,即,矩阵序列Ak有相同的特征值.,因为上Hessenberg矩阵次对角线以下的元素全为0, 因此, 只要证明, 当k时, 由迭 代格式产生的矩阵Ak的次对角元趋向于零就可以了.,记,容易得到 是Ak的一个QR分解,如果A是一个满秩的上Hessenberg矩阵, 可以证明, 经过一个QR迭代步得到的A2Q-11A1Q1仍然是上Hessenberg矩阵.,例4,设矩阵,试用QR算法求它的特征值。,乘幂法是适用于求一般矩阵按模最大特征值及相应特征向量的算法.,设A是n阶矩阵, 其n个特征值按模从大到小排序为,又假设关于1, 2, , n的特征向量v1, v2, ,vn线性无关,一、乘幂法,任意取定初始向量x0,建立迭代公式 ：,故当k时， xk1ka1v1.,因此，xk可看成是关于特征值1的近似特征向量,有一严重缺点，当|1|1 （或| 1 |1时）vk中不为零的分量将随k的增大而无限增大，计算机就可能出现上溢（或随k的增大而很快出现下溢）,因此，在实际计算时，须按规范法计算，每步先对向量xk进行“规范化”。,迭代格式改为:,因为,对任意给定的初始向量x0,类似地,当10时,按模最大特征值1及其相应的特征向量v1的乘幂法的计算公式：,当10时,若1为A的实重根, 幂法仍然有效.,
