数值分析ppt第6章_解线性方程组的迭代法

上页下页第6章解线性方程组的迭代方法•6.1引言•6.2基本迭代法•6.3迭代法的收敛性•6.4*分块迭代法上页下页其中A为非奇异矩阵,当A为低阶稠密矩阵时,第5章讨论的选主元消去法是有效的.但对于大型稀疏矩阵方程组(A的阶数n很大，但零元素较多),利用迭代法求解是合适的.本章将介绍迭代法的一些基本理论及雅可比迭代法，高斯-赛德尔迭代法，超松弛迭代法，而超松弛迭代法应用很广泛。下面举简例，以便了解迭代法的思想.对线性方程组Ax=b，(1.1)6.1引言上页下页例1求解方程组)2.1(.361236,33114,20238321321321xxxxxxxxx记为Ax=b，其中.363330,,12361114238321bxxxxA方程组的精确解是x*=(3,2,1)T.现将改写为上页下页)3.1().3636(121),334(111),2023(81213312321xxxxxxxxx或写为x=B0x+f，其中.,0001236113382012312611111482830fB上页下页我们任取初始值，例如取x(0)=(0,0,0)T.将这些值代入(1.3)式右边(若(1.3)式为等式即求得方程组的解，但一般不满足)，得到新的值x(1)=(x1(1),x2(1),x3(1))T=(3.5,3,3)T，再将x(1)分量代入(1.3)式右边得到x(2)，反复利用这个计算程序，得到一向量序列和一般的计算公式(迭代公式),,,,)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0(kkkkxxxxxxxxxxxx上页下页)4.1(.12/)3636(,11/)334(,8/)2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx简写为x(k+1)=B0x(k)+f，其中k表示迭代次数(k=0,1,2,).迭代到第10次有;)999813.0,999838.1,000032.3()10(Tx).(000187.0)10()10()10(xx上页下页从此例看出，由迭代法产生的向量序列x(k)逐步逼近方程组的精确解是x*=(3,2,1)T.即有对于任何一个方程组x=Bx+f(由Ax=b变形得到的等价方程组)，由迭代法产生的向量序列x(k)是否一定逐步逼近方程组的解x*呢？回答是不一定.请同学们考虑用迭代法解下述方程组.53,521221xxxx但x(k)并不是所有的都收敛到解x*！xxkk)(lim上页下页对于给定方程组x=Bx+f，设有唯一解x*，则x*=Bx*+f.(1.5)又设x(0)为任取的初始向量,按下述公式构造向量序列x(k+1)=Bx(k)+f,k=0,1,2,.(1.6)其中k表示迭代次数.定义1(1)对于给定的方程组x=Bx+f,用公式(1.6)逐步代入求近似解的方法称为迭代法(或称为一阶定常迭代法，这里B与k无关).B称为迭代矩阵.(2)如果limx(k)(k→∞)存在(记为x*),称此迭代法收敛,显然x*就是方程组的解,否则称此迭代法发散.上页下页由上述讨论，需要研究{x(k)}的收敛性.引进误差向量,)1()1(xxkk由(1.6)减去(1.5)式，得ε(k+1)=Bε(k)(k=0,1,2,)，递推得.)0()1()(kkkBB要考察{x(k)}的收敛性，就要研究B在什么条件下有limε(k)=0(k→∞)，亦即要研究B满足什么条件时有Bk→0(零向量)(k→∞).上页下页6.2基本迭代法其中，A=(aij)∈Rn×n为非奇异矩阵，下面研究任何建立Ax=b的各种迭代法.设线性方程组Ax=b，(2.1)其中，M为可选择的非奇异矩阵，且使Mx=d容易求解，一般选择A的某种近似，称M为分裂矩阵.将A分裂为A=M-N.(2.2)上页下页于是，求解Ax=b转化为求解Mx=Nx+b，即求解.11bMNxMxbAx求解可构造一阶定常迭代法)3.2(),,,1,0()()()1()0(kfBxxxkk，初始向量其中B=M-1N=M-1(M-A)=I-M-1A，f=M-1b.称B=I-M-1A为迭代法的迭代矩阵，选取M矩阵，就得到解Ax=b的各种迭代法.设aii0(i=1,2,,n)，并将A写成三部分上页下页.00000000,121,211,1121,212,11,1212211ULDaaaaaaaaaaaaaaaAnnnnnnnnnnnnnn上页下页111212122212nnnnnnaaaaaaAaaa1122nnaaDa2112000nnaLaa1212000nnaaaU即A=D-L-U上页下页6.2.1雅可比(Jacobi)迭代法设aii0(i=1,2,,n)，选取M为A的对角元素部分,即选取M=D(对角阵)，A=D-N，由(2.3)式得到解方程组Ax=b的雅可比(Jacobi)迭代法.又称简单迭代法.其中B=I-D-1A=D-1(L+U)=J,f=D-1b.称J为解Ax=b的雅可比迭代法的迭代矩阵.)5.2(),,,1,0()()()1()0(kfBxxxkk，初始向量上页下页于是雅可比迭代法可写为矩阵形式bDxULDxkk1)(1)1()(其Jacobi迭代矩阵为)(1ULDBJ0002122222211111112nnnnnnnnaaaaaaaaaaaa上页下页下面给出雅可比迭代法(2.5)的分量计算公式,记,),,,,()()()(1)(Tknkikkxxxx由雅可比迭代法(2.5)有,)()()1(bxULDxkk每一个分量写出来为).,,2,1(1)(11)()1(nibxaxaxainijkjijijkjijkiii即当aii0时，有).,,2,1()(11)(11)()1(nibxaxaaxinijkjijijkjijiiki上页下页等价方程组其中aii(i)0(i=1,2,,n)112211112211222211221[]1[]1[]nnnnnnnnnnxaxaxbaxaxaxbaxaxaxba即由方程组Ax=b得到的上页下页建立的雅可比迭代格式为)(1)(1)(1)(11)(11)1(2)(2)(323)(12122)1(21)(1)(313)(21211)1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax上页下页于是，解Ax=b的雅可比迭代法的计算公式为)6.2().,1,0(),,2,1(,/)(,),,(1)()1()0()0(1)0(表示迭代次数kniaxabxxxxiinijjkjijikiTn由(2.6)式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵A始终不变.上页下页6.2.2高斯－赛德尔迭代法在Jacobi迭代中，计算xi(k+1)(2in)时，使用xj(k+1)代替xj(k)(1ji-1)，即有)(1)(1)(1)1(11)1(11)1(2)(2)(323)1(12122)1(21)(1)(313)(21211)1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax建立迭代格式上页下页或缩写为称为高斯—塞德尔(Gauss—Seidel)迭代法.bLDxULDxkk1)(1)1()()(其Gauss—Seidel迭代矩阵为BG=(D-L)-1U于是高斯—塞德尔迭代法可写为矩阵形式).,,2,1()(11)(11)1()1(nibxaxaaxinijkjijijkjijiiki上页下页这就是说，选取分裂矩阵M为A的下三角部分,即选取M=D-L(下三角阵)，A=M-N，由(2.3)式得到解Ax=b的高斯—塞德尔(Gauss—Seidel)迭代法.其中B=I-(D-L)-1A=(D-L)-1U=G,f=(D-L)-1b.称矩阵G=(D-L)-1U为解Ax=b的高斯—塞德尔迭代法的迭代矩阵.)7.2(),,,1,0()()()1()0(kfBxxxkk，初始向量上页下页由高斯—塞德尔迭代法(2.7)有,)()()1(bUxxLDkk每一个分量写出来为).,,2,1(1)(11)1()1(nixaxabxanijkjijijkjijikiii即当aii0时，有(与前面一样的式子)).,,2,1()(11)(11)1()1(nixaxabaxnijkjijijkjijiiiki或,)()1()1(bUxLxDxkkk上页下页于是，解Ax=b的高斯—塞德尔迭代法的计算公式为)8.2().,1,0(),,2,1(,/)(),(),,(1)(11)1()1()0()0(1)0(表示迭代次数初始向量kniaxaxabxxxxiinijkjijijkjijikiTn或)9.2().,1,0(),,2,1(,/)(,,),,()(11)1()()1()0()0(1)0(kniaxaxabxxxxxxxiinijkjijijkjijiiikikiTn上页下页雅可比迭代法不使用变量的最新信息计算xi(k+1)，而由高斯—塞德尔迭代公式(2.8)可知，计算x(k+1)的第i个分量xi(k+1)时，利用了已经计算出的最新分量xj(k+1)(j=1,2,,i-1).可看作雅可比迭代法的一种改进.由(2.8)可知，高斯—塞德尔迭代公式每迭代一次只需计算一次矩阵与向量的乘法.算法1(高斯—塞德尔迭代法)见书p239.上页下页例2用高斯—塞德尔迭代法解例1的方程组(1.2).).,2,1,0(.12/)3636(,11/)433(,8/)2320()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kxxxxxxxxxkkkkkkkkk解用高斯—塞德尔迭代公式：取x(0)=(0,0,0)T.迭代到第7次有;)9999930.0,9999987.1,000002.3()7(Tx.1002.24)7()7(xx上页下页由此例可知，用高斯—塞德尔迭代法，雅可比迭代法解线性方程组(1.2)(且取x(0)=0)均收敛，而高斯—塞德尔迭代法比雅可比迭代法收敛较快(即取相同的x(0)，达到同样精度所需迭代次数较少)，但这结论只当A满足一定条件时才是对的.上页下页例1用雅可比迭代法解方程组2.453.82102.7210321321321xxxxxxxxx