1、河南師大數學與信息科學學院河南師大數學與信息科學學院線性方程組迭代解法線性方程組迭代解法本章討論解線性方程組 bAx 古典迭代解法。主要內容包括：雅可比(Jacobi)迭代法高斯-賽德爾(Gauss-Seidel)迭代法超松馳(SOR)迭代法收斂性分析.;,.,) 1 . 4(, 2 , 1,)0()1()()0(或或發發散散的的否否則則就就稱稱它它是是不不收收斂斂的的斂斂的的則則稱稱該該迭迭代代法法是是收收序序列列有有極極限限如如果果由由算算法法產產生生的的向向量量叫叫做做叫叫做做做做叫叫其其中中的的迭迭代代稱稱作作形形如如指指定定初初始始向向量量代代算算法法我我們們很很容容易易建建立立如如

2、下下迭迭那那么么假假若若線線性性方方程程組組初始向量常數項迭代矩陣單步線性定常迭代.nnnnkkxgMkgMxxxgxMxbAxRRR單步線性定常迭代算法單步線性定常迭代算法雅可比(Jacobi)迭代法0000,0000),(:, 122311312, 1213231212211nnnnnnnnnnaaaaaaUaaaaaaLaaadiagDULDAbAx其其中中令令考考慮慮線線性性方方程程組組.),(,11bDgULDBgBxxbAx其中其中可等價寫成可等價寫成那么那么。JacobiBkgBxxxxxxJacobikkTn迭代矩陣迭代矩陣稱為稱為其中其中給定給定迭代法迭代法我們得到我們得到從

3、而從而, 2 , 1,),(:,)1()()0()0(2)0(1)0(雅可比迭代法的分量形式nnnnnnnnnnnnnnnnnnnababababgaaaaaaaaaaaaaaaaaaaaaaaaULDBJacobi333222111,1,2,1 , 13332333122222232221111111311121,0000)(迭迭代代矩矩陣陣注注意意到到., 2 , 1., 2 , 1,1)1(,11)1(,)(kniaxaxabxJacobiiinijkjjiijkjjiiki迭代法的分量形式為迭代法的分量形式為于是于是雅可比迭代程序設計編制計算程序時,應注意以下幾個問題:.,.;, 0否

4、否則則迭迭代代終終止止時時迭迭代代繼繼續續當當大大限限定定值值和和最最量量還還需需要要增增設設迭迭代代次次數數變變情情形形如如果果考考慮慮到到算算法法發發散散的的否否則則繼繼續續迭迭代代終終止止算算法法當當并并確確定定一一種種向向量量范范數數預預定定一一個個允允許許誤誤差差常常量量CNTcountCNTcountxy )(:,1bxULDyyxyx這這樣樣作作為為輸輸出出作作為為輸輸入入和和設設置置向向量量根根據據迭迭代代法法的的特特點點2. 算法的終止3. 程序設計點擊對象展開程序點擊對象展開程序1. 算法的實現高斯-賽德爾(Gauss-Seidel)迭代法0000,0000),(:, 12

5、2311312, 1213231212211nnnnnnnnnnaaaaaaUaaaaaaLaaadiagDULDAbAx其其中中令令考考慮慮線線性性方方程程組組.)(,)(,11bLDgULDGgxGxbAx其中其中可等價寫成可等價寫成那么那么。SeidelGaussSGGkgxGxxxxxSeidelGaussSGkkTn迭代矩陣迭代矩陣稱為稱為其中其中給定給定迭代法迭代法我們得到我們得到從而從而)(, 2 , 1,),(:)(,)1()()0()0(2)0(1)0(G-S迭代法的分量形式., 2 , 1., 2 , 1,)(,1)1(,11)(,)(1)1(1)(1)()1()(knia

6、xaxabxSGbDUxDLxDxbUxxLDiinijkjjiijkjjiikikkkkk迭代法的分量形式為迭代法的分量形式為于是于是所以所以由于由于.,) 3(.,)2(.,) 1 (:很大的區別很大的區別因此它們的收斂性有著因此它們的收斂性有著陣區別很大陣區別很大但迭代矩但迭代矩迭代法的分量形式相似迭代法的分量形式相似迭代法和迭代法和盡管盡管計算順序有關計算順序有關迭代法與分量的迭代法與分量的而而關系關系迭代與分量的順序沒有迭代與分量的順序沒有量量出向量的已計算好的分出向量的已計算好的分時地使用了輸時地使用了輸子中的前一個和式中及子中的前一個和式中及區別僅在于右端迭代式區別僅在于右端迭代

7、式似似迭代的分量形式非常相迭代的分量形式非常相迭代法的分量形式與迭代法的分量形式與注意注意SGJacobiSGJacobiJacobiSGG-S迭代程序設計編制計算程序時,應注意以下幾個問題:.,.;, 0否否則則迭迭代代終終止止時時迭迭代代繼繼續續當當大大限限定定值值和和最最量量還還需需要要增增設設迭迭代代次次數數變變情情形形如如果果考考慮慮到到算算法法發發散散的的否否則則繼繼續續迭迭代代終終止止算算法法當當并并確確定定一一種種向向量量范范數數預預定定一一個個允允許許誤誤差差常常量量CNTcountCNTcountxy )( :,1bxULDxx既既作作為為輸輸入入又又作作為為輸輸出出只只需

8、需要要設設置置向向量量根根據據迭迭代代法法的的特特點點2. 算法的終止3. 程序設計點擊對象展開程序點擊對象展開程序1. 算法的實現超松馳(Successive Overrelaxation)迭代法0000,0000),(:, 122311312, 1213231212211nnnnnnnnnnaaaaaaUaaaaaaLaaadiagDULDAbAx其其中中令令考考慮慮線線性性方方程程組組.)(,)()()1 (,11bLDgULDGgxGxxbAx其其中中可可等等價價寫寫成成那那么么對對于于任任一一正正數數 )1()(:, 2 , 1, )()1 (,),(:)(,1)1()(1)1()(

9、)0()0(2)0(1)0(UDLDLkbUxxLDxxxxxxtionOverrelaxaSuccessiveSORkkkkTn 其迭代矩陣為其迭代矩陣為給定給定迭代法迭代法我們得到我們得到從而從而SOR迭代法的分量形式., 2 , 1., 2 , 1)1 (,1)1(,11)(,)1()(kniaxaxabxxSGiinijkjjiijkjjiikiki 迭代法的分量形式為迭代法的分量形式為于是于是.,)4(.,)3(.,1)2()1 (,) 1 (:)()1()()()1(,1)1()1(,11)()(,)(應應該該存存在在最最佳佳松松馳馳因因子子程程來來說說甚甚至至對對一一特特定定的的

10、方方導導致致不不同同的的迭迭代代效效果果不不同同的的松松馳馳因因子子可可能能會會算算法法具具有有相相對對的的可可變變性性因因此此子子由由于于算算法法引引入入了了松松馳馳因因有有關關迭迭代代與與分分量量的的計計算算順順序序迭迭代代法法一一樣樣與與迭迭代代法法就就轉轉化化為為了了時時當當作作如如下下組組合合和和對對確確定定一一個個正正數數即即迭迭代代的的一一種種外外推推是是迭迭代代法法實實質質上上可可以以看看作作注注意意SORSORSGSGSORxxxxxaxaxabxSGSORkikikikikiiinijkjkjiijkjkjiiki G-S迭代程序設計編制計算程序時,應注意以下幾個問題:.,

11、.;, 0否否則則迭迭代代終終止止時時迭迭代代繼繼續續當當大大限限定定值值和和最最量量還還需需要要增增設設迭迭代代次次數數變變情情形形如如果果考考慮慮到到算算法法發發散散的的否否則則繼繼續續迭迭代代終終止止算算法法當當并并確確定定一一種種向向量量范范數數預預定定一一個個允允許許誤誤差差常常量量CNTcountCNTcountxy )( :,1bxULDxx既既作作為為輸輸入入又又作作為為輸輸出出只只需需要要設設置置向向量量根根據據迭迭代代法法的的特特點點2. 算法的終止3. 程序設計點擊對象展開程序點擊對象展開程序1. 算法的實現注意注意: : 迭代陣迭代陣M不唯一不唯一, ,影響收斂性。影響

12、收斂性。1()max |()|ii n MM (0)( )(1)( )0,1,2,;.kknnAxbxMxgxxMxgkx線性方程組單步線性定常迭代算法指定初始向量如果由收斂算法產生的向量序列有極限 則稱該迭代法是的不收斂否則就稱它是的發散或的單步線性定常迭代法的收斂性單步線性定常迭代法的收斂性定義定義：矩陣M的譜半徑譜半徑為：定義定義：如果存在矩陣G使：G(I M)=A，Gg=b.則稱迭代法與方程組Ax=b是相容相容的。0 ()kk Mn nMCn nC()MM0nnC()MM引理引理1 迭代法迭代法 收斂當且僅當收斂當且僅當引理引理4.3.2 設設 ，則有，則有 1. 對對 上的任意矩陣范

13、數上的任意矩陣范數 ，有，有2. 對任給的對任給的 ,存在存在 上的算子范數上的算子范數 使得使得(1)( )kkxMxg注注: 引理的詳細證明過程引理的詳細證明過程,請閱讀第四章請閱讀第四章,第第3節節.定理定理1 1 當且僅當當且僅當 定理定理2 2 單步線性定常迭代法收斂當且僅當單步線性定常迭代法收斂當且僅當1.M（）,0()n nkk MRM1.M（）例例 1 當方程組的系數矩陣為122111221A可以驗證：Jacobi迭代收斂，而Gauss-Seidel迭代不收斂。 例例 2 當方程組的系數矩陣為211111112A可以驗證：Jacobi迭代不收斂，而Gauss-Seidel迭代收

14、斂。 例例3 3 對于方程組對于方程組1212321532xxxx JacobiJacobi迭代公式為迭代公式為，迭代矩陣為23103530, ( )10BB Gauss-Seidel Gauss-Seidel迭代公式為迭代公式為(1)()121233(1)(1)522133kkkkxxxx，迭代矩陣為231091090, ( )10GG(1)()121233(1)()522133kkkkxxxx顯然，兩種迭代都不收斂。顯然，兩種迭代都不收斂。 若將方程的順序調整，即若將方程的順序調整，即1212532321xxxx JacobiJacobi迭代公式為迭代公式為，迭代矩陣為353 101032

15、0, ( )10BB Gauss-Seidel Gauss-Seidel迭代公式為迭代公式為(1)()321255(1)(1)312122kkkkxxxx，迭代矩陣為359109100, ( )10GG(1)()321255(1)()312122kkkkxxxx顯然，兩種迭代都收斂。顯然，兩種迭代都收斂。1 qM1I)(kx*x,1)0()1(*)(xxqqxxkk定理定理3 若迭代矩陣M的范數 且 ，則單步線性定常迭代的第k次迭代向量與準確解的誤差有估計式 ,1)()1(*)(kkkxxqqxx1 qM1I)(kx*x定理定理4 若迭代矩陣M的范數 且 ，則單步線性定常迭代的第k次迭代向量與準確解的誤差有估計式定理定理5 5 若系數矩陣A對稱，對角線元素),.,2 , 1(0niaii則Jacobi迭代收斂的充分必要條件是A和2D-A都正定。定理定理6 6 若系數矩陣A正定，則G-S迭代收斂。定理定理7 7 若矩陣A是嚴格