Hermitian半正定線性系統(tǒng)中定長迭代法收斂的必要條件

1、Hermitian半正定線性系統(tǒng)中定長迭代法收斂的必要條件Andreas Frommer, Daniel B. Szyld關(guān)鍵詞線性系統(tǒng) 奇異線性系統(tǒng) 定長迭代法 半模 收斂性分析摘要在之前的文章中我們得到了定常迭代收斂的能量半模的充分條件，且該迭代是對于系數(shù)矩陣是Hermitian的且半正定的線性系統(tǒng)的。在這篇文章中，我們將說明在什么情況下這些條件依舊必要，以及在什么情況下不然。1. 介紹我們考慮一個(gè)（奇異）線性系統(tǒng) （1）假設(shè)其中系數(shù)矩陣是Hermitian的且半正定的。如果是大型稀疏矩陣，迭代思想是解決問題（1）的標(biāo)準(zhǔn)方法。在本文中，我們關(guān)注定常迭代法，例如，代數(shù)多重網(wǎng)格法，加性和乘性施

2、瓦茨法。有時(shí)，通過把它們作為Kryov子空間法的預(yù)調(diào)節(jié)器，這些迭代法是加速的，就像共軛梯度一樣。當(dāng)我們不考慮后者的任何細(xì)節(jié)，只涉及其中通常假設(shè)預(yù)調(diào)節(jié)器是收斂的作為前提條件的情況，所以我們的工作在這種情況中也是相關(guān)的。對于定常迭代法，我們通常考慮用非奇異矩陣分離，得到一個(gè)迭代矩陣,并且得到迭代式. （2）眾所周知，當(dāng)是非奇異的，對任意起始向量當(dāng)且僅當(dāng)時(shí)，迭代（2）收斂到一個(gè)（1）的唯一解，其中是的譜半徑，這樣的矩陣被稱為收斂的；見例3,19。我們之前提到當(dāng)時(shí)非奇異時(shí)，給定矩陣和一個(gè)收斂矩陣，就存在唯一相應(yīng)的非奇異矩陣使得10。當(dāng)是Hermitian的且正定時(shí)，在下面的結(jié)果20.Satz 1,p.

3、156中給出了迭代法（2）收斂的充分條件（也見7,p.111,8.p.21）,現(xiàn)在通常稱之為-正則分解定理。如果 是正定的，則的分解（Hermitian正定矩陣）被稱為-正則的。定理1.令是Hermitian正定的，且是一個(gè)-正則分解。則 ，其中。經(jīng)典的證明使用了Stein的理論（見例，14, 7.1.8）。下面我們給出一個(gè)本質(zhì)上相同的證明，但是強(qiáng)調(diào)不僅要求，并且要有其中算子范數(shù)的給出是通過能量模，其中， （3）表示歐式內(nèi)積。這個(gè)結(jié)果很值得說明，因?yàn)樗砻鳟?dāng)能量范數(shù)是系統(tǒng)（1）的正則范數(shù)時(shí)，迭代（2）的誤差是單調(diào)遞減的。進(jìn)一步，定理1中的“能量范數(shù)”也是正則收斂的，也就是說表明這個(gè)分解是-正則

4、的。定理2. 令是Hermitian正定的。則，是一個(gè)-正則分解當(dāng)且僅當(dāng)。證明. 可得則，對任意向量有當(dāng)且僅當(dāng)是正定的。我們提到定理1的其他收斂情況也是可能的。其中一種典型結(jié)果就是給定一個(gè)-正則分解和Hermitian矩陣，表明是正定的，見例，9,14,E71.9，且進(jìn)一步，可以得到當(dāng)不是Hermitian矩陣時(shí)的結(jié)果，見例1,7.p.111，并被引用其中。許多作者都給出了半正定矩陣普遍形式下收斂的充分條件；我們將在第二部分看到，其中我們將強(qiáng)調(diào)基于下面定義給出的-半范數(shù)的條件。在第三部分，我們將回答以下問題：在那種情況中這些充分條件也是必要的。2. 半定的情況和-半范數(shù)當(dāng)半定時(shí)，（3）式定義了

