迭代法解線性方程組

　　下面是一篇關于迭代法解線性方程組的論文,對正在寫有關數學論文的寫作者有一定的參考價值和指導作用!

　　摘 要: 現實生活中許多數學模型都可以歸結為解線性方程組,線性方程組的解法有很多種,其中數值分析中迭代法是比較重要的一種。本文利用系數矩陣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.

【迭代法解線性方程組】相關文章：

最小比值旋轉迭代法在生產計劃中的應用10-09

學習教案進學解10-07

學習教案進學解10-07

作文素材：解網10-07

解簡易方程教案10-05

《進學解》教學方案10-08

庖丁解牛教案01-06

解函數題中類比的應用10-26

歇后語解生肖09-06

庖丁解牛教案10-08