求解病態(tài)線(xiàn)性方程組的精細(xì)積分新主元加權(quán)迭代法

郝 強(qiáng)，王慧蓉,常金勇

(1.長(zhǎng)治學(xué)院 數(shù)學(xué)系, 山西 長(zhǎng)治 046011;2.西安建筑科技大學(xué) 信息與控制工程學(xué)院, 陜西 西安 710055)

對(duì)一般的線(xiàn)性方程組求解算法的研究已經(jīng)非常成熟.但在許多實(shí)際問(wèn)題中，往往會(huì)涉及病態(tài)方程組的求解問(wèn)題.許多學(xué)者對(duì)病態(tài)方程組的求解算法進(jìn)行了大量的研究.富明慧等[1]利用精細(xì)積分法的思想，將病態(tài)代數(shù)方程組歸結(jié)為一個(gè)常微分方程初值問(wèn)題的極限形式，提出了一種求解病態(tài)代數(shù)方程的精細(xì)積分解法，具有較高的精度和效率.唐麗等[2]通過(guò)在系數(shù)矩陣主元上疊加一個(gè)權(quán)值降低條件數(shù)，提出了求解病態(tài)方程組的主元加權(quán)迭代解法.潘軼等[3]將誤差轉(zhuǎn)移與主元加權(quán)迭代法相結(jié)合，提出了一種改進(jìn)的主元加權(quán)迭代算法.富明慧等[4-5]將范數(shù)均衡法與精細(xì)積分法相結(jié)合，提出了一種范數(shù)均衡預(yù)處理精細(xì)積分法，以及一個(gè)求解病態(tài)方程組的形式簡(jiǎn)單、便于應(yīng)用的迭代終止準(zhǔn)則.

論文將新主元加權(quán)迭代法與精細(xì)積分法相結(jié)合，提出了一種求解病態(tài)線(xiàn)性方程組的精細(xì)積分新主元加權(quán)迭代算法，并用這種方法求解兩種病態(tài)方程組.實(shí)驗(yàn)結(jié)果表明，論文提出的算法不僅提高了病態(tài)方程組的求解精度，而且大大減少了迭代次數(shù)，提高了計(jì)算效率.

1 精細(xì)積分法

對(duì)于線(xiàn)性方程組

Ax=b，

(1)

其中：系數(shù)矩陣A為正定矩陣.

對(duì)式(1)用預(yù)處理精細(xì)積分法進(jìn)行求解.由

(-A)-1(0-1)=A-1,

記

(2)

則

即

F(2τ)=(I+exp(-Aτ))F(τ)，

(3)

式(3)兩邊同時(shí)乘以b，得

F(2τ)*b=(I+exp(-Aτ))F(τ)*b，

(4)

將式(4)寫(xiě)成迭代格式，得

xk+1=(I+exp(-2kAτ))xk.

(5)

對(duì)式(5)中的exp(-2kAτ)可以用精細(xì)積分求解.對(duì)exp(-Aτ)進(jìn)行Taylor展開(kāi)，取τ是一個(gè)非常小的正數(shù)，只需取前幾項(xiàng)就能滿(mǎn)足精度要求，得

(6)

將式(6)帶入式(2)，得

(7)

記

將(6)式寫(xiě)成等號(hào)，得

exp(-Aτ)=I+Ta.

由于

exp(-2kAτ)=(exp(-Aτ))2k=((exp(-Aτ))2)2k-1，

(exp(-Aτ))2=(I+Ta)2=I+2Ta+Ta2，

構(gòu)造迭代格式

Ta=2Ta+Ta2，

(8)

循環(huán)k次后，有

exp(-2kAτ)=I+Ta，

(9)

將式(5)與式(8)，(9)兩個(gè)過(guò)程合二為一，寫(xiě)成迭代格式，即

(10)

2 精細(xì)積分新主元加權(quán)迭代法

根據(jù)主元加權(quán)的思想[6]，對(duì)病態(tài)線(xiàn)性方程組(1)，兩邊同時(shí)加上ωPx(ω>0,P為對(duì)角矩陣)，其中

則病態(tài)線(xiàn)性方程組(1)變?yōu)?/p>

(A+ωP)x=b+ωPx，

(11)

將式(11)寫(xiě)成迭代格式為

(A+ωP)x(k+1)=b+ωPx(k).

(12)

定理1若A為正定矩陣，對(duì)于初始值x(0)=0，當(dāng)0<ω<1時(shí)，由迭代格式(12)產(chǎn)生的序列{x(k)}收斂.

證明A為正定矩陣，當(dāng)0<ω<1時(shí)，A+ωP也為正定矩陣.由(12)式可知

(A+ωP)x(1)=b+ωPx(0)，

(13)

(A+ωP)x(2)=b+ωPx(1)，

(14)

(14)式減(13)式，得

(A+ωP)(x(2)-x(1))=ωP(x(1)-x(0))，

(15)

記z(k)=(x(k+1)-x(k))，則(15)式可以寫(xiě)成(A+ωP)z(1)=ωPz(0)，進(jìn)而可得(A+ωP)z(k)=ωPz(k-1)，即

