陳麗紅，周志剛，萬 立

求解線性方程組的一種迭代法的改進(jìn)

陳麗紅，周志剛，萬 立★

（武漢紡織大學(xué) 理學(xué)院，湖北 武漢430073）

對系數(shù)為對稱正定矩陣的線性方程組，將文獻(xiàn)[1]中構(gòu)造的收斂迭代格式進(jìn)行了改進(jìn)，并給出了數(shù)值仿真結(jié)果。

線性方程組；對稱正定矩陣；收斂迭代；漸進(jìn)收斂速度

在科學(xué)技術(shù)、工程和經(jīng)濟(jì)領(lǐng)域中都會遇到解線性方程組的問題。求解線性方程組AX=b是科學(xué)計(jì)算的中心問題。解線性方程組主要有直接法和迭代法。對于大規(guī)模線性方程組的求解問題，特別是大規(guī)模稀疏線性方程組，迭代法是求解線性方程組的一種有效方法,它有存儲空間小，程序簡單等特點(diǎn)。線性方程組：的迭代格式一般按如下方式構(gòu)造，首先將矩陣A分裂：A=A1+A2，其中A1是非奇異的且易于求逆，則方程組(1)可等價(jià)地寫成：

于是方程組(1)的迭代格式可構(gòu)造為：

一些經(jīng)典的求解線性方程組的方法如Jacobi，Gauss—seidel都是定常迭代法。不同的分裂方法可以構(gòu)造多種不同的迭代算法，在多種有關(guān)文獻(xiàn)中都有介紹。

1 定理、定義及證明

文獻(xiàn)[1]給出如下定理：

定理[1]：如果A是對稱正定n×n矩陣，則線性方程組（1）的迭代格式：

是收斂的。（證明參看文獻(xiàn)[1]）

定 義 ： 迭 代 格 式 Xk+1= BXk+ F中 ，R (B)=? ln ρ( B)稱為迭代格式（2）的漸近收斂速度，其中ρ(B)為B的譜半徑。

定理[2]：如果A是對稱正定n×n矩陣，則線性方程組（1）的迭代格式：

是收斂的，且漸近收斂速度比格式（3）的漸近收斂速度快， 其中，最大特征值。

證明：設(shè) λi（i=1,2,…,n）為A的n個(gè)特征值，因A對稱正定，故 λi＞0（i=1,2,…,n）， λ1+λ2+…+λn= a11+ a22+…+ ann， 且 存 在 可 逆 P， 使 得P?1AP = diag( λ, λ,…,λ )。于是

12n又的特征多

項(xiàng)式為：

即迭代格式（4）的漸近收斂速度比格式（3）的漸近收斂速度快。證畢。

對于線性方程組（1），若A為可逆非正定矩陣，通過預(yù)處理： A:=AAT， b:=ATb，即可轉(zhuǎn)化為對稱正定矩陣，故上面僅討論了對稱正定矩陣。此外在定理[2]中只給出α的取值范圍，而且知道在給出的范圍中，α越大，迭代格式（4）的漸近收斂速度越快。在Pentium(R)4 PC、MATLAB（6.5.1版本）平臺下進(jìn)行數(shù)值仿真時(shí)，我們?nèi)镸ATLAB軟件數(shù)與數(shù)之間的最小分辨率）。

2 數(shù)值仿真結(jié)果比較及分析

下面用迭代格式（4）求解線性方程組，并與迭代格式（3）作比較。

例1 求解AX=b，其中，A=

不難知道A正定，方程組的解為：（1，2，3）。文[1]已指出用Jacobi迭代格式來解此方程組時(shí)，由于迭代矩陣譜半徑＞1,故此格式不可取。分別用迭代格式（3）和（4）結(jié)果對比如表1。

當(dāng)dig=0.000001時(shí)，格式（3）、（4）都收斂到精確解。

下面取A分別為4階和5階Pascal矩陣來做數(shù)值實(shí)驗(yàn)。Pascal矩陣為對稱正定矩陣，隨著階數(shù)的增加，病態(tài)程度越嚴(yán)重,6階Pascal矩陣的條件數(shù)為：1.1079e+005。

例2 求解AX=b，其中A分別為4階和5階Pascal

