增量未知元及其预处理迭代算法

本书针对线性方程组和非线性方程组的数值解法进行了研究，提出了一些有特色的理论研究结果和高效实用且稳定的算法，并对每一种算法的收敛性稳定性都给出了严格的证明，同时附有大量的数值实验来验证理论的重要性和有效性。本书可供高等学校数学系高年级本科生或研究生数值分析课程教材，也可供有关研究人员和工程技术人员参考。 

代数方程组的高效求解是计算数学中一个基础共性且十分关键的问题。本书根据作者近几年在代数方程组求解方面研究所取得的成果以及国内外相关研究成果撰写而成。全书共6 章，对增量未知元预处理技术、非线性特征值问题、非埃尔米特正定线性代数方程组以及非线性代数方程组的求解方法进行了系统而深入的介绍。
本书可作为信息与计算科学、数学与应用数学以及相关数学专业的研究生和高年级本科生的拓展读物，也可供相关领域从事教学与科研的专业人士参考。

目录
第1章引言1
1.1增量未知元方法与微分方程数值解1
1.1.1一阶增量未知元1
1.1.2二阶增量未知元2
1.1.3类小波增量未知元6
1.2数值代数方法7
1.3本书的主要工作11
第2章基于增量未知元方法的非线性特征值问题的研究13
2.1非线性特征值问题简介13
2.2线性Richardson方法和MarderWeitzner方法14
2.2.1线性Richardson方法14
2.2.2MarderWeitzner 方法14
2.3MarderWeitzner方法的改进15
2.3.1修正的Richardson方法15
2.3.2修正的MarderWeitzner方法15
2.3.3A1方法17
2.4数值实验18
2.4.1Dirichlet 问题18
2.4.2非线性特征值问题18
2.4.3结论24
第3章一类反应扩散方程的多层分块类小波增量未知元25
3.1多层分块类小波增量未知元25
3.2逼近格式及其等价形式29
3.3关于范数的三个引理33
3.4显格式和半隐格式的稳定性估计33
3.5数值结果37
第4章非埃尔米特正定线性系统的迭代方法40
4.1简介40
目录增量未知元及其预处理迭代算法4.2非埃尔米特正定线性系统的预条件NSS方法41
4.2.1预条件正规/反对称分裂(PNSS)迭代方法的建立41
4.2.2PNSS迭代方法收敛性分析41
4.2.3不精确的预条件正规/反对称分裂(IPNSS)迭代及其
收敛性分析43
4.2.4数值算例44
4.2.5总结46
4.3非埃尔米特正定线性系统的两参数预处理NSS迭代方法46
4.3.1两参数预处理NSS迭代方法的建立46
4.3.2两参数预处理NSS迭代方法收敛性分析47
4.3.3最优化策略50
4.3.4不精确两参数预处理NSS迭代策略54
4.3.5数值算例55
第5章基于SOR迭代的复对称线性系统的MHSS加速方法60
5.1简介60
5.2MHSS迭代方法61
5.3基于SOR迭代的MHSS加速方法62
5.3.1MHSS加速方法的建立62
5.3.2MHSS加速方法收敛性的证明64
5.3.3数值实验65
5.3.4总结65
第6章非线性系统的迭代法66
6.1简介66
6.2关于NewtonLHSS后退方法及其全局收敛性的研究67
6.2.1NewtonLHSS后退方法的提出67
6.2.2Newton|LHSS后退方法的全局收敛性定理68
6.2.3数值实验69
6.3PicardAHSS方法及其局部收敛定理72
6.3.1AHSS方法73
6.3.2PicardAHSS方法73
6.3.3PicardAHSS方法收敛定理74
6.3.4非线性AHSSlike迭代方法及其收敛性定理76
6.3.5数值结果78
6.4一类弱非线性方程组的PicardMHSS迭代方法81
6.4.1PicardMHSS方法及其局部收敛定理81
6.4.2非线性MHSSlike迭代方法及其收敛定理84
6.4.3数值结果86
参考文献89

