求解非埃爾米特正定方程組的廣義LHSS迭代法

初魯， 鮑亮， 董貝貝

(華東理工大學(xué) 理學(xué)院， 上海 200237)

對于大規(guī)模正定線性方程組的求解問題，迭代法是目前的主要方法. 2001年，BAI等[1]提出了一類HSS迭代法，該方法因具有形式簡單、易程序化等優(yōu)點，成為當前的研究熱點，得到了許多新的推廣. 基于HSS迭代法，BAI等[2]給出了PSS算法, CAO等[3]對PSS算法做了改進，給出了廣義PSS(GPSS)算法，LI等[4]給出了修正的GPSS算法；HUANG等[5]將系數(shù)矩陣分解成正定和半正定兩部分，在這兩部分之間進行迭代；2007年，LI等[6]提出了一類LHSS(Lopsided HSS)迭代算法，在系數(shù)矩陣的埃爾米特和非埃爾米特之間做非對稱迭代，此算法格式簡單，在參數(shù)較為松弛的約束條件下即可達到收斂；后來，POUR等[7]在LHSS法基礎(chǔ)上提出了一類新的HSS方法，圍繞系數(shù)矩陣的埃爾米特部分做二步非對稱迭代.

本文對LHSS迭代法做進一步研究，將方程組的系數(shù)矩陣分解成2個正定部分，然后在這2個正定部分間做非對稱迭代，給出了一類廣義LHSS迭代法.數(shù)值結(jié)果表明，只要恰當?shù)貙⑾禂?shù)矩陣分解為2個正定部分，廣義LHSS迭代法在處理某些問題時能取得比HSS迭代法更好的效果.

1 背景知識

在多學(xué)科領(lǐng)域常出現(xiàn)Ax=b形式的大規(guī)模線性方程組，其中A∈Cn×n為非埃爾米特正定矩陣.為了求解該方程，BAI等[1]在矩陣的HS分解(埃爾米特和反埃爾米特分解)基礎(chǔ)上提出了HSS迭代算法,該算法基于以下分解：

A=H+S，

(1)

然后給出一個初始向量x(0)∈Cn，通過以下2步計算x(k+1)，直到迭代序列{x(k)}收斂：

(2)

其中α為大于0的常數(shù).對于HSS迭代法，BAI等[1]證明了其迭代矩陣的譜半徑小于1，即HSS算法收斂.

2007年，LI等[6]提出了一類LHSS迭代法，該迭代法在系數(shù)矩陣A的埃爾米特部分H和反埃爾米特部分S之間做非對稱二步迭代. LHSS迭代法的迭代過程如下：

給定初始向量x(0)∈Cn，通過以下2步計算x(k+1)，直到序列{x(k)}滿足停止條件：

(3)

其中α為大于0的常數(shù).

2 廣義LHSS迭代法

本文對LHSS迭代法做進一步研究，給出了廣義LHSS(GLHSS)迭代算法以及相應(yīng)迭代法的格式.

首先，任意非埃爾米特正定矩陣A有以下分裂形式[3]：

A=G+K+S，

(4)

其中，S表示反埃爾米特矩陣，G和K表示埃爾米特正定矩陣.

其次，任意非埃爾米特正定矩陣A又可分裂為以下形式：

A=P1+P2，

(5)

其中，P1和P2為正定矩陣.

P1和P2的2種可供選擇的格式如下：

最后，在系數(shù)矩陣A的分裂矩陣P1和P2之間做非對稱的二步迭代，得到GLHSS迭代法.

算法1GLHSS迭代算法.

給定初始向量x(0)∈Cn，通過以下2步計算x(k+1)，直到迭代序列{x(k)}滿足停止條件：

(6)

其中α為大于0的常數(shù).

3 收斂性證明

為得到GLHSS迭代法的收斂性質(zhì)，需要以下引理：

引理1[8]設(shè)A∈Cn×n，A=Mi-Ni(i=1,2)為矩陣A的2種分裂格式，x(0)∈Cn為一個給定的初始向量，由矩陣A的2種分裂格式得到的二步迭代格式為：

(7)

由上述二步迭代生成的迭代序列{x(k)}為

(8)

(9)

則對于任意初向量x(0)∈Cn，矩陣序列{x(k)}收斂于線性方程Ax=b的唯一解x*∈Cn.