迭代格式（3）和（4）的計(jì)算結(jié)果對比見表2。在例1中，迭代格式（4）迭代次數(shù)顯然比迭代格式（3）少，但多花銷了點(diǎn)時(shí)間，隨著系數(shù)矩陣 A階數(shù)的增加，如在例2中，迭代格式（4）比格式（3）不僅迭代次數(shù)減少，而且時(shí)間花銷也少，而且A階數(shù)增加后，格式（4）比格式（3）迭代次數(shù)減少的更多，時(shí)間也花銷的更少。在表2中，A為4階Pascal矩陣時(shí)，格式（4）比格式（3）迭代次數(shù)減少了988次，時(shí)間減少了0.02s,；A為5階Pascal 矩陣時(shí)，格式（4）比格式（3）迭代次數(shù)減少了10098次，時(shí)間減少了0.18s。因此格式（4）從整體來說比格式（3）優(yōu)越。

3 格式（4）的進(jìn)一步分析

在格式（4）中α的取值與系數(shù)矩陣A的最大特征值有關(guān)，因此對A的特征值的擾動(dòng)必須作分析。Bauer-Fike定理 設(shè)μ是的一個(gè)特征值，且則有：其中為矩陣的p范數(shù)，p=1, 2,∞。（證明參閱文獻(xiàn)[4]）

4 結(jié)語

在迭代格式（4）中由于要計(jì)算A的特征值，我們能否利用定理：設(shè)則A的任一特征值λ滿足，從A本身出發(fā)，避免計(jì)算它的特征值來對格式（4）改進(jìn)，以得到更好的收斂格式是值得進(jìn)一步研究的問題。

[1] 常雙領(lǐng), 張傳林. 求解線性方程組的一種迭代解法[J]. 暨南大學(xué)學(xué)報(bào), 2004(3): 06.

[2] 李慶揚(yáng). 數(shù)值計(jì)算原理[M]. 北京: 清華大學(xué)出版社, 2000: 307-308.

[3] Mathias R. Accurate eigensystem computations by jaccobi methods[J]. SIAMJ Matrix Anal Appl, 1995(15): 215-218.

[4] 戈盧布 G H, 范洛恩C F. 矩陣計(jì)算[M]. 袁亞湘, 譯, 北京：科學(xué)出版社, 2001: 370-378.

[5] Zhang J L, Zhang X S. Neural network for linear inequalities[J]. OR Transations, 2002, 6(1): 9-18.

[6] Martin T H, Howard B D, Mark H B. Neural Network Design[M]. Beijing: K.Dai Trans.Industry Press, 2002.

[7] Zhao H M, Chen K Z. Neural network for solving systems of nonlinear equations[J]. Journal of Xidian University, 2001(2): 35-38.

[8] Burden Richard L, Faires J Douglas. Numerical analysis[M]. 7th ed. Beijing: Higher Education Press, 2001.

[9] Lou F L, Unbehauen R. Applied neural networks for signal processing[M]. London: Cambridge University Press, 1997.

[10] Abbasbandy S, Asady B. Newton’s method for solving fuzzy nonlinear equations[J]. Applied Mathematics and Computation. 2004(2): 349-356.

[11] Abbasbandy S. Extended Newton’s method for a system of nonlinear equations by modified adomian decomposition method[J].Applied Mathematics and Computation, 2005, 170: 648-656.

[12] Feiwu Chen, Daniel M Chipman. Boundary element method for dielectric cavity construction and integration[J]. J Chem Phys 2009, 119: 10289-10297.

[13] ZHOU Z G, CHEN L H Wan L. Neural Network Algorithm for Solving System of Linear Equations[J]. Proceedings of 2009 International Conference on Computational Intelligence and Natural Computing, 2009(1): 7-9.

[14] Saad Y. Numerical methods for large eigenvalue problems[M]. New York: Halstead Press NY,1992.

[15] Li Chuanguang. CGNR is an error reducing algorithm[J] . SIAM J Sci Comput, 2001, 22: 2109-2112.

[16] 張藝. 線性方程組求解的一個(gè)迭代算法[J]. 寧波大學(xué)學(xué)報(bào): 理工版, 2001, 14 (1) : 51- 55.

Improvement of an Iterative Algorithm for Linear Equation

CHEN Li-hong, ZHOU Zhi-gang, WAN Li
(Wuhan Textile University, College of Science, Wuhan 430073, China)

A convergent iterative scheme for symmetric positive definite linear equations given by paper [1] is improved and the simulative result of numerical value is put forward.

linear equation; symmetric positive definite matrix; convergent iterative; gradual convergence rate

O241.6

A

1009－5160(2010)02－0033－03

*通訊作者：萬立（1978-），男，博士，研究方向：動(dòng)力系統(tǒng)及其穩(wěn)定性理論等.

武漢科技學(xué)院?；穑?93877）;湖北省教育廳項(xiàng)目（Q20091705，2009b248）；湖北省統(tǒng)計(jì)局項(xiàng)目（HB092-28）.