前言
在很多科学与工程计算领域，都会遇到大规模代数方程组的求解，有效求解大规模代数方程组是科学和工程计算中的重要研究内容。
本书分为两个部分共6章，主要内容概述如下。
第一部分第1～3章首先介绍增量未知元预处理技术和近年来的HSS 类迭代方法，然后对于非线性特征值问题，基于二阶增量未知元方法，提出修正的MarderWeitzner 方法；对于各项异性反应扩散方程，基于矩阵分块，提出一种新的类小波增量未知元（WIU）,这里包含了作者的一些研究成果。
第二部分第4～6章研究几种增量未知元预处理迭代算法。第4 章对非埃尔米特正定线性代数方程组的数值解法进行研究，基于NSS 迭代方法，提出预处理NSS 方法和双参数NSS 方法，并对方法的收敛性进行细致的分析，给出迭代格式中迭代参数的计算方法。第5章首先介绍复对称线性代数方程组的迭代解法，提出基于SOR 迭代的复对称线性系统的MHSS 加速方法，分析迭代格式的收敛性，并以数值结果证明方法的优越性。第6 章研究非线性代数方程组的数值解法，基于LHSS 方法提出NewtonLHSS 后退方法并分析方法的全局收敛性，对于一类特殊的弱非线性代数方程组，提出PicardAHSS 迭代方法、非线性AHSSlike 迭代方法以及PicardMHSS 方法，分析方法的收敛性，并给出数值结果。
本书多数为作者的研究成果，在相关问题中参考了伍渝江教授近几年的研究资料，在此表示感谢。
由于作者的学识与研究水平有限，研究领域与视角不够宽阔，书中一定有很多不尽如人意的地方，敬请相关专家和读者指正。

作者
2018年3月

