劉仲云，周孜

(長(zhǎng)沙理工大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖南 長(zhǎng)沙，410114)

文中考慮用CG型方法求解全正線(xiàn)性方程組

Ax=b

(1)

其中A=[ai，j]∈Rn×n(i，j=1，2，…，n)為全正矩陣。

全正矩陣是一類(lèi)特殊的結(jié)構(gòu)矩陣，目前已有一些相關(guān)的理論與算法的研究[1-6]。

全正線(xiàn)性方程組的解法可分為直接解法和迭代解法，直接法即通過(guò)Neville消元法將系數(shù)矩陣分解為一系列下雙對(duì)角矩陣、對(duì)角矩陣和一系列上雙對(duì)角矩陣的積，進(jìn)而求解方程組[5]。關(guān)于這一類(lèi)的方程組的迭代解法的研究不多，CARNICER等[3]在2010年提出了的Richardson迭代方法解全正矩陣線(xiàn)性方程組，該方法證明了對(duì)任何的全正矩陣，一個(gè)松弛的Richardson迭代法是收斂的。

一般來(lái)說(shuō)，直接解法主要適用于小規(guī)模問(wèn)題。對(duì)于大型問(wèn)題，直接解法計(jì)算量太大且數(shù)值不穩(wěn)定，而迭代解法數(shù)值穩(wěn)定且易于并行計(jì)算。所以文中考慮用迭代解法求解全正線(xiàn)性方程組。眾所周知，一個(gè)好的預(yù)處理子可以使CG型方法具有戲劇性的收斂性。

1 預(yù)備知識(shí)

首先給出幾個(gè)定義及引理。

定義1.1[3]如果一個(gè)矩陣的任意階子式都是非負(fù)的，那么該矩陣稱(chēng)為全正矩陣。

定義1.3[5]設(shè)A是m×n階矩陣，而B(niǎo)是p×q階矩陣，則A和B的Kronecker積A?B是一個(gè)(m·p)×(n·q)階矩陣

引理 1.2[5]如果有λ(A)={λ1，…，λm}，λ(B)={μ1，…，μm}，則A，B矩陣的Kronecker積的特征值可以表示為

λ(A?B)={λiμii=1，2，…m；j=1，2，…，n}

另外，如果A，B都為全正矩陣，則A?B也為全正矩陣。

2 多水平預(yù)處理子

記{A(k)k=0，1，…l}是一個(gè)矩陣序列，Dk是k水平上所對(duì)應(yīng)的行標(biāo)的集合。

首先，定義

A(0)=A

將矩陣A(0)進(jìn)行分塊：

這里

基于以上序列，構(gòu)造一系列多水平預(yù)處理子{M(k)}。

首先，構(gòu)造A(l)的預(yù)處理子

(3)

這里

是S(l)的近似矩陣。

則當(dāng)k=l-1，l-2，…，0時(shí)，與此類(lèi)似，直到k=0，

(4)

這里

易知，在每一個(gè)水平上構(gòu)造的預(yù)處理矩陣[M(k)](k=0，1，2，…，l)是非奇異的。

3 數(shù)值實(shí)驗(yàn)

下面的數(shù)值實(shí)驗(yàn)例子是曲面擬合中兩個(gè)經(jīng)典的例子。因?yàn)橄禂?shù)矩陣不正定，所以通常用共軛梯度法求解下面的預(yù)處理線(xiàn)性方程組：

(M-1B)T(M-1B)x=(M-1B)TM-1b

(5)

(6)

對(duì)應(yīng)于曲面擬合的配置矩陣為A=Bn?Bm。

例6 令Sn是由Said-Ball基Si(t)在區(qū)間[0，1]上生成全正矩陣，這里

(7)

當(dāng)n是偶數(shù)的時(shí)候，

此處?k」表示小于或等于k的最大整數(shù)，「k?表示大于或等于k的最小整數(shù)。

則對(duì)應(yīng)于曲面擬合的配置矩A=Sn?Sm。

表1 CG解例5時(shí)所用迭代次數(shù)

Tabel 1 The iterations for example 5by CG method

nP=IP=M(m,l)48442438(88,2)67654525(145,2)72945322(160,2)84179552(137,4)96195096(116,6)1 02489984(67,14)

表2 CG解例6時(shí)所用迭代次數(shù)

Tabel 2 The iterations for example 6by CG method

nP=IP=M(m,l)3261(3,4)169177(16,4)225162(15,3)441181(25,14)676191(44,14)729192(44,14)

由以上表格可以看出，經(jīng)過(guò)預(yù)處理后的迭代步數(shù)遠(yuǎn)遠(yuǎn)小于沒(méi)有進(jìn)行預(yù)處理的迭代步數(shù)。

為了進(jìn)一步說(shuō)明其有效性，文中描繪出了例5當(dāng)n=484，例6當(dāng)n=169時(shí)，對(duì)應(yīng)的預(yù)處理矩陣的譜分布圖，如下圖所示，可以看出加了預(yù)處理子矩陣的譜更加聚集，從而也說(shuō)明該預(yù)處理子的有效性。

圖1 例5中n=484預(yù)處理矩陣的譜分布圖Fig.1 The spectral distribution of preconditioned matrix for example 5 when n=484

圖2 例6中n=169預(yù)處理矩陣的譜分布圖Fig.2 The spectral distribution of preconditioned matrix for example 6 when n=169