王芳，馬艷麗

(1.安徽外國語學(xué)院 公共基礎(chǔ)課教學(xué)部，安徽 合肥 231200；2.安徽新華學(xué)院 通識教育部，安徽 合肥 230088)

對于求解大型稀疏線性方程組Ax=b，其中A∈Rm×m，x，b∈m×1.文[1]中有以下結(jié)論：

其中，rank(A)=r，A11是矩陣A的一個(gè)最大線性無關(guān)子塊，P、Q為相應(yīng)的置換矩陣，R是任意一個(gè)r階的非奇異矩陣.可知，得到M+的關(guān)鍵在于提取矩陣A的一個(gè)最大線性無關(guān)子塊A11，本文將給出提取A11及相應(yīng)的置換矩陣P、Q的算法.

1 相關(guān)定義及引理

定義1 若矩陣A的秩為r，則A必有一個(gè)非奇異的子矩陣A11∈Rr×r，稱A11為矩陣A的最大線性無關(guān)子塊.

2 提取A11及相應(yīng)置換矩陣P,Q的算法

則

故

是齊次線性方程組Λix=0的一個(gè)解.其中

算法1：

(1)size(A)=[m,n]，置初始量：m階單位矩陣Im×m,n階單位矩陣In×n，l=2，k=1，s=[1]；

(2)若a11=0，aij≠0，則將Im×m第一行與第i行互換，In×n的第一列與第j列互換，并將互換后的矩陣記作P1與Q1，令A(yù)=P1AQ1；

算法2：

(2)置初始量：m階單位矩陣Im×m,n階單位矩陣In×n；

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

以下數(shù)值實(shí)驗(yàn)均在Intel(R) Core(TM) i5-8265U CPU@1.60GHz 1.80GHz內(nèi)存為8.00 GB的個(gè)人計(jì)算機(jī)上完成，所用軟件為MATLAB R2018a，矩陣來自“Matrix Market”，皆為實(shí)數(shù)矩陣.取初始向量x0=0，停機(jī)準(zhǔn)則為：

數(shù)值實(shí)驗(yàn)2 使用算法2提取以下矩陣的最大線性無關(guān)子塊，其中ε取1.0×10-10，t表示算法2運(yùn)行時(shí)間(單位為秒)，運(yùn)算結(jié)果見表1..

表1 算法2的運(yùn)行時(shí)間(單位為秒)

數(shù)值實(shí)驗(yàn)3(見文獻(xiàn)[3]) 對于泊松方程

考慮周期邊界條件u(x,0)=u(x,1),u(0,y)=u(1,y),則矩陣A是如下矩陣，其中h=1/m，n=m2，α±=1±dh/2，取m=64，d=10，即得A是4 096×4 096階矩陣.

rank(BBT)=1，rank(CTC)=1，

圖1 數(shù)值實(shí)驗(yàn)2的收斂圖像

4 小 結(jié)

綜上所述，預(yù)條件QMR算法與預(yù)條件TFQMR算法，預(yù)條件GMRES算法是高效的，對于提取大型稀疏矩陣的最大線性無關(guān)子塊A11，算法中ε的取值，對算法有一定的影響.構(gòu)造基于恰當(dāng)分裂的預(yù)條件子時(shí)，如果需要提取最大線性無關(guān)子塊A11，代價(jià)也是昂貴的.