Hermitian半正定线性系统中定长迭代法收敛的必要条件

Hermitian半正定线性系统中定长迭代法收敛的必要条件AndreasFrommer,DanielB.Szyld关键词线性系统奇异线性系统定长迭代法半模收敛性分析摘要在之前的文章中我们得到了定常迭代收敛的能量半模的充分条件，且该迭代是对于系数矩阵是Hermitian的且半正定的线性系统的。在这篇文章中，我们将说明在什么情况下这些条件依旧必要，以及在什么情况下不然。1.介绍我们考虑一个（奇异）线性系统Axb（1）假设其中系数矩阵nnA£是Hermitian的且半正定的。如果A是大型稀疏矩阵，迭代思想是解决问题（1）的标准方法。在本文中，我们关注定常迭代法，例如，代数多重网格法，加性和乘性施瓦茨法。有时，通过把它们作为Kryov子空间法的预调节器，这些迭代法是加速的，就像共轭梯度一样。当我们不考虑后者的任何细节，只涉及其中通常假设预调节器是收敛的作为前提条件的情况，所以我们的工作在这种情况中也是相关的。对于定常迭代法，我们通常考虑用非奇异矩阵M分离()AMMA，得到一个迭代矩阵1HIMA,并且得到迭代式11kkxHxMb.（2）众所周知，当A是非奇异的，对任意起始向量0x当且仅当()1H时，迭代（2）收敛到一个（1）的唯一解，其中()H是H的谱半径，这样的矩阵H被称为收敛的；见例[3,19]。我们之前提到当A时非奇异时，给定矩阵A和一个收敛矩阵H，就存在唯一相应的非奇异矩阵M使得1HIMA[10]。当A是Hermitian的且正定时，在下面的结果[20.Satz1,p.156]中给出了迭代法（2）收敛的充分条件（也见[7,p.111],[8.p.21]）,现在通常称之为P-正则分解定理。如果HMMA是正定的，则A的分解（Hermitian正定矩阵）()AMMA被称为P-正则的。定理1.令nnA£是Hermitian正定的，且()AMMA是一个P-正则分解。则()1H，其中1HIMA。经典的证明使用了Stein的理论（见例，[14,7.1.8]）。下面我们给出一个本质上相同的证明，但是强调不仅要求()1H，并且要有1AH其中算子范数AH的给出是通过能量模1/2,AAxxx，其中,,(,)AxxAxxxAx，（3）,xy表示欧式内积。这个结果很值得说明，因为它表明当能量范数是系统（1）的正则范数时，迭代（2）的误差是单调递减的。进一步，定理1中的“能量范数”也是正则收敛的，也就是说1AH表明这个分解是P-正则的。定理2.令nnA£是Hermitian正定的。则，()AMMA是一个P-正则分解当且仅当1AH。证明.可得111()()().HHHHHAHIMAAIMAAAMMMAMA则，对任意向量0u有22HHHAAHuuHAHuuAuu当且仅当HMMA是正定的。我们提到定理1的其他收敛情况也是可能的。其中一种典型结果就是给定一个P-正则分解和Hermitian矩阵A，()1H表明A是正定的，见例，[9],[14,E71.9]，且进一步，可以得到当A不是Hermitian矩阵时的结果，见例[1],[7.p.111]，并被引用其中。许多作者都给出了半正定矩阵A普遍形式下收敛的充分条件；我们将在第二部分看到，其中我们将强调基于下面定义给出的A-半范数的条件。在第三部分，我们将回答以下问题：在那种情况中这些充分条件也是必要的。2.半定的情况和A-半范数当A半定时，（3）式定义了一个半范数，而不是范数。在这部分我们将调查诱导算子A-半范数在基于分解的迭代下收敛的充分条件的细节。除了命题7以外，这部分的结果并不新鲜；然而，算子半范数的系统使用在结果的公式中提供了一种同一方法，是我们所感兴趣的。当讨论根据文章下面所述的定理6所得的各种收敛结果时我们会论证这一点。A的零空间()NullA和()()RangeANullA表示其范围，我们假设()bRangeA。这意味着（1）的解集非空且它给出了（1）的一些解*nx£的一个仿射空间*()xNullA。接着[5]，我们考虑一般情况下在（1）的哪种迭代矩阵H是这样的形式（4）其中是一个有可能奇异的矩阵。由矩阵H和诱导得到迭代（5）我们要注意这里，作为与非奇异相反的情况，对于给定的A和H，（4）中的矩阵并不唯一；参见[2].对于的最低假设要求它到()RangeA是单射，因为不这样的话，如果()bRangeA，在中0b且00x，迭代式（5）的结果全都会迭代到0，也就是迭代并不能收敛到（1）的解。（4）中迭代算子的一般形式尤其能说明由分解()AMMA所得到的迭代，其中M非奇异，在这种情况下可被当做1M。（4）在时的迭代也是一些奇异矩阵M的广义逆的伪逆解；见[4,11,12]，其中对这种迭代有过研究。这种情况尤其会出现在构造边界条件是诺依曼或罗宾型的施瓦茨迭代的分析中；见，例[13,16,18]。根据下面的定义，迭代式（5）的收敛等价于H是半收敛的；见，例[3,4,17]。定义3.一个矩阵nnH£是半收敛的，如果()1H，1是系数1的唯一特征值且1是H的半单特征值，即就是，它的几何多重性等于代数多重性。n£上的A-半范数可以导出nn£上的算子A-半范数AH通过下式2()(),1max(max).AAAxRangeAxRangeAxAAHxHxHxx（6）在正定的情况下，1AH表示()1H而且因此迭代（5）是收敛的。在半正定的情况下，用算子A-半范数可以有类似的结果。定理4.令A是Hermitian的并且是半正定的。令是迭代式（5）的迭代算子，且令1AH。则（i）在()RangeA中是单射的。（ii）H是半收敛的。证明。当假定1AH被取代为().AAxNullAHxx（7）这个结果在[5]中已经被给出。作为[15]中的标注，这两者是等价的：当表示()RangeA上的正交投影时对所有的x我们都有AAxx。由于对()yNullA有Hyy，对所有的x我们同样能得到()()HxHIxHxIxHx。这表明对于任意的x都有AAxx和AAHxHx，并且因此（7）式与下面的（8）式等价()AAxRangeAHxx（8）根据从（6）中得到的A的定义我们可以把x限制在()RangeA和单球圆的交集内，这是个紧致集，这与1AH是等价的。证毕。我们的过程通过叙述定理1和2在半定的情况下的对应情况来推进。我们说如果在n£的子空间中所有,0xVx都有,0Bxx那么Hermitian矩阵nnB£就是正定的。定理5.令nnA£是Hermitian且半正定的。令M是非奇异的，令1HIMA并且假设HMMA在1()RangeMA内是半正定的。则H是半收敛的。这个结论可以在[20,Hauptsatz,p.160]找到。通过类比正定的情况，定理5的假设已经表明1AH，且相应的逆向的结论也是成立的。此外，我们可以处理标准形式（4）的迭代矩阵H，即就是我们可以用一个在()RangeA中单射的并且可能奇异的矩阵来替换1M。注意如果或者等价地，如果存在一个矩阵M使得，则在()RangeA中是单射的。其精确结果如下并在[5]中给出。定理6.令nnA£是Hermitian且半正定的。令在()RangeA中是单射的，令nnM£满足（9）并且令。则1AH当且仅当HMMA在上是正定的。下面的命题将说明（9）中M多种可能的选择对定理中的声明并没有影响。命题7.所有满足的矩阵M在上诱导出一个相同的二次形式(),HMMAxx。证明。令,nnMM£是两个矩阵，其不同之处只在的补空间上体现。则对x有,,MxxMxx，并且，类似地，对x有,,,,HHMxxxMxxMxMxx。命题7特别说明当在()RangeA内是单射的，则要么对所有的满足的M矩阵HMMA都是正定的在内，要么就不存在M使得HMMA是正定的。我们用对两种出现在表现定理6的特殊情况的文章中的已知情况的讨论来结束这部分。我们由[4，定理3.4]开始，这里说明对于分解()AMMA,广义逆†M，如果()()RangeARangeM且HMMA在†()RangeMA上正定，则1AH。在这种方式中，[4]的结果同样可以解释[11，定理4.4]中的可能的误解。因为()()RangeARangeM表明†M在()RangeA上是单射的[4,定理3.3]，我们看到这种结果其实是当时定理6的特殊情况。论文[12]让是一个M的普通的自反逆，这里AMN，即就是说，这个矩阵满足以及。这篇文章考虑迭代（10）这与（5）中如果是一致的。这是因为以及对（10）中所有的迭代kx都有。如果0x，（10）中所有的后续迭代都属于，所以（10）中的kx和（5）中的(1)k阶迭代是完全一样的，如果（5）式把（10）式第一个迭代作为其初始向量的话。因此，（5）式收敛就表明（10）式收敛。[12]中的定理3.2现在说明如果()()RangeARangeM，HMMA是对称正定的在上并且有，对于任意的起始向量0x和()bRangeA迭代式（10）都是收敛的。这里正如之前所说的，()()RangeARangeM说明在()RangeA上是单射的，并且如果HMMA是对称正定的在上以及，则它在也是对称正定的。所以应用定理6我们又能得到。3.充分条件。在这部分我们展现一个新的结果，表明定理6所展现的充分条件在时Hermitian的时候也是必要的。我们也将展示当不是Hermitian的时候，这种情况就不是必要的了，除非2n。定理8.令nnA£是Hermitian且半正定的。令使得H是半收敛的。假设在()RangeA上单射且令M使得。（i）对于2n，且A奇异，HMMA是正定的在上（并且因此，通过定理6有，）。对于3n，这就不是必要的了。（ii）假设是Hermitian的。则（并且因此，通过定理6，HMMA是正定的在上）。证明。（i）我们首先考虑2n的情况。如果0A,我们可以得到HI是半收敛的，并且对于任意的M矩阵HMMA在上是平凡正定的。我们现在来看当A的秩为1时的情况。通过对基础的改变，而不改变其大部分，我们可以假设0,000cAc。在(){(1,0)}TRangeAspan上是单射的表明，其中(,)(0,0)ab。因此我们可以得到因为H是半收敛的，这表明0a（因为不这样的话就有0b，而这是不可能的，因为(,)(0,0)ab）并且02ac。条件（9）给出1/000aM作为M的一个可能选择。则2/0,00HacMMA因为2/0ac，所以这个矩阵在上正定。通过命题7，我们知道HMMA在上也是正定的，对于任意其它满足的M来说。当矩阵A的秩为2的时候这种情况就不再适用了，因为我们假设A是半定的而不是定的。对于3n的情况来说，我们给出受[1]启发得到的一个例子。随之则有，以及是半收敛的。但是我们有340430000HMMA在上不是正定的。通过命题7，对于任意的M满足，它的二次形式(),HMMAxx和(),HMMAxx在上是一致的，这表明对于任意的M矩阵HMMA在上都不是正定的。（ii）令并且标注这里当时我们有1/21/2,HIACHICA.对于任意两个同样大小的方阵K和L，由它们得到的KL和LK有相同的谱，例见[6，定理1.3.20]。因此，1/2AC和1/2CA拥有共同的谱，这一点对于H和H也是一样的。由于H是半收敛的，我们得到()(){1}[,]specHspecH其中[0,1)。（11）我们同样标注1/2()()RangeARangeA以及1/2()()NullANullA。我们现在首先来说明在()RangeA上是正定的，也就是说，（12）如果这里存在一