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

1、Hermitian半正定线性系统中定长迭代法收敛的必要条件Andreas Frommer, Daniel B. Szyld关键词线性系统 奇异线性系统 定长迭代法 半模 收敛性分析摘要在之前的文章中我们得到了定常迭代收敛的能量半模的充分条件，且该迭代是对于系数矩阵是Hermitian的且半正定的线性系统的。在这篇文章中，我们将说明在什么情况下这些条件依旧必要，以及在什么情况下不然。1. 介绍我们考虑一个（奇异）线性系统 （1）假设其中系数矩阵是Hermitian的且半正定的。如果是大型稀疏矩阵，迭代思想是解决问题（1）的标准方法。在本文中，我们关注定常迭代法，例如，代数多重网格法，加性和乘性施

2、瓦茨法。有时，通过把它们作为Kryov子空间法的预调节器，这些迭代法是加速的，就像共轭梯度一样。当我们不考虑后者的任何细节，只涉及其中通常假设预调节器是收敛的作为前提条件的情况，所以我们的工作在这种情况中也是相关的。对于定常迭代法，我们通常考虑用非奇异矩阵分离，得到一个迭代矩阵,并且得到迭代式. （2）众所周知，当是非奇异的，对任意起始向量当且仅当时，迭代（2）收敛到一个（1）的唯一解，其中是的谱半径，这样的矩阵被称为收敛的；见例3,19。我们之前提到当时非奇异时，给定矩阵和一个收敛矩阵，就存在唯一相应的非奇异矩阵使得10。当是Hermitian的且正定时，在下面的结果20.Satz 1,p.

3、156中给出了迭代法（2）收敛的充分条件（也见7,p.111,8.p.21）,现在通常称之为-正则分解定理。如果 是正定的，则的分解（Hermitian正定矩阵）被称为-正则的。定理1.令是Hermitian正定的，且是一个-正则分解。则 ，其中。经典的证明使用了Stein的理论（见例，14, 7.1.8）。下面我们给出一个本质上相同的证明，但是强调不仅要求，并且要有其中算子范数的给出是通过能量模，其中， （3）表示欧式内积。这个结果很值得说明，因为它表明当能量范数是系统（1）的正则范数时，迭代（2）的误差是单调递减的。进一步，定理1中的“能量范数”也是正则收敛的，也就是说表明这个分解是-正则

4、的。定理2. 令是Hermitian正定的。则，是一个-正则分解当且仅当。证明. 可得则，对任意向量有当且仅当是正定的。我们提到定理1的其他收敛情况也是可能的。其中一种典型结果就是给定一个-正则分解和Hermitian矩阵，表明是正定的，见例，9,14,E71.9，且进一步，可以得到当不是Hermitian矩阵时的结果，见例1,7.p.111，并被引用其中。许多作者都给出了半正定矩阵普遍形式下收敛的充分条件；我们将在第二部分看到，其中我们将强调基于下面定义给出的-半范数的条件。在第三部分，我们将回答以下问题：在那种情况中这些充分条件也是必要的。2. 半定的情况和-半范数当半定时，（3）式定义了

5、一个半范数，而不是范数。在这部分我们将调查诱导算子-半范数在基于分解的迭代下收敛的充分条件的细节。除了命题7以外，这部分的结果并不新鲜；然而，算子半范数的系统使用在结果的公式中提供了一种同一方法，是我们所感兴趣的。当讨论根据文章下面所述的定理6所得的各种收敛结果时我们会论证这一点。的零空间和表示其范围，我们假设。这意味着（1）的解集非空且它给出了（1）的一些解的一个仿射空间。接着5，我们考虑一般情况下在（1）的哪种迭代矩阵是这样的形式 （4）其中是一个有可能奇异的矩阵。由矩阵和诱导得到迭代 （5）我们要注意这里，作为与非奇异相反的情况，对于给定的和，（4）中的矩阵并不唯一；参见2. 对于的最低

6、假设要求它到是单射，因为不这样的话，如果，在中且，迭代式（5）的结果全都会迭代到，也就是迭代并不能收敛到（1）的解。（4）中迭代算子的一般形式尤其能说明由分解所得到的迭代，其中非奇异，在这种情况下可被当做。（4）在时的迭代也是一些奇异矩阵的广义逆的伪逆解；见4,11,12，其中对这种迭代有过研究。这种情况尤其会出现在构造边界条件是诺依曼或罗宾型的施瓦茨迭代的分析中；见，例13,16,18。根据下面的定义，迭代式（5）的收敛等价于是半收敛的；见，例3,4,17。定义3.一个矩阵是半收敛的，如果，是系数1的唯一特征值且是的半单特征值，即就是，它的几何多重性等于代数多重性。上的-半范数可以导出上的算

7、子-半范数通过下式 （6）在正定的情况下，表示而且因此迭代（5）是收敛的。在半正定的情况下，用算子-半范数可以有类似的结果。定理4.令是Hermitian的并且是半正定的。令是迭代式（5）的迭代算子，且令。则（i）在中是单射的。（ii）是半收敛的。证明。当假定被取代为（7）这个结果在5中已经被给出。作为15中的标注，这两者是等价的：当表示上的正交投影时对所有的我们都有。由于对有，对所有的我们同样能得到。这表明对于任意的都有和，并且因此（7）式与下面的（8）式等价 （8）根据从（6）中得到的的定义我们可以把限制在和单球圆的交集内，这是个紧致集，这与是等价的。证毕。我们的过程通过叙述定理1和2在半