5、一個(gè)半范數(shù)，而不是范數(shù)。在這部分我們將調(diào)查誘導(dǎo)算子-半范數(shù)在基于分解的迭代下收斂的充分條件的細(xì)節(jié)。除了命題7以外，這部分的結(jié)果并不新鮮；然而，算子半范數(shù)的系統(tǒng)使用在結(jié)果的公式中提供了一種同一方法，是我們所感興趣的。當(dāng)討論根據(jù)文章下面所述的定理6所得的各種收斂結(jié)果時(shí)我們會論證這一點(diǎn)。的零空間和表示其范圍，我們假設(shè)。這意味著（1）的解集非空且它給出了（1）的一些解的一個(gè)仿射空間。接著5，我們考慮一般情況下在（1）的哪種迭代矩陣是這樣的形式 （4）其中是一個(gè)有可能奇異的矩陣。由矩陣和誘導(dǎo)得到迭代 （5）我們要注意這里，作為與非奇異相反的情況，對于給定的和，（4）中的矩陣并不唯一；參見2. 對于的最低

6、假設(shè)要求它到是單射，因?yàn)椴贿@樣的話，如果，在中且，迭代式（5）的結(jié)果全都會迭代到，也就是迭代并不能收斂到（1）的解。（4）中迭代算子的一般形式尤其能說明由分解所得到的迭代，其中非奇異，在這種情況下可被當(dāng)做。（4）在時(shí)的迭代也是一些奇異矩陣的廣義逆的偽逆解；見4,11,12，其中對這種迭代有過研究。這種情況尤其會出現(xiàn)在構(gòu)造邊界條件是諾依曼或羅賓型的施瓦茨迭代的分析中；見，例13,16,18。根據(jù)下面的定義，迭代式（5）的收斂等價(jià)于是半收斂的；見，例3,4,17。定義3.一個(gè)矩陣是半收斂的，如果，是系數(shù)1的唯一特征值且是的半單特征值，即就是，它的幾何多重性等于代數(shù)多重性。上的-半范數(shù)可以導(dǎo)出上的算

7、子-半范數(shù)通過下式 （6）在正定的情況下，表示而且因此迭代（5）是收斂的。在半正定的情況下，用算子-半范數(shù)可以有類似的結(jié)果。定理4.令是Hermitian的并且是半正定的。令是迭代式（5）的迭代算子，且令。則（i）在中是單射的。（ii）是半收斂的。證明。當(dāng)假定被取代為（7）這個(gè)結(jié)果在5中已經(jīng)被給出。作為15中的標(biāo)注，這兩者是等價(jià)的：當(dāng)表示上的正交投影時(shí)對所有的我們都有。由于對有，對所有的我們同樣能得到。這表明對于任意的都有和，并且因此（7）式與下面的（8）式等價(jià) （8）根據(jù)從（6）中得到的的定義我們可以把限制在和單球圓的交集內(nèi)，這是個(gè)緊致集，這與是等價(jià)的。證畢。我們的過程通過敘述定理1和2在半

8、定的情況下的對應(yīng)情況來推進(jìn)。我們說如果在的子空間中所有都有那么Hermitian矩陣 就是正定的。定理5.令是Hermitian且半正定的。令是非奇異的，令并且假設(shè)在內(nèi)是半正定的。則是半收斂的。這個(gè)結(jié)論可以在20,Hauptsatz,p.160找到。通過類比正定的情況，定理5的假設(shè)已經(jīng)表明，且相應(yīng)的逆向的結(jié)論也是成立的。此外，我們可以處理標(biāo)準(zhǔn)形式（4）的迭代矩陣，即就是我們可以用一個(gè)在中單射的并且可能奇異的矩陣來替換。注意如果或者等價(jià)地，如果存在一個(gè)矩陣使得，則在中是單射的。其精確結(jié)果如下并在5中給出。定理6.令是Hermitian且半正定的。令在中是單射的，令滿足 （9）并且令。則當(dāng)且僅當(dāng)在

9、上是正定的。下面的命題將說明（9）中多種可能的選擇對定理中的聲明并沒有影響。命題7.所有滿足的矩陣在上誘導(dǎo)出一個(gè)相同的二次形式。證明。令是兩個(gè)矩陣，其不同之處只在的補(bǔ)空間上體現(xiàn)。則對有，并且，類似地，對有。命題7特別說明當(dāng)在內(nèi)是單射的，則要么對所有的滿足的矩陣都是正定的在內(nèi)，要么就不存在使得是正定的。我們用對兩種出現(xiàn)在表現(xiàn)定理6的特殊情況的文章中的已知情況的討論來結(jié)束這部分。我們由4，定理3.4開始，這里說明對于分解,廣義逆，如果且在上正定，則。在這種方式中，4的結(jié)果同樣可以解釋11，定理4.4中的可能的誤解。因?yàn)楸砻髟谏鲜菃紊涞?,定理3.3，我們看到這種結(jié)果其實(shí)是當(dāng)時(shí)定理6的特殊情況。論文

