第四章线性方程组的迭代法

1第四章线性方程组的迭代法第一节迭代法及其收敛性一、迭代法的一般格式在前面我们已经介绍了解线性方程组bAx（1）的一些直接方法，下面我们将简略介绍一下解方程组(1)的另一类方法——迭代法，所谓迭代法是这样一种方法，对任意给定初始近似0x,按某种规则逐次生成序列,xx,x,xk210使极限xxlimkk(2)为方程组(1)的解，即bAx设把矩阵A分解成矩阵N和P之差PNA其中N为非奇异矩阵,于是,方程组(1)便可以表示成bPxNx即fBxbNPxNx11(3)其中bNf;PNB11,据此,我们便可以建立迭代公式2101,,kfBxxkk(4)我们称迭代公式(4)中的矩阵B为迭代矩阵.若序列kx收敛xxlimkk显然有fBxx2即，极限x便是所求方程组的解.定义1（1）对给定的方程组(3)，用公式(4)逐步代入求近似解的方法称为迭代法.(2)如果kkxlim存在(记为x)，则称迭代法收敛，此时x就是方程组的解,否则称此迭代法发散.为了讨论迭代公式(4)的收敛性,我们引进误差向量.,...,,k,xxekk210(5)由(3)和(4)便得到误差向量所满足的方程kkBee1(6)递推下去,最后便得到011eBekk(7)二、迭代法的收敛性若欲由(4)所确定的迭代法对任意给定的初始向量0x都收敛,则由(7)确定的误差向量ke应对任何初始误差0e都收敛于0.定义2若0AAlimkk(8)则称矩阵序列kA依范数‖·‖收敛于A.由范数的等价性可以推出，在某种范数意义下矩阵序列收敛，则在任何一种范数意义下该矩阵序列都收敛.因此,对矩阵序列kA收敛到矩阵A，记为AAlimkk(9)而不强调是在那种范数意义下收敛.从定义及矩阵的行(列)范数可以直接推出下面定理.定理1设矩阵序列,...,kaAnnkijk21及矩阵nnijaA，则kA收敛于A的充分必要条件为ijkijkaalim,n,...,j,i213因此，矩阵序列的收敛可归结为元素序列的收敛.此外,还可以推出下面定理.定理2迭代法(4)对任何0x都收敛的充分必要条件为0kkBlim(10)定理3矩阵序列kB收敛于0的充分必要条件为1B(11)证明：如果0kkBlim,则在任一范数‖·‖意义下有0kkBlim而由第六节定理4有kkkBBB所以必有1B反之，若1B则存在足够小的正数，使1B,则第六节定理5可知,存在范数使，1BB.于是kkkBBB因为0kkBlim所以0kkBlim即0kkBlim定理4：迭代法(4)对任意0x都收敛的充分必要条件为1B三、迭代法的收敛速度考察误差向量0eBxxekkk设B有n个线性无关的特征向量n,...,,21,相应的特征值为n,...,,21,由4njjjae10得0eBekknjjkjBa1njjkjja1可以看出，当1B愈小时，kkj0愈快，即0ke愈快，故可用量B来刻划迭代法的收敛快慢.现在来确定迭代次数k，使skB10(12)取对数得Blnlnsk10定义3称BlnBR(13)为迭代法(4)的收敛速度.由此看出,1B愈小,速度R(B)就愈大，(12)式成立所需的迭代次数也就愈少.由于谱半径的计算比较困难,因此,可用范数‖B‖来作为B的一种估计.定理5如果迭代矩阵的某一种范数1qB，则对任意初始向量0x，迭代公式(4)收敛,且有误差估计式||||qq||xx||)k()k()k(1xx1(14)或||||qq||xx||)()(k)k(01xx1(15)证明利用定理4和不等式BB,可以立即证得收敛的充分条件,下面推导误差估计式.5因为x方程组的精确解，则fBxx又1qBB,则由第六节定理7可知,I-B可逆，且qB||BI||11111由于fBxfBxxxkk1fBIBBxk11fxBIBIBk11kkxxBIB11两边取范数即得||||qq||||BIB||xx||)k()k()k()k()k(111xx1xx又由于011211xxBxxBxxkkkkk所以0111xxBxxkkk，即||||qq||xx||)()(k)k(01xx1有了定理5的误差估计式,在实际计算时,对于预先给定的精度，若有kkxx1则就认为1kx是方程组满足精度的近似解.此外，还可以用第二个估计式(15)来事先确定需要迭代的次数以保证ke第二节雅可比迭代法与高斯—塞德尔迭代法6一、雅可比迭代法设线性方程组bAx(1)的系数矩阵A可逆且主对角元素nna,...,a,a2211均不为零,令nna,...,a,adiagD2211并将A分解成DDAA(2)从而(1)可写成bxADDx令11fxBx其中bDf,ADIB1111.(3)以1B为迭代矩阵的迭代法(公式)111fxBxkk(4)称为雅可比(Jacobi)迭代法(公式),用向量的分量来表示,(4)为,...,,k,n,...,ixabaxnijj)k(jjiiii)k(i21021111(5)其中Tnx,...x,xx002010为初始向量.由此看出,雅可比迭代法公式简单,每迭代一次只需计算一次矩阵和向量的乘法.在电算时需要两组存储单元,以存放kx及1kx.例1用雅可比迭代法求解下列方程组2453821027210321321321.xxx.xxx.xxx解：将方程组按雅可比方法写成7840202083020107202010213312321.x.x.x.x.x.x.x.x.x取初始值TT,,,x,x,xx0000302010按迭代公式840202083020107202010211331123211.x.x.x.x.x.x.x.x.xkkkkkkkkk进行迭代，其计算结果如表1所示表1k01234567kx100.720.9711.0571.08531.09511.0983…kx200.831.0701.15711.18531.19511.1983…kx300.841.1501.24821.28281.29411.2980…二、高斯—塞德尔迭代法由雅可比迭代公式可知,在迭代的每一步计算过程中是用kx的全部分量来计算1kx的所有分量,显然在计算第i个分量1kix时,已经计算出的最新分量1111kikx,...,x没有被利用，从直观上看,最新计算出的分量可能比旧的分量要好些.因此，对这些最新计算出来的第1k次近似1kx的分量1kjx加以利用,就得到所谓解方程组的高斯—塞德（Gauss-Seidel）迭代法.把矩阵A分解成ULDA(6)其中nna,...,a,adiagD2211,U,L分别为A的主对角元除外的下三角和上三角部分,于是,方程组(1)便可以写成bUxxLD8即22fxBx其中bLDf,ULDB1212(7)以2B为迭代矩阵构成的迭代法(公式)221fxBxkk(8)称为高斯—塞德尔迭代法(公式),用量表示的形式为,...,,k,n,,ixaxabaxijnij)k(jij)k(jijiii)k(i21021111111(9)由此看出,高斯—塞德尔迭代法的一个明显的优点是,在电算时,只需一组存储单元(计算出1kix后kix不再使用,所以用1kix冲掉kix,以便存放近似解.例2用高斯——塞德尔迭代法求解例1.解：取初始值TT,,,x,x,xx0000302010，按迭代公式840202083020107202010121113311123211.x.x.x.x.x.x.x.x.xkkkkkkkkk进行迭代，其计算结果如下表2表2k01234567kx100.721.043081.093131.099131.099891.099991.1kx200.9021.167191.195721.199471.199931.199991.2kx301.16441.282051.297771.299721.299961.31.3从此例看出,高斯—塞德尔迭代法比雅可比迭代法收敛快(达到同样的精度所需9迭代次数少),但这个结论,在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛，而高斯—塞德尔迭代法却是发散的.三、迭代收敛的充分条件定理1在下列任一条件下,雅可比迭代法(5)收敛.①111nijjiiijiaamaxB;②1111nijiiiijjaamaxB;③111njiijjijjTaamaxADI定理2设21BB,分别为雅可比迭代矩阵与高斯—塞德尔迭代矩阵,则12BB(10)从而，当111nijjiiijiaamaxB时，高斯—塞德尔迭代法(8)收敛.证明：由21BB,的定义,它们可表示成ULDB11UDLDIULDB11112用e表示n维向量T,...,,e111,则有不等式eBeB11UDLDB111这里,记号｜·｜表示其中矩阵的元素都取绝对值,而不等式是对相应元素来考虑的,于是10IeBLDIeLDBeUD111111容易验证011nnLDLD所以,LDI1及LDI1可逆，且1111111111LDILD...LDILD...LDILDInnILDI11从而有eIBLDILDIeUDLDIeB111111121eBeLDIIBI11111因此必有12BB因为已知11B所以12B.即高斯—塞德尔迭代法收敛.若矩阵A为对称，我们有定理3若矩阵A正定,则高斯—塞德尔迭代法收敛.证明：把实正定对称矩阵A分解为TLLDATLU,则D为正定的,迭代矩阵TLLDB12设是2B的任一特征值,x为相应的特征向量,则xxLLDT1以LD左乘上式两端,并由TLLDA有11AxxLT1用向量x的共轭转置左乘上式两端,得AxxxLxTTT1(11)求上式左右两端的共轭转置,得AxxxLxTT1以1和1分别乘以上二式然后相加,得AxxxLLxTTT