第3章解线性方程组的迭代方法.ppt

迭代法研究的主要问题,1）迭代格式的构造；2）迭代的收敛性分析；3）收敛速度分析；4）复杂性分析；（计算工作量）5）初始值选择。,3.5大型方程组的迭代方法,定义:设xk是Rn上的向量序列，,又设x*（x1*，x2*,，xn*)是Rn上的向量.,则称向量x*是向量序列xk的极限，,若一个向量序列有极限,称这个向量序列是收敛的.,向量序列的极限,如果,矩阵序列的极限,证：,设矩阵,定理4,，则的,充要条件是(A)1,证：矩阵A相似于其Jordan标准型,即存在可逆矩阵P,使得,J为对角分块矩阵(Ji称为Jordan块):,其中:,ni为特征值i的重数,且n1+n2+nr=n,由于,所以,而,一、简单迭代思想,设矩阵A可逆，把矩阵A分裂为则,迭代过程B称为迭代矩阵。,给定初值就得到向量序列,定义：若称简单迭代法收敛，否则，称逐次逼近法不收敛或发散。,问题：是否是方程组x=Bx+f的解？,结论1：任意给定初始向量，若由迭代公式(1)产生的迭代序列收敛到，则是方程组x=Bx+f的解。,证：,又如何判定所给迭代格式(1)是否收敛哪？,迭代法收敛的条件,定理1：对任意初始向量，由（1）得到的迭代序列收敛的充要条件是迭代矩阵的谱半径证：因此,结论2：设矩阵，则,注：要检验一个矩阵的谱半径小于1比较困难，所以我们希望用别的办法判断迭代格式是否收敛。,定理2：若迭代法的迭代矩阵满足（矩阵的某一种算子范数），则迭代格式产生的序列收敛于x=Bx+f的精确解x*，且有误差估计式：,证：由定理1、结论1和知迭代格式产生的序列收敛于x=Bx+f的精确解x*。且,整理即得估计式。,Remark:因为矩阵范数，都可以直接用矩阵的元素计算，因此，用定理2，容易判别迭代法的收敛性。定理2的条件只是充分的，而不是必要的，也就是说：如果，则迭代法收敛；但若，我们并不能断定迭代法就一定发散，此时需要用定理1来判定迭代法的敛散性。,迭代格式的收敛速度与初始值x(0)有关，同时也与|B|和(B)有关，一般来说，|B|和(B)越小，收敛速度越快。Def：称为迭代法的渐近收敛速度。,二、Jacobi迭代法,例1：用迭代法解方程组,解:将方程组化为等价形式:,构造迭代格式:,取初始值代入计算，得,注：如何判断迭代过程终止？利用定理2的误差估计式可以判断迭代过程是否可以终止，但这种方法比较麻烦，通常采用的方法是通过前后两次迭代近似值的差来判断，即利用：,终止迭代过程。上述这种求解方程组的方法称为Jacobi迭代法。,Jacobi迭代法的步骤：,3、判断迭代格式的收敛性。取初值x(0)带入计算。,1、写出等价方程组即将第i个方程的xi解出。2、写出相应的迭代格式分量式：,假设A非奇异,且aii0,i=1,2,n,Jacobi迭代矩阵形式,记则有迭代格式：,上式称为Jacobi迭代格式，其中BJ称为Jacobi迭代矩阵。,注：Jacobi迭代矩阵BJ：其中的元素恰为原方程组系数矩阵A中的主对角线元素换为0，而其余元素即为除以该行主对角元素后的相反数。,Jacobi迭代法在计算xi(k+1)时所用分量仍为上一次近似值的各个分量，但此时，我们已经求出了新近似值的分量x1(k+1),x2(k+1),xi-1(k+1)，计算xi(k+1)时，用新分量x1(k+1),x2(k+1),xi-1(k+1)代替原来相应的分量，则得到一种新的迭代格式，即Gauss-Seidel迭代格式。,三、Gauss-Seidel迭代法,假设,Jacobi迭代,矩阵表示：记上式整理可得：这是一种简单迭代格式，其中的BG-S称为GS迭代矩阵。,例2：用G-S迭代法解方程组：,解：原方程可化为等价形式：,建立迭代格式：,取初始向量x(0)=(0,0,0)T代入迭代格式，得：,两种迭代法收敛性判定：,希望直接对系数矩阵A研究这俩种迭代收敛条件。,定理4：若A为(行或列)严格对角占优矩阵，则相应的G-S迭代格式收敛。,定理3:A按行(列)严格对角占优，则Jacobi迭代收敛。,证：(仅证按行占优，反证)设是任一特征值，x是相应特征向量。设,若,则,定理5：设A是有正对角元的n阶对称矩阵，则Jacobi迭代收敛A和2D-A同为正定矩阵。,证：记,则,由A的对称性，也对称，因而特征值全为实数，记为则的任一特征值为。,定理6：若A为对称正定矩阵，则相应的G-S迭代格式收敛。,正定。,又,，故正定。,A正定正定，特征值小于1.若正定,特征值小于1,所以特征值大于1。,所以,所以,迭代矩阵BG-S的谱半径(BG-S)1,从而当方程组Ax=b的系数矩阵A是实对称正定矩阵时,G-S迭代法收敛,Remark:G-S迭代法的计算过程比Jacobi迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。G-S迭代不一定比Jacobi迭代收敛快。Jacobi迭代和G-S迭代的收敛范围并不一致，即Jacobi迭代收敛，G-S迭代不一定收敛，反之亦然。前面的定理1、定理2对于Jacobi迭代和G-S迭代都适用。,(i=1,2,n;k=1,2,3,),四超松驰(SOR)迭代法,G-S迭代格式,定理7.若A是对称正定矩阵,则当02时SOR迭代法解方程组Ax=b是收敛的,定理8.若A是严格对角占优矩阵,则当00,计算r(k-1)=bAx(0),若|r0|结束;否则p(1)r(k-1),k1,转第二步;,共轭梯度算法：,第二步:计算tk=(p(k),r(k-1)/(Ap(k),p(k)x(k)=x(k-1)+tkp(k);,第三步:如果k=n,则结束;否则,计