数值代数主要知识点.doc

20世纪最好的十个算法 ( Computing in Science Engineering 评选 ) 1.1946.Los Alamos的Von Neumann,Stan Vlam,Nick Metropolis编的? Metropolis算法,即Monte Carlo方法 2.1947兰德公司的Grorge Dantzig创造的线性规划的单纯性算法 3.1950.美国国家标准局数值分析所的Magnus Hestenes,Edward Stiefel,? Cornelius Lanczos的Krylovz空间迭代法 4.1951 橡树岭国家实验室的Alston Householder矩阵计算的分解方法 5.1951 John Backus在IBM领导的小组研制的Fortron最优编译程序 6.1959-61 伦敦的Ferranti Ltd的J.G.F.Francis的称为QR的算法的计算机? 本征值的稳定的算法 7.1962London的Elliot Brothers Ltd的Tony Hoare提出的快速(按大小)分? 类法 8.1965 IBM的Cooley与Princeton及Bell的Turkey的FFT算法 9.1977 Brighham Young大学的Helaman Ferguson和Rodney Forcede的整数? 关系侦察算法 10.1987 Yale的Leslie Greengard和Vladinimir Rokhlin发明的快速多级?? 算法 1）误差分析 2）范数理论 3）初等变换与矩阵分解 二、 线性方程组的求解 1）直接法 2）迭代法 3）最小二乘问题与矩阵广义逆 三、 矩阵特征值问题 1）普通特征值问题 幂法和反幂法 QR方法 2）对称特征值问题 各部分的主要知识要点：（主要看上课笔记） 一、预备知识 （基础） §1 误差分析基本要求： 了解数值代数的研究对象与特点及主要研究内容 了解误差的基本知识及误差来源、误差种类 了解浮点运算和舍入误差分析 了解算法的评价及算法的向后稳定 §2范数理论 基本要求： 熟练掌握向量范数的定义，会判断给定的某个函数是否是向量范数 （范数的三个条件 正定性、齐次性和三角不等式） 了解常用向量范数 、范数等价定理 熟练掌握矩阵范数的定义，会判断给定的某个函数是否是矩阵范数 （范数的三个条件 正定性、齐次性和三角不等式） 熟练掌握几个特殊的矩阵范数－算子范数、相容范数、酉不变范数的定义 掌握常用矩阵范数 1－范数，2－范数，－范数，F－范数的定义，并清楚且会证明它们分别属于算子范数、相容范数、酉不变范数的那一种范数 会证明常用的范数不等式 了解矩阵的谱和谱半径的定义 二、 初等变换与矩阵分解 §1初等变换（主要看上课笔记） 基本要求： 了解初等变换的一般形式和一般初等变换的性质 熟练掌握两种特殊的初等变换－Gauss消元变换、Household变换 熟练掌握Gauss消元变换的定义和性质，特别是消元性质，会利用Gauss消元变换对向量进行消元 b) 熟练掌握Householder变换/初等Hermit阵 的定义和性质，特别是变换性质和消元性质，会利用Householder变换对向量进行消元，会求Householder变换矩阵 3)熟练掌握Givens旋转变换的定义和性质，特别是消元性质即消元特点，会灵活运用Givens旋转变换对向量进行消元 （消调某一个变量） 4）了解交换阵的定义即性质 §2 矩阵分解 1、 熟练掌握列主元LU分解的具体过程，会写出相应的程序，给定一个矩阵，会计算它的PLU分解矩阵 会计算对称正定阵的Cholesky分解－可通过LU分解或元素比较法求解 了解带状矩阵的定义及带状矩阵的LU分解特点，特别是会计算三对角矩阵的LU分解矩阵 基于Householder变换的矩阵约简 基于Householder变换的矩阵约简，包括 OR分解、上－Hessenberg分解 基本要求： 了解矩阵的QR分解定理，会利用Ｇram－Schmidt正交化方法和Householder变换方法对给定矩阵A进行QR分解，并会熟练写出分解程序。 了解QR分解的行修改问题的QR分解方法（充分利用已有的结果） 若已知A的QR分解，a是n为列向量，如何求 的QR分解 注：利用Givens旋转变换 清楚上－Hessenberg分解的想法及分解的具体过程，给定一个矩阵，熟练求出其上－Hessenberg分解，了解该分解的用处－计算矩阵特征值 了解 关于上－Hessenberg分解的几点说明 （5条 ） 会证明 Q及H由A及Q的第一列确定 3、 收敛 5）会对迭代格式进行误差估计，确定停机