10、12讓是一個(gè)的普通的自反逆，這里，即就是說，這個(gè)矩陣滿足以及。這篇文章考慮迭代（10）這與（5）中如果是一致的。這是因?yàn)橐约皩Γ?0）中所有的迭代都有。如果，（10）中所有的后續(xù)迭代都屬于，所以（10）中的和（5）中的階迭代是完全一樣的，如果（5）式把（10）式第一個(gè)迭代作為其初始向量的話。因此，（5）式收斂就表明（10）式收斂。12中的定理3.2現(xiàn)在說明如果，是對稱正定的在上并且有，對于任意的起始向量和迭代式（10）都是收斂的。這里正如之前所說的，說明在上是單射的，并且如果是對稱正定的在上以及，則它在也是對稱正定的。所以應(yīng)用定理6我們又能得到。3. 充分條件。在這部分我們展現(xiàn)一個(gè)新的結(jié)果，表

11、明定理6所展現(xiàn)的充分條件在時(shí)Hermitian的時(shí)候也是必要的。我們也將展示當(dāng)不是Hermitian的時(shí)候，這種情況就不是必要的了，除非。定理8.令是Hermitian且半正定的。令使得是半收斂的。假設(shè)在上單射且令使得。（）對于，且奇異，是正定的在上（并且因此，通過定理6有，）。對于，這就不是必要的了。（）假設(shè)是Hermitian的。則（并且因此，通過定理6，是正定的在上）。證明。（）我們首先考慮的情況。如果,我們可以得到是半收斂的，并且對于任意的矩陣在上是平凡正定的。我們現(xiàn)在來看當(dāng)?shù)闹葹闀r(shí)的情況。通過對基礎(chǔ)的改變，而不改變其大部分，我們可以假設(shè)。在上是單射的表明，其中。因此我們可以得到因?yàn)槭?/p>

12、半收斂的，這表明（因?yàn)椴贿@樣的話就有，而這是不可能的，因?yàn)椋┎⑶?。條件（9）給出作為的一個(gè)可能選擇。則因?yàn)椋赃@個(gè)矩陣在上正定。通過命題7， 我們知道在上也是正定的，對于任意其它滿足的來說。當(dāng)矩陣的秩為的時(shí)候這種情況就不再適用了，因?yàn)槲覀兗僭O(shè)是半定的而不是定的。對于的情況來說，我們給出受1啟發(fā)得到的一個(gè)例子。隨之則有，以及是半收斂的。但是我們有在上不是正定的。通過命題7，對于任意的滿足，它的二次形式和在上是一致的，這表明對于任意的矩陣在上都不是正定的。（）令并且標(biāo)注這里當(dāng)時(shí)我們有.對于任意兩個(gè)同樣大小的方陣和，由它們得到的和有相同的譜，例見6，定理1.3.20。因此，和擁有共同的譜，這一點(diǎn)對

13、于和也是一樣的。由于是半收斂的，我們得到其中。 （11）我們同樣標(biāo)注以及。我們現(xiàn)在首先來說明在上是正定的，也就是說，（12）如果這里存在一個(gè)向量，它使得，則其中，并且因此有我們可以把化成標(biāo)準(zhǔn)的并由此我們可以看出Hermitian矩陣有一個(gè)大于的Rayleigh商。這是不可能的，因?yàn)槭亲畲蟮奶卣髦?，見?1）。此外，如果這個(gè)向量使得，則并且由此得到，這表明因?yàn)槲覀兗僭O(shè)在上是單射的。我們由此證明了（12）。現(xiàn)在，令，則并且由此有。因?yàn)樵谏鲜钦ǖ?，這說明，即就是說，。因?yàn)轱@然，無論何時(shí)我們都能得到，就有（13）為了完成證明我們標(biāo)注這里由于對于所有的都有，我們得到（14）因?yàn)槭荋ermitian的，這承認(rèn)了特征向量的一個(gè)標(biāo)準(zhǔn)正交基。通過（13），我們可以得到是由的特征向量生成的空間，其特征值并由（11）我們知道他們是來自的。因此在（14）中我們得到。4. 結(jié)論在早期的工作中，已經(jīng)說明對于一個(gè)以Hermitian半正定矩陣為系數(shù)矩陣的線性系統(tǒng)，以迭代矩陣為的定常迭代收斂一個(gè)充分條件，其中在上是單射的，是