數值分析中的迭代法解線性方程組

摘 要: 現實生活中許多數學模型都可以歸結為解線性方程組，線性方程組的解法有很多種，其中數值分析中迭代法是比較重要的一種。本文利用系數矩陣A的對角線上元素的和給出了線性方程組Ax=b的一種新的迭代格式。

關鍵詞: 數值分析迭代法線性方程組

在工程技術、自然科學和社會科學中的許多問題最終都可歸結為解線性方程組，因此線性方程組的求解對于解決實際問題是極其重要的。線性方程組的解法有很多種，其中數值分析中的迭代法是比較重要的一種。

迭代法的基本思想是將線性方程組:

Ax=b(其中A∈R，b∈R)，(1)

經過變換構造出一個等價同解方程組:x=Mx+c，然后改寫成Jacobi迭代式:

x=Mx+c(k=0，1，2，…)，(2)

或者Gauss-Seidel迭代式:

x=Bx+Bx+c(k=0，1，2，…)(其中B+B=M)，

選定初始向量:x=(x，x，…，x)，反復不斷地使用迭代式來構造一個序列:{x}(k=0，1，2，…)。如果{x}(k=0，1，2，…)收斂，它就是該方程組的近似解序列，否則它就沒有實用價值。本文利用系數矩陣A的對角線上元素的和給出了系數為對稱正定矩陣的線形方程組Ax=b的一種新的定常迭代格式，如果系數矩陣A為可逆的非正定矩陣，可以通過預處理轉化為正定矩陣，令A:=AA，b:=Ab即可。且充分考慮加快計算速度。

一、收斂定理及證明

1.引理:如果M是一個n×n矩陣，對任意的n維向量c迭代格式(2)收斂的充分必要條件是ρ(M)<1，其中ρ(M)為矩陣的M譜半徑。

證明見文獻[1]。

2.定理1:如果A為對稱正定n×n矩陣，則線形方程組Ax=b的迭代格式

x=[I-A]x+(3)

是收斂的。

證明見文獻[3]。

對任意系數為正定矩陣的線性方程組，迭代格式(3)都是收斂的，因為收斂速度取決于迭代矩陣譜半徑的大小，譜半徑越小，收斂速度越快，譜半徑越大，收斂速度越慢。但迭代格式(3)只能保證迭代矩陣的譜半徑小于1，如果迭代矩陣的譜半徑非常接近1，其收斂速度是非常慢的。

下面通過在迭代格式(3)中引入一個因子來改進收斂速度。

構造迭代格式:

{y=[I-A]x+b(4)

或者與(4)等價的迭代格式:

x=[I-A]x+b(5)

3.定理2:如果A為對稱正定n×n矩陣，則線性方程組Ax=b的迭代格式(5)是收斂的。

證明:設λ(i=1，2，…，n)為A的n個特征值，因為A是對稱正定矩陣，所以λ>0(i=1，2，…，n)，λ+λ+…+λ=a+a+…+a。

I-A的n個特征值為1-(i=1，2，…，n)，

顯然-1<1-<1(i=1，2，…，n)，

這樣有ρ[I-A]<1，由引理知迭代格式(5)是收斂的。

如果正定線性方程組Ax=b的系數矩陣特征值的分布相對比較集中，還可以進一步對定理2的迭代格式進行改進，以加快計算速度。

當系數矩陣的特征值分布比較集中時，(i=1，2，…，n)近似等于，

即A的特征值近似等于。

構造迭代格式:

{y=[I-A]x+b(6)

或者與(6)等價的迭代格式:

x=[I-A]x+b(7)

因為當系數矩陣的特征值分布比較集中時，(i=1，2，…，n)近似等于，這時迭代格式(7)的迭代矩陣[I-A]的譜半徑就與0非常接近，從而使得收斂速度極快。

4.定理3:迭代格式(7)收斂的充分必要條件是:

<，i=1，2，…，n(8)

證明:迭代格式(7)收斂的充分必要條件是其迭代矩陣I-A的譜半徑小于1，

而矩陣I-A的譜半徑小于1的充分必要條件是:

<2，即<，i=1，2，…，n。

5.推論1:迭代格式(7)收斂的充分條件是λ≤2λ。

證:因為λ≤2λ，所以得到:<，i=1，2，…，n，

即迭代格式(7)是收斂的。

二、實驗結果

在特征值分布比較集中時，分別用迭代格式(7)對應的算法(iterativen函數)與Gauss_seidel迭代算法、Cholesky分解算法對系數矩陣的階數J=100，200，500，1000的4個線性方程組進行計算，對所耗時間進行比較，結果如下表:

Iterativen，Gauss_seidel，Cholesky算法耗時比較表

雖然Gauss_seidel算法的迭代次數比Iterativen算法少，但是Gauss_seidel算法在求逆的過程中浪費了大量的時間。當系數矩陣的特征值比較集中時，Iterativen算法要遠遠優于其他2種方法。

參考文獻:

[1]Kelley C T.Iterative Methods for Linear and Nonlinear Equations[M].Philade-lphia U.S.A:SIAM，1995.

[2]張傳林.數值方法[M].北京:中國科學文化出版社，2001:80-150.

[3]戈盧布·G.H，范洛恩·C.F著.袁亞湘譯.矩陣計算[M].北京:科學出版社，2002.

[4]許波，劉征.Matlab工程數學應用[M].北京:清華大學出版社，2000.

[5]James W Demmel.Applied Numerical Linear Algebra[M].Philadelphia U.S.A:SIAM，1997.