数值代数主要知识点

20世纪最好的十个算法(ComputinginScience&Engineering评选)1.1946.LosAlamos的VonNeumann,StanVlam,NickMetropolis编的Metropolis算法,即MonteCarlo方法2.1947兰德公司的GrorgeDantzig创造的线性规划的单纯性算法3.1950.美国国家标准局数值分析所的MagnusHestenes,EdwardStiefel,CorneliusLanczos的Krylovz空间迭代法4.1951橡树岭国家实验室的AlstonHouseholder矩阵计算的分解方法5.1951JohnBackus在IBM领导的小组研制的Fortron最优编译程序6.1959-61伦敦的FerrantiLtd的J.G.F.Francis的称为QR的算法的计算机本征值的稳定的算法7.1962London的ElliotBrothersLtd的TonyHoare提出的快速(按大小)分类法8.1965IBM的Cooley与Princeton及Bell的Turkey的FFT算法9.1977BrighhamYoung大学的HelamanFerguson和RodneyForcede的整数关系侦察算法10.1987Yale的LeslieGreengard和VladinimirRokhlin发明的快速多级算法数值代数上课内容：一、预备知识（基础）1）误差分析2）范数理论3）初等变换与矩阵分解二、线性方程组的求解1）直接法2）迭代法3）最小二乘问题与矩阵广义逆三、矩阵特征值问题1）普通特征值问题a)幂法和反幂法b)QR方法2）对称特征值问题各部分的主要知识要点：（主要看上课笔记）一、预备知识（基础）§1误差分析基本要求：1）了解数值代数的研究对象与特点及主要研究内容2）了解误差的基本知识及误差来源、误差种类3）了解浮点运算和舍入误差分析4）了解算法的评价及算法的向后稳定§2范数理论基本要求：1）熟练掌握向量范数的定义，会判断给定的某个函数是否是向量范数（范数的三个条件正定性、齐次性和三角不等式）2）了解常用向量范数、范数等价定理3）熟练掌握矩阵范数的定义，会判断给定的某个函数是否是矩阵范数（范数的三个条件正定性、齐次性和三角不等式）4）熟练掌握几个特殊的矩阵范数－算子范数、相容范数、酉不变范数的定义5）掌握常用矩阵范数1－范数，2－范数，－范数，F－范数的定义，并清楚且会证明它们分别属于算子范数、相容范数、酉不变范数的那一种范数6）会证明常用的范数不等式7）了解矩阵的谱和谱半径的定义二、初等变换与矩阵分解§1初等变换（主要看上课笔记）基本要求：1）了解初等变换的一般形式和一般初等变换的性质2）熟练掌握两种特殊的初等变换－Gauss消元变换、Household变换a)熟练掌握Gauss消元变换的定义和性质，特别是消元性质，会利用Gauss消元变换对向量进行消元b)熟练掌握Householder变换/初等Hermit阵的定义和性质，特别是变换性质和消元性质，会利用Householder变换对向量进行消元，会求Householder变换矩阵3)熟练掌握Givens旋转变换的定义和性质，特别是消元性质即消元特点，会灵活运用Givens旋转变换对向量进行消元（消调某一个变量）4）了解交换阵的定义即性质§2矩阵分解1、基于Gauss消元阵的分解基于Gauss消元阵的分解，包括无主元LU分解、列主元LU分解、对称正定阵的Cholesky分解基本要求：1）熟练掌握无主元LU分解的具体过程，会写出相应的程序，给定一个矩阵，会计算它的LU分解矩阵2）了解LU分解的不稳定性和LU分解的唯一性及存在条件det()0(1,2,,).1nnkknARDAknALUALU若阶方阵的顺序主子式则可唯一地分解为一个单位下三角阵和非奇异的上三角阵的乘积。即定理（矩阵分解定理）3）熟练掌握列主元LU分解的具体过程，会写出相应的程序，给定一个矩阵，会计算它的PLU分解矩阵4）会计算对称正定阵的Cholesky分解－可通过LU分解或元素比较法求解5）了解带状矩阵的定义及带状矩阵的LU分解特点，特别是会计算三对角矩阵的LU分解矩阵2、基于Householder变换的矩阵约简基于Householder变换的矩阵约简，包括OR分解、上－Hessenberg分解基本要求：1)了解矩阵的QR分解定理，会利用Ｇram－Schmidt正交化方法和Householder变换方法对给定矩阵A进行QR分解，并会熟练写出分解程序。2)了解QR分解的行修改问题的QR分解方法（充分利用已有的结果）若已知A的QR分解，a是n为列向量，如何求0TAAa的QR分解注：利用Givens旋转变换0Q1,12,11,1100GnnGnGnA3)清楚上－Hessenberg分解的想法及分解的具体过程，给定一个矩阵，熟练求出其上－Hessenberg分解，了解该分解的用处－计算矩阵特征值4)了解关于上－Hessenberg分解的几点说明（5条）会证明Q及H由A及Q的第一列确定3、奇异值分解（SVD）（主要看上课笔记和课件）基本要求：1）了解矩阵奇异值的定义和奇异值分解定理ＳＶＤ2了解奇异值分解定理的证明过程3）掌握正交投影的定义及正交投影算子的定义和计算4）了解矩阵A的值域、零空间及其各自正交补空间的正交投影算子与SVD分解中两个酉阵的关系4、矩阵的Schur分解定理基本要求：了解矩阵的Schur分解定理的内容及证明过程三、线性方程组的求解1）直接法2）迭代法3）最小二乘问题与矩阵广义逆§1直接法（参考蒋长锦第二章）基本要求1）了解直接构造法的一般思想2）会用回代方法解三角方程组，并编写程序3）对三对角方程组会利用追赶法求解，并编写程序4）结合矩阵的常用分解可得几个基本直接法。给定一个线性方程组，会利用LLI、PLU和QR分解等方法分解方程组§2线性方程组的扰动分析基本要求1）了解计算解与精确解的相对误差、绝对误差2）掌握并会灵活应用Banach引理3）熟练掌握矩阵的条件数的概念，了解条件数的性质，会利用条件数判断问题、良态、坏条件、病态。4）了解参差的概念§3线性方程组的迭代法基本要求1）了解迭代法的一般想法2）理解迭代法要解决的几个问题（1）如何构造迭代格式（2）迭代序列是否收敛（3）收敛速度（4）何时停机（5）误差估计3）了解迭代法的构造思想，了解迭代矩阵的概念4）掌握迭代收敛的充要条件、充分条件；会判断一个迭代格式是否收敛迭代(1)()(0,1,2,)kkxBxgk收敛0()1kBB()(1)()1,.kkxBxgBB迭代法收敛的充分条件如果迭代格式的迭代矩阵的某一种范数则此迭代格式收敛5）会对迭代格式进行误差估计，确定停机准则或最大迭代步数6）了解迭代的平均收敛速度和渐近收敛速度的定义7）熟练掌握三个常用迭代法的迭代格式（矩阵形式、分量形式），会求它们的迭代矩阵。掌握收敛条件/收敛准则，给定一个方程组，会利用三种迭代中某种指定迭代法求解。§4大型稀疏实对称方程组的lancaos方法（暂略），共轭梯度法（最优化中会讲）四、最小二乘问题§1，最小二乘问题1）了解最小二乘问题的来源，最小二乘问题的表达方式2）了解最小二乘问题解的存在性3）了解法方程组/正规方程的概念4）会求最小二乘问题的通解5）了解极小范数最小二乘问题，解的存在性、唯一性6）了解常用的数值解法①正规方程法②QR分解法③BJorok方法§2Moor-Penrose广义逆基本要求1）了解矩阵的广义逆的定义2）了解广义逆的的基本性质和特殊性质3）熟练计算一个给定矩阵的广义逆§3广义逆与最小二乘问题会利用广义逆表示最小二乘问题的解第五部分普通特征值问题§1矩阵特征值的基本性质41）了解第一圆盘定理、第二圆盘定理§2幂法原理－1）了解幂法的基本原理2）会利用幂法计算矩阵的最大特征值对应特征向量3）了解幂法的基本算法并会利用反幂法计算矩阵的最小特征值及特征向量4）了解反幂法的基本算法并会利用反幂法计算矩阵的最小特征值及特征向量5）掌握Rayleigh商的定义§QR方法（十大计算法之一）1）理解QR迭代的过程2）掌握QR方法的改进技术——上Hesenbeng化3）掌握位移技巧——双步位移QR迭代