求解線性方程組的一種迭代法的改進

陳麗紅，周志剛，萬 立

求解線性方程組的一種迭代法的改進

陳麗紅，周志剛，萬 立★

（武漢紡織大學 理學院，湖北 武漢430073）

對系數為對稱正定矩陣的線性方程組，將文獻[1]中構造的收斂迭代格式進行了改進，并給出了數值仿真結果。

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

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

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

一些經典的求解線性方程組的方法如Jacobi，Gauss—seidel都是定常迭代法。不同的分裂方法可以構造多種不同的迭代算法，在多種有關文獻中都有介紹。

1 定理、定義及證明

文獻[1]給出如下定理：

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

是收斂的。（證明參看文獻[1]）

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

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

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

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

12n又的特征多

項式為：

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

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

2 數值仿真結果比較及分析

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

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

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

當dig=0.000001時，格式（3）、（4）都收斂到精確解。

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

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

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

3 格式（4）的進一步分析

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

4 結語

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

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

[2] 李慶揚. 數值計算原理[M]. 北京: 清華大學出版社, 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. 矩陣計算[M]. 袁亞湘, 譯, 北京：科學出版社, 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] 張藝. 線性方程組求解的一個迭代算法[J]. 寧波大學學報: 理工版, 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-），男，博士，研究方向：動力系統及其穩定性理論等.

武漢科技學院校基金（093877）;湖北省教育廳項目（Q20091705，2009b248）；湖北省統計局項目（HB092-28）.