
本书讨论了数值线性代数涉及的基础内容:正交化、最小二乘问题和正交相似变换;Gauss消去法、三角分解、大型稀疏矩阵的Cholesky分解和QR分解;线性方程组的迭代解法(包括古典迭代法、加速方法、多重网格方法和现代迭代法);特征值的计算(包括幂法、Jacobi方法、QR算法、奇异值分解和对称(三对角)矩阵的特征值计算);大型稀疏矩阵的特征值计算(包括Lanczos方法、子空间迭代法、Rayleigh—Ritz投影方法、Arnoldi迭代法和Jacobi.Davidson方法)。书中对一些重要的算法给出了相应的并行算法,同时对大型稀疏矩阵也给出了相关讨论。每章后附大量习题并在全书最后统一给出了绝大部分的解答。
书中内容深入浅出,理论联系实际,适用于普通高等院校数学专业课程教学,同时也可供有一定数学基础的学生自学或作为数值实验、并行算法等相关专业课程的辅助教材及教师参考书。
给定矩阵A ∈ Rn×n ,数值线性代数研究三个基本问题:第一个是A的LU分解;第二个是A的QR分解;第三个是A的Hessenberg分解A=UHUT ,其中U为正交矩阵,H为(上)Hessenberg矩阵.有两种方法贯穿这三个问题的始终,它们分别是直接约化和直接法.直接约化就是对A进行操作,最终把它变为上三角矩阵或上Hessenberg矩阵.直接法类似方程求解,要求解的变量需要按照一定规则来计算.对于LU分解,直接约化和直接法分别为Gauss消去法和直接三角分解方法.对于QR分解,直接约化为Householder方法或者平面旋转方法,而直接法为Gram-Schmidt(正交化)方法.对于Hessenberg分解,直接约化还是Householder方法或者平面旋转方法,而直接法为Arnoldi方法.直接约化和直接法对上述三个问题求解的结果最多相差一个符号,这由分解的唯一性来保证.
Gauss消去法通常用于LU分解,它也可以用于Hessenberg分解,但Hessenberg分解中要求U为非奇异矩阵.Gauss消去法往往会把原来很大的元素变为很小,从而导致数值上的不稳定,所以需要主元技术确保被变换矩阵中的元素大小之间不会差别太大.Householder方法或者平面旋转方法(也称正交化技术)保持向量的2-范数不变,被变换的矩阵中的元素不会产生量级上的差异,从而在数值上是相当稳定的.所以正交化技术往往不需要选主元.但例外的是列主元的QR分解,它包含了主元技术,原因在于原来的矩阵可能不是列满秩的或接近秩亏.
对于LU分解,主元技术在直接约化和直接法中都得到了体现,如列主元的Gauss消去法和列主元的直接三角分解.但是主元技术没有在QR分解的直接法(Gram-Schmidt方法)和Hessenberg分解(包括直接法和直接约化)中得到体现.Wilkinson[8] 说过,“当用初等矩阵技术时若不允许作‘稳定化’,就不存在相应的正交矩阵技术.”所以,当有某种正交化技术时,那么也有相应的“稳定化”的初等矩阵技术.用正交化技术实现了矩阵A的QR分解,相应地可以用列主元Gauss消去法实现它的三角分解;用正交化技术实现了矩阵A的Hessenberg分解,相应地可以用列主元Gauss消去法实现它的相似分解A=THTT ,其中T为非奇异矩阵,H为上Hessenberg矩阵.
我们下面先来分别说明这三个问题如何贯穿到本书之中;接下来介绍和它们思想完全不同的迭代技术,这种技术常用于线性方程组和特征值问题的求解;最后给出一些前面没有提到的问题、方法和数学基础等.
矩阵A的LU分解详见3.2节~3.4节.不选主元的Gauss消去法仅仅用到一种行初等变换,即某行的若干倍数加到另一行中.该过程能进行的前提是A的前n. 1个顺序主子式不为0.即使该条件满足,Gauss消去法的除法运算中分母也可能接近0而导致计算不准确.为此,引入完全主元或列主元的Gauss消去法(3.2节),它们的区别在于主元的选择范围不同.主元不一定在对角线上,所以选主元的Gauss消去法需要行交换,甚至列交换.舍入误差分析(3.6节)和实践都表明列主元Gauss消去法对绝大多数矩阵在数值上都是稳定的.列主元的直接三角分解和列主元的Gauss消去法执行的结果相同(不考虑舍入误差),计算量也相同,区别在于矩阵元素的更新方式不同.当A具有带状结构时,直接三角分解和Gauss消去法需要的工作量会大大降低,它往往和带宽的平方以及矩阵的阶数大小成正比.计算量降低的原因在于LU分解具有保带宽的性质.如果用主元技术的话,LU分解不再具有保带宽性质(3.4.2节).对于对称正定矩阵,LU分解中主元必定在对角线上,所以没有必要选主元.另外,根据对称性,LU分解的工作量减半(3.4.1节).对称正定矩阵的LU分解的一个变种就是Cholesky分解(3.4.1节),它有不同的执行方式.比较受欢迎的两种方式就是列方向的Cholesky分解和子矩阵的Cholesky分解,它们的并行执行方式见3.8.5节.矩阵A的不完全三角分解A=LU+R(3.7节)主要用于迭代法中的预处理,这里要求下三角矩阵L和上三角矩阵U具有某种给定的结构,同时R要比较小,(LU).1 作用到向量上的工作量不能太大.对于大型稀疏矩阵,我们提到了它的存储格式(3.8.1节)以及Gauss消去法产生的填入如何控制等(3.8.2节).对于大型稀疏对称正定矩阵,我们详述了用于Cholesky分解的多波前方法(3.8.3节).该方法和Gauss消去树密切相关,它的并行执行方式也依赖于消去树.由于一般矩阵A的QR分解和ATA的Cholesky分解有关,多波前方法也用于大型稀疏矩阵的QR分解(3.8.4节).LU分解的主要目的是用于线性方程组Ax=b的求解.A和b的扰动对解的影响决定了问题的难易程度,为此引出矩阵条件数的概念(3.5节).条件数的估算在实际中是非常重要的,矩阵A的列主元LU分解PA=LU把A的病态性转化为U的病态性,这就是Cline等[3] 给出的条件数估计算法.我们前面指出,对A进行约化时,如果矩阵元素中的大数约化后还是变为大数,那么该过程在数值上很稳定,比如QR分解和列主元的LU分解.可以想象一个矩阵比较光滑地过渡到另一个矩阵不会改变矩阵的病态程度,猜测应该有某种正交化的方法来估算矩阵的条件数.列主元Gauss消去法的并行实现分为两种情况:第一种就是在共享内存的机器中需要实现BLAS-3级别的运算,这可以对A按列分块,每次对某一块进行消元.第二种就是在分布式内存的机器中按行对A进行分块,每个进程都占了某一块并对所占的数据负责消元操作.为了保持负载平衡,按一维卷帘方式把A存放在各个进程中.我们对每一个算法的并行执行都分为这两种情况讨论.
QR分解(第2章)在数值代数中有非常重要的地位.它可以用于线性方程组和最小二乘问题的求解,基于QR分解的QR算法用于特征值计算,Krylov子空间的正交化用于构造线性方程组的迭代解法等.2.1节给出了两个常用的正交变换工具Householder变换和平面旋转变换.它们具有把某个向量的若干分量变为0的功能,同时保持向量的2-范数不变,所以这两种变换在数值上相当稳定.一般矩阵的QR分解(2.2节)正是利用这两种变换来实现.这两种方法都是QR分解的直接约化方法,但平面旋转方法常常用于特殊结构的QR分解,如上Hessenberg矩阵的QR分解.Gram-Schmidt正交化也可以现实QR分解,但在数值上不大稳定,从而需要一些补救方法,如重新正交化方法等.当子空间的维数很高时,内存的开销变大,所以提出了不完全正交化方法,它只要保存和前面几个向量正交的向量就够了.QR分解常用于最小二乘问题(2.3节),当A不是列满秩时,应该用列主元的QR分解.Krylov子空间常用于线性方程组的迭代法和特征值问题的求解,一个主要问题就是正交基的选取,这也归结为矩阵的QR分解问题,所以也有Gram-Schmidt方法和Householder方法(2.4.3节).在第2章中,我们还给出了正交化的并行实现.
Hessenberg分解是一种正交相似变换(2.5节).和QR分解类似,它也有Householder方法和平面旋转方法,还可以通过Krylov子空间的正交化来实现.如果A的Hessenberg分解A=THTT 中的T仅仅是非奇异的,则可以通过列主元的Gauss消去法实现.需要强调的是,正交相似变换只能把一个实矩阵化到拟上三角矩阵,这就是实矩阵的Schur分解定理.实矩阵的Schur分解是某种迭代过程(如QR算法)的极限.
迭代法是数值线性代数中另一大类计算方法,下面先考虑特征值问题的迭代解法.用于特征值计算的QR算法利用了QR分解以及正交相似变换,它是一种迭代方法(5.4节).对于一般的矩阵,不大可能通过有限步运算求出特征值,即使对称三对角矩阵也是如此.QR算法首先把A∈ Rn×n 经过正交相似变换变为上Hessenberg矩阵,这一步也就是矩阵A的Hessenberg分解.以后每一步的迭代只要对上Hessenberg矩阵进行就够了,这导致了每一步只有O(n2)的计算复杂度.由于实矩阵可能存在复特征值,为了加入复运算而提出了两步位移的Francis算法(5.4节).如果A为实对称矩阵,则QR算法得到简化.此时上Hessenberg矩阵被对称三对角矩阵代替,正交相似变换通过平面旋转变换来实现,也不再需要两步位移的技巧(5.5节).QR算法的目的就是实现矩阵的Schur分解,而A的奇异值分解和ATA的Schur分解密切相关,所以对ATA用QR算法给出了矩阵A的奇异值分解(5.6节).
幂法是求主特征值和主特征向量的一种迭代方法(5.2节).该方法的主要依据在于一个向量被矩阵A不断作用后,会越来越趋向于和主特征向量平行.为了避免溢出,矩阵乘向量后得到的向量需要归一化.显然,归一化不改变每次迭代中向量的方向.幂法(几乎所有计算特征值的方法,甚至线性方程组的迭代法)的收敛速度都由矩阵的特征值分布决定,这里引出了原点平移技巧.原点平移和反幂法相结合用于计算任意一个特征值和相应的特征向量.Wieldant收缩(5.2.3节)给出了求特征值按模次大的特征对的方法,这种收缩通过对原矩阵做秩为1修正来实现.由于舍入误差的影响,不断做秩为1的修正导致以后计算特征值的误差会越来越大,所以有必要寻求能同时进行多个特征值计算的方法.对于大型稀疏矩阵,一般只要计算几个特征值,如按模最大的几个特征值.子空间迭代(5.9.1节)是一种基本方法,它是幂法的直接推广.事实上QR算法可以看成子空间迭代的特殊情况,迭代产生的子空间会收敛到主不变子空间,或者说每次迭代产生的Qk中的每列本质上收敛到相应的Schur向量.实际中常常把子空间迭代和Rayleigh-Ritz投影方法相结合(5.9.2节),原因在于产生一个子空间后,如果把A限制在该子空间上就得一个阶数比较小的矩阵,那么我们可以花费比较少的工作量(如QR算法)计算这个小矩阵的Schur向量,再利用这些Schur向量构造一个更接近主不变子空间的子空间.如果取Krylov子空间作为投影子空间,这就是Arnoldi迭代(5.9.3节).这里的子空间还有其他取法,比如Jacobi-Davidson算法(5.9.4节).子空间的维数越来越高时,矩阵在该子空间的限制产生的特征值越来越接近原矩阵的特征值分布,至少对于实对称矩阵确实如此(5.8节).但是子空间的维数变高的潜在危险就是Lanczos方法(即对称矩阵的Arnoldi方法)产生的Krylov子空间中正交基失去正交性.正因为如此,在保持维数不变的情况下,如何取更好的子空间变得非常重要.隐式重启动的Arnoldi方法(5.9.3节)考虑了如何选取q1,使得m维Krylov子空间Km(A,q1)变得更好.
前面提到的这些方法不会改变原矩阵的结构,所以常用于大型稀疏矩阵的特征值计算.另一个很经典的方法就是Jacobi方法(5.3节).它用平面旋转变换求对称矩阵的所有特征值.其特别可取之处在于算法具有并行性,但是改变了原矩阵的结构.
线性方程组常用迭代法求解(第4章).我们首先提到几种古典迭代法(4.1节~4.3节),这些迭代法对于比较特殊的矩阵可以保证收敛性,但收敛速度比较慢.比如Gauss-Seidel迭代法的误差刚开始减少比较快,但后来就很慢,所以也称为光滑迭代.为此,接下来提出了加速方法,比如外推方法和Chebyshev加速(4.4节),但这些方法需要特征值范围的大致估计.虽然光滑迭代很难减少误差的低频部分,但可以通过求解限制在粗网格上的残差方程进行校正,这就是多重网格方法的基本思想(4.6节).几何多重网格方法往往用于求解微分方程在某网格下离散后的线性方程组,网格对应于求解区域的几何网格.几何多重网格的构造往往不依赖微分方程.代数多重网格直接从线性方程组出发构造多重网格,它是一种代数意义上的网格.如果线性方程组是微分方程在某网格上离散得到的,那么构造出来的网格包含了微分方程的信息.对于具有间断系数的微分方程,这两种多重网格方法构造的网格有很大不同.
线性方程组的很多现代迭代解法(4.7节)都可以在Krylov子空间K = Km(A,r(0))的框架下推导,这里r(0) 为初始向量的残差.一个基本思想就是在Km(A,r(0))中找近似解xm使得残差b.Axm和某个m维子空间L 正交.有两种途径来提高解的近似程度.第一种是提高Krylov子空间的维数.当m增大时,Amr(0) 会接近A的主特征向量,见幂法(5.2节).也就是说,定义Krylov子空间中的向量会很快互相之间接近线性相关.用修改的Gram-Schmidt正交化方法会导致计算的正交基很容易失去正交性.所以,提高子空间维数的方法在实际中很难行得通.第二种是当子空间的维数达到某个固定值后,利用最近的近似解重新开始.
如果取L = K,就得到完全正交化方法(FOM)(4.7.1节).如果用不完全正交化代替Krylov子空间的完全(Arnoldi)正交化,FOM方法变为直接不完全正交化方法(DIOM),它给出了估计解之间的递推关系.在投影方法中取L = AK,得到广义极小残差方法(GMRES)
(4.7.2节).和FOM方法类似,也可以构造重新启动的GMRES方法.当A为对称矩阵时,Arnoldi正交化变为Lanczos算法.FOM方法变为共轭梯度方法(CG),估计解满足三项递推关系.共轭梯度方法(4.5节)是求解系数矩阵对称正定的线性方程组的常用方法,它也可以从二次函数极小值问题的角度推导(4.5节).
将共轭梯度方法推广到一般矩阵,可以导出双共轭梯度方法(BICG)(4.7.4节).在BICG对应多项式的基础上,可以构造一般的共轭梯度平方方法(GCGS).GCGS的两个特例为共轭梯度平方方法(CGS)和稳定化的双共轭梯度方法(BICGSTAB).
迭代法往往涉及向量的内积、向量的更新、矩阵和向量的乘法和预处理等操作.它的并行实现(4.8节)需要考虑这些操作的并行化.在分布式内存的机器中,向量和矩阵常常放在不同的进程中,分别称这些向量和矩阵为分布式向量和分布式矩阵.向量的更新往往不涉及通信,而向量的内积和矩阵与向量的乘法需要进程的通信,它们是一种全局操作.预处理的并行实现(4.8.1节)往往依赖于预处理矩阵的选取.用不完全LU分解作预处理要解三角形方程组,如系数矩阵为下三角的线性方程组.方程组的未知量之间的依赖关系确定了并行性,但是并行力度不大.一种改进方式就是对原方程组先作变换,再作预处理.如矩形区域上用五点差分格式解Poisson问题时,对节点重新标号(如用红黑染色),这样的方程组对应的预处理更容易并行,但可能需要更多的迭代次数.
并行实现CG方法(4.8.2节)的主要问题就是如何使得计算和通信重叠.当预处理矩阵取M=LLT ,其中L为下三角矩阵时,适当安排计算次序就有可能实现计算和通信的重叠.并行的预处理GMRES方法(4.8.3节)中的主要问题是Krylov子空间的正交化的并行实现,这可以用更易并行的修改的Gram-Schmidt正交化算法来实现.
最后来引入一些其他内容. 求对称三对角矩阵A ∈ Rn×n 的特征值可以用QR算法,但这里我们给出了QL算法
(5.7.3节).QL算法基于矩阵的QL分解,其中L为下三角矩阵.QL分解(QL算法)和QR分解(QR算法)有完全类似的结论,所以每一步迭代只要O(n)的工作量.对于这种特殊矩阵,还存在两种方法分而治之方法(5.7.1节)和对分方法(5.7.2节),这两个方法的优势在于它们的并行性,这和QR算法很难并行形成鲜明对照.
和特征值相关的一些结论包括特征值的定位(圆盘定理)和矩阵的扰动对特征值的影响
(5.1节).下面的基础内容在第1章中.其中有和Hermite矩阵的特征值相关的结论(1.4节),如Courant-Fisher定理和特征值分割定理等.矩阵的一些标准分解(1.2节)包括了Jordan分解、Schur分解和奇异值分解.由于Jordan分解证明的困难性,我们仅仅给出了结论部分.
向量和一般矩阵的范数见1.3节,我们也仅仅给出了结论部分.正交投影、子空间之间的距离和不变子空间在1.5节给出.子空间和它对应的正交投影之间有一一对应关系,子空间之间的距离也可以用它们对应的正交投影之差的2-范数来度量.不变子空间和特征值相对应,按模最大的特征值对应有主不变子空间,这在子空间迭代中常常用到.1.6节给出了正方形区域上的Poisson问题以及它的离散格式,我们常常用它做数值实验.1.7节给出了并行计算简介,包括矩阵同向量的乘法和矩阵同矩阵的乘法的并行实现.1.8节给出了矩阵、向量和标量混合运算时确定次序的一个原则.最后,1.9节给出了和矩阵有关的几个概念,以利于读者对后文相关知识的掌握.
书后仅仅给出了部分参考目录.GeneH.Golub和CharlesF.VanLoan合写的MatrixComputations[1] 中给出了非常详细的参考文献. 除了该参考书之外, 本书很多内容参考了其他文献, 在此对这些文献的作者表示由衷的感谢. 下面给出了具体的参考内容.
参考[1]:引理1.1、引理1.2、定理1.4、定理1.7、推论1.2、秩亏时的最小二乘问题(第
. 51页)参考[4]:列主元消去法的舍入误差分析(第125页)
. 参考[5]:定理1.24、定理2.3、列主元QR分解(第46页)、定理2.7、定理2.10、矩阵
. 条件数的估算(第122页)、不完全三角分解(第132页)、Chebyshev加速方法(第189页)、QR算法的实现(第268页)、对称矩阵的特征值计算(第275页)、奇异值分解的计算(第279页)、分而治之方法(第285页)参考[6]:三对角方程组的循环约化方法(第117页)、稀疏方程组的直接法(第140页)
. 参考[8]:Gauss消去法中系数的显式表达(第85页)、定理3.14(第126页)、Jacobi方
. 法的收敛性证明(第256页)、Jacobi方法的并行实现(第259页)、对分法(第290页)参考[9]:算法2.6、算法2.7、2.4.2节~2.4.3节、FOM方法(第215页)、GMRES方法
. (第220页)、Lanczos方法(第223页)参考[10]:谱投影(第4页)、第二圆盘定理(第245页)、Wieldant收缩方法(第253页)、
. 子空间迭代的收敛性证明(第300页)、子空间投影方法的收敛性证明(第305页)参考[13]:大型稀疏对称正定矩阵的三角分解(第142页)
. 参考[15]:带状的线性方程组的并行求解方法(第113页)
. 参考[19]:代数多重网格(第206页)
. 参考[21]:QR分解的BLAS-3版本(第45页)、算法2.8(第60页)、对称矩阵的
. Hessenberg正交相似变换的BLAS-2和BLAS-3版本(第72页)、Cholesky分解的三种形式(第105页)、计算和通信重叠的CG算法和并行的GMRES(m)算法(第237页)、QR算法的并行实现(第274页)参考其他文献的内容不再详述.
本书是为了满足两类读者的需求而编写的.第一类是从事数值线性代数学习或研究的本科生、研究生以及大学教师等;第二类是运用数值线性代数从事科学计算的人员.我们欢迎广大读者提出宝贵的批评和建议.本书编者对清华大学出版社刘颖编辑和陈明编辑的辛勤劳动表示感谢.此外,本书在编写过程中获得了国家自然科学青年基金的资助,项目号10701056.
编者
2009年12月
前言........................................................................................ i 记号及约定................................................................................ix 第1 章数学基础........................................................................ 1
1.1 一些概念.........................................................................1
1.2 矩阵的几种标准分解............................................................. 2
1.2.1 Jordan 分解............................................................... 2
1.2.2 Schur 分解................................................................. 5
1.2.3 奇异值分解............................................................... 10
1.3 向量和矩阵的范数.............................................................. 15
1.4和Hermite矩阵的特征值相关的几个结论...................................... 20
1.5 正交投影、子空间之间的距离和不变子空间.................................... 22
1.6 Poisson 问题.................................................................... 25
1.7 并行计算简介...................................................................27
1.8 矩阵相乘的算法复杂度......................................................... 30
1.9 和矩阵有关的几个概念......................................................... 31 习题................................................................................. 32 第2 章正交化、最小二乘问题和正交相似变换........................................ 37
2.1 两种常用的正交变换工具....................................................... 37
2.1.1 Householder 变换......................................................... 37
2.1.2 Givens 变换.............................................................. 42
2.2 QR 分解........................................................................ 43
2.3 最小二乘问题...................................................................51
2.3.1 最小二乘问题的性质..................................................... 51
2.3.2 满秩的最小二乘解问题................................................... 54
2.3.3 秩亏的最小二乘解问题................................................... 55
2.4线性无关向量组和Krylov子空间的正交化..................................... 57
2.4.1线性无关向量组的Gram-Schmidt正交化................................ 58
2.4.2线性无关向量组的Householder正交化................................... 60
2.4.3 Krylov 子空间的正交化...................................................63
2.5 正交相似变换...................................................................69 习题................................................................................. 76 第3 章线性方程组的直接法........................................................... 79
3.1 引言............................................................................ 79
3.2 Gauss 消去法................................................................... 79
3.2.1不选主元的Gauss消去法................................................ 80
3.2.2完全主元Gauss消去法...................................................87
3.2.3 程序的实现............................................................... 90
3.2.4列主元Gauss消去法..................................................... 95
3.3 直接三角分解..................................................................101
3.3.1 不选主元的三角分解.................................................... 101
3.3.2 选主元的三角分解.......................................................102
3.4 特殊矩阵的三角分解.......................................................... 105
3.4.1 对称矩阵的三角分解.................................................... 105
3.4.2 带状矩阵的三角分解.................................................... 109
3.4.3 追赶法.................................................................. 114
3.5 矩阵的条件数..................................................................118
3.5.1 矩阵的条件数引出.......................................................118
3.5.2 迭代的改进..............................................................121
3.5.3 矩阵的条件数的估算.................................................... 122
3.6 误差分析...................................................................... 125
3.6.1 列主元消去法的舍入误差分析...........................................125
3.7 不完全三角分解............................................................... 132
3.8 大型稀疏矩阵的分解.......................................................... 138
3.8.1 稀疏矩阵的存储格式.................................................... 138
3.8.2 解稀疏方程组的直接法......................................................140
3.8.3 大型稀疏对称正定矩阵的三角分解...................................... 142
3.8.4稀疏矩阵的QR分解.................................................... 159
3.8.5稀疏对称正定矩阵的Cholesky分解的并行实现......................... 168 习题................................................................................ 170 第4 章线性方程组的迭代法.......................................................... 177
4.1 一般迭代法.................................................................... 177
4.2Jacobi迭代、Gauss-Seidel迭代、SOR迭代和SSOR迭代..................... 180
4.3 迭代法的收敛性............................................................... 184
4.4 加速方法...................................................................... 188
4.4.1 外推方法................................................................ 188
4.4.2 Chebyshev 加速方法.....................................................189
4.5 预处理的共轭梯度方法........................................................ 194
4.6 多重网格方法..................................................................198
4.6.1 方法的引出..............................................................198
4.6.2 几何多重网格........................................................... 201
4.6.3 代数多重网格........................................................... 206
4.7 现代迭代法.................................................................... 215
4.7.1 FOM 方法............................................................... 215
4.7.2 GMRES 方法............................................................ 220
4.7.3 Lanczos 方法............................................................ 223
4.7.4BICG,CGS和BICGSTAB迭代法...................................... 227
4.7.5 迭代法的比较........................................................... 233
4.8 迭代法的并行实现............................................................. 235
4.8.1 预处理的并行实现.......................................................235
4.8.2计算和通信重叠的CG算法............................................. 237
4.8.3并行的GMRES(m)算法............................................... 239 习题................................................................................ 239 第5 章矩阵特征值问题的数值计算................................................... 244
5.1 特征值问题中的一些结论......................................................244
5.2 幂法及反幂法..................................................................247
5.2.1 幂法..................................................................... 248
5.2.2 反幂法.................................................................. 252
5.2.3 收缩方法................................................................ 253
5.3 Jacobi 方法.................................................................... 255
5.4 QR 算法....................................................................... 259
5.4.1 QR 算法及收敛性....................................................... 259
5.4.2 QR 算法的实现......................................................... 268
5.4.3 QR 算法的并行实现..................................................... 274
5.5 对称矩阵的特征值计算........................................................ 275
5.6 奇异值分解的计算............................................................. 279
5.7 对称三对角矩阵的特征值计算................................................. 285
5.7.1 分而治之方法........................................................... 285
5.7.2 对分法.................................................................. 290
5.7.3 QL 方法................................................................. 292
5.8 Lanczos 方法求解大型稀疏对称矩阵的特征值................................. 296
5.9 大型稀疏矩阵的特征值计算................................................... 300
5.9.1 子空间迭代..............................................................300
5.9.2 Rayleigh-Ritz 投影方法.................................................. 303
5.9.3 Arnoldi 迭代.............................................................307
5.9.4 Jacobi-Davidson 方法.................................................... 312 习题................................................................................ 317 部分习题解答............................................................................321 参考文献................................................................................ 348