第5章基于SOR迭代的复对称线性系统的MHSS加速方法5.1简介
复线性代数系统广泛出现在科学与工程计算的许多领域，例如光学层析成像，量子力学，分子散射和结构力学等. 其中复对称线性系统(即系数矩阵的实部和虚部均为对称矩阵)由于其特殊的结构和广泛的应用背景，吸引着越来越多的学者的关注. 针对复线性方程组的直接解法是最早出现的求解方法，但是当矩阵规模较大时，由于直接解法的存储量和计算量一般很大，所以迭代法在近年来越来越受到重视. 目前，迭代法已成为求解大型稀疏复对称线性方程组的主要方法. 然而，由于复系数矩阵在方程组的规模较大或系数矩阵的条件数较大时，系数矩阵容易呈现病态特征，所以许多适用于实线性代数方程组的迭代方法，如共轭梯度方法(CG)、预共轭梯度方法(PCG),对于复线性代数方程组的求解效果并不理想，存在着不收敛或收敛速度慢的问题. 于是，很多学者对原线性代数方程采用适当的预处理技术，例如SSOR预处理、多项式预处理、不完全分解预处理、CtoR等预处理方法，用来降低系数矩阵的条件数，改善矩阵病态特性，以加快迭代方法的收敛速度.
对于复线性代数方程组的求解，另一种方法就是将其转化为等价的实系数线性代数方程组，这样就可以将实系数线性代数方程组的解法用在复系数线性代数方程组的求解上.
例如，我们考虑下面的复系数线性代数方程组的求解问题:Ax=b(5.1)其中，A=W iT，x=y iz，b=d ig，这里，矩阵W,T均为实系数矩阵，y,z,d,g都是实向量，i=－1为虚数单位. 方程组(5.1)可以写成下列形式: WT
TWy
z=d
g(5.2)这里需要强调的是，方程组(5.1)的实系数形式并不唯一，例如，也可以将其写为 T－W
WTy
－z=g
d(5.3)然而普通迭代法求解式(5.2)或者式(5.3)，其收敛速度往往要慢于最初始的复系数线性代数方程组(5.1). 尽管如此，我们依然可以借助复系数线性方程组的实系数形式，构造合适的预处理子，来加快迭代方法收敛的速度.
近来，基于矩阵的对称和反对称分裂(HSS)技术，白中治，Golub,Ng等提出了修正的对称和反对称分裂(MHSS)方法，MHSS迭代方法保持了HSS迭代方法的优点，即对于格式中 α>0，MHSS迭代均无条件收敛到复线性代数方程组(5.1)的解. 同时又克服了HSS方法中的不足，即避免了在迭代中计算系数矩阵为复数矩阵的情形. MHSS方法是针对矩阵W,T为对称矩阵情形下对HSS方法的推广。很多学者对MHSS方法进行了推广. 王坤针对复系数线性方程组的特点，对MHSS算法进行了修正，提出了MLHSS迭代方法. 2013年，郭晓霞、王坤讨论了矩阵W,T为非对称情形的情况，并给出了收敛定理，进行了数值实验，证明了方法的有效性.
增量未知元及其预处理迭代算法第5章基于SOR迭代的复对称线性系统的MHSS加速方法本章首先回顾修正的HSS迭代方法及其收敛定理，为了提高复线性代数方程组的求解效率，基于NSS超松弛加速迭代格式，提出一类求解复线性代数方程组的超松弛迭代MHSS加速迭代格式. 然后推导该加速迭代方法的收敛条件以及加速迭代格式中参数ω的选取办法，最后用数值实验证明方法的正确性和有效性.
5.2MHSS迭代方法
考虑求解大型稀疏线性方程组Ax=bx,b∈Cn(5.4) 其中A∈Cn×n为大型稀疏复对称矩阵，即A具有下述形式: A=W iT (5.5)矩阵W,T分别为实正定矩阵和实正半定矩阵且满足WT=W,TT=T. i=－1 为虚数单位. 为了保证A为非Hermit矩阵，我们假定T≠0. 为了避免在迭代中计算系数矩阵为复数矩阵，白中治，Golub,Ng提出了修正的对称和反对称分裂(MHSS)方法，迭代格式定义如下:
MHSS 迭代方法: 给定一个初值x(0)∈Cn，对于k=0,1,2…，直到{x(k)}收敛，计算(αI W)xk 12=(αI－iT)x(k) b,
(αI T)x(k 1)=(αI iW)xk 12－ib, (5.6)其中α>0，I为与矩阵A同阶的单位矩阵.
对于MHSS迭代方法的收敛性，我们有下面两个收敛定理.
定理5.1假设A=W iT∈Cn×n，W∈Rn×n，T∈Rn×n，分别为实正定矩阵和实正半定矩阵且满足WT=W,TT=T,i=-1为虚数单位. 对于α>0，MHSS迭代矩阵的谱半径ρ(M(α))都满足ρ(M(α))≤σ(α)其中M(α)=(αI T)-1(αI iW)(αI W)(αI-iT),
σ(α)≡maxλj∈λ(W)α2 λ2jα λj其中，λ(W)表示矩阵W的谱集，因此，ρ(W(α))≤σ(α)<1,α>0,即对α>0,MHSS迭代方法收敛到线性方程组(5.4)的唯一解x∈Cn.
定理5.1说明了MHSS方法的收敛速率只与对称正定矩阵W的特征值有关,而与矩阵T的特征值以及矩阵W,T的特征向量无关. 若已知矩阵W的最大和最小特征值，便可以得到使得谱半径ρ(M(α))上界σ(α)取得极小时参数的计算方法.
定理5.2假设A=W iT∈Cn×n，W∈Rn×n,T∈Rn×n分别为实正定矩阵和实正半定矩阵且满足WT=W,TT=T，i=-1为虚数单位. 令Υmin和Υmax代表对称正定矩阵W的特征值的最大值和最小值，那么α=arg minαmaxΥmin≤λ≤Υmaxα2 λ2α λ≡ΥminΥmax相应地，σ(α)=Υmin ΥmaxΥmin Υmax=κ(W) 1κ(W) 1其中，κ(W)=Υmax/Υmin表示矩阵W的谱条件数.
5.3基于SOR迭代的MHSS加速方法〖*3/4〗5.3.1MHSS加速方法的建立下面我们基于NSS超松弛加速迭代格式，提出一类求解复线性代数方程组的超松弛MHSS加速迭代格式. 为了给出MHSS加速迭代方法，我们首先考虑下面两个不动点方程: (αI W)x=(αI-iT)y b,
(αI T)y=(αI iW)x-ib,(5.7)容易得到，这两个不动点方程的解与方程组(5.4)的解有如下关系.
定理5.3如果x∈Cn是(5.4)的解，那么同时也是式(5.7)中两个方程的不动点；反过来，如果x∈Cn是(5.7)中任一个方程的不动点，那么也是式(5.4)的解.
证明: 设x∈Cn是(5.4)的解，由方程Ax=b和-iAx=-ib同解，以及Ax=(W iT)x
=(αI W)x-(αI-iT)x=b
iAx=(-iW T)x
=(αI T)x-(αI iW)x=-ib可知，定理结论成立.
下面，我们将两个不动点方程等价转换写成具有2×2分块结构的线性方程组，A0(α)x
y=αI W-(αI-iT)
-(αI iW)αI Tx
y=b
-ib(5.8)定理5.4证明了A0(α)为非奇异矩阵，定理5.5证明了求解式(5.1)和求解式(5.8)是等价的. 从而我们可以从式(5.8)出发建立MHSS迭代加速方法.
定理5.4假设A=W iT∈Cn×n，W∈Rn×n,T∈Rn×n分别为实正定矩阵和实正半定矩阵且满足WT=W,TT=T,i=-1为虚数单位. 对于α>0，矩阵A0(α)=αI W-(αI-iT)
-(αI iW)αI T∈C2n×2n为非奇异矩阵.
证明由于W∈Rn×n,T∈Rn×n分别为对称正定和对称半正定矩阵，因此，对于α>0，αI T和αI W为正定的非奇异矩阵，除此之外，成立A0(α)=αI W-(αI-iT)
-(αI iW)αI T
=I0
-(αI iW)(αI W)-1IαI W-(αI-iT)
0Γ(α)(5.9)其中Γ(α)=(αI T)-(αI iW)(αI W)-1(αI-iT)为矩阵的Schur补且Γ(α)=(αI T)(I-M(α))M(α)为MHSS迭代方法的迭代矩阵，由文献［113    ］中定理2.1，对于α>0，ρ(M(α))<1. 因此，A0(α)为非奇异矩阵，定理证毕.
利用定理5.4，两个不动点方程(5.7)构成了一个2×2块状线性代数方程组，这个方程组与(5.4)等价，于是得到下面定理:
定理5.5假设A满足定理5.4的条件. 如果x∈Cn是(5.4)的解，那么z=x
x∈C2n为线性方程组(5.8)的解，反之，若z=x
y∈C2n为线性方程组(5.8)的解，那么x=y必然成立，且x为式(5.4)的解.
证明: 利用定理5.4和简单计算可以得到定理的结论，证明过程略.
下面，我们由式(5.8)出发，给出分块Jacobi迭代和超松弛(SOR)迭代算法:
块Jacobi迭代方法: 给定一个初值x(0)，y(0)∈Cn对于k=0,1,2…，x(k 1)=(αI W)-1［(αI-iT)y(k) b］,
y(k 1)=(αI T)-1［(αI iW)x(k)-ib］,其中α>0，I为与矩阵A同阶的单位矩阵.
Jacobi迭代方法也可以等价地写为z(k 1)=J(α)z(k) C(α)其中J(α)=0(αI W)-1(αI-iT)
-(αI T)-1(αI iW)0(5.10)
C(α)=(αI W)-1b
-(αI T)-1ib2×2分块结构的线性方程组(5.8)的块SOR迭代格式定义如下:
块SOR迭代方法给定一个初值x(0)，y(0)∈Cn，对于k=0,1,2…，x(k 1)=(1-ω)x(k) ω(αI W)-1［(αI-iT)y(k) b］,
y(k 1)=(1-ω)y(k) (αI T)-1［(αI iW)x(k 1)-ib］,(5.11)其中α>0，ω为松弛参数. I为与矩阵A同阶的单位矩阵.
式(5.11)也可以等价地写为z(k 1)=Υω(α)z(k) Cω(α)其中Υω(α)=(1-ω)Iω(αI W)-1(αI-iT)
ω(1-ω)(αI T)-1(αI iW)(1-ω)I ω2M(α)(5.12)这里，M(α)为MHSS迭代方法的迭代矩阵.
注5.1当ω=1时，块SOR退化为块2×2线性方程组(5.8)的块GS迭代，相应地Υω(α)T退化为GS迭代矩阵Υ1(α).
5.3.2MHSS加速方法收敛性的证明
由块Jacobi矩阵J(α),块GS迭代矩阵Υ1(α)和MHSS迭代矩，容易得到下面的定理:
定理5.6① 如果μ是J(α)的特征值，那么μ2是Υ1(α)的特征值. 如果θ为Υ1(α)的一个非零特征值且μ2=θ，那么μ为J(α)的特征值. 因此块Jacobi迭代方法收敛的充分必要条件是块GS迭代方法收敛，且如果二者均收敛，那么ρ(Υ1(α))=ρ(J2(α))<1.
② 块GS迭代矩阵Υ1(α)的非零特征值集合等于MHSS迭代矩阵M(α)的特征值集合. 因此，GS迭代收敛当且仅当MHSS迭代收敛；如果二者同时收敛，我们有ρ(Υ1(α))=ρ(M(α))<1.
利用定理5.6及相关文献，我们马上得出下面的推论:
推论5.1假设A满足定理5.4的条件. 块GS迭代方法和MHSS迭代方法均无条件收敛，且ρ(Υ1(α))=ρ(M(α))=ρ(J2(α))<1.
注5.2推论5.1说明了GS迭代和MHSS迭代的渐近收敛速率是一样的，且二者的收敛速率是块Jacobi迭代收敛速率的2倍.
下面我们进一步讨论块SOR方法的收敛条件. 由于系数矩阵A0(α)具有块状性质A,我们可以得出SOR迭代矩阵Υω(α)和Jacobi矩阵J(α)的特征值之间具有下面的关系:
定理5.7假设A满足定理5.4的条件. J(α)，Υω(α)分别由式(5.10)和式(5.12)所定义，则:
① 设λ为Υω(α)的非零特征值，则由关系式(λ ω-1)2=λω2μ2(5.13)所确定的μ为J(α)的特征值.
② 若μ为J(α)的特征值，则由关系式(5.13)所确定的λ为Υω(α)的特征值.
证明略.
最后，由推论5.1和定理5.7，得到块SOR迭代方法的收敛定理:
定理5.8假设A满足定理5.4的条件. J(α)，Υω(α)分别由式(5.10)和式(5.12)所定义，则:
① 当J(α)的所有特征值为实数时，ρ(Υω(α))<1的充分必要条件是0② 当J(α)的某些特征值为虚数时，如果对于某个整数τ∈(0,1)，Υω(α)的每个特征值μ=δ iβ，点(δ,β)都落在椭圆ε(1,τ)def(δ,β): δ2 β2τ2=1的内部且0证明略.
5.3.3数值实验
下面，我们用数值实验来检验SOR方法对MHSS的加速效果.
考虑求解下列复线性代数方程组K 3 3τI iK 3-3τIx=b其中τ表示时间步长，K∈Rn×n=IVm VmI,Vm=h-2tridiag(-1,2,-1)∈Rm×m表示在［0,1］×［0,1］上满足齐次边值条件的拉普拉斯算子经过五点差分离散所得到的矩阵，因此，K为n×n块三对角矩阵，n=m2，空间步长h=1m 1，右端向量b的元素bj=(1-i)jτ(j 1)2,j=1,2,3，…这里i=-1为虚数单位. 经过计算，得到W=K 3 3τI,T=K 3-3τI为了方便，在SOR加速算法3中，参数α与MHSS方法中参数的选取一致，另外，在所有情形下，取ω=1.2. 从表5.1中可以看出，在各种测试下，基于SOR迭代的MHSS加速方法在迭代步数(IT)和时间(CPU)上都要优于MHSS迭代方法. 表5.1迭代步数和迭代时间的比较m2×m2MHSS方法MHSS加速方法ITCPUITCPU202×20211124.273719.921252×25213482.5408737.752302×302159176.51103114.86402×402207966.72135645.125.3.4总结
本章提出了一类求解大型稀复疏线性代数方程组加速MHSS方法，并分析了方法的收敛性质，数值实验证明了加速MHSS方法在迭代步数和迭代时间上都优于MHSS方法. 最后，我们要强调的是，为了方便，本文中加速方法中松弛参数ω的值选为1.2，事实上，ω最优值的讨论是一个很有意义和难度的问题，将在以后继续研究.