8、定的情况下的对应情况来推进。我们说如果在的子空间中所有都有那么Hermitian矩阵 就是正定的。定理5.令是Hermitian且半正定的。令是非奇异的，令并且假设在内是半正定的。则是半收敛的。这个结论可以在20,Hauptsatz,p.160找到。通过类比正定的情况，定理5的假设已经表明，且相应的逆向的结论也是成立的。此外，我们可以处理标准形式（4）的迭代矩阵，即就是我们可以用一个在中单射的并且可能奇异的矩阵来替换。注意如果或者等价地，如果存在一个矩阵使得，则在中是单射的。其精确结果如下并在5中给出。定理6.令是Hermitian且半正定的。令在中是单射的，令满足 （9）并且令。则当且仅当在

9、上是正定的。下面的命题将说明（9）中多种可能的选择对定理中的声明并没有影响。命题7.所有满足的矩阵在上诱导出一个相同的二次形式。证明。令是两个矩阵，其不同之处只在的补空间上体现。则对有，并且，类似地，对有。命题7特别说明当在内是单射的，则要么对所有的满足的矩阵都是正定的在内，要么就不存在使得是正定的。我们用对两种出现在表现定理6的特殊情况的文章中的已知情况的讨论来结束这部分。我们由4，定理3.4开始，这里说明对于分解,广义逆，如果且在上正定，则。在这种方式中，4的结果同样可以解释11，定理4.4中的可能的误解。因为表明在上是单射的4,定理3.3，我们看到这种结果其实是当时定理6的特殊情况。论文

10、12让是一个的普通的自反逆，这里，即就是说，这个矩阵满足以及。这篇文章考虑迭代（10）这与（5）中如果是一致的。这是因为以及对（10）中所有的迭代都有。如果，（10）中所有的后续迭代都属于，所以（10）中的和（5）中的阶迭代是完全一样的，如果（5）式把（10）式第一个迭代作为其初始向量的话。因此，（5）式收敛就表明（10）式收敛。12中的定理3.2现在说明如果，是对称正定的在上并且有，对于任意的起始向量和迭代式（10）都是收敛的。这里正如之前所说的，说明在上是单射的，并且如果是对称正定的在上以及，则它在也是对称正定的。所以应用定理6我们又能得到。3. 充分条件。在这部分我们展现一个新的结果，表

11、明定理6所展现的充分条件在时Hermitian的时候也是必要的。我们也将展示当不是Hermitian的时候，这种情况就不是必要的了，除非。定理8.令是Hermitian且半正定的。令使得是半收敛的。假设在上单射且令使得。（）对于，且奇异，是正定的在上（并且因此，通过定理6有，）。对于，这就不是必要的了。（）假设是Hermitian的。则（并且因此，通过定理6，是正定的在上）。证明。（）我们首先考虑的情况。如果,我们可以得到是半收敛的，并且对于任意的矩阵在上是平凡正定的。我们现在来看当的秩为时的情况。通过对基础的改变，而不改变其大部分，我们可以假设。在上是单射的表明，其中。因此我们可以得到因为是

12、半收敛的，这表明（因为不这样的话就有，而这是不可能的，因为）并且。条件（9）给出作为的一个可能选择。则因为，所以这个矩阵在上正定。通过命题7， 我们知道在上也是正定的，对于任意其它满足的来说。当矩阵的秩为的时候这种情况就不再适用了，因为我们假设是半定的而不是定的。对于的情况来说，我们给出受1启发得到的一个例子。随之则有，以及是半收敛的。但是我们有在上不是正定的。通过命题7，对于任意的满足，它的二次形式和在上是一致的，这表明对于任意的矩阵在上都不是正定的。（）令并且标注这里当时我们有.对于任意两个同样大小的方阵和，由它们得到的和有相同的谱，例见6，定理1.3.20。因此，和拥有共同的谱，这一点对

13、于和也是一样的。由于是半收敛的，我们得到其中。 （11）我们同样标注以及。我们现在首先来说明在上是正定的，也就是说，（12）如果这里存在一个向量，它使得，则其中，并且因此有我们可以把化成标准的并由此我们可以看出Hermitian矩阵有一个大于的Rayleigh商。这是不可能的，因为是最大的特征值，见（11）。此外，如果这个向量使得，则并且由此得到，这表明因为我们假设在上是单射的。我们由此证明了（12）。现在，令，则并且由此有。因为在上是正定的，这说明，即就是说，。因为显然，无论何时我们都能得到，就有（13）为了完成证明我们标注这里由于对于所有的都有，我们得到（14）因为是Hermitian的，这承认了特征向量的一个标准正交基。通过（13），我们可以得到是由的特征向量生成的空间，其特征值并由（11）我们知道他们是来自的。因此在（14）中我们得到。4. 结论在早期的工作中，已经说明对于一个以Hermitian半正定矩阵为系数矩阵的线性系统，以迭代矩阵为的定常迭代收敛一个充分条件，其中在上是单射的，是