線性方程組迭代解法平均收斂速度收斂階的定量估計

劉宇民

(太原師范學院數(shù)學系，山西太原030012)

在自然科學和工程技術中,很多問題的解決常常歸結為求解線性代數(shù)方程組,迭代法就是用某種極限過程去逼近線性方程組精確解的方法,該方法具有對計算機的存貯單元需求少,程序計算簡單,原始系數(shù)矩陣在計算過程中不變等優(yōu)點,是求解大型稀疏矩陣方程組的重要方法。常用的迭代法有Jacobi迭代法、Gauss-seidel迭代法等。

1 迭代法原理和性質

1.1 Jacobi迭代原理

設有方程組

其中，A∈Rn×n，x，b∈Rn。

A為非奇異矩陣,可分裂為A＝D－L－U,其中:

將式(1)用矩陣形式表示為

令

由此可構造迭代公式:

故迭代公式的形式為

這種方法稱為Jacobi迭代法,其中BJ稱為Jacobi迭代矩陣。

1.2 Gauss-Seidel迭代原理[1]

對式(1)中的系數(shù)矩陣A分裂為A＝D－L－U,其中D，L，U與式(2)相同。

將式(1)可寫成矩陣形式Dx＝b＋Lx＋Ux，進而（D－L）x＝b＋Ux,若設（D－L）－1存在,則

其中,BG＝（D－L）－1U,f＝（D－L）－1b，于是 Gauss-Seidel迭代公式的矩陣形式為

BG稱為式(1)的Gauss-Seidel迭代法的迭代矩陣。

通過實例分析,我們可以得出:由于Gauss－Seidel迭代充分利用了迭代過程的新信息,一般來說,它的迭代效果要比Jacobi迭代好[1],當然也有例外的情形。文中討論Gauss－Seidel和Jacobi迭代法的平均收斂速度與漸進收斂速度的關系。

1.3 這兩種迭代方法收斂性與Bk→0是否成立有關，且斂速與Bk→0的速度有關[1]

當 ρ（B）＜1 時,Bk趨于零矩陣的速度有賴于 ρ（B）的大小:一般說來,ρ（B）愈小,則Bk趨于零矩陣的愈快,反之就愈慢。通常,當 ρ(B)＜1時,可以用正數(shù)－1nρ(B)的大小作為迭代法漸進收斂速度的度量。這時ρ（B）愈小,迭代法的收斂速度愈大。

1.4 平均收斂速度與漸進收斂速度之間的聯(lián)系

對于收斂的迭代法xk＋1＝Bxk＋f（k＝0，1，2，…）,Rk＝－ln（‖Bk‖1/k） 稱為平均收斂速度(它與所用的范數(shù)以及 k 有關);R∞＝－lnρ（B）稱為漸進收斂速度?？梢宰C明因此當k→∞時假設成立下列漸近關系式(常數(shù)),為估計平均收斂速度收斂到漸進收斂速度的階,當k充分大時有如下近似形式:

兩邊取對數(shù)得:

此式說明當k較大時,lnRk＋1與lnRk有近似的線性關系,而它們的斜率剛好為p,這樣可以通過當k較大時作出lnRk＋1與lnRk數(shù)據擬合曲線的方法估計出收斂階p。

2 數(shù)值估計漸進收斂速度和平均收斂速度的關系

考慮五階方程組

其Jacobi迭代法的迭代矩陣為

漸進收斂速度為:

則迭代平均收斂速度Rk(見表1)以及取對數(shù)后作最小二乘擬合圖像(見圖1)如下所示:

圖1 最小二乘擬合圖像

Linear Fit:y=a+bx Coefficient Data:

a＝－0.53486615 b＝0.4411919

即

ln（Rk＋1）＝ 0.4411919ln（Rk）－0.53486615，

其中，由(3)式定義的收斂階 p＝0.4411919。而該方程組的Gauss－Seidel迭代矩陣為:

其漸進收斂速度為

R∞＝－ln（ρ(BG))＝－ln（0.425）＝0.855666，

則迭代平均收斂速度Rk(見表2)以及取對數(shù)后作最小二乘擬合圖像(見圖2)如下所示:

表1 迭代平均收斂速度Rk(以下Rk均在∞范數(shù)意義下得出)

表2 迭代平均收斂速度Rk(以下Rk均在∞范數(shù)下得出)

Linear Fit:y=a+bx Coefficient Data:a=-0.10426802 b=0.59261285

即

ln（Rk＋1）＝ 0.59261285ln（Rk）－0.10426802

從而得知由(3)式定義的收斂階為 p＝0.59261285。

注:在本例中,由于方程組的系數(shù)矩陣嚴格對角占優(yōu),故前述兩種迭代過程均收斂,依實際迭代過程:對 Jacobi迭代有‖x（34）－x（33）‖∞≤10－6‖x（33）‖∞而 Gauss-Seidel迭代有‖x（19）－x（18）‖∞≤10－6‖x（18）‖∞,即二者均收斂,但后者更快一些[1]。這與收斂階p＝0.59261285＞0.4411919 之間關系一致。

圖2 最小二乘擬合圖像

[1]陳公寧,沈嘉驥.計算方法[M].北京:高等教育出版社,2002.

[2]蔡大用.數(shù)值分析與實驗學習指導[M].4版.北京:清華大學出版社,2001.

[3]李慶揚,王能超,易大義.數(shù)值分析[M].武漢:華中科技大學出版社,2006.

[4]王兵團,桂文豪.數(shù)學實驗基礎[M].北京:北方交通大學出版社,2003.

[5]吳勃英.數(shù)值分析[M].北京:高等教育出版社,2007.

[6]趙秉新,鄭來運.MATLAB在求解線性方程組的應用[J].通化師范學院學報,2007,28(12):13-15.

[7]宋道金,趙文玲.線性方程組的補充定理[J].淄博學院學報,2000,2(3):3-5.

[8]Richard L，Burden,Douglas J,et al.NUMERICAL ANALYSIS數(shù)值分析[M].北京:高等教育出版社，2005.