数值代数主要知识点

1、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矩阵计算的分解方

2、法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 Greengar

3、d和Vladinimir Rokhlin发明的快速多级 算法数值代数上课内容：一、 预备知识 （基础）1）误差分析2）范数理论3）初等变换与矩阵分解二、 线性方程组的求解1）直接法2）迭代法3）最小二乘问题与矩阵广义逆 三、 矩阵特征值问题1）普通特征值问题a) 幂法和反幂法b) QR方法2）对称特征值问题各部分的主要知识要点：（主要看上课笔记）一、预备知识 （基础）1 误差分析基本要求：1） 了解数值代数的研究对象与特点及主要研究内容2） 了解误差的基本知识及误差来源、误差种类3） 了解浮点运算和舍入误差分析4） 了解算法的评价及算法的向后稳定2范数理论基本要求：1） 熟练掌握向量范数的定义

4、，会判断给定的某个函数是否是向量范数 （范数的三个条件 正定性、齐次性和三角不等式）2） 了解常用向量范数 、范数等价定理3） 熟练掌握矩阵范数的定义，会判断给定的某个函数是否是矩阵范数 （范数的三个条件 正定性、齐次性和三角不等式）4） 熟练掌握几个特殊的矩阵范数算子范数、相容范数、酉不变范数的定义5） 掌握常用矩阵范数 1范数，2范数，范数，F范数的定义，并清楚且会证明它们分别属于算子范数、相容范数、酉不变范数的那一种范数6） 会证明常用的范数不等式7） 了解矩阵的谱和谱半径的定义二、 初等变换与矩阵分解1初等变换（主要看上课笔记）基本要求：1） 了解初等变换的一般形式和一般初等变换的性质

5、2） 熟练掌握两种特殊的初等变换Gauss消元变换、Household变换a) 熟练掌握Gauss消元变换的定义和性质，特别是消元性质，会利用Gauss消元变换对向量进行消元 b) 熟练掌握Householder变换/初等Hermit阵 的定义和性质，特别是变换性质和消元性质，会利用Householder变换对向量进行消元，会求Householder变换矩阵3)熟练掌握Givens旋转变换的定义和性质，特别是消元性质即消元特点，会灵活运用Givens旋转变换对向量进行消元 （消调某一个变量）4）了解交换阵的定义即性质2 矩阵分解1、基于Gauss消元阵的分解 基于Gauss消元阵的分解，包括

6、无主元LU分解、列主元LU分解、对称正定阵的Cholesky分解基本要求：1） 熟练掌握无主元LU分解的具体过程，会写出相应的程序，给定一个矩阵，会计算它的LU分解矩阵2） 了解LU分解的不稳定性和LU分解的唯一性及存在条件3） 熟练掌握列主元LU分解的具体过程，会写出相应的程序，给定一个矩阵，会计算它的PLU分解矩阵4） 会计算对称正定阵的Cholesky分解可通过LU分解或元素比较法求解5） 了解带状矩阵的定义及带状矩阵的LU分解特点，特别是会计算三对角矩阵的LU分解矩阵2、 基于Householder变换的矩阵约简基于Householder变换的矩阵约简，包括 OR分解、上Hessenb

7、erg分解基本要求：1) 了解矩阵的QR分解定理，会利用ramSchmidt正交化方法和Householder变换方法对给定矩阵A进行QR分解，并会熟练写出分解程序。2) 了解QR分解的行修改问题的QR分解方法（充分利用已有的结果）若已知A的QR分解，a是n为列向量，如何求 的QR分解 注：利用Givens旋转变换 3) 清楚上Hessenberg分解的想法及分解的具体过程，给定一个矩阵，熟练求出其上Hessenberg分解，了解该分解的用处计算矩阵特征值4) 了解 关于上Hessenberg分解的几点说明 （5条 ） 会证明 Q及H由A及Q的第一列确定3、奇异值分解（SVD）（主要看上课笔记

8、和课件）基本要求：1）了解矩阵奇异值的定义和奇异值分解定理2了解奇异值分解定理的证明过程3） 掌握正交投影的定义及正交投影算子的定义和计算4） 了解矩阵A的值域、零空间及其各自正交补空间的正交投影算子与SVD分解中两个酉阵的关系4、矩阵的Schur分解定理基本要求：了解矩阵的Schur分解定理的内容及证明过程三、 线性方程组的求解1）直接法2）迭代法3）最小二乘问题与矩阵广义逆1 直接法 （参考 蒋长锦 第二章）基本要求1）了解直接构造法的一般思想2）会用回代方法解三角方程组，并编写程序3）对三对角方程组会利用追赶法求解，并编写程序4）结合矩阵的常用分解可得几个基本直接法。给定一个线性方程组，

9、会利用LLI、PLU和QR分解等方法分解方程组2线性方程组的扰动分析基本要求1）了解计算解与精确解的相对误差、绝对误差2）掌握并会灵活应用Banach引理3）熟练掌握矩阵的条件数的概念，了解条件数的性质，会利用条件数判断问题、良态、坏条件、病态。4）了解参差的概念3线性方程组的迭代法基本要求1）了解迭代法的一般想法2）理解迭代法要解决的几个问题（1）如何构造迭代格式 （2）迭代序列是否收敛（3）收敛速度（4）何时停机 （5）误差估计3）了解迭代法的构造思想，了解迭代矩阵的概念4）掌握迭代收敛的充要条件、充分条件；会判断一个迭代格式是否收敛迭代 收敛5）会对迭代格式进行误差估计，确定停机准则或最

10、大迭代步数6）了解迭代的平均收敛速度和渐近收敛速度的定义7）熟练掌握三个常用迭代法的迭代格式（矩阵形式、分量形式），会求它们的迭代矩阵。掌握收敛条件/收敛准则，给定一个方程组，会利用三种迭代中某种指定迭代法求解。4大型稀疏实对称方程组的lancaos方法（暂略），共轭梯度法（最优化中会讲）四、 最小二乘问题1，最小二乘问题1）了解最小二乘问题的来源，最小二乘问题的表达方式2）了解最小二乘问题解的存在性3）了解法方程组/正规方程的概念4）会求最小二乘问题的通解5）了解极小范数最小二乘问题，解的存在性、唯一性6）了解常用的数值解法正规方程法QR分解法BJorok方法2Moor-Penrose广义逆基本要求1）了解矩阵的广义逆的定义2）了解广义逆的的基本性质和特殊性质3）熟练计算一个给定矩阵的广义逆3广义逆与最小二乘问题会利用广义逆表示最小二乘问题的解第五部分 普通特征值问题1矩阵特征值的基本性质 41）了解第一圆盘定理、第二圆盘定理2幂法原理1）了解幂法的基本原理2）会利用