世界著名数值分析专家牛津大学教授LloydNTrefethen和DavidBauIII指出:\如果除了微积分与微分方程，还有什么数学领域是数学科学基础，那就是数值线性代数"数值
线性代数领域中的一个十分重要的课题是大型稀疏线性系统的高效求解这主要是因为在实践中，如计算流体动力学、电磁计算、材料模拟与设计、石油勘。探数据处理、地震数据处理、数值天气预报及核爆炸数值模拟等都离不开(偏)微分方程的数值求解，而解决这些问题的主要策略是通过有限差分、有限元、有限体积、区域分解、多重网格、无网格等方法对(偏)微分方程离散将所需求解问题转。化为大型稀疏线性系统的数值求解当今，如何快速有效的求解大型稀疏线性系统。已成为许多专家及学者研究的焦点这主要体现在数值计算及其模拟中求解大型。稀疏线性系统所花费的时间往往在求解整个问题所需的时间中占有很大的比重，有。时甚至高达百分之八十以上。
通常，求解线性系统的方法有两类:基于矩阵分解的直接法和基于递归的迭代。法直接法的工作主要集中在20世纪6070年代，主要途径是通过对矩阵进行变。换(如Gauss消元、LU分解等)，将原线性系统化为三角或三对角等容易求解的形式，然后通过回代或追赶等方法得到线性系统的解其优点在于不计舍入误差的情。况下能得到准确解不足之处是当矩阵的条件数很大时，由于舍入误差的存在而导。致所求出的解与准确解相差甚远;当矩阵阶数较大时，由于存储的需求而迫使直接。法相对于其他方法更费时所以用直接法求解大型稀疏线性系统往往是不可取的。基于此，在实际求解中，通常采用运算量小、内存需求小且能充分利用矩阵稀疏性。的迭代法。
当前，迭代法已成为求解大型稀疏线性系统的主流方法迭代求解大型稀疏线。性系统现已成为科学计算中十分重要的课题之一，其迭代策略一般可分为两类一。类是基于矩阵分裂的定常迭代法定常迭代法的工作主要集中于20世纪5060年。代，其基本途径是通过矩阵单分裂(若线性系统的系数矩阵A分裂为A=MN(其。中M为非奇异矩阵)，则称为矩阵A的单分裂)而构建迭代格式根据矩阵分裂的。形式不同而形成了许多行之有效的方法，如Jacobi，Gauss-Seidel(G-S)，Successive。
Over-Relaxation(SOR)，AcceleratedOver-Relaxation(AOR)等以及这些方法的改。进和加速形式定常迭代法具有结构简单、易于程序实现等优点因此，自Jacobi。方法诞生以来，新的定常迭代法层出不穷，备受工程人员及科研人员的青睐目前，。这些方法又有新的发展，如将其作为预处理子与Krylov子空间方法结合起来求解。大型稀疏线性系统另一类是非定常迭代法目前，非定常迭代法主要存在两大分。支:一是以ConjugateGradient(CG)方法为代表的Krylov子空间迭代法;二是基。于矩阵分裂的分裂迭代法，如非定常Richardson迭代法、内外迭代法以及非定常。多分裂迭代法等目前，对求解大型稀疏线性系统来说，比较流行的Krylov子空间。迭代法有CG，MinimalResidualmethod(MINRES)，GeneralizedMinimalResidual。method(GMRES)等。
无论是定常迭代法还是非定常迭代法，其收敛速度在一定程度上与矩阵的谱分。布有着密不可分的关系对矩阵分裂的定常迭代法来说，在迭代矩阵谱半径小于1。的前提下，迭代矩阵的谱半径越小其收敛速度越快;对非定常Krylov子空间迭代法。来说，其收敛速度依赖于矩阵的谱分布，谱分布越集中，收敛速度越快[14]因此，。为了提高迭代法求解线性系统的收敛速度，目前，一个切实可行的途径是采用预处。理技术，其主要目的是使预处理后的矩阵的谱更加聚集为特定的大型稀疏线性系。统寻找\量身定做"的预处理子已成为迭代法研究中的重要课题。
预处理技术的主要策略是通过利用预处理子将原线性系统转化为易求解的等。价线性系统通常，构建一个好的预处理子已被公认为是艺术与科学的完美结合。
一般地，构造预处理子有两种途径:一是纯代数技术，如不完全分解(ILU)预处理子、。稀疏近似逆(AINV)预处理子等;二是从特定问题出发，通过利用较多原问题信息。来构建预处理子，一般情况下，原问题信息利用的越多，构建的预处理子越有效具。体地，对预处理子的构造可以从以下五个方面考虑:。(1)线性系统的背景;。(2)矩阵本身的性质，如是否具有稀疏性、对称性、占优性等;。(3)预处理部分的计算量比较小;。(4)预处理矩阵特征值分布相对集中;。(5)预处理矩阵需满足一定的性质，如是否具有正定性、是否具有对称性、特。征值是否全是实数。一般地，一个切实可行有效预处理子的选择可以从以下四个方面把握:。(1)预处理子在某一方面是系数矩阵的逆矩阵的一个较好逼近(事实上，构造。预处理子主要目的是使预处理矩阵为单位阵的近似);。(2)构造预处理子需在计算机的内存和CPU的工作时间上有保障(即花费不。太大);。(3)预处理矩阵的条件数要远小于原系数矩阵的条件数，其最小奇异值会相应 的增大而最大奇异值会相应的减小;。(4)新的预处理线性系统要比原线性系统更易求解。当今，预处理技术已渗入到所需问题的数值求解中，是提高相应数值算法收敛。速度的一个十分重要的途径，已成为数值计算领域中的一个很重要的研究方向。
111经典定常迭代法。
在科学计算中，许多实际问题的求解最终都要归结为求解大型稀疏线性系统:。Ax=b;。其中A是一个给定的非奇异矩阵，b是一个给定的向量，x是一个待求的向量由。于不同问题在不同条件下产生的线性系统不同，进而导致其相对应的系数矩阵A。不同，如在偏微分方程数值解、控制论、均衡论及加权最小二乘问题等数值求解中，。通过适当的技术处理(如用有限差分离散偏微分方程或对加权最小二乘问题等价。变换)，可以获得系数矩阵为非奇异L-矩阵(或H-矩阵)的线性系统如前所述，若。用直接法求解，则数值效果并没有达到令人十分满意的程度常采用迭代法对其求。解，为了加快迭代法的收敛速度，通常迭代法需要与预处理子结合起来求解大型稀。疏的线性系统。
近年来，对系数矩阵为L(H)-矩阵的非奇异线性系统预处理子的构造主要是。将系数矩阵A分裂为A=DLU，其中D是A的对角矩阵，L和U分。别是矩阵A的严格下三角矩阵和严格上三角矩阵基于这一分裂，预处理子的构。造通常是\D+S"型，其中矩阵S的元素常取系数矩阵A的某些非零元的相反。数，如取系数矩阵A的第一列的相反数[5，6]、取系数矩阵A的上次对角元的相反。数[7，8]等这种构造预处理子的基本思想源于Gauss消元法，其目的是通过将系。数矩阵A的某些对应元素化为0来达到减少迭代矩阵谱半径的目的，进而提高迭。代法的收敛速度，其理论依据是迭代矩阵的谱半径越小，矩阵分裂迭代法的收敛速。度越快[9]此类预处理子常常与经典迭代法(如G-S迭代法、SOR迭代法及AOR。迭代法等)结合到一起来求解大型稀疏的线性系统此方法的优点是理论性强、计。算代价小;不足之处是计算的效果相对要差在这类预处理子中，修正预处理方法。研究较多，在一定程度上可看成是Gauss消元法的一种扩展目前，国内外很多学。者对此进行了相关的研究[10，11]，得出了很多理论结果，促进了新预处理子研发的。进程。
另一方面，若将系数矩阵A分裂为A=PRS(其中P为非奇异矩阵)，则。称为矩阵A的双分裂[12]，矩阵双分裂所确定的迭代法称为双分裂迭代法[12]如。Jacobi双SOR方法、G-S双SOR方法、EWA双SOR方法等都属于双分裂迭代。法这些方法虽是传统单分裂迭代法的简单推广，但现已有效地求解某些实际问题，。如核反应堆物理学中的离散多维椭圆型方程[13]
展开
