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

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,第,6,章 解线性方程组的迭代法,6.1,引 言,考虑线性方程组,（,1.1,）,其中,A,为非奇异矩阵，当,A,为低阶稠密矩阵时，第,5,章所讨,论的选主元消去法是有效方法,.,但对于,A,的阶数,n,很大，零元素较多的大型稀疏矩阵,方程组，例如求某些偏微分方程数值解所产生的线性方程,组来说，利用迭代法求解则更为合适,.,迭代法通常都可利用,A,中有大量零元素的特点,.,从而得到,简单迭代格式为,例,用简单迭代法解方程组,方程组的准确解是,:,把方程组改写成,解,当,k=0,时,迭代格式为,代入得,选取初始迭代向量,当,k=1,时,迭代格式为,代入得,把,使用这种迭代格式，得到迭代结果如下表所示,:,从表中看到，近似解向量序列收敛，且收敛到准确解。,0,0,0,0,5,1.0951,1.1951,1.2941,1,0.72,0.83,0.84,6,1.0983,1.1983,1.2980,2,0.971,1.070,1.150,7,1.0944,1.1998,1.2993,3,1.057,1.1571,1.2482,8,1.0998,1.1998,1.2997,4,1.0853,1.1853,1.2828,9,1.0999,1.1999,1.2999,迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法，其具有需要计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点,由于迭代法是通过逐次迭代来逼近方程组的解的，因此收敛性和收敛速度是构造迭代法时要注意的问题,问题：,是否可以构造一种适合于一般情况的迭代法呢？,一般如何构造迭代法的计算格式呢,?,设方程组为,将其变形为,.,由此构造下面迭代格式,:,对于给定方程组 ，,设有惟一解 ，,（,1.3,）,又设 为任取的初始向量，,按上述迭代格式可构造向量序,列,（,1.2,）,其中 表迭代次数,.,则,定义,1:,(2),如果 存在,(,记为,),，,显然 就是方程组的解，否则称此,迭代法发散,.,(1),对于给定的方程组,逐步代入求近似解的方法称为,迭代法,(,或称为一阶定常迭代,法，这里,与 无关,).,用公式,(1.2),称此,迭代法收敛,，,构造迭代格式,(1),显然迭代格式,(1),对任何的,初始向量,，得到的序列都,不收敛,.,如对方程组,构造迭代格式,(2),-4.000,-3.999,-3.997,-3.993,-3.750,-3.334,-2.500,0,-3.000,-2.999,-2.998,-2.994,-2.778,-2.500,-1.700,0,10,9,8,7,3,2,1,0,k,此例说明,:,的收敛性于迭代格式有关,.,6.2,基本迭代法,设有,（,2.1,）,其中，为非奇异矩阵,.,将 分裂为,（,2.2,）,其中，为可选择的非奇异矩阵，且使 容易求解，,一般选择为 的某种近似，称 为,分裂矩阵,.,于是，求解 转化为求解 ，,即求解,可构造一阶定常迭代法,（,2.3,）,其中,称 为迭代法的迭代矩阵,.,选取 阵，就得到解 的各种迭代法,.,设,并将 写为三部分：,（,2.4,）,6.2.1,雅可比迭代法,由 ，选取 为 的对角元素部分，,即选取,(,对角阵,),，,（,2.5,）,其中,称 为解 的雅可比迭代法的迭代阵,.,解 的雅可比,(,Jacobi,),迭代法,由,(2.3),式得到,1,矩阵形式,研究雅可比迭代法,(2.5),的分量计算公式,.,记,由雅可比迭代公式,(2.5),有,或,于是，解 的雅可比迭代法的分量计算公式为,（,2.6,）,由,(2.6),式可知，雅可比迭代法计算公式简单，每迭代,一次只需计算一次矩阵和向量的乘法且计算过程中原始矩,阵 始终不变,.,把,项留在左边,其它项移到右边得到,n,阶线性代数方程组,:,设,第,i,个方程两边除,得到,2,方程形式,令,再令,则有,则有,选取任意初始向量,得到一个新向量,把它代入,(*),式右边,按这样做下去就会得到一个向量序列,把它代入,(*),式右边又得到一个新向量,记为,它通常称为,简单迭代序列或,Jacobi,迭代序列,.,简单迭代序列中的向量可以表示为,它称为简单迭代格式或,Jacobi,迭代格式,称为初始迭代向量,称为简单迭代矩阵或,Jacobi,迭代矩阵,.,即有,记为,Jacobi,迭代,法算法,k=1,则打印,“,求解失败,”,停机,;,否则,对,j,=1,2,n,计算,迭代 对,i,=1,2,n,计算,若,，输出,X,k,停机,;,否则,做下一步,.,输入,A,b,，初始向量,Y,，容许误差,，容许最大迭代次数,M,若,形成迭代矩阵,B,（存放在,A,中）,对,i,=1,2,n,循环,若,k,M,则,k,=,k,+1,，将,X,赋值给,Y,，转,;,否则，输出求解失败信息，停机。,(,下三角阵,),，,6.2.2,高斯,-,塞德尔迭代法,选取分裂矩阵 为 的下三角部分，,即选取,（,2.7,）,其中,称 为解 的高斯,-,塞德尔迭代法的迭,代阵,.,于是由,(2.3),式得到解,的高斯,-,塞德尔,(,Gauss-Seidel,),迭代法,1,矩阵形式,研究高斯,-,塞德尔迭代法的分量计算公式,.,由,(2.7),式有,或,即,记,于是解 的高斯,-,塞德尔迭代法计算公式为,（,2.8,）,或,（,2.9,）,而由高斯,-,塞德尔迭代公式可知，,雅可比迭代法不使用变量的最新信息计算 ，,计算 的第 个分量,时，,利用了已经计算出的最新分量,由,(2.8),可知，高斯,-,塞德尔迭代法每迭代一次只需计算,一次矩阵与向量的乘法,.,高斯,-,塞德尔迭代法可看作雅可比迭代法的一种改进,.,称为,Seidel,迭代格式,.,2,方程形式,对上面式子归纳得到如下计算公式,:,从而得到,Seidel,迭代格式为,例,用,Seidel,迭代法解方程组,方程组的准确解是,:,把方程组改写成,解,当,k=0,时,迭代格式为,代入得,选取初始迭代向量,当,k=1,时,迭代格式为,代入得,把,例,用雅可比迭代法和高斯塞德尔迭代法解线性方程组：,精确至三位有效数字。,解 雅可比迭代格式：,计算结果：,k,0,1,2,3,4,0,0.66667,0.50000,0.61111,0.58333,0,0.50000,0.16667,0.25000,0.19445,k,5,6,7,8,9,0.60185,0.59722,0.60031,0.59954,0.60005,0.20833,0.19908,0.20139,0.19985,0.20023,高斯塞德尔迭代格式,计算结果：,k,0,1,2,3,4,5,0,0.66667,0.61111,0.60185,0.60031,0.60005,0,0.16667,0.19445,0.19908,0.19985,0.19975,有上述结果可看出：高斯塞德尔迭代法比雅可比迭代法收,敛得快。,Seidel,迭代,法算法,k=1,对,i,=1,2,n,做,则打印,“,求解失败,”,停机，否则,对,j,=1,2,n,计算,迭代 对,i,=1,2,n,计算,若,，输出,X,k,停机,;,否则,做下一步,.,输入,A,b,，初始向量,Y,，容许误差,，容许最大迭代次数,M,若,形成迭代矩阵,B,（存放在,A,中）,对,i,=1,2,n,循环,若,k,M,则,k,=,k,+1,，将,X,赋值给,Y,，转,，否则，输出求解失败信息，停机。,例,用,Jacobi,迭代法解方程组,它的准确解是,:,取初始迭代向量,X,(0),=(0,0,0),T,利用,Jacobi,迭代格式，迭代计算结果如下表：,这说明,:,迭代序列收敛是有条件的。,0,0,0,0,1,11,-14,-3,2,-69,81,66,3,-499,-374,-429,从表中可以看到，迭代,序列,发散,.,6.3,迭代法的收敛性,Jacobi,迭代格式,:,Seidel,迭代格式,:,上面几种迭代格式都具有如下形式,:,定义,设,n,阶方阵,A,的特征值为,j,(,j=,1,2,n,),则 称为,A,的谱半径,.,定理,6.1,对任何初始向量,X,(0),和常数项,f,，由迭代格式,产生的向量序列,收敛的充分必要条件是迭代矩阵的谱半径,可以看到，迭代格式是否收敛与迭代矩阵的谱半径有关,而,迭代矩阵是由方程组的系数矩阵演变而来的,所以迭代格式是否收敛与系数矩阵和演变方式有关,与方程组的常数项,b,和初始迭代向量,X,(0),无关,.,6.3.1,迭代法收敛性的讨论,从而得到,简单迭代格式为,补充例,考察用简单迭代法和,Seidel,迭代法解方程组,的收敛性,.,把方程组改写成,解,因,而得到,简单迭代矩阵为,又因,M,的特征方程,为,所以,M,的特征值,为,从而得知,据定理,6.1,使用,简单迭代法解此方程组是收敛的,.,从,而得到,Seidel,迭代,矩阵为,又因,M,的特征方程,为,所以,M,的特征值,为,从而得知,据定理,6.1,使用,Seidel,迭代法解此方程组是不收敛的,.,求,矩阵的谱半径是比较困难的,但由前面证明得知,故由,就能保证有,所以可以用,来判别迭代,法的收敛性,.,需注意的是,:,不能保证有,故不能用,判别不收敛,.,从而得到,简单迭代格式为,补充例,考察用简单迭代法解方程组,的收敛性,.,把方程组改写成,解,因,而得到,简单迭代矩阵为,所以使用,简单迭代法解此方程组是收敛的,.,定理,6.2,若迭代矩阵,M,的范数,，则迭代格式,对任何初始向量,X,(0),一定收敛,.,定理,6.3,Jacobi,迭代法收敛的充分必要条件是,的所有根,i,(i=1,2,n),的绝对值（复数理解为模）,小于,1,。,从而得到,补充例,考察用简单迭代法,(Jacobi,迭代法,),解方程组,的收敛性,.,由,6.3,式得,解,解方程得,因而,据定理,6.3,用,Jacobi,迭代法解此方程组不收敛,.,定理,6.4,Seidel,迭代法收敛的充分必要条件是,的所有根,i,(i=1,2,n),的绝对值小于,1,。,从而得到,补充例,考察用,Seidel,迭代法解方程组,的收敛性,.,由,6.4,式得,解,解方程得,因而,据定理,6.4,用,Seidel,迭代法解此方程组收敛,.,