武汉大学求解方程组的迭代法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章,2.2,解线性方程组的迭代法,数学与统计学院,解线性方程组的两类方法,直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!),迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。,迭代法研究的主要问题,1,）迭代格式的构造；,2,）迭代的收敛性分析；,3,）收敛速度分析；,4）,复杂性分析；（计算工作量）,5,）初始值选择。,迭代格式的构造,把矩阵,A,分裂为,则,迭代过程,B,称为迭代矩阵。,给定初值 就得到向量序列,定义：若 称逐次逼近法收敛，否则，称逐次逼近法不收敛或发散。,问题：是否是方程组（,1,）的解？,定理,1,：任意给定初始向量 ，若由迭代公式（,2,）产生的迭代序列收敛到 ，则 是方程组（,1,）的解。,证：,逐次逼近法收敛的条件,定理,2,：对任意初始向量 ，由（,2,）得到的迭代序列收敛的充要条件是迭代矩阵 的谱半径,证：,因此,要,检验一个矩阵的谱半径小于,1,比较困难，所以我们希望用别的办法判断是否有,定理,3,：若逐次逼近法的迭代矩阵满足 ，,则逐次逼近法收敛。,Remark:,因为矩阵范数 ，都可以直接用矩阵 的元素计算，因此，用定理,3,，容易判别逐次逼近法的收敛性。,问题：如何判断可以终止迭代？,定理,4,：若迭代矩阵 满足 则,（,3,）,（,4,）,Remark,:,(4),式给出了一个停止迭代的判别准则。,(3,）式指出 越小收敛越快。,，,证：,Jacobi,迭代,=,Jacobi,迭代,分裂,迭代过程：,若记,算法描述,1,输入,2,if ,then,2.1 for,2.1.1,s=0,2.1.2 for,2.1.3,2.1.4 if then,2.2,k=k+1,2.3 if then,2.3.1,2.3.2,goto,2,else,输出 结束。,else,2.4,输出 迭代次数太大。,3,结束,Gauss-Seidel,迭代,假设,Jacobi,迭代,分裂,算法描叙,1,输入,2,if ,then,2.1 for,2.1.1,s=0，,2.1.2 for,2.1.3,2.1.4,if then,2.2 k=k+1,2.3 if ,输出结果，结束。,else,2.4,输出迭代次数太大。,3,结束,Remark:,Gauss-Seidel,迭代法的计算过程比,Jacobi,迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。,Gauss-Seidel,迭代不一定比,Jacobi,迭代收敛快。,例,希望直接对系数矩阵,A,研究这俩种迭代收敛条件。,定理,5,设,A,是有正,对角元的,n,阶对称矩阵，则,Jacobi,迭代收敛,A,和,2,D-A,同为正定矩阵。,证：记,则,即 ，,从而有相同的谱半径。,由,A,的对称性，也对称，因而特征值全为实数，记为,则 的任一特征值为 。,A,，,正定。,故 正定。,A,正定 正定，特征 值小于,1,。,若,2,D-A,正定,特征值小于,1,所以,特征值大于,1,。,定理,6,A,按行（列）严格对角占优，则,Jacobi,迭代收敛。,引理,A,按行（列）严格对角占优,（）,证 （提示）,定理,7,A,按行严格对角占优，则,Gauss-Seidel,迭代收敛。,证 设 是 任一特征值，,x,是相应特征向量。设,若,则,定理,8,A,按列严格对角占优，则,Gauss-Seidel,迭代收敛。,证,设 是 的任一特征值，,x,是相应特征向量。设,