解线性方程组的迭代法

第七章解线性方程组的迭代法7.1迭代方法7.2迭代法的收敛性12/14/20221【本章重点】

1.迭代法构造及迭代法收敛的条件和收敛速度。

2.Jacobi迭代法，Gauss-Seidel迭代法和SOR迭代法的计算公式及迭代收敛的充分必要条件和充分条件。12/14/20222定义

线性方程组Ax=b等价于x=Bx+f，x*为精确解构造迭代公式

x(k+1)=Bx(k)+f(k=0,1,2…)x(0)任意的初始向量，逐步代入求解近似解的方法称为迭代法。若存在（为x*），则称此迭代法收敛，否则称此迭代法

发散§1迭代方法将A分解为两个矩阵M和N，即A=M-N,M为可选择的非奇异矩阵则(M-N)x=b，即x=M-1Nx+M-1b记B=M-1N=M-1(M-A)=I-M-1Af=M-1b构造向量序列{x(k）}：x(k+1)=Bx(k)+fx(0)任意的初始向量构造过程：12/14/20223

线性方程组的迭代法主要有Jocobi迭代法、Seidel迭代法和超松弛(SOR)迭代法.一般地，若aii≠0(i=1,2,..,n)，将写为三部分12/14/20224一、Jacobi

迭代法Jacobi迭代公式:Jacobi迭代的矩阵格式：取A=D-L-U,即M=D,N=L+UB=I-D-1A=D-1D-D-1A=D-1(L+U)≡BJ

,f=D-1b≡fJ

（BJ为Jacobi迭代的迭代阵）。12/14/20225亦即：12/14/20226例解Jacobi迭代格式:12/14/20227function[x,k]=Jacobimethod(A,b,x0,N,emg)n=length(A);x1=zeros(n,1);x2=zeros(n,1);x1=x0;k=0;r=max(abs(b-A*x1));whiler>emgfori=1:nsum=0;forj=1:nifi~=jsum=sum+A(i,j)*x1(j);endendx2(i)=(b(i)-sum)/A(i,i);endr=max(abs(x2-x1));x1=x2;k=k+1;ifk>Ndisp('迭代失败,返回');return;endendx=x1;%A是线性方程组的系数矩阵%b是右端向量%x0是迭代初始值%N是表示迭代次数上限，若迭代次数大于N，则迭代失败%emg表示控制精度%用Jacobi迭代法求线性方程组Ax=b的解%k表示迭代次数%x表示用迭代法求得的线性方程组的近似解12/14/20228x=-0.99997616216851-0.99997616216851-0.99997616216851-0.99997616216851k=37formatlongA=[-4111;1-411;11-41;111-4]b=[1111]'x0=[0000]'[x,k]=Jacobimethod(A,b,x0,100,10^-5)12/14/20229取M=D-L，N=U，则B=I-(D-L)-1A=(D-L)-1(D-L-A)=(D-L)-1U=BGf=(D-L)-1b≡fG

GS迭代法的矩阵形式为:

二、Gauss-Seidel迭代法即用迭代格式：12/14/202210亦即：12/14/202211例解Gauss-Seidel迭代格式:12/14/202212三、

逐次超松弛（SOR）迭代法即用迭代格式：12/14/202213亦即：结论1）SOR亦即G-S迭代2）称为超松弛迭代法称为低松弛迭代法3）选择的好，将大大提高SOR迭代法的收敛速度12/14/202214§2收敛性及误差估计Jacobi迭代和GS迭代格式可表述为统一形式:对于其收敛性，我们有如下定理：对任意初始向量x(0)及任意右端向量f，由此产生的迭代向量序列{x(k)}收敛的充要条件是证明：必要性：设｛x(k)｝收敛，其极限为x*，则因上式对任意均成立，故Bk0(k),

故；(B)<1(p224定理3)定理1(迭代法基本定理)12/14/202215充分性：设(B)<1,则1不是B的特征值，因而|I－B|≠0，且所以有唯一解,记为x*,则

故定理2(P251)

设Ax=b,如果:(1)A为严格对角占优矩阵(P249),则Jacobi,G-S迭代法收敛;(2)A为弱对角占优阵,且为不可约矩阵,则Jacobi,G-S,SOR

迭代法均收敛;12/14/202216定理3(P252)

设Ax=b,如果:(1)A为对称正定矩阵,A=D-L-U;(2)0<w<2则解Ax=b的SOR迭代法收敛;定理4(P249)

设Ax=b,如果:(1)A为严格对角占优矩阵（或A为弱对角占优不可约矩阵）(2)0<w≤1则解Ax=b的SOR迭代法收敛;定义(P255)

称为迭代法x(k+1)=Bx(k)+f(k=0,1,2…)的渐进收敛速度，简称迭代法收敛速度。12/14/202217举例写出Jacoai和G-S的迭代式并判断两种迭代格式的收敛性结论：该方程组采用Jacoai迭代法计算是收敛的。一、已知线性方程组：

8x1-3x2+2x3=204x1+11x2-x3=336x1+3x2+12x3=36（1）Jacoai迭代公式12/14/202218结论：该方程组采用G-S迭代法计算是收敛的。（2）G-S迭代公式12/14/202219二、设方程组为解：Jacobi迭代格式为故Jacobi迭代矩阵为BJ=试分别写出其Jacobi迭代格式和Seidel迭代格式以及相应的迭代矩阵。（习题1）12/14/202220Seidel迭代格式为从式中解出,i=1,2,3得：故可得Seidel迭代矩阵为BG=从例中可以看出Jacobi迭代矩阵Bj的主对角线为零，而Gauss-Seidel迭代矩阵Bs的第1列都是零，这对一般情况也是成立的。12/14/202221迭代法的特点Jacoai迭代和Seidel迭代由于收敛速度较慢，已经越来越不适应当前信息时代人们对计算速度和精度的要求，所以在实际应用中使用得并不多。但是，他们体现了迭代法的最基本的思想，是学习其它迭代法的基础。优点：方法简单，每次迭代都是简单的重复运算，易于编制程序；与求解线性方程的