第四章_線性方程組的迭代解法

1、第第 4 章章理學(xué)院應(yīng)用數(shù)學(xué)系理學(xué)院應(yīng)用數(shù)學(xué)系立體化教學(xué)資源系列立體化教學(xué)資源系列數(shù)值分析數(shù)值分析線性方程組迭代解法線性方程組迭代解法4.1 引言引言當(dāng)當(dāng)A為低階稠密矩陣時，選主元消去法是有效方法。為低階稠密矩陣時，選主元消去法是有效方法。對于對于大型稀疏的線性方程組迭代法是合適的。大型稀疏的線性方程組迭代法是合適的。迭代法的基本步驟迭代法的基本步驟（1 1）等價形式）等價形式B稱為迭代矩陣；稱為迭代矩陣；fBxx（2 2）迭代公式）迭代公式), 2 , 1 , 0()() 1(kfBxxkk線性方程組線性方程組 bAx A為非奇異矩陣為非奇異矩陣。基本思想基本思想:用某種極限過程逐步逼近方程

2、組的精確解。用某種極限過程逐步逼近方程組的精確解。（3 3）任取向量）任取向量,由上式生成向量序列由上式生成向量序列 ) 0(x；若；若 )(kx，則迭代過程收斂，則迭代過程收斂 。*)(limxxkk線性方程組迭代解法線性方程組迭代解法（3 3）計算機(jī)算法？）計算機(jī)算法？本章討論本章討論（2 2）迭代法的收斂性與收斂速度？誤差估計？）迭代法的收斂性與收斂速度？誤差估計？（1 1）常用的迭代方法及具體形式？常用的迭代方法及具體形式？4.2 基本迭代法基本迭代法4.2.1 雅可比迭代法雅可比迭代法一、三階方程組的雅可比（一、三階方程組的雅可比（Jacobi）迭代法）迭代法例例1 1 解方程組解方

3、程組 .14103, 53102,14310321321321xxxxxxxxx線性方程組迭代解法線性方程組迭代解法解解 1 1）等價形式）等價形式 ).314(101),325(101),314(101213212321xxxxxxxxx2 2）雅可比迭代公式）雅可比迭代公式 .,2,1 ,0),314(101),325(101),314(101)(2)(1)1(3)(2)(1)1(2)(3)(2)1(1kxxxxxxxxxkkkkkkkkk3 3）取初始向量）取初始向量 Tx)0,0,0()0(4 . 11014, 5 . 0105, 4 . 11014)1(3)1(2)1(1xxx.終止

4、條件終止條件 線性方程組迭代解法線性方程組迭代解法 ( ) kxTx)1 , 1 , 1 (*顯然迭代序列顯然迭代序列逐步逼近精確解逐步逼近精確解迭代計算結(jié)果如表迭代計算結(jié)果如表 (7)(6)(7)(6)(0.002,0.00567,0.002) ,0.00567Txxxx(7)*(7)*(0.00176,0.00126,0.00176) ,0.00176Txxxx二、二、n階方程組的雅可比迭代法階方程組的雅可比迭代法niaii,2, 1,0), 2 , 1(11nibxaxaxaininiiii),2, 1()(1nixabaxnijijjijiiii線性方程組迭代解法線性方程組迭代解法第第

5、i個方程個方程 對于對于n階線性方程組階線性方程組Ax= =b, ,A為非奇異矩陣，且為非奇異矩陣，且 等價方程組等價方程組 雅可比雅可比(Jacobi)(Jacobi)迭代公式迭代公式：對于：對于 ,2, 1 ,0k),2, 1() (11)(i)1(nixabaxnijjkjijiiki任取任取)0(x( ),0,1, kxk ,計算得計算得三、雅可比迭代法的矩陣描述三、雅可比迭代法的矩陣描述ULDA，其中，其中， 線性方程組迭代解法線性方程組迭代解法nnaaaD221100021323121nnaaaaaL0001112nnnaaaU max)1(1)()1(kikinikkxxxx終止

6、條件終止條件)1(kx為滿足精度為滿足精度 的近似值。的近似值。bxULDAx)(bxULDx)(，即，即 bDxULDx11)(雅可比迭代公式的矩陣形式雅可比迭代公式的矩陣形式JkJkfxBx)()1(bDfJ1線性方程組迭代解法線性方程組迭代解法稱為雅可比迭代矩陣，稱為雅可比迭代矩陣， )(1ULDBJ其中，其中，雅可比迭代法的雅可比迭代法的MATLABMATLAB程序：程序：Jacobi.mJacobi.mfunctionx,k,index=functionx,k,index=Jacobi(A,b,ep,it_maxJacobi(A,b,ep,it_max) ) % %求線性方程組的求線

7、性方程組的JacobiJacobi迭代法，其中，迭代法，其中，%A%A為方程組的系數(shù)矩陣；為方程組的系數(shù)矩陣；%b%b為方程組的右端項；為方程組的右端項；% %epep為精度要求，缺省值為精度要求，缺省值1e-51e-5；%it_max%it_max為最大迭代次數(shù)，缺省值為最大迭代次數(shù)，缺省值100100；%x%x為方程組的解；為方程組的解；%k%k為迭代次數(shù)；為迭代次數(shù)；%index%index為指標(biāo)變量，為指標(biāo)變量，index=0index=0表示迭代失敗，表示迭代失敗，%index=1%index=1表示收斂到指定要求表示收斂到指定要求.n,m=size(A);.n,m=size(A);

8、nbnb=length(b); =length(b); % %當(dāng)方程組行與列的維數(shù)不相等時，停止計算，并輸當(dāng)方程組行與列的維數(shù)不相等時，停止計算，并輸出出錯信息出出錯信息. . 線性方程組迭代解法線性方程組迭代解法if n=mif n=m error(The rows and columns of matrix A error(The rows and columns of matrix A must be equal!);must be equal!); return; return;endend% %當(dāng)方程組與右端項的維數(shù)不匹配時，停止計算，當(dāng)方程組與右端項的維數(shù)不匹配時，停止計算，并輸出

9、出錯信息并輸出出錯信息. .if m=nb error(The columns of A must be equal the length of b!); return;end if nargin4 it_max=100;endif nargin3 ep=1e-5;end線性方程組迭代解法線性方程組迭代解法k=0;x=zeros(n,1);y=zeros(n,1);index=1;k=0;x=zeros(n,1);y=zeros(n,1);index=1;while 1while 1 for i=1:n for i=1:n y(i)=b(i); y(i)=b(i); for j=1:n for

10、 j=1:n if j=i if j=i y(i)=y(i)-A(i,j) y(i)=y(i)-A(i,j)* *x(j);x(j); end end end end if abs(A(i,i)1e-10|k=it_max index=0;return; end y(i)=y(i)/A(i,i); end 線性方程組迭代解法線性方程組迭代解法k=k+1;k=k+1; if if norm(y-x,infnorm(y-x,inf)epep break; break; end end x=y; x=y;endend調(diào)用函數(shù)調(diào)用函數(shù) Jacobi.mJacobi.m 解例解例1.1.線性方程組迭代解

11、法線性方程組迭代解法得到得到輸入輸入A=10 3 1;2 -10 3;1 3 10;b=14 -5 14;A=10 3 1;2 -10 3;1 3 10;b=14 -5 14;epep=0.005;=0.005;x,k,index=x,k,index=Jacobi(A,b,epJacobi(A,b,ep) )x = 0.9982 k = 7 index = 1 x = 0.9982 k = 7 index = 1 迭代成功，收斂。迭代成功，收斂。 1.0001 1.0001 0.9982 0.9982function function x,k,index=x,k,index=Jacobi_ma

12、trix(A,b,ep,it_maxJacobi_matrix(A,b,ep,it_max) ) % %解線性方程組的解線性方程組的JacobiJacobi迭代矩陣方法迭代矩陣方法if if narginnargin4 it_max=100;end4 it_max=100;endif if narginnargin3 3 epep=1e-5;end=1e-5;endn=length(A);x=zeros(n,1);y=zeros(n,1); n=length(A);x=zeros(n,1);y=zeros(n,1); index=1;k=0;index=1;k=0;D=D=diag(diag(

13、Adiag(diag(A); % D); % D為為A A的對角元矩陣的對角元矩陣U=-triu(A,1); % -UU=-triu(A,1); % -U為為A A的上三角矩陣的上三角矩陣L=-tril(A,-1); % -LL=-tril(A,-1); % -L為為A A的下三角矩陣的下三角矩陣 f=Db;B=D(L+U);% Bf=Db;B=D(L+U);% B為為JacobiJacobi迭代矩陣迭代矩陣 while 1 while 1 if if abs(prod(diag(Aabs(prod(diag(A)1e-10|k=it_max)1e-10|k=it_max線性方程組迭代解法線性

14、方程組迭代解法雅可比迭代矩陣描述的雅可比迭代矩陣描述的MATLABMATLAB程序程序: :Jacobi_matrix.m index=0;return;index=0;return;endendy=By=B* *x+f;k=k+1;x+f;k=k+1;if if norm(y-x,infnorm(y-x,inf)epep break; break; end end x=y; x=y;end end x=y x=y 調(diào)用函數(shù)調(diào)用函數(shù)Jacobi_matrix.mJacobi_matrix.m解例解例1 1線性方程組迭代解法線性方程組迭代解法輸入輸入A=10 3 1;2 -10 3;1 3 10

15、;b=14 -5 14; A=10 3 1;2 -10 3;1 3 10;b=14 -5 14; epep=0.005;=0.005;x,k,index=x,k,index=Jacobi_matrix(A,b,epJacobi_matrix(A,b,ep) ) 4.2.2 高斯高斯塞德爾迭代法塞德爾迭代法.14103,53102,14310321321321xxxxxxxxx線性方程組迭代解法線性方程組迭代解法例例2 2 解下面方程組（與例解下面方程組（與例1 1相同，精確解相同，精確解 Tx) 1 , 1 , 1 (* ）解解 1 1） 等價方程組等價方程組 ).314(101),325(1

16、01),314(101213212321xxxxxxxxx2 2） 高斯高斯- -賽德爾迭代公式賽德爾迭代公式 ., 2 , 1 , 0),314(101),325(101),314(101) 1(2) 1(1) 1(3)(2) 1(1) 1(2)(3)(2) 1(1kxxxxxxxxxkkkkkkkkk線性方程組迭代解法線性方程組迭代解法3 3） 取初始向量取初始向量 Tx)0 , 0 , 0()0(4 .1)00314(101)1(1x78. 0)034 . 125(101)1(2x026. 1)78. 034 . 114(101)1(3x線性方程組迭代解法線性方程組迭代解法迭代得表迭代得

17、表 00613.0)3()4(xx00123.0*)4(xx【注注】高斯高斯- -賽德爾迭代法比雅可比迭代法收斂快。賽德爾迭代法比雅可比迭代法收斂快。 線性方程組迭代解法線性方程組迭代解法二、二、n階方程組的高斯階方程組的高斯塞德爾迭代法塞德爾迭代法第第i個方程個方程 ), 2 , 1(11nibxaxaxaininiiii等價方程組等價方程組 ), 2 , 1()(1111nixaxabaxnijjijijjijiiii), 2 , 1() (11)(11)1(i)1(nixaxabaxnijkjijijkjijiiki任取初始解向量任取初始解向量 )0(x計算得迭代序列計算得迭代序列 ,

18、1 , 0,)(kxk高斯高斯- -賽德爾賽德爾(G-S)(G-S)迭代公式迭代公式, 2 , 1 , 0k對于對于 終止條件終止條件 max)1(1)()1(kikinikkxxxx)(11)1()()(kkUxLDbLDxG-SG-S迭代公式的矩陣形式迭代公式的矩陣形式 SGkSGkfxBx)()1(ULDBSG1)(bLDfSG1)(線性方程組迭代解法線性方程組迭代解法【注注】（1 1）雅可比迭代法和高斯）雅可比迭代法和高斯- -賽德爾迭代法的分賽德爾迭代法的分量形式供計算編程使用，矩陣形式供研究迭代序列量形式供計算編程使用，矩陣形式供研究迭代序列是是否收斂等理論分析使用。否收斂等理論分

19、析使用。（2 2）雅可比迭代適合并行計算；不足的是需要存放雅可比迭代適合并行計算；不足的是需要存放兩個向量空間。兩個向量空間。（3 3）高斯）高斯- -賽德爾迭代法只需一個向量存儲空間。賽德爾迭代法只需一個向量存儲空間。三、高斯三、高斯塞德爾迭代法的矩陣描述塞德爾迭代法的矩陣描述ULDA矩陣表示矩陣表示 )()1()(kkUxbxLD （4 4）在某些情況下，）在某些情況下，G-SG-S迭代法加速收斂，但它是迭代法加速收斂，但它是一種典型的串行算法。一種典型的串行算法。 線性方程組迭代解法線性方程組迭代解法高斯高斯- -賽德爾迭代的賽德爾迭代的MATLABMATLAB程序：程序：Gauss_S

20、eidel.mGauss_Seidel.m function x,k,index=Gauss_Seidel(A,b,ep,it_max) % %解線性方程組的解線性方程組的G-SG-S迭代法，其中，迭代法，其中，%A%A為方程組的系數(shù)矩陣；為方程組的系數(shù)矩陣； %b%b為方程組的右端項；為方程組的右端項； % %epep為精度要求，缺省值為精度要求，缺省值1e-51e-5； %it_max%it_max為最大迭代次數(shù)，缺省值為最大迭代次數(shù)，缺省值100100；%x%x為方程組的解；為方程組的解； %k%k為迭代次數(shù)；為迭代次數(shù)； %index%index為指標(biāo)變量，為指標(biāo)變量，index=0i

21、ndex=0表示迭代失敗，表示迭代失敗，%index=1%index=1表示收斂到指定要求表示收斂到指定要求. .n,m=n,m=size(A);nbsize(A);nb=length(b); =length(b); % %當(dāng)方程組行與列的維數(shù)不相等時，停止計算，并輸出當(dāng)方程組行與列的維數(shù)不相等時，停止計算，并輸出出錯信息出錯信息. .if n=mif n=merror(The rows and columns of matrix A must error(The rows and columns of matrix A must be equal!); return;be equal!);

22、return;endend% %當(dāng)方程組與右端項的維數(shù)不匹配時，停止計算，并當(dāng)方程組與右端項的維數(shù)不匹配時，停止計算，并輸出出錯信息輸出出錯信息. .if m=if m=nbnb error(The columns of A must be equal the error(The columns of A must be equal the length of b!);length of b!); return; return;endendif if narginnargin4 it_max=100;end4 it_max=100;endif if narginnargin3 3 epep=1

23、e-5;end=1e-5;endk=0;x=zeros(n,1);y=zeros(n,1);index=1k=0;x=zeros(n,1);y=zeros(n,1);index=1線性方程組迭代解法線性方程組迭代解法while 1while 1 y=x; y=x; for i=1:n for i=1:n z=b(i); z=b(i); for j=1:n for j=1:n if j=i if j=i z=z-A(i,j) z=z-A(i,j)* *x(j);x(j); end end end end if abs(A(i,i)1e-10|k= if abs(A(i,i)1e-10|k=it_

24、max index=0;return;it_max index=0;return; end end z=z/A(i,i);x(i)=z; z=z/A(i,i);x(i)=z; end end線性方程組迭代解法線性方程組迭代解法if if norm(y-x,infnorm(y-x,inf)epep break; break; end end k=k+1; k=k+1;endend調(diào)用函數(shù)調(diào)用函數(shù)Gauss_Seidel.mGauss_Seidel.m 解例解例1.1.線性方程組迭代解法線性方程組迭代解法x = 0.9998 k = 4 index = 1 x = 0.9998 k = 4 ind

25、ex = 1 迭代成功，收斂迭代成功，收斂 0.9998 0.9998 1.0001 1.0001得到得到輸入輸入A=10 3 1;2 -10 3;1 3 10;A=10 3 1;2 -10 3;1 3 10;b=14 -5 14;ep=0.005;b=14 -5 14;ep=0.005;x,k,index=x,k,index=Gauss_Seidel(A,b,epGauss_Seidel(A,b,ep) )例例3 3 分別用雅可比和高斯分別用雅可比和高斯- -賽德爾迭代法解方程組，均賽德爾迭代法解方程組，均取相同初值取相同初值Tx)0,0,0()0(. 122, 1, 12232132132

26、1xxxxxxxxx1 1） Jacobi4Jacobi4次達(dá)到精度次達(dá)到精度5)()1(10kkxxG-SG-S發(fā)散。發(fā)散。 線性方程組迭代解法線性方程組迭代解法2 2） . 478, 059, 1109321321321xxxxxxxxxJacobiJacobi發(fā)散，發(fā)散， G-SG-S發(fā)散發(fā)散. . 3 3） . 41543, 042, 135321321321xxxxxxxxxJacobi 89Jacobi 89次達(dá)到精度次達(dá)到精度01. 0)()1(kkxxG-S 8G-S 8次達(dá)到同樣的精度。次達(dá)到同樣的精度。 線性方程組迭代解法線性方程組迭代解法. 41075, 07104, 1

27、5410321321321xxxxxxxxx4 4） JacobiJacobi發(fā)散，而發(fā)散，而G-S G-S 1010次達(dá)到精度次達(dá)到精度001. 0)()1(kkxx. 雅可比迭代法和高斯雅可比迭代法和高斯- -賽德爾迭代法可能同時賽德爾迭代法可能同時發(fā)散；也可能同時收斂，但一個快另一個慢；可能一發(fā)散；也可能同時收斂，但一個快另一個慢；可能一個收斂而另一個發(fā)散。個收斂而另一個發(fā)散。 線性方程組迭代解法線性方程組迭代解法【注注】4.2.3 逐次超松弛迭代法逐次超松弛迭代法SORSOR迭代法迭代法: :G-SG-S迭代法基礎(chǔ)上迭代法基礎(chǔ)上, ,用參數(shù)校正殘差加速用參數(shù)校正殘差加速. . 一、逐次

28、超松弛迭代公式一、逐次超松弛迭代公式G-SG-S迭代公式中加、減 )(kiiixa)(1)()(1)(11)1()1(kiiikiiinijkjijijkjijiiikixaxaxaxabax)(1)(11)1()(nijkjijijkjijiiikixaxabax),2,1(1)(niraxiiiki線性方程組迭代解法線性方程組迭代解法【注注】（1 1）G-SG-S：對舊值對舊值 )(kix，經(jīng)殘差校正而得新的，經(jīng)殘差校正而得新的近似值，校正量大小為近似值，校正量大小為iiiar /（2 2）為加速收斂，將校正量乘加速因子）為加速收斂，將校正量乘加速因子 ) 0( 有有 ), 2 , 1()

29、(11)() 1()()() 1(nixaxabaxraxxijnijkjijkjijiiikiiiikiki為松馳因子為松馳因子: : 10當(dāng)當(dāng) 時為低松馳因子；時為低松馳因子； 時時當(dāng)當(dāng)G-SG-S公式；公式； 11稱為超松馳因子稱為超松馳因子. .其中其中, , 為第為第i個方程的殘差個方程的殘差. . 1(1)( )1inkkiiijjijjjj irba xa x線性方程組迭代解法線性方程組迭代解法二、逐次超松弛迭代法的矩陣描述二、逐次超松弛迭代法的矩陣描述fxBxkSORk)() 1()1()(1UDLDBSOR其中，其中， bLDfSOR1)(例例4 4 用用SORSOR解方程組

30、，取解方程組，取4 . 1010121001210012100124321xxxx解解 方程組的精確解為：方程組的精確解為： Tx) 8 . 0 , 6 . 1 , 4 . 1 , 2 . 1 (取初值取初值 Tx) 1 , 1 , 1 , 1 ()0(線性方程組迭代解法線性方程組迭代解法用用G-SG-S迭代得迭代得 Tx)798216.0 ,5964336.1 ,3955917.1 ,1966324.1 ()10(利用利用SORSOR方法方法 ).2(2),21 (2),2(2),21 (2)(4)1(3)(4)1(4)(4)(3)1(2)(3)1(3)(3)(2)1(1)(2)1(2)(2

31、)(1)(1)1(1kkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxx初值初值 Tx) 1 , 1 , 1 , 1 ()0(迭代計算結(jié)果迭代計算結(jié)果 線性方程組迭代解法線性方程組迭代解法SORSOR迭代迭代5 5次，與次，與G-SG-S法迭代法迭代1010次的結(jié)果大體相次的結(jié)果大體相同，同，SORSOR方法的松馳因子起到了加速收斂的重方法的松馳因子起到了加速收斂的重要作用要作用. . 逐次超松馳迭代的逐次超松馳迭代的MATLABMATLAB程序：程序：SOR.mSOR.m function x,k,index=SOR(A,b,x0,ep,w,it_max)function

32、 x,k,index=SOR(A,b,x0,ep,w,it_max)% %解線性方程組的解線性方程組的SORSOR迭代法，其中，迭代法，其中，%A%A為方程組的系數(shù)矩陣；為方程組的系數(shù)矩陣；%b%b為方程組的右端項；為方程組的右端項；%x0%x0為初始迭代向量；為初始迭代向量；【注注】 線性方程組迭代解法線性方程組迭代解法% %epep為精度要求，缺省值為精度要求，缺省值1e-51e-5；%w%w為超松弛因子，缺為超松弛因子，缺省值為省值為1 1；%it_max%it_max為最大迭代次數(shù)，缺省值為最大迭代次數(shù)，缺省值100100；%x%x為方程組的解；為方程組的解；%k%k為迭代次數(shù)；為迭代

33、次數(shù)；%index%index為指標(biāo)變量，為指標(biāo)變量，index=0index=0表示迭代失敗，表示迭代失敗，%index=1%index=1表示收斂到指定要求表示收斂到指定要求. .n,m=n,m=size(A);nbsize(A);nb=length(b);=length(b);% %當(dāng)方程組行與列的維數(shù)不相等時，停止計算，并輸當(dāng)方程組行與列的維數(shù)不相等時，停止計算，并輸出出錯信息出出錯信息. .if n=mif n=m error(The rows and columns of matrix A error(The rows and columns of matrix A must be

34、 equal!);must be equal!); return; return;end%end%當(dāng)方程組與右端項的維數(shù)不匹配時，停止計算，當(dāng)方程組與右端項的維數(shù)不匹配時，停止計算，并輸出出錯信息并輸出出錯信息. .線性方程組迭代解法線性方程組迭代解法if m=if m=nbnb error(The columns of A must be equal the error(The columns of A must be equal the length of b!); return;length of b!); return;end if end if narginnargin6 it_ma

35、x=100;end6 it_max=100;end if if narginnargin5 w=1;end5 w=1;end if if narginnargin4 4 epep=1e-5;end=1e-5;endk=0;x=x0;y=zeros(n,1);index=1;k=0;x=x0;y=zeros(n,1);index=1;while 1while 1 y=x; y=x; for i=1:n for i=1:n z=b(i); z=b(i); for j=1:n for j=1:n z=z-A(i,j) z=z-A(i,j)* *x(j); x(j); endend線性方程組迭代解法線

36、性方程組迭代解法 if abs(A(i,i)1e-10|k=it_max if abs(A(i,i)1e-10|k=it_max index=0;return; index=0;return; end end x(i)=x(i)+w x(i)=x(i)+w* *z/A(i,i);z/A(i,i); end end if if norm(y-x,infnorm(y-x,inf)1, 所以利用迭代矩陣的范數(shù)不能判別所以利用迭代矩陣的范數(shù)不能判別其收斂性。其收斂性。線性方程組迭代解法線性方程組迭代解法4.3.2特殊方程組的迭代法收斂性特殊方程組的迭代法收斂性【定義【定義2 2】行占優(yōu)：行占優(yōu)： ),

37、 2, 1(1niaanijjijii列占優(yōu)：列占優(yōu)： ),2, 1(1niaanijjjiii（對角占優(yōu)矩陣）對角占優(yōu)矩陣） 弱對角占優(yōu)矩陣：弱對角占優(yōu)矩陣： nijjijiiaa1（或（或nijjjiiiaa1），），且至少有且至少有一個不等式是嚴(yán)格成立。一個不等式是嚴(yán)格成立?！径x【定義3 3】（可約矩陣）（可約矩陣） 存在置換陣存在置換陣p,使使2212110AAAAPPT不存在置換陣不存在置換陣p,使上式成立使上式成立。（不可約矩陣）（不可約矩陣） 【注注】可約陣可約陣, 經(jīng)過行列重排求解經(jīng)過行列重排求解Ax=b化為求解化為求解.,22221212111dyAdyAyA線性方程組迭代

38、解法線性方程組迭代解法【定理定理4 4】 (1)(1)A為嚴(yán)格對角占優(yōu)矩陣，為嚴(yán)格對角占優(yōu)矩陣， JacobiJacobi和和G-SG-S收斂。收斂。(2)(2)A為弱對角占優(yōu)矩陣且不可約為弱對角占優(yōu)矩陣且不可約, , 則則JacobiJacobi和和G-SG-S收斂。收斂。證明證明 JacobiJacobi)(1ULDBJ), 2 , 1( ,1niaanijjijii1max11nijjiiijniJaaBJacobiJacobi收斂收斂例例6 6 . 142, 26214, 15212321321321xxxxxxxxx解解 42162145212A嚴(yán)格對角占優(yōu)嚴(yán)格對角占優(yōu), Jacob

39、iJacobi和和G-SG-S收斂收斂. .【定理定理5 5】 A是對稱正定方陣，則解是對稱正定方陣，則解Ax= =b的的G-SG-S收斂。收斂。 例例7 7 bAx401,107571045410bAA為對稱正定陣，則為對稱正定陣，則G-SG-S收斂收斂線性方程組迭代解法線性方程組迭代解法 001.0max)1(1kikinixx（1）?。┤?Tx)1 , 1 , 1 ()0(T10424)0.5137,0.9(-0.3657,-x（2）Jacobi 收斂收斂 【定理定理6 6】SORSOR收斂收斂 證明證明)1()(1UDLDBUDLDB)1det()det()det(1nnnnnnaaa

40、aaa1)1(1221122111)(1)det(21nnnBBnB21)det(20【定理定理7 7】A A為實對稱正定矩陣為實對稱正定矩陣,則則 2020SORSOR收斂收斂 (1)(1)A A嚴(yán)格對角占優(yōu)嚴(yán)格對角占優(yōu)( (或或弱對角占優(yōu)不可約弱對角占優(yōu)不可約)則解則解Ax=bAx=b的的SORSOR收斂。收斂。10(2)(2)4.3.3迭代法的收斂速度迭代法的收斂速度【定理定理8 8】線性方程組迭代解法線性方程組迭代解法2)0(22)(kkB2)0()(kBB B為對稱矩陣為對稱矩陣 確定使誤差縮小確定使誤差縮小s10迭代次數(shù)，若迭代次數(shù)，若 skB10)()(ln10lnBsk【注注】

41、k k與與)(lnBR成反比成反比 【定義【定義4 4】迭代法收斂速度迭代法收斂速度 )(ln)(BBR4.4 稀疏方程組及稀疏方程組及MATLABMATLAB實現(xiàn)實現(xiàn)4.4.1分塊迭代法分塊迭代法bAxnnRA為大型稀疏矩陣為大型稀疏矩陣 ULDA其中其中 qqqqqqAAAAAAAAAA212222111211qqAAAD22110002121qqAAAL0002112qqAAAU線性方程組迭代解法線性方程組迭代解法對對x x及及b b同樣分塊同樣分塊iiA), 2 , 1(qiinqiinn1階非奇異矩陣，階非奇異矩陣，為為 qxxxx21qbbbb21一、塊雅可比迭代法（一、塊雅可比迭

42、代法（BJBJ）bXULDxkk)() 1()(qijjkjijikiiixAbxA1)() 1(), 2 , 1(qi其中其中)()(2)(1)(kqkkkxxxxinkiRx)(【注注】塊雅可比迭代法塊雅可比迭代法需要求解低階方程組需要求解低階方程組 ), 2 , 1() 1(qigxAikiii其中，其中， qijjkjijiixAbg1)(,1 ,0k線性方程組迭代解法線性方程組迭代解法二、塊二、塊SORSOR迭代法（迭代法（BSORBSOR）), 1 , 0;, 2 , 1()()(11)1()()1(kqixAxAbxAxAqijkjijijkjijikiiikiii 從從) 1()(kkxx共需要解共需要解q個低階方程組個低階方程組 【定理定理9 9】（1 1）如果）如果A為對稱正定矩陣，為對稱正定矩陣，20（2 2）則解則解Ax=b的的BSOR迭代收斂。迭代收