高斯-塞德尔迭代法

1第6章解线性方程组的迭代法26.1引言考虑线性方程组,bAx（1.1）其中为非奇异矩阵，当为低阶稠密矩阵时，第5章所讨论的选主元消去法是有效方法.AA但对于的阶数很大，零元素较多的大型稀疏矩阵方程组，例如求某些偏微分方程数值解所产生的线性方程组来说，利用迭代法求解则更为合适.An迭代法通常都可利用中有大量零元素的特点.A3例1.361236,33114,20238321321321xxxxxxxxx（1.2）记为,bAx,12361114238A方程组的精确解是.Tx)1,2,3(*求解方程组其中,321xxxx.363320b现将(1.2)改写为4).3636(121),334(111),2023(81213312321xxxxxxxxx（1.3）或写为,fxBx0,01231261110114828300B其中.12361133820f5将这些值代入(1.3)式右边(若(1.3)式为等式即求得方程组的解，但一般不满足).任取初始值，例如取.Tx)0,0,0()0(,)3,3,5.2(),,()1(3)1(2)1(1)1(TTxxxx再将分量代入(1.3)式右边得到，反复利用这个计算程序，得到一向量序列和一般的计算公式(迭代公式))1(x)2(x,,,,)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0(kkkkxxxxxxxxxxxx得到新的值6,8/)2023()(3)(2)1(1kkkxxx,11/)334()(3)(1)1(2kkkxxx（1.4）.12/)3636()(2)(1)1(3kkkxxx简写为,)(0)1(fxBxkk其中表示迭代次数k).,2,1,0(k迭代到第10次有;)9998813.0,999838.1,000032.3()10(Tx7从此例看出，由迭代法产生的向量序列逐步逼近)(kx方程组的精确解.*x对于任何由变形得到的等价方程组，fBxxbAx迭代法产生的向量序列不一定都能逐步逼近方程组的解.)(kx*x*).(000187.0)10()10()10(xx如对方程组.53,521221xxxx8构造迭代法.53,52)(1)1(2)(2)1(1kkkkxxxx则对任何的初始向量，得到的序列都不收敛.对于给定方程组，fBxx设有唯一解，*x.**fBxx（1.5）又设为任取的初始向量，)0(x,,2,1,0,)()1(kfBxxkk（1.6）其中表迭代次数.k则按下述公式构造向量序列9定义1(1)对于给定的方程组，fBxx逐步代入求近似解的方法称为迭代法(或称为一阶定常迭代法，这里与无关).Bk(2)如果存在(记为)，)(limkkx*x显然就是方程组的解，否则称此迭代法发散.*x用公式(1.6)称此迭代法收敛，研究的收敛性.}{)(kx引进误差向量*,)1()1(xxkk由(1.6)减去(1.5)式，得，),2,1,0()()1(kBkk10要考察的收敛性,就要研究在什么条件下有}{)(kxB0lim)(kk.0lim(零矩阵)kkB亦即要研究满足什么条件时有B)1()(kkB递推得.)0(kB116.2基本迭代法设有,bAx（2.1）其中，为非奇异矩阵.nnijaAR)(将分裂为A,NMA（2.2）其中，为可选择的非奇异矩阵，且使容易求解，MdMx一般选择为的某种近似，称为分裂矩阵.AM12于是，求解转化为求解，bAxbNxMx.11bMNxMxbAx求解即求解可构造一阶定常迭代法,2,1,0,)()1()0(kfBxxxkk），（初始向量（2.3）其中NMB1.1bMf)(1AMM,1AMI称为迭代法的迭代矩阵.AMIB113选取阵，就得到解的各种迭代法.MbAx设,并将写为三部分),,2,1(0niaiiAnnaaaA22110000,121,211,112nnnnnnaaaaaa（2.4）.ULD00001,212,11,121nnnnnnaaaaaa146.2.1雅可比迭代法由，选取为的对角元素部分，M),,2,1(0niaiiA解的雅可比(Jacobi)bAx即选取(对角阵)，，DMNDA,,2,1,0,)()1()0(kfBxxxkk），（初始向量（2.5）其中ADIB1称为解的雅可比迭代法的迭代阵.JbAx由(2.3)式得到.1bDf)(1ULD,J15研究雅可比迭代法(2.5)的分量计算公式.,),,,,()()()(1)(Tknkikkxxxx记由雅可比迭代公式(2.5),有,)()()1(bxULDxkk或).,,2,1(1)(11)()1(nibxaxaxainijkjijijkjijkiii于是，解的雅可比迭代法的分量计算公式为bAx16,),,()0()0(1)0(Tnxxx,/1)()1(iinijjkjijikiaxabx（2.6）.,1,0),,2,1(表示迭代次数)(kni由(2.6)式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵始终不变.A17(下三角阵)，6.2.2高斯-塞德尔迭代法选取分裂矩阵为的下三角部分，MA即选取LDM,NMA于是由(2.3)式得到解bAx,,2,1,0,)()1()0(kfBxxxkk（初始向量），（2.7）其中,G称为解的高斯-塞德尔迭代法的迭代阵.ULDG1)(bAx的高斯-塞德尔(Gauss-Seidel).)(1bLDfULD1)(ALDIB1)(18研究高斯-塞德尔迭代法的分量计算公式.,),,,,()()()(1)(Tknkikkxxxx由(2.7)式有,)()()1(bUxxLDkk或,)()1()1(bUxLxDxkkk).,,2,1(1)(11)1()1(nixaxabxanijkjijijkjijikiii即记19于是解的高斯-bAx(初始向量),Tnxxx),,()0()0(1)0(,/1)(11)1()1(iinijkjijijkjijikiaxaxabx（2.8）).,1,0;,,1(kni或,),,()0()0(1)0(Tnxxx,)()1(ikikixxx,/1)(11)1(iinijkjijijkjijiiaxaxabx（2.9）).,1,0;,,1(kni20而由高斯-塞德尔迭代公式可知，雅可比迭代法不使用变量的最新信息计算，)1(kix计算个分量)1(kxi时，)1(kix利用了已经计算出的最新分量.)1,,2,1()1(ijxkj由(2.8)可知，高斯-塞德尔迭代法每迭代一次只需计算一次矩阵与向量的乘法.高斯-塞德尔迭代法可看作雅可比迭代法的一种改进.算法1(高斯-塞德尔迭代法)设，bAx其中为非奇异矩阵且nnAR0iia),,,2,1(ni本算法用高斯-塞德尔迭代法解，bAx21),,1(0.0.1nixi迭代一次，这个算法需要的运算次数至多与矩阵的非零元素的个数一样多.A数组开始存放,)(nx)0(x,)(kx后存放0N为最大迭代次数.0,,2,1.2Nk对于ni,,1对于iinijjijijjijiiaxaxabx/11122例2按高斯-塞德尔迭代公式,8/)2023()(3)(2)1(1kkkxxx迭代7次，得，Tx)9999932.09999987.1000002.3()7(.361236,33114,20238321321321xxxxxxxxx（1.2）用高斯-塞德尔迭代法解线性方程组(1.2).Tx)0,0,0()0(取，,11/)334()(3)1(1)1(2kkkxxx),,1,0(.12/)3636()1(2)1(1)1(3kxxxkkk23由此例可知，用高斯-塞德尔迭代法，雅可比迭代法解线性方程组(1.2)(且取)均收敛.0)0(x而高斯-塞德尔迭代法比雅可比迭代法收敛较快(即取相同，达到同样精度所需迭代次数较少).)0(x但这结论只当满足一定条件时才是对的.A.1002.2*6)7(xx且246.2.3解大型稀疏线性方程组的逐次超松弛迭代法选取分裂矩阵为带参数的下三角阵M),(1LDM其中为可选择的松弛因子.0于是，由(2.3)可构造一个迭代法，其迭代矩阵为ALDIL1)(从而得到解的逐次超松弛迭代法(SuccessiveOverRelaxationMethod,简称SOR).bAx).)1(()(1UDLD25解的SOR方法为bAx,,2,1,0,)()1()0(kfxLxxkk（初始向量），（2.10）其中),)1(()(1UDLDL.)(1bLDf研究解的SOR迭代法的分量计算公式.bAx,),,,,()()()(1)(Tknkikkxxxx记26,))1(()()()1(bxUDxLDkk或).()()()1()()1(kkkkkDxUxLxbDxDx由(2.10)式可得由此，得到解的SOR方法的计算公式bAx,),,()0()0(1)0(Tnxxx,/1)(11)1()()1(iinijkjijijkjijikikiaxaxabxx（2.11）为松弛因子.),,1,0;,,1(kni27或,),,()0()0(1)0(Tnxxx,)()1(ikikixxx,/1)(11)1(iinijkjijijkjijiiaxaxabx（2.12）为松弛因子.),,1,0;,,1(kni关于SOR迭代法，有(1)显然，当时，SOR方法即为高斯-塞德尔迭代法.128(2)SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法.(3)当时，称为超松弛法；当时，称为低松弛法.11(4)在计算机实现时可用)()1(11maxmaxkikiniinixxx控制迭代终止，或用控制迭代终止.)()(kkAxbrSOR迭代法是高斯-塞德尔迭代法的一种修正.29设已知及已计算的分量)(kx)1(kx).1,,2,1()1(ijxkj(1)首先用高斯-塞德尔迭代法定义辅助量,~)1(kix./~1)(11)1()1(iinijkjijijkjijikiaxaxabx（2.13）(2)再由与加权平均定义，)(kix)1(~kix)