期南京航空航天大学学报V o l 33N o2

第33卷第2期南　京　航　空　航　天　大　学　学　报Vol.33No.2

2001年4月　Apr.2001JournalofNanjingUniversityofAeronautics&Astronautics

文章编号:100522615(2001)0220139207

求解大规模矩阵问题的Krylov子空间方法

戴　华

(南京航空航天大学理学院　南京,210016)

摘要　求解大规模矩阵问题包括线性方程组和特征值问题等是计算数学和科学工程计算中的重大课题。最近几年,其研究工作取得了许多重大进展。文中给出大型线性方程组和特征值问题Krylov子空间方法若干进展的一个概述,其中包括作者对这些问题的研究成果。涉及的专题包括求解大型线性方程组的共轭梯度法、SYMMLQ算法、MINRES算法、GMRES算法、Lanczos双正交化算法、QMR算法以及这些算法的块格式;求解大型对称特征值问题的Lanczos算法和块Lanczos算法;求解大型非对称特征值问题的Lanczos算法、Arnoldi算法以及这些算法的块推广。讨论求解大规模矩阵问题的加速技术和预处理技术。提出了一些有待进一步研究的问题。关键词:矩阵;线性方程组;特征值;Krylov子空间方法中图分类号:O241.6　　　　文献标识码:A

引　　言

大规模矩阵问题包括线性方程组、矩阵特征值问题等数值解法的理论研究、算法设计和软件研制是当今计算数学和科学工程计算研究的重大课题,是大规模科学与工程计算的基础和重要组成部分,其研究具有重要的理论意义和广泛的应用价值。尤其是其中大型非对称矩阵问题的数值计算,因其理论上的复杂性,导致在算法的理论研究和软件设计中产生了许多本质的困难。问题的挑战性吸引了国内外许多数值分析专家从事该领域的研究,并取得了许多重大进展。

求解线性方程组和矩阵特征值问题的Krylov子空间方法可以追溯到50年代初Lanczos

[1,2]

理论分析和数值试验,充分认识到Krylov子空间

方法是求解大型线性方程组和大型矩阵特征值问题的一类最有效的方法。本文概述Krylov子空间方法的若干进展,其中包括作者对这些问题的研究成果,并提出一些有待进一步研究的问题。

1　求解大型线性方程组的Krylov子

空间方法

对线性方程组

Ax=b

(1)

其中,A∈Rn×n,b∈Rn,设x0∈Rn是式(1)解的初始估计,r0=b-Ax0是初始残量。称Kk(A,r0)=

k-span{r0,Ar0,…,A

1

r0}为由A和r0产生的

,

Krylov子空间。Krylov子空间方法求式(1)的具有

[3][4]

Arnoldi,Hestenes和Stiefel的工作。但在其后

20年,人们一直认为这类方法是数值不稳定的,很

如下形式的近似解

xk∈x0+Kk(A,r0)并且使残量rk=b-Axk满足Galerkin条件

rk⊥Lk

(2)(3)

少用于实际计算。直到70年代初Paige在其著名的博士论文[5]中重新研究了Lanczos方法以及80年代初Saad[6]重新研究了Arnoldi方法,才使人们重新认识了这两个方法。之后,人们又做了大量的

其中Lk是Rn中的一个子空间,或使残量rk的范数极小化,即

　基金项目:国家自然科学基金(编号:19671043)、江苏省自然科学基金(编号:BK97059)、江苏省“333工程”基金和江苏省“青蓝工程”基金资助项目。

　收稿日期:2000204211;修订日期:2000211201

　作者简介:戴　华,男,教授,博士导师,1959年6月生。