引理2對?α>0,若矩陣P為復(fù)數(shù)域上的正定矩陣，則‖P(αI+P)-1‖2<1，其中‖‖2表示矩陣的二范數(shù).

證明因P為正定矩陣，P*也為正定矩陣，α為一個大于0的常數(shù)，則對任意非零向量y有

〈(α2I+P+P*)y,y〉>0，

(10)

其中〈,〉表示向量內(nèi)積，式(10)兩端同時加上〈P*Py,y〉有

〈(α2I+P+P*+P*P)y,y〉>〈P*Py,y〉，

(11)

整理后即得

〈(αI+P)y,(αI+P)y〉>〈Py,Py〉.

(12)

令x=(αI+P)y，由于矩陣αI+P非奇異，所以對于任意非零向量x，都可找到一個非零向量y與之對應(yīng)，經(jīng)變換，式(12)可化為

〈x,x〉>〈P(αI+P)-1x,P(αI+P)-1x〉，

(13)

于是可得

(14)

由向量x的任意性可得

‖P(αI+P)-1‖2<1.

(15)

證畢！

‖(αI-P)P-1‖2<1.

〈αy,y〉<〈Hy,y〉.

代入H=(P+P*)，得到

〈αy,y〉<〈(P+P*)y,y〉.

(16)

式(16)兩邊做進一步整理，得

〈(α2I-αP-αP*+P*P)y,y〉<〈P*Py,y〉.

(17)

于是有

〈(αI-P)y,(αI-P)y〉<〈Py,Py〉.

(18)

令x=Py，由于y為任意非零向量且矩陣P為非奇異矩陣，因此，x可選取為任意非零向量，經(jīng)變換，式(18)可化為

〈(αI-P)P-1x,(αI-P)P-1x〉<〈x,x〉，

(19)

變形后得到

(20)

由于x的選取是任意的，因此，對于任意大于0的常數(shù)α有

‖(αI-P)P-1‖2<1 .

(21)

證畢！

證明由引理1，GLHSS迭代法對應(yīng)的迭代矩陣為

(22)

式(22)相似于：

(23)

對M′(α)譜半徑ρ(M′(α))，有：

(24)

綜上,即可得到M′(α)的譜半徑ρ(M′(α))<1；再由矩陣的相似性質(zhì)，即可得到ρ(M(α))<1.

證畢！

4 數(shù)值實驗

數(shù)值實驗中用Matlab編程求解以下大型稀疏矩陣的線性方程組：

Ax=b，A=I?B+BT?I，

其中，

M=tridiag(-1,2,-1)N=tridiag(0.5,0,-0.5)，

tridiag表示三對角矩陣，?表示克羅內(nèi)克積.當n=8和16時，系數(shù)矩陣的維度實際上為64×64階和256×256階，記達到截斷誤差所需的迭代時間為CPU，迭代次數(shù)為IT，實驗中截斷誤差選為10-6，使用英特爾四核處理器(2.70 GHZ，8 GB RAM).表1～表2，圖1～圖4為2種算法的比較.

表1 n=8時HSS和GLHSS法的迭代次數(shù)和迭代時間比較

表2 n=16時HSS和GLHSS法的迭代次數(shù)和迭代時間比較

圖1 n=8時HSS與GLHSS法譜半徑比較Fig.1 Comparison of spectral radius between HSS and GLHSS when n=8

圖2 n=16時HSS與GLHSS法譜半徑比較Fig.2 Comparison of spectral radius between HSS and GLHSS when n=16

圖3 n=8時HSS與GLHSS法殘量下降速度比較Fig.3 Comparison of residual decline between HSS and GLHSS when n=8

圖4 n=16時HSS與GLHSS法殘量下降速度比較Fig.4 Comparison of residual decline between HSS and GLHSS when n=16

從圖1～圖4、表1和表2中可以看出，對于本文中的算例，GLHSS法到達截斷誤差所需的迭代步數(shù)及迭代時間均優(yōu)于HSS，GLHSS迭代矩陣的最小譜半徑優(yōu)于HSS，且殘量下降速度亦優(yōu)于HSS.

5 總 結(jié)

提出了一種廣義的LHSS(GLHSS)迭代法用于求解大規(guī)模正定線性方程組，數(shù)值結(jié)果表明，該方法在求解某些問題時較經(jīng)典的HSS迭代法效果更好.將來的研究可以圍繞如何選取更佳的正定矩陣來開展.