z(k)=(A+ωP)-1ωPz(k-1)=(A+ωP)-1ωP((A+ωP)-1ωPz(k-2))=

ω2((A+ωP)-1P)2z(k-2)，

依次迭代下去，得

z(k)=ωk((A+ωP)-1P)kz(1)，

(16)

對(duì)(16)式兩端同時(shí)左乘以(P-1(A+ωP))k，得

(P-1(A+ωP))kz(k)=ωkx(1).

(17)

由(13)式可知，當(dāng)x(0)=0時(shí)，有

(A+ωP)x(1)=b，

(18)

將(18)式代入(17)式，得

(A+ωP)(P-1(A+ωP))kz(k)=ωkb，

顯然，當(dāng)0<ω<1時(shí)，有

引理[7]若A為正定矩陣，當(dāng)0<ω<1時(shí)，有

cond2(A+ωP)

由式(10)，(12)，得到新的迭代格式

(19)

迭代終止的條件有兩個(gè)：一是設(shè)置閾值，即對(duì)迭代算法需要迭代的次數(shù)設(shè)置一個(gè)上限.它是一種經(jīng)驗(yàn)式的迭代終止條件，具有很大的不確定性，并且不能保證其有效性和相應(yīng)的精度.二是引進(jìn)迭代殘差，即前后兩次迭代的差小于一個(gè)非常小的量，即err(k)=‖xk-xk-1‖<ε.但是，這種方法在求解病態(tài)方程組時(shí)效果不是很好.基于以上方法，文獻(xiàn)[8]提出了一種新的迭代終止準(zhǔn)則，即把迭代殘差看作是兩個(gè)過(guò)程算法：?jiǎn)握{(diào)下降過(guò)程和單調(diào)上升過(guò)程，而最為理想的迭代終止點(diǎn)會(huì)出現(xiàn)在下降過(guò)程到上升過(guò)程的拐點(diǎn)處，即迭代終止條件滿(mǎn)足err(k)/err(k-1)≥1.

3 實(shí)驗(yàn)結(jié)果與分析

3.1 以Hilbert矩陣為系數(shù)矩陣的病態(tài)方程組的求解

Hilbert矩陣的定義采用以下形式

H=(hij)n×n，

Hx=b，

其精確解可以取為x=[1,1,1,…，1].

對(duì)于上述例子，在相同條件下，取ω=0.000 01,τ=1e-8，將論文方法與主元加權(quán)改善法、新主元加權(quán)法的絕對(duì)誤差和迭代次數(shù)進(jìn)行比較，實(shí)驗(yàn)結(jié)果見(jiàn)表1,2.

表1 3種方法絕對(duì)誤差對(duì)比

通過(guò)表1的實(shí)驗(yàn)結(jié)果可以看出，論文算法精度要優(yōu)于主元加權(quán)改善法和新主元加權(quán)法.通過(guò)表2的迭代次數(shù)對(duì)比可以看出，論文算法的迭代次數(shù)要遠(yuǎn)遠(yuǎn)小于后面兩種方法.

表2 3種方法迭代次數(shù)對(duì)比

3.2 以Vandermonde矩陣為系數(shù)矩陣的病態(tài)方程組的求解

取Vandermonde矩陣[9]為下列形式

其中:x向量的定義為x=H×1,H為與Vandermonde矩陣同階的Hilbert矩陣，1為元素全為1的列向量，精確解同樣取為x=[1,1,1,…,1].

Vandermonde矩陣是一個(gè)高度病態(tài)的矩陣，階數(shù)比較小時(shí)，會(huì)出現(xiàn)很大的條件數(shù).下面采用論文提出的求解病態(tài)線(xiàn)性方程組的精細(xì)積分新主元加權(quán)迭代算法對(duì)此病態(tài)方程組進(jìn)行求解，并與精確解進(jìn)行比較，實(shí)驗(yàn)結(jié)果見(jiàn)表3.

表3 論文算法結(jié)果和真解對(duì)比

從表3中的實(shí)驗(yàn)數(shù)據(jù)可以看到，Vandermonde矩陣的條件數(shù)受階數(shù)的影響非常大，條件數(shù)隨著其階數(shù)的增加急劇增大，論文的算法所得結(jié)果與真解相比達(dá)到了令人滿(mǎn)意的結(jié)果，并且迭代次數(shù)比較少.

4 結(jié)束語(yǔ)

通過(guò)構(gòu)造一個(gè)特殊矩陣，對(duì)病態(tài)方程組的系數(shù)矩陣進(jìn)行主元加權(quán)，并將其與精細(xì)積分法相結(jié)合，提出了一種新主元加權(quán)迭代法和精細(xì)積分相結(jié)合的方法.數(shù)值實(shí)驗(yàn)結(jié)果表明，和主元加權(quán)改善法和新主元加權(quán)法相比較，該方法無(wú)論在計(jì)算精度還是計(jì)算效率方面都有提升，是一種有效的求解病態(tài)方程組的迭代方法.