第四章_线性方程组的迭代解法

1、第第 4 章章理学院应用数学系理学院应用数学系立体化教学资源系列立体化教学资源系列数值分析数值分析线性方程组迭代解法线性方程组迭代解法4.1 引言引言当当A为低阶稠密矩阵时，选主元消去法是有效方法。为低阶稠密矩阵时，选主元消去法是有效方法。对于对于大型稀疏的线性方程组迭代法是合适的。大型稀疏的线性方程组迭代法是合适的。迭代法的基本步骤迭代法的基本步骤（1 1）等价形式）等价形式B称为迭代矩阵；称为迭代矩阵；fBxx（2 2）迭代公式）迭代公式), 2 , 1 , 0()() 1(kfBxxkk线性方程组线性方程组 bAx A为非奇异矩阵为非奇异矩阵。基本思想基本思想:用某种极限过程逐步逼近方程

2、组的精确解。用某种极限过程逐步逼近方程组的精确解。（3 3）任取向量）任取向量,由上式生成向量序列由上式生成向量序列 ) 0(x；若；若 )(kx，则迭代过程收敛，则迭代过程收敛 。*)(limxxkk线性方程组迭代解法线性方程组迭代解法（3 3）计算机算法？）计算机算法？本章讨论本章讨论（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 (*显然迭代序列显然迭代序列逐步逼近精确解逐步逼近精确解迭代计算结果如表迭代计算结果如表 (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为方程组的系数矩阵；为方程组的系数矩阵；%b%b为方程组的右端项；为方程组的右端项；% %epep为精度要求，缺省值为精度要求，缺省值1e-51e-5；%it_max%it_max为最大迭代次数，缺省值为最大迭代次数，缺省值100100；%x%x为方程组的解；为方程组的解；%k%k为迭代次数；为迭代次数；%index%index为指标变量，为指标变量，index=0index=0表示迭代失败，表示迭代失败，%index=1%index=1表示收敛到指定要求表示收敛到指定要求.n,m=size(A);.n,m=size(A);

8、nbnb=length(b); =length(b); % %当方程组行与列的维数不相等时，停止计算，并输当方程组行与列的维数不相等时，停止计算，并输出出错信息出出错信息. . 线性方程组迭代解法线性方程组迭代解法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% %当方程组与右端项的维数不匹配时，停止计算，当方程组与右端项的维数不匹配时，停止计算，并输出

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调用函数调用函数 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 调用函数调用函数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为方程组的系数矩阵；为方程组的系数矩阵； %b%b为方程组的右端项；为方程组的右端项； % %epep为精度要求，缺省值为精度要求，缺省值1e-51e-5； %it_max%it_max为最大迭代次数，缺省值为最大迭代次数，缺省值100100；%x%x为方程组的解；为方程组的解； %k%k为迭代次数；为迭代次数； %index%index为指标变量，为指标变量，index=0i

21、ndex=0表示迭代失败，表示迭代失败，%index=1%index=1表示收敛到指定要求表示收敛到指定要求. .n,m=n,m=size(A);nbsize(A);nb=length(b); =length(b); % %当方程组行与列的维数不相等时，停止计算，并输出当方程组行与列的维数不相等时，停止计算，并输出出错信息出错信息. .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% %当方程组与右端项的维数不匹配时，停止计算，并当方程组与右端项的维数不匹配时，停止计算，并输出出错信息输出出错信息. .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调用函数调用函数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次达到精度次达到精度5)()1(10kkxxG-SG-S发散。发散。 线性方程组迭代解法线性方程组迭代解法2 2） . 478, 059, 1109321321321xxxxxxxxxJacobiJacobi发散，发散， G-SG-S发散发散. . 3 3） . 41543, 042, 135321321321xxxxxxxxxJacobi 89Jacobi 89次达到精度次达到精度01. 0)()1(kkxxG-S 8G-S 8次达到同样的精度。次达到同样的精度。 线性方程组迭代解法线性方程组迭代解法. 41075, 07104, 1

27、5410321321321xxxxxxxxx4 4） JacobiJacobi发散，而发散，而G-S G-S 1010次达到精度次达到精度001. 0)()1(kkxx. 雅可比迭代法和高斯雅可比迭代法和高斯- -赛德尔迭代法可能同时赛德尔迭代法可能同时发散；也可能同时收敛，但一个快另一个慢；可能一发散；也可能同时收敛，但一个快另一个慢；可能一个收敛而另一个发散。个收敛而另一个发散。 线性方程组迭代解法线性方程组迭代解法【注注】4.2.3 逐次超松弛迭代法逐次超松弛迭代法SORSOR迭代法迭代法: :G-SG-S迭代法基础上迭代法基础上, ,用参数校正残差加速用参数校正残差加速. . 一、逐次

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，经残差校正而得新的，经残差校正而得新的近似值，校正量大小为近似值，校正量大小为iiiar /（2 2）为加速收敛，将校正量乘加速因子）为加速收敛，将校正量乘加速因子 ) 0( 有有 ), 2 , 1()

29、(11)() 1()()() 1(nixaxabaxraxxijnijkjijkjijiiikiiiikiki为松驰因子为松驰因子: : 10当当 时为低松驰因子；时为低松驰因子； 时时当当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(迭代计算结果迭代计算结果 线性方程组迭代解法线性方程组迭代解法SORSOR迭代迭代5 5次，与次，与G-SG-S法迭代法迭代1010次的结果大体相次的结果大体相同，同，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为方程组的系数矩阵；为方程组的系数矩阵；%b%b为方程组的右端项；为方程组的右端项；%x0%x0为初始迭代向量；为初始迭代向量；【注注】 线性方程组迭代解法线性方程组迭代解法% %epep为精度要求，缺省值为精度要求，缺省值1e-51e-5；%w%w为超松弛因子，缺为超松弛因子，缺省值为省值为1 1；%it_max%it_max为最大迭代次数，缺省值为最大迭代次数，缺省值100100；%x%x为方程组的解；为方程组的解；%k%k为迭代次数；为迭代

33、次数；%index%index为指标变量，为指标变量，index=0index=0表示迭代失败，表示迭代失败，%index=1%index=1表示收敛到指定要求表示收敛到指定要求. .n,m=n,m=size(A);nbsize(A);nb=length(b);=length(b);% %当方程组行与列的维数不相等时，停止计算，并输当方程组行与列的维数不相等时，停止计算，并输出出错信息出出错信息. .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%当方程组与右端项的维数不匹配时，停止计算，当方程组与右端项的维数不匹配时，停止计算，并输出出错信息并输出出错信息. .线性方程组迭代解法线性方程组迭代解法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, 所以利用迭代矩阵的范数不能判别所以利用迭代矩阵的范数不能判别其收敛性。其收敛性。线性方程组迭代解法线性方程组迭代解法4.3.2特殊方程组的迭代法收敛性特殊方程组的迭代法收敛性【定义【定义2 2】行占优：行占优： ),

37、 2, 1(1niaanijjijii列占优：列占优： ),2, 1(1niaanijjjiii（对角占优矩阵）对角占优矩阵） 弱对角占优矩阵：弱对角占优矩阵： nijjijiiaa1（或（或nijjjiiiaa1），），且至少有且至少有一个不等式是严格成立。一个不等式是严格成立。【定义【定义3 3】（可约矩阵）（可约矩阵） 存在置换阵存在置换阵p,使使2212110AAAAPPT不存在置换阵不存在置换阵p,使上式成立使上式成立。（不可约矩阵）（不可约矩阵） 【注注】可约阵可约阵, 经过行列重排求解经过行列重排求解Ax=b化为求解化为求解.,22221212111dyAdyAyA线性方程组迭代

38、解法线性方程组迭代解法【定理定理4 4】 (1)(1)A为严格对角占优矩阵，为严格对角占优矩阵， JacobiJacobi和和G-SG-S收敛。收敛。(2)(2)A为弱对角占优矩阵且不可约为弱对角占优矩阵且不可约, , 则则JacobiJacobi和和G-SG-S收敛。收敛。证明证明 JacobiJacobi)(1ULDBJ), 2 , 1( ,1niaanijjijii1max11nijjiiijniJaaBJacobiJacobi收敛收敛例例6 6 . 142, 26214, 15212321321321xxxxxxxxx解解 42162145212A严格对角占优严格对角占优, 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严格对角占优严格对角占优( (或或弱对角占优不可约弱对角占优不可约)则解则解Ax=bAx=b的的SORSOR收敛。收敛。10(2)(2)4.3.3迭代法的收敛速度迭代法的收敛速度【定理定理8 8】线性方程组迭代解法线性方程组迭代解法2)0(22)(kkB2)0()(kBB B为对称矩阵为对称矩阵 确定使误差缩小确定使误差缩小s10迭代次数，若迭代次数，若 skB10)()(ln10lnBsk【注注】

41、k k与与)(lnBR成反比成反比 【定义【定义4 4】迭代法收敛速度迭代法收敛速度 )(ln)(BBR4.4 稀疏方程组及稀疏方程组及MATLABMATLAB实现实现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迭代收敛。迭代收